Lecture Schedule

To view the videos via Udacity (need free account, e.g.: gtalgorithms@gmail.com, gtalgorithms).
Or go to (sans quizzes):     https://www.cc.gatech.edu/~vigoda/GA

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
HW 1 due Monday, Jan. 15 at 8am EST.
HW 2 due Monday, Jan. 22 at 8am EST.

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: Thursday, February 1 – Sunday, February 4 on DP, D&C, and FFT
(exam opens on Thursday at 10am and submissions close at 8am EST on Monday)

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: Thursday, March 1 – Sunday, March 4 on graph algorithms + Max-Flow
(exam opens on Thursday at 10am and submissions close at 8am EST on Monday)

Project: PageRank and Markov Chains:  notes and GR4 lecture video
Project released on Friday, February 23 and submissions close at 8am on Monday, March 19 [24 days after release].

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: Thursday, April 12 – Sunday, April 15 on NP-Completeness + LP
(exam opens on Thursday at 10am and submissions close at 8am EST on Monday)

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:  Friday, April 27 – Sunday, April 29
cumulative final covering all topics of exams 1-3 plus RSA (but no PageRank)
(exam opens on Friday at 8am and submissions close at 8am EST on Monday)

Supplemental: Bloom filters – notes, and RA3 lecture video
(Bloom filters are not on the midterm or final exams)

Supplemental / Optional Reading Chapter Numbers: Kleinberg & Tardos:

  1. DP: Week 1: Chapter 6
  2. D&C: Weeks 2-3: Chapter 5
  3. Graphs I & II: Weeks 5-6: Chapter 3
  4. Max-Flow I, II & III: Weeks 6-8: Chapter 7
  5. NP-completeness: Weeks 9 & 13: Chapter 8
  6. Approximation Algorithms: Week 12: Chapter 11