Advanced Algorithms – Lecture Plan (36
Lectures)
S. Unit Total
Content
No. No. Lectures
Foundations: Review of analysis, Complexity Classes (P, NP, NP-Hard),
1 Unit 1 10
Reductions, Cook–Levin & Classic NP-complete Problems
Unit Exact Methods for NP-hard: ILP basics, Branch & Bound, Cutting
2 5
2A Planes, SAT Solvers, CSPs
Unit Approximation Algorithms: Performance ratios, Vertex Cover, Set
3 5
2B Cover, Facility Location, TSP, Scheduling
Unit Heuristics / Metaheuristics: Greedy heuristics, Local Search, Simulated
4 5
2C Annealing, Tabu Search, Genetic Algorithms
Advanced Graph Algorithms: Flows, Matchings, Min/Max Cut,
5 Unit 3 6
Randomized Algorithms, Streaming, Graph Partitioning,
Recruitment-Oriented & Cutting-Edge Topics: Divide & Conquer
6 Unit 4 (FFT, Strassen), DP on Graphs, Game Theory, Parameterized Complexity, 5
Quantum Algorithms
Prerequisites
Solid background in Data Structures and Algorithms (sorting, searching, graphs,
DP, greedy).
Familiarity with Discrete Mathematics (sets, relations, logic, graphs, combinatorics).
Knowledge of Computational Complexity basics (Big-O, Ω, Θ notations).
Comfort with Programming in C++/Java/Python for algorithm implementation.
Basic linear algebra and probability helpful for approximation & randomized
algorithms.
References
1. Vazirani, V. – Approximation Algorithms (Springer).
2. Cormen, Leiserson, Rivest, Stein (CLRS) – Introduction to Algorithms.
3. Arora & Barak – Computational Complexity: A Modern Approach.
4. Kleinberg & Tardos – Algorithm Design.
5. William Cook – In Pursuit of the Traveling Salesman (applied perspective).
6. Papadimitriou, C. – Computational Complexity.
7. Selected recent research papers/tutorials from FOCS/SODA/STOC for advanced
topics.
