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 not. 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.

Videos of all past lectures are available on a separate page. New videos should appear automatically a few hours after each lecture. I will also add links on this page to lecture videos, but because that process is manual, it may take me a few days.

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

Recursion/Dynamic Programming

Wed Jan 18
Introduction, administrivia
Backtracking and dynamic programming: introduction
[“slides”]
Mon Jan 23
Dynamic programming: subsequences
[“slides”]
Wed Jan 25
Dynamic programming in trees
[“slides”]
Mon Jan 30
Dynamic programming in dags
[“slides”, video]
Mon Feb 1
Add deadline
Wed Feb 1
Dynamic programming in graphs: Bellman-Ford and Floyd-Warshall
Mon Feb 6
Faster dynamic programming: monotonicity, Monge property, SMAWK

Randomization

Wed Feb 8
Introduction: Coin flipping, Pokémon hunting, shuffling cards
Mon Feb 13
Sorting nuts and bolts
Wed Feb 15
Treaps
Mon Feb 20
No lecture; optional review session
Tue Feb 21
Midterm 1, 7pm-9pm
Wed Feb 22
Tail inequalities
Mon Feb 27
Hashing: limited randomness, universality, chaining, perfect hashing
Wed Mar 1
Hashing: open addressing, linear/binary probing
Mon Mar 6
💩 Bloom filters, streaming algorithms, the count-min sketch

Optimization

Wed Mar 8
Flows and cuts, maxflow-mincut theorem, residual graphs and augmenting paths
Fri Mar 10
Drop deadline
Mon Mar 13
Ford-Fulkerson, efficient maxflow algorithms, flow decomposition
Wed Mar 15
Applications of maximum flows: disjoint paths, vertex capacities, bipartite matchings, assignment
Mar 18–26
☼ Spring break ☼
Mon Mar 27
More applications of maximum flows: baseball elimination, project selection, minimum path cover for dags
Wed Mar 29
💩 Minimum-cost flows: minimum-cost circulations, cycle canceling, successive shortest paths
Mon Apr 3
No lecture; optional review session
Tue Apr 4
Midterm 2, 7pm–9pm
Wed Apr 5
Linear programming: definitions, duality
Mon Apr 10
The (primal and dual) simplex algorithm(s)

Hardness and approximation

Wed Apr 12
NP-hardness: Definitions, examples, Cook-Levin Theorem
Mon Apr 17
NP-hardness: 3SAT, Max Independent Set, Vertex cover
Wed Apr 19
NP-hardness: 3-Color, Hamiltonian cycle, international draughts
Mon Apr 24
Approximation: greedy load balancing, greedy/dumb vertex cover
Wed Apr 26
Approximation: nothing good for TSP, Christofedes algorithm for metric TSP
Mon May 1
Approximation by LP rounding, deterministic or randomized
Wed May 3
Any questions?
Wed May 10
Final exam, 1:30pm–4:30pm