These lecture notes are intended for use with the textbook
Algorithm Design
by Jon Kleinberg and Éva Tardos.
The slides were created by
Kevin Wayne and are distributed by
Pearson Addison-Wesley.
If you are an instructor using the textbook and would like the most
up-to-date version of the ppt files, please email me.
| TOPICS | READING | IN-CLASS DEMOS |
|---|---|---|
| Stable matching | 1 | Propose-and-reject |
| Algorithm analysis | 2 | |
| Graphs | 3 | Topological order |
| Greedy algorithms | 4.1 - 4.4 | Interval scheduling · Dijkstra |
| Minimum spanning tree | 4.5 - 4.7 | |
| Huffman codes † | 4.8 | |
| Divide-and-conquer | 5.1 - 5.4 | Merge · Merge and invert |
| Multiplication | 5.5 - 5.6 | |
| Dynamic programming | 6.1 - 6.7 | |
| Bellman-Ford | 6.8 - 6.10 | |
| Max flow, min cut | 7.1 - 7.3 | Ford-Fulkerson |
| Network flow applications | 7.5 - 7.12 | |
| Assignment problem | 7.13 | |
| Intractability | 8.1 - 8.2 | |
| Poly-time reductions | 8.5 - 8.8, 8.10 | The Longest Path [mp3] |
| NP-completeness | 8.3 - 8.4, 8.9 | |
| PSPACE | 9 | |
| Extending limits of tractability | 10 | |
| Approximation algorithms | 11 | List scheduling |
| Local search | 12 | |
| Randomized algorithms | 13 |
† Lecture slides provided by Mathijs de Weerd.
Here is a list of errata in
the lecture slides.