CS 473: Lecture Schedule

The schedule below lists the topic of each lecture, with links to relevant notes, slides, and lecture videos. All future lecture topics are subject to change, but exam dates are set in stone. Notes are tagged 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.

For the first time in 16 years, I'm teaching in a room that does not have video-capture hardware built in, so I'm making the videos myself. All videos can be streamed or downloaded directly from this page. I'm also making my "slides" available for each lecture, in both PDF and native Notability formats.

All notes and videos should be permanently and freely available from anywhere on earth. Please let me know if you have trouble accessing anything. More recent versions of the lecture notes may be available at Algorithms, Etc. and/or the web page of whatever course I'm currently teaching. Course materials from previous algorithms classes at Illinois are also available.

Prerequisite material

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

Dynamic Programming

Tue Jan 19
Introduction, administrivia
♬ Dynamic Programming: introduction, Fibonacci, edit distance
[video, slides.pdf, slides.note]
Thu Jan 21
♬ Dynamic programming 2: iterative edit distance, maximum independent set in trees
[video, slides.pdf, slides.note]
Tue Jan 26
Dynamic programming in graphs: ♬ Dags and depth-first search, ♺ Shimbel-Bellman-Ford (no time for ♺ Kleene-Roy-Floyd-Warshall)
[video, slides.pdf, slides.note]
Thu Jan 28
♬ Advanced tricks: Hirshberg's divide-and-conquer algorithm, exploiting sparseness
[video, slides.pdf, slides.note]
Mon Feb 1
Add deadline
Tue Feb 2
♬ Advanced tricks: total monotonicity, the Monge property, the SMAWK algorithm
[video1, video2, slides.pdf, slides.note]

Randomization

Thu Feb 4
♺ Sorting nuts and bolts
[video, slides.pdf, slides.note]
Tue Feb 9
♺ Treaps — I made a few significant mistakes in this lecture, which I corrected on Thursday.
[video, slides.pdf, slides.note]
Thu Feb 11
♬ Tail inequalities
[video, slides.pdf, slides.note]
Tue Feb 16
♺ Hashing: limited randomness, universality, chaining, perfect hashing
[video, slides.pdf, slides.note]
Thu Feb 18
♺ Hashing: open addressing, linear/binary probing
[video, slides.pdf, slides.note]
Tue Feb 23
Midterm 1, 7-9pm
No lecture; optional review session
[video, slides.pdf, slides.note]
Thu Feb 25
♺💩 Bloom filters, streaming algorithms, the count-min sketch
[video, slides.pdf, slides.note]
Tue Mar 1
∅ Locality sensitive hashing
[video, slides.pdf, slides.note]

Optimization

Thu Mar 3
♬ Flows and cuts, maxflow-mincut theorem, residual graphs and augmenting paths
[video, slides.pdf, slides.note]
Tue Mar 8
♬ Ford-Fulkerson, efficient maxflow algorithms, flow decomposition
[video, slides.pdf, slides.note]
Thu Mar 10
♬ Applications of maximum flows: disjoint paths, vertex capacities, bipartite matchings, assignment
[video, slides.pdf, slides.note]
Fri Mar 12
Drop deadline
Tue Mar 15
♬ More applications of maximum flows: baseball elimination, project selection, minimum path cover for dags
[video, slides.pdf, slides.note]
Thu Mar 17
💩 Minimum-cost flows: minimum-cost circulations, cycle canceling, successive shortest paths
[video, slides.pdf, slides.note]
Mar 21–26
☼ Spring break ☼
Tue Mar 29
♬ Linear programming: definitions, duality
[video, slides.pdf, slides.note]
Thu Mar 31
♺ The (primal and dual) simplex algorithm(s)
[video, slides.pdf, slides.note]
Tue Apr 5
Midterm 2
No lecture; optional review session
[video, slides.pdf, slides.note]

Hardness and approximation

Thu Apr 7
♬ NP-hardness: Definitions, examples, Cook-Levin Theorem
[video, slides.pdf, slides.note]
Tue Apr 12
♬ NP-hardness: 3SAT, Max Independent Set, Vertex cover
[video, slides.pdf, slides.note]
Thu Apr 14
♬ NP-hardness: 3-Color, Hamiltonian cycle, international draughts
[video, slides.pdf, slides.note]
Tue Apr 19
∅ Lower bounds from the strong exponential time hypothesis
[video, slides.pdf, slides.note]
Thu Apr 21
♬ Approximation: greedy load balancing, greedy/dumb vertex cover
[video, slides.pdf, slides.note]
Tue Apr 26
♬ Approximation: nothing good for TSP, Christofedes algorithm for metric TSP
[video, slides.pdf, slides.note]
Thu Apr 28
♬ Approximation by LP rounding, deterministic or randomized
[video, slides.pdf, slides.note]
Tue May 3
Any questions?
Fri May 6
Final exam