• Algorithm Design
  •   1.  Representative Problems
    • Stable Matching
    • Five Represenative Problems
  •   2.  Algorithm Analysis
    • Computational Tractability
    • Asymptotic Order of Growth
    • Common Running Times
  •   3.  Graphs
    • Basic Definition
    • Connectivity and Traversal
    • Implementing Graph Traversal
    • Bipartiteness
    • Connectivity in Digraphs
    • Topological Order in DAGs
  •   4.  Greedy Algorithms
    • Coin Changing
    • Interval Scheduling
    • Interval Partitioning
    • Minimizing Lateness
    • Optimal Caching
    • Shortest Paths in a Graph
    • Minimum Spanning Trees
    • Single-Link Clustering
    • Huffman Codes
  •   5.  Divide and Conquer
    • Mergesort
    • Counting Inversions
    • Closest Pair of Points
    • Karatsuba's Algorithm
    • Convolution and FFT
  •   6.  Dynamic Programming
    • Weighted Interval Scheduling
    • Segmented Least Squares
    • Knapsack Problem
    • RNA Secondary Structure
    • Sequence Alignment
    • Hirschberg's Algorithm
    • Bellman-Ford Algorithm
    • Distane Vector Protocol
    • Negative Cycles
  •   7.  Network Flow
    • Max-Flow and Min-Cut
    • Ford-Fulkerson Algorithm
    • Capacity-Scaling
    • Bipartite Matching
    • Disjoint Paths
    • Demands and Lower Bounds
    • Survey Design
    • Airline Scheduling
    • Image Segmentation
    • Project Selection
    • Baseball Elimination
    • Assignment Problem
  •   8.  Intractability
    • Polynomial-Time Reductions
    • Vertex Cover
    • Independent Set
    • Set Cover
    • 3-Satisfiability
    • Hamiltonian Cycle
    • 3-Dimensional Matching
    • Graph 3-Colorability
    • Subset Sum
    • P vs. NP
    • NP-Completeness
    • co-NP
  •   9.  PSPACE
    • PSPACE
    • Quantified SAT
    • Planning Problem
    • PSPACE-Complete
  • 10.  Limits of Tractability
    • Small Vertex Covers
    • NP-Hard Problems on Trees
    • Circular Arc Coloring
  • 11.  Approximation Algorithms
    • Load Balancing
    • Center Selection
    • Vertex Cover
    • Weighted Vertex Cover
    • Generalized Load Balancing
    • Knapsack Problem
  • 12.  Local Search
    • Gradient Descent
    • Metropolis Algorithm
    • Hopfield Neural Networks
    • Maximum Cut
    • Nash Equilibria
  • 13.  Randomized Algorithms
    • Contention Resolution
    • Global Min Cut
    • Linearity of Expectation
    • Max 3-SAT
    • Universal Hashing
    • Chernoff Bounds
    • Load Balancing
    • Randomized Quicksort

Lecture Slides for Algorithm Design

These are the offical lecture slides that accompany the textbook Algorithm Design [ Amazon · Pearson] by Jon Kleinberg and Éva Tardos. The slides were created by Kevin Wayne and are distributed by Pearson.

TOPIC	SLIDES	READINGS
Stable Matching	1up · 4up	1
Algorithm Analysis	1up · 4up	2
Graphs	1up · 4up	3
Greedy Algorithms	1up · 4up	4.1–4.4
Minimum Spanning Trees	1up · 4up	4.5–4.7
Huffman Codes †	1up · 4up	4.8
Divide and Conquer	1up · 4up	5.1–5.4
Multiplication	1up · 4up	5.5–5.6
Dynamic Programming	1up · 4up	6.1–6.7
Bellman-Ford	1up · 4up	6.8–6.10
Maximum Flow and Minimum Cut	1up · 4up	7.1–7.3
Maximum Flow Applications	1up · 4up	7.5–7.12
Assignment Problem	1up · 4up	7.13
Intractability	1up · 4up	8.1–8.2
Polynomial-Time Reductions	1up · 4up	8.5–8.8, 8.10
NP-Completeness	1up · 4up	8.3–8.4, 8.9
PSPACE	1up · 4up	9
Extending Limits of Tractability	1up · 4up	10
Approximation Algorithms	1up · 4up	11
Local Search	1up · 4up	12
Randomized Algorithms	1up · 4up	13

† Lecture slides provided by Mathijs de Weerd.