Skip to main content

This site is currently under development.

On this page

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)

Announcements

28/01 · Tomorrow’s lecture will be a guest lecture by Arjun Arul on the hardness of 3-COL and Subset Sum.

08/03 · The next two classes will be guest lectures by Venkatesh Raman and will offer an introduction to the parameterized paradigm.

23/03 · The next two classes will be guest lectures by Arjun Arul on FAST and chromatic coding.

25/03 · Some notes and problems have been added to this website.

03/04 · Course feedback is scheduled on the 16th of April.

05/04 · Quiz 3 and Quiz 4 are now available and due next Sunday, 12th April, midnight. I will share the details of how to submit soon.

2026 · Jan-Apr Term (IITGN)

Lecture Plan

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

Grading Policy

There will be six quizzes, each worth 20 points. Your total score will be capped at 100. No re-exams.

Quiz 2 and Quiz 6 will be held during the midsem and endsem exam weeks respectively. Sample questions will be added here in due course. Quiz 3 and Quiz 4 will be take-home.

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