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:
 ℞
Prerequisite material that will not be covered in detail in lecture.
 ♺
Recycled from previous semesters;
not (yet) revised for this semester.
 ♬
Revised for this semester. (Revisions may be minor.)
 ✍
Newly written, rewritten, or significantly revised for this semester.
 💩 Notes are incomplete or have other significant issues.
 ∅
Notes don't exist yet.
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 videocapture 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
℞
Whateverfirst search
♬
Depthfirst 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 depthfirst search,
♺
ShimbelBellmanFord
(no time for ♺
KleeneRoyFloydWarshall)
[video,
slides.pdf,
slides.note]
 Thu Jan 28

♬
Advanced tricks: Hirshberg's divideandconquer 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, 79pm
No lecture; optional review session
[video,
slides.pdf,
slides.note]
 Thu Feb 25

♺💩
Bloom filters, streaming algorithms, the countmin sketch
[video,
slides.pdf,
slides.note]
 Tue Mar 1

∅
Locality sensitive hashing
[video,
slides.pdf,
slides.note]
Optimization
 Thu Mar 3

♬
Flows and cuts, maxflowmincut theorem, residual graphs and augmenting paths
[video,
slides.pdf,
slides.note]
 Tue Mar 8

♬
FordFulkerson, 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

💩
Minimumcost flows: minimumcost 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

♬
NPhardness: Definitions, examples, CookLevin Theorem
[video,
slides.pdf,
slides.note]
 Tue Apr 12

♬
NPhardness: 3SAT, Max Independent Set, Vertex cover
[video,
slides.pdf,
slides.note]
 Thu Apr 14

♬
NPhardness: 3Color, 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