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