"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:

℞ Prerequisite material that will not be covered in detail in lecture.
♺ Recycled from previous classes; not revised for this semester.
♬ Revised for this semester.
✍ Newly (re)written for this semester. Most of these notes are incomplete drafts; some are still only outlines.
♥ More advanced material (not covered in class and not appearing in any homework or exam)

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

already: ℞ Induction
℞ Solving recurrences
℞ Divide and conquer
℞ Whatever-first search
℞ Depth-first search and topological sorting

NP-hardness

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]

Randomization

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