Historical course edition. Assessment material and former logistics are excluded from this archive view.

Advanced Algorithms

A foray into measured compromises.

When we think about designing algorithms, we are usually very demanding in how we go about it: we require our algorithms to be fast and accurate on all conceivable inputs.

This is asking for quite a bit, and perhaps it is not surprising that we cannot afford this luxury all the time. The good news is that most of the time we can make meaningful progress by relaxing just one of these demands.

This course will survey three broad themes in this direction:

• suppress the demand for an exact answer (randomized and/or approximation algorithms)

• do not insist on solving the problem on all conceivable instances (parameterized algorithms and algorithms for special classes of input)

• give up on speed (exact and/or parameterized algorithms)

---

2026 · Jan-Apr Term (IITGN)

Lecture Plan

Date	Topic
06 Jan, 2026	Week 1: Introduction and Overview - I · Slides
08 Jan, 2026	Introduction and Overview - II
13 Jan, 2026	Week 2: Interval Scheduling · Slides
15 Jan, 2026	Matroids · Correctness of Greedy
20 Jan, 2026	Week 3: Realistic Sets · Graphic Matroids
22 Jan, 2026	Sports Elimination via MaxFlow
27 Jan, 2026	Week 4: Elections to MinCut · SAT to Independent Set
29 Jan, 2026	Hardness of 3-COL and Subset Sum
05 Feb, 2026	Week 5: PSPACE · Relating COL and NoGo
10 Feb, 2026	Week 6: Hardness of Geography · Randomized QuickSort
12 Feb, 2026	No Class
17 Feb, 2026	Week 7: Polynomial Identity Testing · Counting Matchings
19 Feb, 2026	Karger's Algorithm for Mincut · 2-approx for Maxcut
20 Feb - 07 Mar	Midsem Break
10 Mar, 2026	Week 8: Parameterized Algorithms
12 Mar, 2026	Branching Algorithms and Kernelization
17 Mar, 2026	Week 9: Iterative Compresssion for FVS
19 Mar, 2026	Color Coding for Long Path
24 Mar, 2026	Week 10: Kernel for FAST
26 Mar, 2026	Chromatic Coding for FAST
31 Mar, 2026	Holiday - No Class
02 Apr, 2026	Week 11: Approximation via Greedy
07 Apr, 2026	LP Rounding and Primal-Dual Methods
09 Apr, 2026	Week 12: Randomized Rounding - I
14 Apr, 2026	Randomized Rounding - II
16 Apr, 2026	Week 13: Hardness Frameworks (ETH, SETH)
21 Apr, 2026	Hardness Frameworks (PCP, UGC)

References

1. Parameterized Algorithms Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh Springer, 2015 Book website | Springer

2. The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Cambridge University Press, 2011 Book website (free PDF) | Cambridge

3. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd Edition) Michael Mitzenmacher and Eli Upfal Cambridge University Press, 2017 Cambridge

4. Exact Exponential Algorithms Fedor V. Fomin and Dieter Kratsch Springer, 2010 Springer