Lecture Schedule

Tentative schedule for 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
Supplemental: Shortest paths – 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 and GR1 lecture video
2-SAT (2/16) – notes and GR2 lecture video

Week 7 (Oct. 2): Graph II and Max-flow I (see [DPV] Chpt. 3+7): 

MST – notes and GR3 lecture video
Ford-Fulkerson algorithm for Max-flow – notes and MF1 lecture video

Week 8 (Oct. 9): 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 9 (Oct. 16): Max-flow III + Exam 2 (see [DPV] Chapter 7):

 Edmonds-Karp algorithm for max-flow – notes and MF4 lecture video

Exam 2: Friday, October 20 on Graph algorithms + Max-Flow


Week 10 (Oct. 23): 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 11 (Oct. 30): 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 12 (Nov. 6) NP and LP: 

Max-SAT approx. alg.  – notes and LP4 lecture video

Week 13 (Nov. 13): NP+LP Exam: 

Exam 3: Friday, November 17 on NP-Completeness + LP

Week 14 (Nov. 20): Thanksgiving week

Week 15 (Nov. 27): More Complexity (see [DPV] Chapter 8): 

Knapsack – notes and NP4 lecture video
Halting problem – notes and NP5 lecture video

Extra (optional): PageRank and Markov Chains:  notes

Final exam:  Friday, December 8

 

Advertisements