CS 473: Schedule and Lecture Notes

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 about a week before the homework is due.

For most of the topics listed below, lecture notes from previous semesters are already available. You can also find these notes, notes on related and more advanced topics, and old homeworks and exams, on Jeff's web site. Jeff will update and revise these notes as the semester progresses; updated notes are indicated by the symbol .

Please let me know if you have trouble downloading or printing anything. Please also let me know if you find any of the bugs Jeff has cleverly hidden in the notes. We will give extra credit to anyone who finds any particular bug and describes how to fix it on the official discussion forum.

Recorded video for all lectures is available on a separate web page. Links to individual lecture videos will also appear on this page a day or two after each lecture. Lecture notes and videos of Jeff's lectures from Spring 2010 are also available. (You need an active NetID and password to access videos from an off-campus computer.)

Prerequisite stuff

already
Induction Solving recurrences Other prerequisite stuff
Tue Aug 28
Introduction, history, and administrivia [video]

Recursion

Thu Aug 30
Divide and conquer: tower of Hanoi, mergesort, quicksort, linear-time selection [video]
Tue Sep 4
More divide and conquer: selection continued, fast multiplication, fast exponentiation [video]
Thu Sep 6
Backtracking: n queens, game trees, subset sum, longest increasing subsequence [video]
Mon Sep 10
Add deadline
Tue Sep 11
Dynamic programming: Fibonacci numbers, longest increasing subsequence [video]
Thu Sep 13
More dynamic programming: edit distance, optimal binary search trees, independent sets in trees [video]
Tue Sep 18
Greedy algorithms: class scheduling, tape sorting, Huffman coding [video]

Randomization and Amortization

Thu Sep 20
Sorting/matching nuts and bolts (aka randomized quicksort) [video]
Tue Sep 25
Treaps and skip lists [video]
Thu Sep 27
Midterm 1 — no lecture [video of review session]
Tue Oct 2
Hashing: perfect hashing, universal hashing, tabulation hashing [video]
Thu Oct 4
More hashing: linear probing, cuckoo hashing — no notes yet [video]
Tue Oct 9
Amortized analysis: counters, charging arguments, potential functions [video]
Thu Oct 11
Scapegoat trees and splay trees [video]
Tue Oct 16
Disjoint sets ("union-find") [video]

Graphs

Thu Oct 18
Introduction to graphs: adjacency lists, adjacency matrices, other representations, whatever-first traversal
Fri Oct 19
Drop deadline
Tue Oct 23
Class canceled (Jeff was sick)
Thu Oct 25
Depth-first search in detail: directed acyclic graphs, topological sorting
Tue Oct 30
More depth-first search: dynamic programming revisited
Minimum spanning trees: safe and useless edges, Borůvka, Jarník-Prim, Kruskal
Thu Nov 1
Midterm 2 — 7pm-9pm — location TBA — no lecture
Tue Nov 6
Shortest paths: relaxing tense edges, greedy (Dijkstra), dynamic programming (Bellman-Ford)
Thu Nov 8
Flows and cuts: Definitions, examples, the maxflow-mincut theorem
Tue Nov 13
Maxflow/mincut algorithms: Ford-Fulkerson (augmenting paths), Edmonds-Karp (shortest path), Dinits (fattest path)
Thu Nov 15
Maxflow applications: disjoint paths, maximum matchings, assignment problems
Nov 17–25
Thanksgiving break
Tue Nov 27
More maxflow applications: cycle covers, baseball elimination, project selection

NP-hardness

Thu Nov 29
P, NP, co-NP, NP-hard; the Cook-Levin theorem; poly-time reductions to SAT, SAT, 3SAT, independent set, clique
Tue Dec 4
NP-hardness via poly-time reductions: clique, vertex cover, 3-color, Hamiltonian cycle
Thu Dec 6
Even more poly-time reductions: Super Mario Bros, Super Mario Brothers, Minesweeper, international draughts
Tue Dec 11
Any questions?
Fri Dec 14
Conflict final exam — 1pm-4pm
Tue Dec 18
Final exam — 8am-11am