Lecture Schedule

To view the videos you need a free Udacity account
(such as: gtalgorithms@gmail.com, gtalgorithms)

[dates hidden to avoid confusing students during subsequent semesters who may be browsing this site]

Week 1 (January 8): 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 (January 15): 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 (January 22): Divide & Conquer II  (see [DPV] Chapter 2): 

FFT – notes and DC5 lecture video
Median  – notes, and DC2 lecture video

Week 4 (January 29): 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 (February 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 (February 12): 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 (February 19): 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 (February 26): 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 (March 5): 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 (March 12): 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 (March 19): Spring break

Week 12 (March 26) NP and LP: 

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

Week 13 (April 2): More Complexity  (see [DPV] Chapter 8): 

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

Week 14 (April 9): 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 (April 16) 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