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, unweighted assignment
Mar 18–26
☼ Spring break ☼
Mon Mar 27
✍️ More applications of maximum flows: disjoint path cover for dags, scheduling, baseball elimination, project selection
Wed Mar 29
✍️ Supplies, demands, and psuedoflows
Mon Apr 3
No lecture; optional review session
Tue Apr 4
Midterm 2, 7pm–9pm
Wed Apr 5
✍️ Minimum-cost flows: minimum-cost circulations, cycle canceling, successive shortest paths
Mon Apr 10
✍️ Linear programming: definitions, duality
Wed Apr 12
✍️ The (primal and dual) simplex algorithm(s)

Hardness and approximation

Mon Apr 17
NP-hardness: Definitions, examplesm 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