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 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)



References.

The lectures slides are based primarily on the textbook: Some of the lecture slides are based on material from the following books:
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein Algorithms by Dasgupta, Papadimitriou, and Vazirani The Design and Analysis of Algorithms by Dexter Kozen Algorithms 4/e by Sedgewick and Wayne Data Structures and Network Algorithms Linear Programming by Vasek Chvátal


Instructors.

If you are an instructor using the textbook and would like the latest version of the keynote source files, please email Kevin Wayne.

Errata.

Here are the known errata in these lecture slides.

Credits.

Special thanks to Pierre Flener, for finding and reporting dozens of errors and suggesting numerous improvements in the presentation.