Tentative Schedule: Fall 2017

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

Advertisements