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