Instructors: Sumantra Dutta Roy (SDR) and Sumeet Agarwal (SA)
3 credits (3-0-0)
Pre-requisites: COL106
I Semester 2017–18
Tu W F 8:00–9:00, IIA 201 (Bharti building)
Class(es) | Topics | References | Instructor |
1–21 | See here | SDR | |
22–23 | Mid-course overview: From Problems to Programs | AHU Chapter 1 | SA |
24–26 | NP-completeness | CLRS Chapter 34 | SA |
27–28 | Additional data structures: Binary search trees, Merge-Find sets | AHU Chapter 5 | SA |
29–31 | Undirected graphs: Minimum spanning trees—Prim's and Kruskal's algorithms, Traversal—Depth-first and Breadth-first search | AHU Chapter 7 | SA |
32–35 | Network flows: Flow networks, Maximum flow, Ford-Fulkerson algorithm, Edmonds-Karp algorithm | CLRS Chapter 26 | SA |
36–38 | Approximation algorithms | CLRS Chapter 35 | SA |
38–40 | Randomised algorithms | CLRS Chapters 5, 35 | SA |
41–42 | Software design | UML slides; Formal Verification slides; LTL slides; LCS Chapter 3 | SA |