| Lectures | Date | Supplemetary Material | Reference Reading |
|---|---|---|---|
| 1. Greedy algorithms: interval scheduling | 18/07/19 | -- | Chapters on Greedy Algorithms from CLRS and KT books, chapter on Minimum Spanning Trees in CLRS. |
| 2. Principle of mathematical induction | 22/07/19 | -- | |
| 3. Mathematical induction (contd.), concluding interval scheduling. | 23/07/19 | -- | |
| 4. Prim's algorithm: proof of correctness | 25/07/19 | Proof of correctness of Prim's algorithm. | |
| 5. Prim's algorithm: runtime | 29/07/19 | -- | |
| 6. Kruskal's Algorithm, Dijkstra's single source shortest path algorithm | 30/07/19 | Proof of Correctness of Kruskal's Algorithm(write-up by Prof. Palash Dey). | |
| 7. Dijkstra's algorithm | 05/08/2019 | -- | |
| 8. Dynamic programming: Weighted Interval Scheduling, Bellman-Ford algorithm | 06/08/2019 | -- | Chapters on Dynamic Programming in CLRS and KT books. |
| 9. Dynamic programming: Bellman-Ford algorithm | 08/08/2019 | -- | |
| 10. All pairs shortest paths: Johnson's algorithm, Network flow: Ford-Fulkerson algorithm | 13/08/2019 | -- | Chapter on all pairs shortest paths in CLRS book, Tim Roughgarden's lecture note 1. |
| 11. Ford-Fulkerson algorithm: termination, optimality. s-t cut and mincut. | 19/08/2019 | -- | Tim Roughgarden's lecture note 2, An example where Ford-Fulkerson does not terminate. |
| 12. Maxflow mincut theorem, correctness of Ford-Fulkerson algorithm, Edmonds-Karp algorithm. | 20/08/2019 | -- | |
| 13&14. The push-relabel algorithm | 26/08/2019 and 29/08/2019 | -- | Tim Roughgarden's lecture note 3 |
| 15. Applications of flow: bipartite matching, Hall's theorem | 31/08/2019 | -- | Tim Roughgarden's lecture note 4 |
| 16. NP-completeness: decision problems, polynomial time reduction. | 02/09/2019 | -- | Chapter on NP-completeness in CLRS book. |
| 17. NP-completeness: polynomial time verification, classes P and NP, Cook-Levin Theorem, Reduction of 3SAT to vertex cover. | 03/09/2019 | -- | 3SAT to vertex cover reduction |
| 18. Finishing 3SAT to vertex cover reduction. 0-1 integer linear programming. | 09/09/2019 | -- | |
| 19. Reduction of subset-sum from 3SAT. | 01/10/2019 | -- | Chapter on NP-completeness in CLRS book. |
| 20. Finishing up subset-sum reduction, Knapsack problem. Randomized algorithms: max-cut | 02/10/2019 | -- | |
| 21. Randomized algorithms: Matrix product verification. | 04/10/2019 | -- | Lecture note from cmu |
| 22. Randomized algorithms: min-cut. | 14/10/2019 | -- | Chapter on randomized algorithms in Kleinberg-Tardos |
| 23. Using Karger's algorithm to bound the number of minimum cuts, 2-approximation algorithm of vertex cover. | 15/10/2019 | -- | Chapter on approximation algorithm in CLRS and Kleinberg-Tardos. |
| 24. A 2-approximation algorithm for load-balancing. | 17/10/2019 | -- | Chapter on approximation algorithm in Kleinberg-Tardos book. |
| 25. A 3/2-approximation algorithm for load-balancing. | 21/10/2019 | -- | |
| 26. A PTAS for subset-sum | 22/10/2019 | -- | Chapter on approximation algorithms in CLRS book. |
| 27. Inapproximability of general TSP | 24/10/2019 | -- | |
| 28. A 2-approximation algorithm for metric TSP | 28/10/2019 | -- | |
| 29. Computational geometry: Testing if two line segments intersect, Checking existence of an intersecting pair of line segments in a collection of line segments by the sweeping line method. | 29/10/2019 | -- | Chapter on computational geometry in CLRS book. |
| 30. Graham's scan | 04/11/2019 | -- | |
| 31. Finding closest pair in O(n log n) time. | 05/11/2019 | -- |