- Assignment 1 (Due on Feb 17th): Problems 2.2, 3.1, 3.9 from WS, Problems 3.4, 3.5 from VV Assignment 2 (Due on April 21st) here

- Jan 3: Introduction, 2-approximation for vertex cover, 2-approximation for metric TSP using minimum spanning trees (Ref: Sections 1.1 and 3.2 of VV)
- Jan 6: Christofides' 1.5-approximation algorithm for TSP, Scheduling on identical parallel machines (Ref: Sections 2.4, 2.3 of WS)
- Jan 10: Scheduling on identical parallel machines continued: 2-approximation, LPT rule and 3/2-approximation, 4/3-approximation using LPT rule (Ref: Section 2.3 of WS, and this for 3/2 approximation)
- Jan 13: Introduction to randomized algorithms, Karger's min-cut algorithm (Ref: this)
- Jan 17: Karger's min-cut algorithm continued, Improving the running time of Karger's min-cut (Ref: this), Introduction to online algorithms: Ski rental
- Jan 20: Randomized algorithms for weighted MAX-SAT: 1/2 approximation and 0.618 approximation (Ref: Sections 5.1, 5.2, 5.3 of WS)
- Jan 24: Set cover greedy algorithm, Knapsack problem dynamic programming algorithm (Ref: Section 2.1 of VV and Section 3.1 of WS)
- Jan 27: Knapsack problem FPTAS, Introduction to bin packing, hardness and inapproximability, 2-approximation by first-fit (Ref: Sections 3.1 and 3.3 of WS)
- Feb 6: Bin packing: Better than 4/3 inapproximability result for online algorithms, 4/3-approximation for first-fit decreasing (Ref: this)
- Feb 7: APTAS for Bin-packing (Ref: Section 3.3 of WS)
- Feb 10: APTAS for bin-packing continued, Introduction to LP, Weighted vertex-cover by LP-rounding (Ref: this)
- Feb 13: Uncapacitated facility location: 6-approximation (Ref: this)
- Feb 14: Uncapacitated facility location continued
- Feb 17: LP duality, primal-dual algorithm for weighted vertex cover (Ref: this, Section 11.4 of Kleinberg-Tardos)
- Feb 28: Feedback vertex set primal-dual algorithm (Ref: Section 7.2 of WS)
- Mar 3: Feedback vertex set primal-dual algorithm continued, Introduction to Hopcroft-Karp algorithm
- Mar 7: Hopcroft-Karp algorithm (Ref: this)
- Mar 10: Hopcroft-Karp algorithm continued, Weighted bipartite matching (Ref: this)
- Mar 14: Weighted bipartite matching - Primal-dual algorithm, Bipartite matching polytope (Ref: this)
- Mar 17: Non-bipartite matching: Edmond's blossom shrinking algorithm (Ref: this)
- Mar 21: (Lecture by Partha) Randomized parallel algorithm for bipartite matching
- Mar 24: Edmond's algorithm continued, Introduction to streaming algorithms: Majority (Ref: Chapter 1 of this)
- Mar 28: Streaming algorithms: Misra-Gries algorithm (Ref: Same as previous lecture), a lower bound on Most-frequent element problem (Ref: this)
- Mar 31: Estimating the number of distinct elements (Ref: this)
- Apr 4: Streaming algorithms for graph problems: Connectedness, bipartiteness, distance estimate (Ref: Lecture 13 of this)
- Apr 7: Matchings in streaming model (Ref: Section 15.2 of this)
- Apr 11: Lovász Local Lemma: Constructive proof and applications to hypergraph coloring and k-CNF SAT (Ref: this)
- Apr 18: Approximate counting: FPRAS for DNF counting (Ref: this)