Skip to main content


All information on this page is subject to change.

Permanent Zoom link:

Legend:    handouts      slides      code      video

Basic Algorithms
8/22 Welcome and introduction; O(n) median and selection
8/24 DFS; BFS; connected and strongly connected components
8/26 Topological sort; transitive closure; shortest paths
8/29 All-pairs shortest paths; Kleene algebra
Greedy algorithms
8/31 Minimum spanning trees; blue–red rules
9/2 Matroids and matroid duality
9/5 Labor day – no class
9/6 Last day to add/change credits
Advanced data structures
9/7 Homework 1 due
9/7 Binomial heaps
9/9 Fibonacci heaps
9/12 Union-find Fibonacci heaps cont.
9/14 Splay trees Union-find
9/16 Random treaps
Flow and matching
9/19 Flow definitions
9/21 Homework 2 due
9/21 Max-flow min-cut theorem
9/23 Edmonds–Karp algorithm
9/26 Dinic and MPM algorithms
9/28 Bipartite matching; weighted matching
9/30 Matching algorithms
Algebraic algorithms
10/3 Fast Fourier transform
10/5 Homework 3 due
Parallel algorithms
10/5 PRAMS and uniform circuit families; NC
10/7 Gray code; hypercube implementation of parallel prefix
10/8–10/11 Fall break
10/12 Arithmetic; linear recurrences; characteristic polynomials
10/14 Matrix inversion; matrix rank
10/15–10/26 Prelim exam period
10/17 Last day to drop/change grading basis
10/17 Linear equations; Polynomial GCDs
10/19 Chinese remainder theorem; RSA
Reductions and NP-completeness
10/21 NP; reductions; satisfiability
10/24 Clique; independent set; vertex cover
10/26 Colorability; planar colorability; Hamiltonian circuit
10/28 Knapsack; bin packing
10/31 Exact cover by 3-sets; 3-dimensional matching; NP-completeness of SAT
11/2 Homework 4 due
11/2 Cook/Levin theorem
11/4 No class; Hartmanis event
Randomized algorithms
11/7 Luby's algorithm
11/9 Analysis of Luby's algorithm
11/11 Derandomization
11/14 Polynomial testing; tail bounds
11/16 Homework 5 due
Approximation algorithms
11/16 Set cover
11/18 Bin packing
11/21 Steiner tree; metric TSP
11/23–11/27 Thanksgiving recess
LP Approximation
11/28 Linear programming; duality; weighted vertex cover
11/30 Weighted set cover via LP dual fitting
12/2 LP with randomized rounding
12/5 Homework 6 due
12/5 Strong LP duality
12/5–12/12 12/5–12/13 Final exam period