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
| video
|
|
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]
| video
|
|
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
| video
|
|
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)
|