Lecture Slides for Algorithm Design
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 Addison-Wesley.
| TOPIC | SLIDES | READINGS | DEMOS |
|---|---|---|---|
| Introduction (administrative information) | 1up · 4up | Preface · ToC | – |
| Stable Matching (Gale-Shapley) | 1up · 4up | Chapter 1 | Gale-Shapley |
| Algorithm Analysis (big-Oh notation) | 1up · 4up | Chapter 2 | – |
| 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 · red-blue · Prim · Kruskal · Borůvka · Edmonds |
| Divide and Conquer I (sorting and selection) | 1up · 4up | Chapter 5 | merging · inversions · 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 · pathological |
| 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 | – |
| 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) | – |
| 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 | (Chvatal) | – |
| Linear Programming II (linear programming duality) | 1up · 4up | (Chvatal) | – |
| Linear Programming III (ellipsoid algorithm) | 1up · 4up | Lecture notes (Michel Goemans) | – |
References.
The lectures slides are based primarily on the textbook:- Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2005.
- Introduction to Algorithms, Third Edition by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. MIT Press, 2009.
- Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. McGraw Hill, 2006.
- The Design and Analysis of Algorithms by Dexter Kozen. Springer, 1992.
- Algorithms 4/e by Robert Sedgewick and Kevin Wayne. Addison-Wesley Professional, 2011.
- Data Structures and Network Algorithms by Robert Tarjan. Society for Industrial and Applied Mathematics, 1987.
- Linear Programming by Vašek Chvátal. W. H. Freeman, 1983.
No comments :
Post a Comment