## Readings

- Lecture 1 (Stable Matchings): Section 1.1, Section 2.3 and Solved Exercise 2.
- Lecture 2 (Dynamic Programming): Section 6.1, Section 6.2 and Section 6.4. Do brush up on Section 2.2 for a refresher on asymptotic analysis.
- Lecture 3 (Shortest Paths): Section 6.8, Section 6.10.
- Lecture 4 (Greedy Algorithms: Caching, Minimum Spanning Tree): Section 4.3, Section 4.5.
- Lecture 5 (Greedy Algorithms: Minimum Spanning Tree, Matroid): Section 16.4 from CLRS.
- Lecture 6 (Randomized Algorithms: Global Min-Cut): Section 13.2.
- Lecture 7 (Randomized Algorithms: Online Algorithms: Caching): 13.8
- Lecture 8 (Linear Programming, Max Flow): Secion 29.1,29.2,29.4 CLRS, Section 7.1, Section 7.2 (KT)
- Lecture 9 (Max-Flow Min-Cut Theorem, LP duality): Section 29.2, Section 29.4 (Exercises 29.4.1,29.4.2, 29.4.5)
- Lecture 10 (Max-Flow Min-Cut Algorithms): Section 7.1 (KT) and Section 26.2 (CLRS).
- Lecture 11 (Max-Flow Min Cut Application): Section 7.5, 7.6, 7.7, 7.8,7.9,7.12. Slides by Kevin Wanye.
- Lecture 12 (Simplex Method): Section 29.3 CLRS.
- Lecture 13 (Fundamental Theorem of Linear Programming): Section 29.4, 29.5 (CLRS).
- Lecture 14 (Reductions): Section 8.1, 8.2.
- Lecture 15 (P and NP): Section 8.2,8.3.
- Lecture 16 (Mid-Term, NP-completeness): Section 8.4,8.5,8.6,8.7,8.8.
- Lecture 17 (co-NP, PSPACE): Section 9.1,9.2
- Lecture 18 (Fast Algorithms for Trees, Fixed Parameter Tractability): Section 10.1,10.2,10.3
- Lecture 19 (Tree Width): Section 10.4
- Lecture 20 (Approximation Algorithms: Greedy): Section 11.1,11.3
- Lecture 21 (Approximation Algorithms: Dynamic Programming, LP rounding): Section 11.8,11.6
- Lecture 22 (Approximation Algorithms: Semi-Definite Programming): Handout.
- Lecture 23 (Hardness of Approximation): See notes by Shuchi Chawla.
- Lecture 24 (Weighted Majority): Class Notes.
- Lecture 25 (Game Theory, 2-player Zero sum game, Linear Programming): Class Notes.