Week 1 (August 21): Dynamic Programming (see [DPV] Chapter 6):
LIS, LCS – notes and DP1 lecture video
Knapsack, Chain Multiply – notes and DP2 lecture video
Shortest paths (Floyd-Warshall all-pairs) – notes and DP3 lecture video
Week 2 (August 28) RSA Cryptosystem (see [DPV] Chapter 1):
Modular arithmetic – notes and RA1 lecture video
RSA protocol, Primality testing – notes and RA2 lecture video
Week 3 (Sept. 4): Divide & Conquer I (see [DPV] Chapter 2):
Multiplication – notes and DC1 lecture video
(See also Lecture DC3 on Solving Recurrences)
Complex Numbers – notes and DC4 lecture video
Week 4 (Sept. 11): Divide & Conquer II (see [DPV] Chapter 2):
FFT – notes and DC5 lecture video
Median – notes, and DC2 lecture video
Week 5 (Sept. 18): Hashing and Exam 1:
Bloom filters – notes, and RA3 lecture video
Exam 1: Friday Sept. 22 on DP, RSA, D&C, FFT
Week 6 (Sept. 25): Graph Algorithms I (see [DPV] Chapter 3):
Strongly Connected Components (SCC’s) (2/14) – notes
2-SAT (2/16) – notes
Week 7 (Oct. 2): Graph II and Max-flow I (see [DPV] Chpt. 3+7):
MST – notes
Ford-Fulkerson algorithm for Max-flow – notes
Week 8 (Oct. 9): Max-flow II (see [DPV] Chapter 7):
Max-flow=min-cut – notes
Image segmentation – notes
Flow variant: demands – notes
Week 9 (Oct. 16): Max-flow III + Exam 2 (see [DPV] Chapter 7):
Edmonds-Karp algorithm for max-flow – notes
Exam 2: Friday, October 20 on Graph algorithms + Max-Flow
Week 10 (Oct. 23): NP-Completeness I (see [DPV] Chapter 8):
NP, Reductions (3/14) – notes
3-SAT (3/16) – notes
Week 11 (Oct. 30): NP-Completeness II + LP I (see [DPV] Chapter 8+7):
Graph problems – notes
Linear Programming (LP) introduction – notes
Week 12 (Nov. 6) Linear Programming (see [DPV] Chapter 7):
Duality – notes
Geometry
Week 13 (Nov. 13): LP+NP:
Max-SAT approx. alg. – notes
Exam 3: Friday, November 17 on NP-Completeness + LP
Week 14 (Nov. 20): Thanksgiving week
Week 15 (Nov. 27): NP-Completeness I (see [DPV] Chapter 8):
Knapsack – notes
Halting, Circuit-SAT – notes
Extra (optional): PageRank and Markov Chains: notes
Final exam: Friday, December 5
