| Assignment 1 | Deadline: 13 August, 2018 in the class | Solution |
|---|---|---|
| Assignment 2 | Deadline: 4 September, 2018 in the class | Solution |
| Assignment 3 | Deadline: 25 October, 2018 in the class | Solution Solution for Questions 21 and 22 |
| Assignment 4 | Deadline: 12 November, 2018 in the class | Solution |
| Lectures | Supplemetary Material | Reference Reading |
|---|---|---|
| 1. Greedy Algorithms: Interval Scheduling, Structure of Minimum Spanning Tree | Structure of MST | Chapters on Greedy Algorithms from CLRS and KT books |
| 2. Greedy Algorithms (continued): Prim's algorithm for computing Minimum Spanning Tree of weighted graphs | Proof of Correctness of Prim's Algorithm | Chapter on Minimum Spanning Tree from CLRS |
| 3. Greedy Algorithms (continued): Running Time of Prim's algorithm. Kruskal's Algorithm | Proof of Correctness of Kruskal's Algorithm | |
| 4. Dynamic programming: Fibonacci number and matrix chain multiplication | -- | Chapters on Dynamic Programming from CLRS and KT books |
| 5. Dynamic programming: Matrix chain multiplication (continued from lecture 4) | -- | |
| 6. Median Finding | -- | Chapter on Medians and Order Statistics from CLRS book |
| 7. Median Finding cont., Dijkstra's Algorithm | Supplementary for Dijkstra's Algorithm Supplementary for Median Finding |
Chapter on Single-Source Shortest Paths from CLRS book. The BFS viewpoint of Dijkstra's Algorithm is from Reference 3. |
| 8. Bellman-Ford Algorithm | -- | Chapter on Single-Source Shortest Paths from CLRS book |
| 9. Floyd Warshall Algorithm | -- | Chapter on All-Pairs Shortest Paths from CLRS book |
| 10. Johnson's Algorithm | -- | |
| 11. Ford Fulkerson Algorithm: Proof of Correctness | -- | Tim Roughgarden's lecture note 1 Tim Roughgarden's lecture note 2 Jeff Erickson's lecture note which includes an example where Ford Fulkerson algorithm does not terminate |
| 12. Finish Proof of Correctness of Ford Fulkerson Algorithm, Max Flow - Min Cut Theorem, Overview of Edmond-Karp Algorithm | -- | |
| 13. Finishing Edmond-Karp Algorithm. Push - Relabel Algorithm | -- | Tim Roughgarden's lecture note 3 Chapters on Maximum Flow from CLRS and KT books. Solve Exercise Problems (Specially from KT Book) Current Fastest Algorithm for Computing Maximum Flow: here and here This is fastest for some regime of capacity values This was fastest for 15 years. |
| 14. Push - Relabel Algorithm cont. | -- | |
| 15. Finishing Push - Relabel Algorithm | -- | |
| 16. Maximum Bipartite Matching using Max Flow, Hall's Theorem, Karger's Algorithm for Finding Minimum Cut |
-- | Applications of Maximum Flow from Tim Roughgarden's lecture note 4 Karger's Algorithm from Jeff Erickson's lecture note |
| 17. Amortized analysis: aggregate analysis. | -- | Chapter on Amortized analysis in the CLRS book. |
| 18. Amortized analysis: accounting method and potential method. | -- | |
| 19. Amortized analysis: disjoint sets and Kruskal's algorithm, Linear programming, LP formulation of maximum bipartite matching. | -- | Chapter on data structures for disjoint sets in the CLRS book. Page 25 onwards from this. Feel free to skip the proof of the lemma stated in page 27. |
| 20. Linear Programming: Definitions and examples. Maximum biparitite matching. | -- | |
| 21. Linear Programming: Maximum biparitite matching continued. | -- | |
| 22. Linear Programming: Duality. | -- | Luca Trevisan's blog post on LP duality.. |
| 23. Linear Programming: Max-flow min-cut theorem using duality NP-completeness: Decision problems, Karp reduction. |
-- | Max-flow min-cut theorem using LP duality, Chapter on NP-completeness in the CLRS book. |
| 24. NP-Completeness: Classes P and NP, NP-complete problems. | -- | Chapter on NP-completeness in the CLRS book. |
| 25. Reduction of SAT to 3SAT | -- | SAT to 3-SAT Reduction |
| 26. Reduction of 3SAT to Vertex Cover | -- | Notes by TB Schardl (MIT) |
| 27. Reduction of 3SAT to Subset Sum | -- | CLRS book. |
| 28. Approximation Algorithm for TSP | Supplemental Material | Section 31.2, 31.6, and 31.7 from Prof. Jeff Erickson's lecture notes |
| 29. Randomized Approximation Algorithm for MAX3SAT | Section 7.1 from here Also see this |
|
| 30. FPTAS for Subset Sum | CLRS book. | |
| 31. FPTAS for Subset Sum cont., FPTAS vs EPTAS vs PTAS, No FPTAS for Set Cover | ||
| 32. Overview of Local Search, Parameterized Algorithms, and Algorithmic Game Theory | -- | -- |