"New CS 473": Lecture and Lab Schedule

The calendar below lists the topics of each lecture and lab section for the semester, with links to relevant lecture notes and videos. Notes are tagged in the schedule as follows:

Please let me know if you find any of the bugs I've cleverly hidden in the notes, especially the new () notes. Most of these bugs are just typos, but undoubtedly a few are actually quite serious. You can also find a complete archive of lectures on a separate web page.

All notes and videos should be available indefinitely, without a password, from anywhere on earth. Please let me know if you have trouble accessing anything. More recent versions of the lecture notes may be avialable at Algorithms, Etc. and/or the web page of whatever course I'm currently teaching.

Notes and videos from Jeff's most recent lectures from CS 473 (Fall 2012) and CS 374 (Fall 2014) are also available.

Prerequisite material

Solving recurrences
Divide and conquer
Whatever-first search
Depth-first search and topological sorting


Tue Jan 20
Introduction, administrivia
NP-hardness: Definitions, examples, Cook-Levin Theorem [video]
Thu Jan 22
NP-hardness: 3SAT, Max Independent Set [video]
Tue Jan 27
NP-hardness: Vertex cover, 3-Color, Hamiltonian cycle [video]
Thu Jan 29
Approximation algorithms: greedy load balancing, greedy vertex cover [video]
Mon Feb 2
Add deadline
Tue Feb 3
More approximation: dumb vertex cover, nothing good for TSP, Christofedes' 3/2-approximation for metric TSP [video]

Dynamic Programming

Thu Feb 5
Review: introduction, Fibonacci, edit distance [video]
Tue Feb 10
Dynamic programming in trees and dags via depth-first search [video]
Thu Feb 12
Dynamic programming in graphs: Shimbel-Bellman-Ford, Kleene-Roy-Floyd-Warshall [video]
Tue Feb 17
Advanced tricks: saving space, exploiting sparseness [video]
Thu Feb 19
Advanced tricks: total monotonicity, the SMAWK algorithm [video]
Tue Feb 24
Midterm 1, 7-9pm
No lecture; optional review session [video]


Thu Feb 26
Randomization: sorting nuts and bolts [video]
Tue Mar 3
Treaps [video]
Thu Mar 5
Tail inequalities [video]
Tue Mar 10
(guest lecture)
Hashing: random but not too random, universality, chaining, perfect hashing [video]
Thu Mar 12
(guest lecture)
Hashing: open addressing, linear/binary probing [video]
Fri Mar 13
Drop deadline
Tue Mar 17
Bloom filters, streaming algorithms, the count-min sketch [video]

Flows and Cuts

Thu Mar 19
Flows and cuts, maxflow-mincut theorem, residual graphs and augmenting paths [video]
Mar 23–27
☼ Spring break ☼
Tue Mar 31
Ford-Fulkerson, efficient maxflow algorithms, flow decomposition [video]
Thu Apr 2
Applications of maximum flows: disjoint paths, bipartite matchings, assignment [video]
Tue Apr 7
Applications of maximum flows: baseball elimination, project selection [video]
Thu Apr 9
Midterm 2
No lecture; optional review session [video]
Tue Apr 14
Extensions of maximum flows: lower bounds, node demands, minimum-cost circulations, cycle canceling [video]

Linear Programming

Thu Apr 16
More minimum-cost flows: vertex potentials, edge reweighting, successive shortest paths [video]
Tue Apr 21
Linear programming: definitions, duality [video]
Thu Apr 23
The (primal and dual) simplex algorithm(s) [video]
Tue Apr 28
Network simplex [video]
Thu Apr 30
Randomized minimum cut — ICES forms [video]
Tue May 5
Any questions?
Fri May 8
Final exam — 7pm–10pm