CS 473: Schedule and Lecture Notes

For most of the topics we will cover in this class, previous semesters' lecture notes are available from both Jeff and Sariel. Jeff will update/revise his notes as the semester progresses. We may also post additional notes on more advanced course material (in rows with a gray background), but the contents of these notes will not be covered on any homework or exam; they're just bonus material for curious students.

Please let me know if you have trouble downloading or printing anything. Please also let me know if you find bugs in the lecture notes (including the extra stuff). I will give extra credit to anyone who finds any particular bug and describes how to fix it on the course newsgroup.

Thanks to TSG, all lectures are being recorded. Direct links to the videos will appear in the schedule below a day or two after each lecture. RSS feeds for video and audio are also available; videos are automatically published to the RSS feeds only a few hours after each lecture. (Unfortunately, access to lecture video and audio may require an Illinois NetID and an Active Directory (AD) password, even from on-campus computers.)

Future lecture topics and homework due dates are subject to change. Exam dates are fixed. Links to future homeworks and exams are placeholders; they won't work until the homeworks are released or the exam has already been offered.

Date Lecture topics Lecture videos Deadlines
Tue Jan 19 Introduction, history, and administrivia
[guest lecture — Jeff will be out of town]
[no video]
Thu Jan 21 Recursion, divide and conquer: tower of Hanoi, mergesort
review of induction and recurrences
Tue Jan 26 More recursion, divide and conquer: quicksort, linear-time selection
more on recursion trees
video HW0 due
[no oral presentations]
Thu Jan 28 Backtracking: n queens, subset sum, longest increasing subsequence video
Tue Feb 2 Dynamic programming: Fibonacci numbers, longest increasing subsequence video HW1 due
Thu Feb 4 More dynamic programming: edit distance, optimal binary search trees video
Tue Feb 9 Greedy algorithms: handgun safety, tape sorting, class scheduling, Huffman coding video HW2 due
Thu Feb 11 Randomized algorithms: sorting/matching nuts and bolts (aka randomized quicksort) video
Tue Feb 16 Randomized nuts and bolts continued, treaps
(We didn't have time for skip lists last year) video
HW3 due
Thu Feb 18 Midterm 1 — 7:00-9:00pm — DCL 1310, MEB 153, and MEB 253 — no lecture
(conflict exam by arrangement)
Tue Feb 23 Hash tables: perfect hashing, universal hashing video
Thu Feb 25 Amortized analysis: counters, charging arguments, potential functions video
Tue Mar 2 Amortized analysis: scapegoat trees and splay trees
[guest lecture — Jeff was out of town]
video HW4 due
Thu Mar 4 Amortized analysis: disjoint sets ("union-find")
[guest lecture — Jeff was out of town]
Tue Mar 9 Graphs: examples, representations, and data structures video HW5 due
Thu Mar 11 Whatever-first search and minimum spanning trees video Drop deadline:
Fri Mar 12
Tue Mar 16 Minimum spanning tree algorithms and single-source shortest paths video HW6 due
Thu Mar 18 More single-source shortest paths
We didn't have time for all-pairs shortest paths, but it's mostly just dynamic programming
Tue Mar 23 Spring break — no classes
Thu Mar 25
Tue Mar 30 Maximum flows and minimum cuts: Definitions, examples video HW6.5 "due"
Thu Apr 1 Maxflow/mincut algorithms: greedy doesn't work, residual graphs, Ford-Fulkerson, non-convergence for irrational capacities video
Tue Apr 6 Maxflow/mincut algorithms: fat vs. short pipes, but write O(EV log V) on your cheat sheet.
Maxflow applications: disjoint paths, maximum matchings
video HW7 due
Thu Apr 8 Midterm 2 — 7:00-9:00pm — MSEB 100 — no lecture
(conflict exam by arrangement)
Tue Apr 13 More maxflow applications: assignment problems, the Franz Kafka High School senior prom, baseball elimination video
Thu Apr 15 Lower bounds: definitions, models of computation, decision trees, leaf counting (sorting, binary search). video Taxes due
Tue Apr 20 Adversary arguments: n-card Monte, finding patterns in bit strings, evasive graph properties, finding the maximum, finding the maximum and minimum, finding the median video HW8 due
Thu Apr 22 P, NP, co-NP, NP-hard, NP-complete, the Cook-Levin theorem (Cicruit satisfiability is NP-complete), reductions video
Tue Apr 27 NP-hardness via poly-time reductions: SAT, 3SAT, independent set, clique, vertex cover, 3-color video HW9 due
Thu Apr 29 Even more poly-time reductions: Hamiltonian cycle, subset sum, Tetris, Minesweeper, Ken-Ken video
Tue May 4 Any questions? video HW10 "due"
[not graded; feedback only]
Fri May 14 Final exam — 1:30-4:30 — 1404 Siebel Center and 1320 DCL
(conflict exam by arrangement)