Skip to main content

Work in Progress

Advanced Algorithms

Latest Edition
← Back to All Courses
Notes Assessments Editions

2025 · Jan-Apr Term

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.

Lecture Schedule

DateTopic
06 Jan, 2025Week 1: Introduction and Overview - I · Slides
08 Jan, 2025Introduction and Overview - II
13 Jan, 2025Week 2: Interval Scheduling · Slides
15 Jan, 2025Matroids and Scheduling with Deadlines
20 Jan, 2025Week 3: Reductions I
22 Jan, 2025Reductions I (continued)
27 Jan, 2025Week 4: Reductions II
29 Jan, 2025Reductions II (continued)
03 Feb, 2025Quiz 1
05 Feb, 2025Week 5: More on Hardness
10 Feb, 2025Week 6: Randomized Algorithms
12 Feb, 2025Randomized Algorithms (continued)
17 Feb, 2025Week 7: Parameterized Algorithms
19 Feb, 2025Quiz 2
20 Feb - 07 MarMidsem Break
10 Mar, 2025Week 8: Approximation Algorithms
12 Mar, 2025Approximation Algorithms (continued)
17 Mar, 2025Week 9: Exact Algorithms
19 Mar, 2025Exact Algorithms (continued)
24 Mar, 2025Week 10: Parameterized Approximation
26 Mar, 2025Quiz 4
31 Mar, 2025Holiday - No Class
02 Apr, 2025Week 11: Randomized Techniques for Parameterized Algorithms
07 Apr, 2025Randomized Techniques (continued)
09 Apr, 2025Week 12: Randomized Approximation
14 Apr, 2025Randomized Approximation (continued)
16 Apr, 2025Week 13: Hardness Frameworks
21 Apr, 2025Hardness Frameworks (continued)
23 Apr, 2025Quiz 5

Grading Policy

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

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

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