• Data Structures
• CS203 at IITG by R. Inkulu

---

• Asymptotic notation      [CLRS]: 43-52
• Intro to algorithm design      [CLRS]: 5-14, 23-25, 27-29; [more]
• Elementary data structures      [CLRS]: 232-240, 246-248; [note]
• More analysis techniques
  • Average-case analysis      [CLRS]: 114-116, 120-121; [more]
  • More on probabilistic analysis      [CLRS]: 139-141
  • Expected analysis      [CLRS]: 122-124
  • Permuting uniformly at random      [CLRS]: 126-128
  • Analyzing a Monte Carlo algorithm      [KT]: 708-713
• Sorting
  • Bubble, Selection      [wiki]: 1, 2
  • Insertion, Shell      [CLRS]: 16-22; [wiki]: 1, 2
  • Bucket      [CLRS]: 200-202; [more]
  • Quick, Merge      [CLRS]: 170-176, 29-37
  • Heapsort      [CLRS]: 159-161
  • Lower bounding with decision trees      [CLRS]: 191-193
  • Counting, Radix      [CLRS]: 194-196, 197-199
  • Avg-case time: Insertion, Bucket      [note]; [CLRS]: 202-204
  • Expected time: Randomized quick      [CLRS]: 179, 181-184
• Selection
  • Minimum and Maximum      [CLRS]: 213-215
  • Blum et al.,'s algorithm      [CLRS]: 220-222
  • Lower bounding with adversary arguments      [note]
  • Range minimum queries      [note]
  • Hoare's Las Vegas algorithm      [CLRS]: 215-219
  • A Monte Carlo algorithm      [MU]: 47, 51-52, 57-62
  • In dynamic sets with a BST      a variant of [CLRS]: 339-347
• Amortized analysis
  • Three methods with two examples      [CLRS]: 451-461
  • Dynamic arrays      [CLRS]: 463-469
• Heaps
  • Binary      [CLRS]: 151-159, 162-165, exer 6.1-2, 6.1-7, 6.3-3
  • Leftist      [note]
  • Fibonacci      [CLRS]: 505-526
• Dictionaries: search trees
  • Binary search tree      [CLRS]: 286-299, exer 12.2-6
  • AVL tree      [note]
  • 2-4 tree and its generalization      [CLRS]: 488-502
  • Red-black tree      [CLRS]: 308-329; [24vsRB]
  • Splay tree      [note]
  • Tries      [note]
• More on suffix arrays      [wiki]: 1, 2   --- not covered this time
• Randomized dictionaries
  • Randomly built BST      [CLRS]: 299-303; [Jensen's ineq]
  • Random treap      [note]
  • Skip list      [note]
• Hashing based dictionaries
  • Separate chaining      [CLRS]: 253-260, 263
  • 2-Universal hashing      [CLRS]: 265, 267-268
  • Static perfect hashing      [CLRS]: 277-282
  • Open addressing      [CLRS]: 269-271, 274-276
  • Bloom filter for set membership      [note]   --- AR
• For disjoint-sets
  • Two representations      [CLRS]: 561-562, 564-571
  • Analysis of disjoint-set forest      [note]
• For graphs
  • Three representations      [CLRS]: 589-592+, 562-564
  • Breadth-first traversal      [CLRS]: 594-601
  • Depth-first traversal      [CLRS]: 603-610
  
  
  
• [CLRS]: Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Third Edition.
• For those (sub)topics covered in lectures but not detailed in the above textbook, links/notes are posted on this page.


• AR stands for additional reading (no lecture delivered but included in syllabus).

---