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. Some additional notes about more advanced course material that Jeff
mentions in class, but doesn't cover in detail, will also be posted here (in rows with a gray background). Material in these notes will not be covered on any homework or exam; they're just bonus material for the curious.
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. Links to the video and audio filed are automagically posted on this TSG web page after each lecture; it may take a day or two for direct links to appear in the schedule below. Unfortunately, access to lecture video and audio requires 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.
| Date | Lecture topics
| Lecture videos
(TSG site)
| Deadlines
|
| Tue Jan 20 |
Introduction, history, and administrivia
| [N/A]
|
| Thu Jan 22 |
Recursion, divide and conquer: tower of Hanoi, quicksort, mergesort
review of induction
| [N/A]
|
| Tue Jan 27 |
More recursion, divide and conquer: Karatsuba multiplication, linear-time selection
review of recursion trees
| video /
audio only
| HW0 due in class
|
| No lecture |
Fast Fourier transforms |
| Thu Jan 29 |
Backtracking: n queens, subset sum, longest increasing subsequence, optimal binary search trees
| video /
audio only
|
| Tue Feb 3 |
Dynamic programming: Fibonacci numbers, longest increasing subsequence
| video /
audio only
| HW1 due
|
| Thu Feb 5 |
More dynamic programming: edit distance, optimal binary search trees, independent sets in trees
|
video /
audio only
|
| No lecture |
Advanced dynamic programming tricks |
| Tue Feb 10 |
Greedy algorithms: handgun safety, tape sorting, Huffman coding
| video /
audio only
| HW2 due
|
| Thu Feb 12 |
Randomized algorithms: sorting/matching nuts and bolts (aka randomized quicksort)
| video / audio only
|
| Tue Feb 17 |
Randomized nuts and bolts continued, treaps
(We didn't have time for skip lists) video / audio only
HW3 due
|
| No lecture |
Tail inequalities: high probability bounds for quicksort and treaps |
| Thu Feb 19 |
Hash tables: perfect hashing, universal hashing
| video /
audio only
|
| Tue Feb 24 |
Midterm 1 — 7:00-9:30pm in 180 Bevier Hall — no lecture
|
| Thu Feb 26 |
Amortized analysis: counters, charging arguments, potential functions
| video /
audio only
|
| Tue Mar 3 |
Amortized analysis: scapegoat trees and splay trees
| video /
audio only
| HW4 due
|
| Thu Mar 5 |
Amortized analysis: disjoint sets ("union-find")
| video /
audio only
|
| No lecture |
Tight analysis of union-by-rank with path compression: Inverse Ackermann and its friends |
| Tue Mar 10 |
Graphs: representations, whatever-first search
[guest lecture — Jeff is out of town]
| video /
audio only
| HW5 due
|
| Thu Mar 12 |
Graphs: minimum spanning trees
[guest lecture — Jeff is out of town]
| video /
audio only
| Drop deadline (Fri Mar 13)
|
| Tue Mar 17 |
Graphs: single-source shortest paths
| video /
audio only
| HW6 due
|
| Thu Mar 19 |
Graphs: all-pairs shortest paths
| video /
audio only
|
| Tue Mar 24 |
Spring break — no classes
|
| Thu Mar 26 |
| Tue Mar 31 |
Maximum flows and minimum cuts: Definitions, examples, maxflow-micut theorem
| [after lecture]
|
| Thu Apr 2 |
Maxflow/mincut algorithms
| [after lecture]
|
| Tue Apr 7 |
Midterm 2 — 7:00-9:30pm — no lecture
|
| Thu Apr 9 |
Maxflow applications: disjoint paths, maximum matchings
| [after lecture]
|
| Tue Apr 14 |
More maxflow applications: assignment problems, baseball elimination
| [after lecture]
| HW7 due
|
| No lecture |
Extensions of maximum flow: maximum-weight matchings, networks with edge demands, minimum-cost flow |
| Thu Apr 16 |
Lower bounds: definitions, models of computation, decision trees, leaf counting (sorting, binary search)
| [after lecture]
|
| Tue Apr 21 |
Adversary arguments: n-card Monte, finding patterns in bit strings, evasive graph properties, finding the maximum, finding the maximum and minimum, finding the median
| [after lecture]
| HW8 due
|
| Thu Apr 23 |
P, NP, co-NP, NP-hard, NP-complete, the Cook-Levin theorem (Cicruit satisfiability is NP-complete), reductions
| [after lecture]
|
| Tue Apr 28 |
NP-hardness via poly-time reductions: SAT, 3SAT, independent set, clique, vertex cover, 3-color
| [after lecture]
| HW9 due
|
| Thu Apr 30 |
Even more poly-time reductions: Hamiltonian cycle, subset sum, Minesweeper, Ken-Ken
| [after lecture]
|
| Tue May 5 |
Any questions?
| [after lecture]
| HW10 "due"
|
| Thu May 14 |
Final exam — 1:30-4:30 — 1404 Siebel Center
| |