This page will be updated frequently with current and upcoming topics.
Topics Day-by-Day
After each unit (lecture), please follow up by reading at least the indicated section of CLRS (the main textbook). Optionally, read the indicated sections of KT (the recommended secondary textbook).
The readings will cover things beyond what I say in class. You are responsible for the material in these readings. Homework and exam problems, and quiz questions, might expect you to know this material.
| # | Date | Topics | Refs & Follow-up Reading |
|---|---|---|---|
| 1 | Tu Mar 28 | Introduction; Searching, Sorting | CLRS 2.1, 2.2, 3.1, 3.2 |
| 2 | Th Mar 30 | Time cost analysis; Induction; Recurrences | CLRS 2.3, 4.1; KT 5.1 Slides, Video |
| 3 | Tu Apr 4 | Heaps and Heapsort | CLRS Ch. 6; KT 2.5 Videos 1, 2, 3 |
| 4 | Th Apr 6 | Graphs, Digraphs, Connected components; BFS and shortest paths | CLRS 22.1, 22.2; KT 3.1, 3.2, 3.3 |
| 5 | Tu Apr 11 | Runtime of BFS; DFS and its properties; DAGs; Topological sort | CLRS 22.3, 22.4; KT 3.5, 3.6 Slides |
| X | We Apr 12 | Analysis of topological sort; Comments on homework | — |
| 6 | Th Apr 13 | Divide-and-conquer I: Karatsuba integer multiplication | CLRS 4.1, 4.3, 4.4, 4.5; KT 5.1, 5.2, 5.3, 5.5 |
| 7 | Tu Apr 18 | Divide-and-conquer II: Strassen matrix multiplication; Linear-time selection | CLRS 9.3; (KT: none) Slides |
| X | We Apr 19 | Divide-and-conquer III: Closest pair of points in 2-D | CLRS 33.4; KT 5.4 |
| 8 | Th Apr 20 | Dynamic programming I: Interval scheduling; Rod cutting; LCS | CLRS 15.1, 15.3, 15.4; KT 6.1, 6.2 |
| 9 | Tu Apr 25 | Dynamic programming II: Weighted shortest paths; Bellman-Ford; Floyd-Warshall | CLRS 24.1, 24.2, 25.2; KT 6.8 |
| 10 | Th Apr 27 | Dynamic programming III: Subset sum; Greedy I: Dijkstra | CLRS 24.3; KT 6.4, 4.4 |
| 11 | Tu May 2 | Greedy II: Minimum spanning trees; Prim; Kruskal | CLRS 23.1, 23.2; KT 4.5, 4.6 |
| 12 | Th May 4 | Greedy algorithms and their analysis | CLRS 16.1, 16.2, 16.3; KT 4.1, 4.2, 4.8 |
| 13 | Tu May 9 | Randomized algorithms; Selection; Quicksort | CLRS 9.2, 7.1, 7.2, 7.3, 7.4; KT 13.3, 13.5; Slides |
| X | We May 10 | Detailed analysis of Quicksort; Comments on midterm | — |
| 14 | Th May 11 | Hashing; Dictionaries; Application to closest-pair | CLRS 11.1, 11.2, 11.3; KT 13.6, 13.7; our notes |
| 15 | Tu May 16 | Amortized analysis I: Incrementing a counter | CLRS 17.1, 17.2, 17.3, 17.4 |
| X | We May 17 | Amortized analysis II: Union-find | CLRS 21.1, 21.2, 21.3 KT 4.6 |
| 16 | Th May 18 | Amortized analysis III: Fibonacci heaps | CLRS 19.1, 19.2, 19.3, 19.4 Slides |
| 17 | Tu May 23 | Max flow; Min cut; Ford-Fulkerson | CLRS 26.1, 26.2 KT 7.1, 7.2 |
| 18 | Th May 25 | Max flow II: Edmonds-Karp; application to bipartite matching | CLRS 26.2, 26.3 KT 7.3, 7.5; Video |
| 19 | Tu May 30 | More applications of Max flow and Min cut; Wrap-Up; AMA | TBD |
Although not shown in the above plan, X-hours may be used (perhaps frequently) to catch up, as needed.