Advanced Algorithms

AY 2024-25, Sem II

co-taught with Prof Manoj Gupta

A link to the materials from the second half of the course will be shared here shortly.


Target Audience

This course is aimed at students interested in modern methods in the design and analysis of algorithms with a predominantly theoretical perspective.

Pre-requisites

We expect learners to be familiar with topics typically taught in an introductory discrete math course (especially graphs, discrete probability, and linear algebra), and elementary algorithm design techniques.

References

  1. The Design of Approximation Algorithms by David P. Williamson and David B.Shmoys
  2. Approximation Algorithms by Vijay V Vazirani


Timings and Venue

Mondays and Thursdays, 11.30AM, 11/206


Course Plan:

Lec # Date Topic Slides Lecture
1 6 Jan Introduction to Approximation Algorithms
Example: Load Balancing
PDF YT
2 9 Jan Introduction to Linear Programming
Example: Vertex Cover
PDF YT[1]
3 13 Jan Adaptive rounding
Example: Bin Packing
PDF Part 1
Part 2
NA 16 Jan Worksheet Discussion
Remark: we spent most of this class concluding
our discussion of adaptive rounding.
4 20 Jan Randomized Rounding
Example: Set Cover
PDF YT
5 23 Jan General Techniques
Multiway Cut via Isolating Cuts
PDF NA
6 27 Jan Randomized Rounding
Multiway Cut
(same) NA
NA 30 Jan Worksheet Discussion
Remark: we spent most of this class concluding
our discussion of multiway cut.
7 3 Feb Primal-Dual Approximation
Vertex Cover
PDF NA
NA 6 Feb Remark: this class is canceled.
8a 10 Feb Primal-Dual Approximation
Steiner Forest
PDF YT
8b 13 Feb Primal-Dual Approximation
Steiner Forest (contd)
(same) YT
9 14 Feb Note: this is an extra makeup class
Primal-Dual Approximation
Facility Location
NA 17 Feb Worksheet Discussion
10 20 Feb Semi-Definite Programming
Maximum Cut
11 24 Feb Semi-Definite Programming
Maximum Cut (contd)
12 27 Feb Approximation Schemes
Knapsack

  1. Sorry about choppy audio! ↩︎