CS G526 Advanced Algorithms and Complexity
Aug–Dec 2026

• Time: Mon Wed Fri 9:00 AM – 9:50 AM
• Place: D103

• Midsem Exam: 07 October Wednesday, 9:30 AM – 11:00 AM
• Comprehensive Exam: 04 December Friday, 10:00 AM – 1:00 PM

Click here to add the course calendar or scan the QR code below.

• Motivation and Warmup
• Growth of Functions. Asymptotic Notations
• Review of Graph Theory Basics

• Greedy Algorithms
• Divide and Conquer
• Dynamic Programming
• Linear Programming

• Complexity Classes P, NP, PSPACE
• Reductions

• Approximation Algorithms
• Randomized Algorithms
• Local Search
• Hardness of Approximation

• Administrivia, slides

• Stable Matching, KT 1.1
• Scribe pdf, overleaf

• Asymptotic Notations, Review of Graph Theory Basics
• Scribe: Amoghavarsha, Sakshi pdf

• Job Scheduling, KT 4.1
• Scribe: Antra, Siddhant pdf

• Minimum Spanning Trees, Prim-Jarník algorithm, Cut Property, KT 4.5
• [Non-eval HW] Prove the time complexity of the implementation using min-heaps.
• Scribe: Sai, Bhaskar pdf

• Single Source Shortest Path problem, Dijkstra's algorithm, KT 4.4
• [Non-eval HW] Prove the time complexity of the implementation using min-heaps.
• Scribe: Dhruv, Yash pdf

• Huffman Codes, Time Complexity, KT 4.8
• Scribe: Prabal, Naisargi pdf

• Huffman Codes, Proof of Correctness, KT 4.8
• Scribe: Vardan, Prajwal pdf

• Finding the Closest Pair of Points in the Plane, KT 5.4
• Scribe: Saketh, Kalidas pdf

• Maximum Independent Set of Rectangles - A Divide-and-Conquer Algorithm
• Reference: Agarwal, P. K., Van Kreveld, M., & Suri, S. (1998). Label placement by maximum independent set in rectangles. Computational Geometry, 11(3-4), 209-218. Section 3 of the paper. https://doi.org/10.1016/S0925-7721(98)00028-5
• Scribe: Gandharva, Niranjan pdf

• Weighted Job (Interval) Scheduling, KT 6.1
• Scribe: Shubham Bhilare, Sarang Shastry pdf

• Subset Sums and Knapsacks, KT 6.4
• [non-eval HW] Read about Pseudo-polynomial time.
• Scribe: Sumedh, Nitish pdf

• Sequence Alignment, KT 6.6
• [non-eval] Read how this problem is related to the Shortest Path problem in the graph defined at the end of KT 6.6.
• Scribe: Dhruv, Sahil pdf

• Sequence Alignment, KT 6.6, 6.7
• Scribe: Harsha, Nidheesh pdf

• Sequence Alignment, KT 6.7
• Scribe: Mayank, Vikranth pdf

• Single Source Shortest Paths in Graphs, KT 6.8, 6.10
• Scribe: Shubham Bhilare, Abinaya pdf

• Network Flows, Residual graphs, KT 7.1

• Network Flows, Ford-Fulkerson algorithm and its running time, KT 7.1

• Network Flows, Max-Flow Min-Cut theorem, Correctness of the Ford-Fulkerson algorithm, KT 7.2

• Network Flows, The Bipartite Matching Problem, Hall's Matching Theorem, KT 7.5

• Network Flows, Edge-Disjoint Paths in Directed Graphs, Menger's Theorem, KT 7.6

• Problem session

• Computational Complexity, Polynomial-Time Reductions, KT 8.1

• Polynomial-Time Reductions, Independent Sets, Vertex Cover, Set Cover, KT 8.1

• Polynomial-Time Reductions, 3-SAT, Efficient Solvers versus Efficient Certifiers, KT 8.2, 8.3.

• Complexity Classes — P, NP. P is a subset of NP.
• NP-hardness, NP-completeness.
• Circuit Satisfiability, Statement of Cook-Levin theorem.
• KT 8.3, 8.4.

• Reducing Circuit Satisfiabilty to 3-SAT, KT 8.4

• Statement of Exponential Time Hypothesis, and the recent claim of OpenAI and Anthropic
• Linear Programming formulations of Minimum Vertex Cover, Minimum Set Cover

• Linear Programming formulations of Interval Scheduling problem and Minimum Piercing Set for Intervals

• Maximization and minimization problems. The relation between ILP optimum and LP optimum
• Weak duality theorem and its proof
• Strong duality theorem
• Integrality and duality gaps
• Intoduction to approximation algorithms. A 2-approximation algorithm for the minimum vertex cover algorithm