These lecture notes are intended for use with the textbook
Algorithm Design
by Jon Kleinberg and Éva Tardos.
† denotes slides that have not been edited.
| TOPICS | READING | IN-CLASS DEMOS |
|---|---|---|
| Stable matching | Chapter 1 | Propose-and-reject |
| Algorithm analysis | Chapter 2 | |
| Graphs | Chapter 3 | Topological order |
| Greedy algorithms | Chapter 4.1 - 4.4 | Interval scheduling · Dijkstra |
| Minimum spanning tree | Chapter 4.5 - 4.7 | |
| Divide-and-conquer | Chapter 5.1 - 5.5 | Merge · Merge and invert |
| Convolution and FFT | Chapter 5.6 | |
| Dynamic programming | Chapter 6.1 - 6.7 | |
| Bellman-Ford | Chapter 6.8 - 6.10 | |
| Max flow, min cut | Chapter 7.1 - 7.3 | Ford-Fulkerson |
| Network flow applications | Chapter 7.5 - 7.12 | |
| Assignment problem † | Chapter 7.13 | |
| Intractability | Chapter 8.1 - 8.2 | |
| Poly-time reductions | Chapter 8.5 - 8.8, 8.10 | The Longest Path [mp3] |
| NP-completeness | Chapter 8.3 - 8.4, 8.9 | |
| PSPACE | Chapter 9 | |
| Extending limits of tractability | Chapter 10 | |
| Approximation algorithms | Chapter 11 | List scheduling |
| Local search | Chapter 12 | |
| Randomized algorithms | Chapter 13 |