Instructors: Sumantra Dutta Roy (SDR) and Sumeet Agarwal (SA)
3 credits (3-0-0)
Pre-requisites: COL106
I Semester 2022–23
Tu W F 8:00–9:00, LH 606
Class(es) | Topics | References | Instructor |
1–19 | See here | SDR | |
20–22 | Mid-course overview: From Problems to Programs | AHU Chapter 1 | SA |
23–24 | Algorithm Design: Greedy algorithms—optimal substructure and greedy-choice property | AHU Chapter 10; Greedy algorithms and minimum spanning tree notes | SA |
25–28 | Undirected graphs: Minimum spanning trees—Prim's and Kruskal's algorithms | AHU Chapters 5, 7; Greedy algorithms and minimum spanning tree notes | SA |
29–33 | Network flows: Flow networks, Maximum flow, Ford-Fulkerson algorithm, Edmonds-Karp algorithm | CLRS Chapter 26 | SA |
34–38 | NP-completeness | CLRS Chapter 34 | SA |
39 | Approximation algorithms | CLRS Chapter 35 | SA |