And so I see, the Universe reveals itself to me.

CS 473: Schedule and Lecture Notes

All lecture notes have been updated for this semester. Please let Jeff know if you find any of the bugs he has cleverly hidden in the notes. Most of these bugs are just typos, but undoubetdly a few are actually quite serious. We will give extra credit to anyone who finds any particular bug and describes how to fix it on the course's Piazza site.

Notes labeled describe (mostly) more advanced material that we will not cover in class this semester; material from these notes will not appear on any homework or exam.

You can also find older revisions of the lecture notes, along with an archive of old homeworks and exams, on Jeff's web site.

Videos for all lectures are also collected on a separate web page. Lecture notes and videos of Jeff's lectures from Spring 2010 and Fall 2012 are also available. (Unfortunately, access to videos from any off-campus computer requires an active UIUC NetID and password.)

Prerequisite stuff

Induction — Solving recurrences — Other prerequisite stuff
Tue Aug 27
Introduction and history: duplation and mediation, stable matching [video]


Thu Aug 29
Divide and conquer: tower of Hanoi, mergesort, quicksort, linear-time selection [video]
Tue Sep 3
More divide and conquer: selection continued, Karatsuba multiplication, fast exponentiation [video]
Fast Fourier transforms
Thu Sep 5
Backtracking: n queens, game trees, subset sum, longest increasing subsequence [video]
Fast exponential algorithms
Tue Sep 10
Dynamic programming: Fibonacci numbers, longest increasing subsequence [video]
Thu Sep 12
More dynamic programming: edit distance, optimal binary search trees [video]
Advanced dynamic programming tricks
Tue Sep 17
Greedy algorithms: class scheduling, tape sorting, Huffman coding [video]
— Midterm 1 material stops here. —

Randomization and Amortization

Thu Sep 19
Sorting/matching nuts and bolts (aka randomized quicksort) [video]
Tue Sep 24
Treaps and skip lists [video]
Thu Sep 26
Midterm 1 — no lecture [review session video]
Mon Sep 30
Conflict Midterm 1
Tue Oct 1
Hashing: why good hash functions are random, universal hashing, perfect hashing [video]
Thu Oct 3
More hashing: linear probing, cuckoo hashing [video]
Tue Oct 8
Midterm feedback: NEVER use weak induction.
Amortized analysis: counters, charging arguments, potential functions [video]
Thu Oct 10
Scapegoat trees and splay trees [video]
Tue Oct 15
Disjoint sets ("union-find") — guest lecture [video]


Thu Oct 17
Introduction to graphs: adjacency lists, adjacency matrices, implicit representations, whatever-first traversal — guest lecture [sorry, no video]
Fri Oct 18
Drop deadline
Tue Oct 22
Depth-first search in detail: directed acyclic graphs, topological sorting, dynamic programming revisited [video]
Thu Oct 24
More depth-first search: strongly connected components, Kosaraju-Sharir
Minimum spanning trees: safe and useless edges, Borůvka, Jarník-Prim, Kruskal, but really you want Borůvka [video]
Tue Oct 29
Single-source shortest paths: relaxing tense edges, greedy (Dijkstra), dynamic programming (Shimbel-Bellman-Ford) [video]
All-pairs shortest paths: reweighting negative edges (Johnson), dynamic programming (Shimbel, Kleene, Floyd-Warshall)
— Midterm 2 material stops here. —
Thu Oct 31
Maximum flows and minimum cuts: Definitions and examples, maxflow-mincut theorem, augmenting path algorithm [video]
Tue Nov 5
Maximum-flow algorithms: fattest augmenting path, shortest augmenting path (Edmonds-Karp) [video]
Thu Nov 7
Midterm 2 — 7pm-9pm — no lecture [review session video]
Mon Nov 11
Conflict Midterm 2
Tue Nov 12
Applications of flows and cuts: disjoint paths, maximum matchings, assignment problems, baseball elimination [video]
Extensions and generalizations of maximum flow: edge demands; vertex supplies and demands; minimum-cost flows; maximum-weight matchings
Linear programming and the simplex method


Thu Nov 14
P, NP, co-NP, NP-hard; the Cook-Levin theorem; poly-time reductions to SAT, SAT, 3SAT, independent set, clique [video]
Tue Nov 19
NP-hardness via poly-time reductions: clique, vertex cover, 3-color, Hamiltonian cycle [video]
Thu Nov 21
Even more poly-time reductions: Super Mario Bros, Super Mario Brothers, Minesweeper, international draughts [video]
Approximation algorithms: load balancing, set cover/hitting set, vertex cover, traveling salesman (Christofedes), k-center clustering (Gonzalez), subset sum
— Final exam material stops here. —
Nov 25–29
Thanksgiving break

Final Review

Tue Dec 3
Zatocoding (see also), Bloom filters, counting Bloom filters, Bloomier filters, Count-min sketches [video]
Thu Dec 5
String matching: Brute force, Rabin-Karp fingerprinting, Knuth-Morris-Pratt [video]
Tue Dec 10
Any questions?
Conflict final exam
Wed Dec 18
Final exam — 1:30pm–4:30pm