Week 1: Dynamic Programming (see [DPV] Chapter 6):
LIS, LCS – notes and DP1 lecture video
Knapsack, Chain Multiply – notes and DP2 lecture video
Supplemental: Shortest paths – notes and DP3 lecture video
Week 2: 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 3: Divide & Conquer II (see [DPV] Chapter 2):
FFT – notes and DC5 lecture video
Median – notes, and DC2 lecture video
Week 4: Exam 1
Exam 1: on DP, D&C, and FFT
Week 5: Graph Algorithms I (see [DPV] Chapters 3 & 4) :
Strongly Connected Components (SCC’s) (2/14) – notes and GR1 lecture video
2-SAT (2/16) – notes and GR2 lecture video
Week 6: Graph II and Max-flow I (see [DPV] Chapters 5.1 & 7):
MST – notes and GR3 lecture video
Ford-Fulkerson algorithm for Max-flow – notes and MF1 lecture video
Week 7: Max-flow II (see [DPV] Chapter 7):
Max-flow=min-cut – notes and MF2 lecture video
Image segmentation – notes and MF3 lecture video
Flow variant: demands – notes and MF5 lecture video
Week 8: Max-flow III + Exam 2 (see [DPV] Chapter 7):
Edmonds-Karp algorithm for max-flow – notes and MF4 lecture video
Exam 2: on graph algorithms + Max-Flow
Project: PageRank and Markov Chains: notes and GR4 lecture video
Week 9: NP-Completeness (see [DPV] Chapter 8):
NP, Reductions (3/14) – notes and NP1 lecture video
3-SAT (3/16) – notes and NP2 lecture video
Graph problems – notes and NP3 lecture video
Week 10: Linear Programming (LP) (see [DPV] Chapter 7):
LP introduction – notes and LP1 lecture video
Duality and Geometry – notes ; LP2 lecture video and LP3 lecture video
Week 11: Spring break
Week 12: NP and LP:
Max-SAT approx. alg. – notes and LP4 lecture video
Week 13: More Complexity (see [DPV] Chapter 8):
Knapsack – notes and NP4 lecture video
Halting problem – notes and NP5 lecture video
Week 14: NP+LP Exam:
Exam 3: on NP-Completeness + LP
Week 15: RSA Cryptosystem (see [DPV] Chapter 1):
Modular arithmetic – notes and RA1 lecture video
RSA protocol, Primality testing – notes and RA2 lecture video
Final exam: cumulative final covering all topics of exams 1-3 plus RSA (but no PageRank)
Supplemental: Bloom filters – notes, and RA3 lecture video
Supplemental / Optional Reading Chapter Numbers: Kleinberg & Tardos:
- DP: Week 1: Chapter 6
- D&C: Weeks 2-3: Chapter 5
- Graphs I & II: Weeks 5-6: Chapter 3
- Max-Flow I, II & III: Weeks 6-8: Chapter 7
- NP-completeness: Weeks 9 & 13: Chapter 8
- Approximation Algorithms: Week 12: Chapter 11
Algorithms 