This webpage hosts the materials required for the course. L-T-P-C: 3-0-2-4 (45 lecture + 30 practice hours).

Schedule

Syllabus

Module 1 — Foundations for Advanced Algorithm Design (9 hrs) Asymptotic analysis and recurrences; binary search trees, heaps, and priority queues; graph representations and traversals (BFS, DFS); dynamic programming review; probability essentials for randomized analysis.

Module 2 — Advanced Data Structures (9 hrs) Red-Black trees; segment trees with lazy propagation; Fenwick trees; KD-trees and nearest-neighbor search; skip lists; performance comparison.

Module 3 — Probabilistic Data Structures and String Processing (9 hrs) Bloom filters; Count-Min sketch; HyperLogLog; tries; suffix arrays; applications in information retrieval and text processing.

Module 4 — Advanced Graph and Optimization Algorithms (9 hrs) Flow networks; max-flow min-cut theorem; Edmonds-Karp algorithm; bipartite matching via network flow; bitmask DP; branch and bound.

Module 5 — Approximation and Heuristic Algorithms (9 hrs) NP-hard problems review; approximation algorithms (vertex cover, greedy set cover); simulated annealing; genetic algorithms; comparative evaluation of exact, approximation, and heuristic approaches.

Lab experiments

# Experiment
1 BST and hash table with benchmarking harness
2 Segment tree with lazy propagation — range-query benchmark
3 Fenwick tree and KD-tree nearest-neighbor search
4 Bloom filter: empirical false-positive rate vs. theoretical bound
5 Count-Min sketch for frequency estimation on a text stream
6 Suffix array — longest repeated substring
7 Maximum flow solver with bipartite assignment
8 Bitmask DP (exact TSP) vs. branch and bound
9 Simulated annealing on TSP instances
10 Comparative evaluation: exact vs. heuristic approaches

Textbooks

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th Edition, MIT Press, 2022.
  • J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2006.