Course description: We will primarily focus on techniques that are used to design approximation algorithms for computationally hard problems. These include linear programming based techniques. In the second part of the course, we will spend more emphasis on designing randomized algorithms.
Class timings: Wed (9:30 - 10:30), Thursday (10:30 - 11:30), Friday (11:30 AM - 1:20 PM) at M3
Prerequisites: Algorithms (CS301). Some familiarity with linear algebra and probability will be assumed.
References: Will provide pointers to books or lecture notes for the topics we cover in class.
Understanding and Using Linear Programming (UULP) : Matousek and Gartner
Design of Approximation algorithms by Williamson and Shmyos (WS( (pdf)
Approximation Algorithms by Vazirani (V) (pdf)
Randomized Algorithms by Rajeev Motwani, Prabhakar Raghavan (MR)
Probability and Computing by Mitzenmacher and Upfal (MU)
Grading: 2 class tests (30%), Mid-sem (25%), End-sem (40%), class participation (5%).
Please find some practice problems here.
Announcements:
First class test will be held on 3rd February (Friday) between 11:30 to 1:30 at M3.
Lectures:
Week 1 (02-01-2023 - 06-01-2023): We covered portions of first two chapters and Section 6.1 from UULP. You may also find lecture notes (Lec 7 & 8) of this course to be useful (also contains videos of lectures).
Lecture 1 (03-01-2023): Course introduction
Lecture 2 (04-01-2023): Introduction to linear programs
Lecture 3 (05-01-2023): Introduction to duality
Lecture 4 + Tutorial (06-01-2023): LP examples for Bipartite matching, Vertex Cover
Week 2 (09-01-2023 - 13-01-2023): We introduced the notions of weak and strong duality., covered two-player zero-sum games. Introduced the notions of complementary slackness and the technique of designing primal-dual algorithms.
Lecture 4 (11-01-2023): Duality continued, weak and strong duality (Section 6.1 and 6.2 in UULP)
Lecture 5 (12-01-2023): Two-player zero-sum games (Section 8.1 in UULP, Section 1 of Lecture 10 here)
Lecture 6 (13-01-2023): Completed two-player zero-sum games. Introduced the primal-dual technique of algorithm design (This note)
Week 3 (16-01-2023 - 20-01-2023): Covered primal-dual algorithm (Hungarian algorithm) for min-cost perfect matching in bipartite graphs. Introduced the idea of approximation algorithms and designed a 2-approx for vertex cover.
Lecture 7 (18-01-2023): Primal-dual algorithm for min-cost perfect matching in bipartite graphs (Many good sources. Here, and here Example from here)
Lecture 8 (19-01-2023): Finished primal-dual algorithm for min-cost perfect matching in bipartite graphs
Lecture 9 (20-01-2023): Introduced the idea of approximation algorithms, designed a 2-approximation algorithm for vertex cover using LP rounding (Chapter 1 of this book).
Week 4 (23-01-2023 - 27-01-2023):
Week 5 (30-01-2023 - 03-02-2023):
Lecture 12 (01-02-2023): Approximation algorithms for max-cut
Lecture 13 (02-02-2023): SDP-based approximation algorithms for max-cut (Lecture notes, Section 6.1 and 6.2 in WS)
Week 6 (06-02-2023 - 10-02-2023):
Lecture 14 (08-02-2023): Complete analysis of max-cut SDP
Lecture 15 (09-02-2023): Introduction to Online learning, Mistake bound model, Weighted Majority Algorithm (Chapter 13 of this notes)
Lecture 16 (10-02-2023): Weighted majority algorithm, Introduce Randomized weighted majority (Chapter 13 of Lecture notes, Lecture notes)
Week 7 (13-02-2023 - 17-02-2023) (Refs: Chapter 13 and 14 of this notes, Lecture 11 and 12 of these notes (11, 12)
Lecture 17 (15-02-2023): Randomized weighted majority algorithm
Lecture 18 (16-02-2023): Multiplicative Weights Update framework, Hedge algorithm
Lecture 19 (17-02-2023): Applications of MW Framework
Week 8 and 9: Mid-semester exams and semester break
For the rest of the course, we will focus on designing randomized algorithms.
Week 10 (06-03-2023 - 10-03-2023):
Lecture 20 (09-03-2023): Started randomized algorithms, Markov and Chebyshev's inequalities. (Chapter 2 of MU)
Lecture 21 (10-03-2023): Balls into bins, Chernoff bounds. (Chapter 3 of MU)
Week 12 (20-03-2023 - 24-03-2023): Chapters 3 and 4 of MU and Chapters 3 and 4 in MR
Lecture 22 (22-03-2023): Concentration inequalities and uses
Lecture 23 (23-03-2023): Examples: Birthday paradox
Lecture 24 (24-03-2023): Sample complexity of estimating a parameter
Week 13 (27-03-2023 - 31-03-2023): Approximate counting and AMS sketch
Week 14 (03-04-2023 - 07-04-2023):
05-04-2023: 2nd class test
Lecture 28 (06-04-2023): Lower bounds for streaming algorithms using communication complexity (Pages 12-16 of this note)
Week 15 (10-04-2023 - 14-04-2023):
Week 16 (17-04-2023 - 21-04-2023):