Instructor: Sumeet Agarwal
TAs: Prabhleen Kaur, Palakh Shangle
3 credits (3-0-0)
Pre-requisite: COL106
I Semester 2018–19
M Th 15:30–16:50, LH 623
Class(es) | Topics | References |
1–4 | Introduction: From Problems to Programs | AHU Chapter 1 |
5–7 | Elementary data structures: Lists, Stacks, Queues | AHU Chapter 2 |
7–10 | Asymptotic analysis of program complexity | AHU Chapters 1, 9; CLRS Chapters 3, 4 |
10–11 | Algorithm Design: Divide and Conquer | AHU Chapter 10 |
11–13 | Sorting algorithms | AHU Chapter 8 |
14 | Algorithm Design: Greedy algorithms | AHU Chapter 10 |
14–18 | Undirected graphs: Minimum spanning trees (Prim and Kruskal algorithms) | AHU Chapter 7 |
18 | Algorithm Design: Dynamic Programming | AHU Chapter 10 |
19–20 | Directed graphs: Shortest paths (Dijkstra and Floyd-Warshall algorithms) | AHU Chapter 6 |
21–22 | Network flows: Flow networks, Maximum flow, Ford-Fulkerson algorithm, Edmonds-Karp algorithm | CLRS Chapter 26 |
23–24 | NP-completeness | CLRS Chapter 34 |
25–26 | Approximation algorithms | CLRS Chapter 35 |
27–28 | Randomised algorithms | CLRS Chapters 5, 35 |