Instructors: Sumantra Dutta Roy (SDR) and Sumeet Agarwal (SA)
3 credits (3-0-0)
Pre-requisites: COL106
I Semester 2019–20
Tu W F 8:00–9:00, IIA 201 (Bharti building)
Class(es) | Topics | References | Instructor |
1–20; 22–24 | See here | SDR | |
21; 25 | Mid-course overview: From Problems to Programs | AHU Chapter 1 | SA |
25–27 | Algorithm Design: Greedy algorithms | AHU Chapter 10 | SA |
27–31 | Undirected graphs: Minimum spanning trees—Prim's and Kruskal's algorithms, Traversal—Depth-first and Breadth-first search | AHU Chapters 5, 7 | SA |
31–35 | Network flows: Flow networks, Maximum flow, Ford-Fulkerson algorithm, Edmonds-Karp algorithm | CLRS Chapter 26 | SA |
35–38 | NP-completeness | CLRS Chapter 34 | SA |
39–40 | Approximation algorithms | CLRS Chapter 35 | SA |
41–42 | Randomised algorithms | CLRS Chapters 5, 35 | SA |