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):

  • Lecture 10: (23-01-2023):  Greedy approximation algorithm for set cover. Tight example for greedy algorithm. (Chapter 1 of this book)

  • Lecture 11 (27-01-2023):  Integrality gap of LPs and integrality gap of vertex cover LP.  LP-based approximation algorithms for set cover. (Chapter 1 of this book)

• 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

  • Lecture 25 (29-03-2023): Approximate counting (Section 2.1 in this note)

  • Lecture 26 (30-03-2023): AMS Sketch (Pages 1-9 of this note)

  • Lecture 27 (31-03-2023):  AMS Sketch (Pages 1-9 of this note, same as above)

• 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):

  • Lecture 29: Lower bounds for streaming algorithms using communication complexity (Pages 12-16 of this note)

  • Lecture 30: Deterministic algorithm for majority in streaming (Unit 1 in this note)

  • Lecture 31: Count-min sketch (Section 4.1 and Section 4.1.1 in this note)

• Week 16 (17-04-2023 - 21-04-2023):

  • Lecture 32: Query lower bounds for deterministic algorithms (This lecture note)

  • Lecture 33: Query lower bounds for randomized algorithms (Same as above, note)

  • Lecture 35: Introduction to property testing (Note)