Tentative Schedule for Fall 2017

Dynamic Programming (see [DPV] Chapter 6): 8/22 and 8/24

LIS, LCS (8/22) – notes, DP1 lecture video
Knapsack, Chain Multiply – notes, DP2 lecture video
Shortest paths (Floyd-Warshall all-pairs) – notes, DP3 lecture video

RSA Cryptosystem (see [DPV] Chapter 1): 8/29 and 8/31

Number theory – notes, RA1 lecture video
RSA protocol, Primality testing –  notes, RA2 lecture video

Divide & Conquer (see [DPV] Chapter 2):

Multiplication (9/5)- notesDC1 lecture video
(see also Lecture D3 on Solving Recurrences)
FFT (9/7, 9/12) – part 1 and DC4 lecture videopart 2 and DC5 lecture video
Median (9/14) – notes and DC2 lecture video

Hashing (Bloom filter): 9/19 – notes, RA3 lecture video

Exam 1: Thursday September 21 on DP, RSA, D&C, FFT

Graph Algorithms (see [DPV] Chapter 3): 

Strongly Connected Components (SCC’s) (9/26) – notes
2-SAT (9/28) – notes
MST (10/3) – notes

Max-flow (see [DPV] Chapter 7):

Algorithms (Ford-Fulkerson, Edmonds-Karp) (10/5) – notes
Max-flow=min-cut, image segmentation (10/10) – notes
Flow variant – demands (10/12) – notes
Edmonds-Karp algorithm (10/17)

Exam 2: Thursday, October 24 on Graph algorithms + Max-Flow

NP-Completeness (see [DPV] Chapter 8): 

NP, Reductions (10/19) – notes
3-SAT (10/26) – notes
Graph problems (10/28) – notes
Knapsack (11/11) – notes
Halting, Circuit-SAT (11/28) – notes

Linear Programming (see [DPV] Chapter 7): 

Intro (11/2) – notes
Duality (11/4) – notes
Geometry (11/9)
Max-SAT approx. alg. (11/14) – notes

Exam 3: Thursday, November 16 on NP-Completeness + LP

PageRank and Markov Chains: 11/30 – notes

Final exam (date/time set by the registrar):  Thursday, December 7

 

Advertisements