CS 614 | Jan-Apr 2022

CS614. Advanced Algorithms

January — April 2023

About the Course

This course will explores the tradeoffs involved in coping with NP-completeness.

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:

1. Give up on accuracy, but not completely: look for solutions that are good enough (approximation) and/or work with algorithms that report the right solution most of the time (Las-Vegas style randomization).

2. Give up on coverage, a little bit: let your algorithms work well on structured inputs. Hopefully the structure is such that it is not too limiting and is interesting enough for some application scenario, and is also enough to give you algorithmic leverage, i.e, there’s enough that you can exploit to make fast and accurate algorithms.

3. Give up on speed, to some extent: going beyond the traditional allowance of polynomial time, which is the holy grail of what is considered efficient, takes you places. You could either allow for your algorithms have super-polynomial running times, and optimize as much as possible while being accurate on all inputs (exact algorithms), or allow for bad running times on a bounded subset of instances (Monte-Carlo style randomization).

This course is an introduction to techniques in achieving specific trade-offs, and understanding the theoretical foundations of frameworks that help us establish when certain tradeoffs are simply not feasible.

Fig. Exploring tradeoffs between the demands of accuracy, speed, and coverage.

Target Audience

Anyone who is biting their nails from the NP-completeness cliffhanger at the end of their introduction to algorithms will probably enjoy this course.

Prerequisites

This is a theoretical course that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs), and some background in the design and analysis of algorithms. Programming experience is tangentially useful but not necessary. For students of IITGN, this course naturally follows up on DSA-II.

References

1. The Design of Approximation Algorithms • David P. Williamson and David B. Shmoys
2. Parameterized Algorithms • Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh
3. Randomized Algorithms • Motwani and Raghavan
4. Beyond the Worst-Case Analysis of Algorithms • Tim Roughgarden
5. Algorithms • Jeff Erickson

Specific Pointers:

1. Matroids: Erickson, the entire chapter and Section 12.2.1 from Parameterized Algorithms.
2. Vertex Cover:
   • Branching: see Section 3.1 in Parameterized Algorithms.
   • Kernels: see Section 2.2.1 for the simple kernel, and Section 2.3.1 for the kernel based on Crown Decomposition in Parameterized Algorithms.
   • 2-approximation via matchings and LP: Section 21.3 in these notes.
3. Set Cover:
   • \(f\)-Approximation via LP rounding: Section 1.2 and 1.3 in The Design of Approximation Algorithms.
   • Rounding a dual solution: Sections 1.4 and 1.5 in The Design of Approximation Algorithms. Also see Chapter A in the appendix for more background on weak duality and complementary slackness.
   • Greedy approximation: Section 1.6 in The Design of Approximation Algorithms.
4. Feedback Vertex Set:
   • The \(O(\log n)\)-approximation: Section 7.2 in The Design of Approximation Algorithms.
   • The \(2\)-approximation: Section 14.2 in The Design of Approximation Algorithms.
5. Miscellaneous
   • Color Coding: Section 5.2 in Parameterized Algorithms.
   • Inclusion-Exclusion for Hamiltonian Path: Section 10.1.1 in Parameterized Algorithms.

Timings and Venue

• Lectures on Mondays: 9PM — 10:30PM (7/206)
• Lectures on Wednesdays: 2PM — 3:30PM (7/206)
• Office Hours: By email.

Evaluation policy

• Each of the three exams account for 20% of the grade.
• Each class will have a quiz worth 2 points. The quizzes will be integrated into the lecture via Mentimeter. The total number of points you can earn through quizzes is capped at 40, and accounts for 40% of the grade.
• The are three assignments that are not graded but are recommended for practice.

Register

For IITGN students, (pre-)register through IMS as usual and on Gradescope via course code 485628.

If you are not from IITGN and are interested in taking up the course, then please send me an email.

Lectures

Quizzes

Exams

Reflections

This course had seven attendees, and included Btech/Mtech/PhD students.

I’d like to thank everyone for keeping all the classes — which were all traditional whiteboard lectuers — very interactive, and frequently helping me out with several arguments. Everyone also put in a lot of effort everyone into the various assessments: kudos on your successful completion of the course!