These are a revised version of the lecture slides that accompany the textbook Algorithm Design by Jon Kleinberg and Éva Tardos. Here are the original and official version of the slides, distributed by Pearson.
| TOPIC | SLIDES | READINGS | DEMOS |
|---|---|---|---|
| Stable Matching (Gale–Shapley) | 1up · 4up | Chapter 1 | Gale–Shapley |
| Algorithm Analysis (big O notation) | 1up · 4up | Chapter 2 | binary search |
| Graphs (graph search) | 1up · 4up | Chapter 3 | – |
| Greedy Algorithms I (basic techniques) | 1up · 4up | Chapter 4 | interval scheduling interval partitioning |
| Greedy Algorithms II (shortest paths and MSTs) | 1up · 4up | Chapter 4 | Dijkstra Prim, Kruskal, Borůvka Edmonds |
| Divide and Conquer I (sorting and selection) | 1up · 4up | Chapter 5 | merging quickselect |
| Divide and Conquer II (integer and polynomial multiplication) | 1up · 4up | Chapter 5 | – |
| Dynamic Programming I (basic techniques) | 1up · 4up | Chapter 6 | – |
| Dynamic Programming II (sequence alignment, Bellman–Ford) | 1up · 4up | Chapter 6 | – |
| Network Flow I (maximum flow theory) | 1up · 4up | Chapter 7 | Ford–Fulkerson |
| Network Flow II (maximum flow applications) | 1up · 4up | Chapter 7 | – |
| Network Flow III (assignment problem) | 1up · 4up | Chapter 7 | – |
| Intractability I (polynomial-time reductions) | 1up · 4up | Chapter 8 | – |
| Intractability II (P, NP, and NP-complete) | 1up · 4up | Chapter 8 | – |
| Intractability III (coping with intractability) | 1up · 4up | Section 10.2, 11.8 | independent set vertex cover |
| PSPACE (PSPACE complexity class) | 1up · 4up | Chapter 9 | – |
| Limits of Tractability (extending limits of tractability) | 1up · 4up | Chapter 10 | – |
| Approximation Algorithms (approximation algorithms) | 1up · 4up | Chapter 11 | list scheduling |
| Local Search (Metropolis, Hopfield nets) | 1up · 4up | Chapter 12 | – |
| Randomized Algorithms (randomized algorithms) | 1up · 4up | Chapter 13 | – |
| Data Structures I (amortized analysis) | 1up · 4up | Chapter 17 (CLRS) | dynamic table |
| Data Structures II (binary and binomial heaps) | 1up · 4up | Chapter 6 (CLRS, 2nd edition) | binary heap heapify |
| Data Structures III (Fibonacci heaps) | 1up · 4up | Chapter 19 (CLRS) | – |
| Data Structures IV (union–find) | 1up · 4up | Section 5.1.4 (Dasgupta et al.) | – |
| Linear Programming I (simplex algorithm) | 1up · 4up | (Chvátal) | – |
| Linear Programming II (linear programming duality) | 1up · 4up | (Chvátal) | – |
| Linear Programming III (ellipsoid algorithm) | 1up · 4up | lecture notes (Michel Goemans) | – |
The lectures slides are based primarily on the textbook: