Schedule: Spring 2017

For the Fall 2017 CS 8803 GA schedule go here.

Below is the Spring 2017 CS 6505 schedule.


Dynamic Programming (see [DPV] Chapter 6): 1/10 and 1/12

LIS, LCS – notes
Knapsack, Chain Multiply – notes
Shortest paths (Floyd-Warshall all-pairs) – notes

RSA Cryptosystem (see [DPV] Chapter 1): 1/17 and 1/19 

Number theory, RSA protocol – notes
Primality testing –  notes

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

Multiplication (1/24)- notes
FFT (1/26, 1/31) – part 1part 2
Median (2/2) – notes

Hashing (Bloom filter): 2/7 – notes

Exam 1: Thursday Feb. 9 on DP, RSA, D&C, FFT

Graph Algorithms (see [DPV] Chapter 3): 

Strongly Connected Components (SCC’s) (2/14) – notes
2-SAT (2/16) – notes
MST (2/21) – notes

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

 Algorithms (Ford-Fulkerson, Edmonds-Karp) (2/23) – notes
Max-flow=min-cut, image segmentation (2/28) – notes
Flow variant – demands (3/7) – notes

PageRank and Markov Chains: 3/2 – notes

Exam 2: Thursday March 9 on Graph algorithms + Max-Flow

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

NP, Reductions (3/14) – notes
3-SAT (3/16) – notes
Graph problems (3/28) – notes
Hamiltonian path (4/6) – notes
Knapsack (4/13) – notes
Halting, Circuit-SAT (4/18) – notes

Linear Programming (see [DPV] Chapter 7): 

Intro (3/30) – notes
Duality (4/4) – notes
Max-SAT approx. alg. (4/11) – notes

Exam 3: Thursday, April 20 on NP-Completeness + LP

Final exam (date/time set by the registrar):

May 2 (Tues) 2:50pm – 5:40pm

Advertisements