Skip to lab content

B.Tech CSE & Allied Branches · II Year, I Semester · AR25

Advanced Data Structures Lab

Build confidence with advanced trees, heaps, pattern matching, sorting, searching and hashing—one carefully explained program at a time.

12weeks23implementations138viva answers
23 exercises

WEEK 01

Disjoint sets

01Disjoint sets — Find and UnionExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 02

String pattern matching

02AKnuth–Morris–Pratt pattern matchingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva02BBoyer–Moore — bad-character ruleExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 03

Comparison-based sorting

03AMerge sort in ascending orderExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva03BQuick sort in ascending orderExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 04

Non-comparison sorting

04ARadix sort — stable decimal passesExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva04BBucket sort — distribute, sort and combineExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 05

Searching techniques

05AJump search in a sorted arrayExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva05BFibonacci search in a sorted arrayExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 06

AVL trees

06AVL tree — insert, search and deleteExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 07

B Trees (2,3)

072–3 tree — insertion and node splittingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 08

Binary heaps

08Binary max heap — insert and extractExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 09

Binomial heaps

09Binomial min heap — insert, meld and extractExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 10

Tries

10ABinary trie — eight-bit integer keysExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva10BStandard trie — words and prefixesExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 11

Hash functions

11AHash function — division methodExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva11BHash function — multiplication methodExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva11CHash function — mid-square methodExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva11DHash function — shift foldingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva

WEEK 12

Collision resolution

12ACollision resolution — linear probingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva12BCollision resolution — quadratic probingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva12CCollision resolution — double hashingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva12DCollision resolution — separate chainingExplanation · flowchart · C source · line-by-line guide · dry run · complexity · viva
Study the reasoning before running the program

Read the input contract, follow the dry run, then run each sample. Algorithm variants and supported operations are stated on their pages, including the bad-character Boyer–Moore version and insertion-focused 2–3 tree.