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: 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 Chvatal


Instructors.

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


Errata.

Here are the known errata in these lecture slides.