| Date | Lecture topics | Deadlines
|
| Wed Aug 25 |
Introduction, history, and administrivia
Additional notes on induction and recurrences
|
| Fri Aug 27 |
P vs NP, NP-hardness, Cook's theorem, SAT, 3SAT
|
| Wed Sep 1
| More NP-hardness: Independent Set, Clique, Vertex Cover, 3-Color (more examples in the notes)
| Homework 0 in class
|
| Fri Sep 3
| Divide and conquer: mergesort and quicksort review, O(n)-time median selection
| Online add deadline
|
| Wed Sep 8
| Fast Fourier transforms
|
| Fri Sep 10
|
Backtracking: subset sum, longest increasing subsequence, maximum independent set
|
| Mon Sep 13
|
| Homework 1
|
| Wed Sep 15
| Dynamic programming: Fibonacci numbers, edit distance, optimal binary search trees
|
| Fri Sep 17
| More dynamic programming: maximum independent sets in trees,
|
| Wed Sep 22
|
Advanced dynamic programming tricks:
saving space via divide-and-conquer, exploiting sparseness
|
| Fri Sep 24
| Greedy algorithms: Tape sorting, scheduling, Huffman codes
|
| Mon Sep 27
|
| Homework 2
|
| Wed Sep 29
|
— Midterm 1
— 7:00-8:30
— David Kinley Hall 119 and 123
— No lecture —
prerequisite material, NP-hardness, recursion, dynamic programming
|
| Fri Oct 1
| Greedy approximation: load balancing, vertex cover, set cover/hitting set
| Paper add deadline
|
| Wed Oct 6
| More approximation algorithms: dumb vertex cover, traveling salesman (both without and with the triangle inequality)
Approximation schemes: k-center clustering
|
| Fri Oct 8
| Randomized algorithms: sorting/matching nuts and bolts
|
| Wed Oct 13
| Randomized treaps and skip lists
|
| Fri Oct 15
| Chernoff bounds
|
Online drop deadline
ACM Conference
|
| Mon Oct 18
|
| Homework 3
|
| Wed Oct 20
| Balls and bins; perfect hashing; universal hashing; cuckoo hashing
|
| Fri Oct 22
| Amplification: Randomized minimum cut
|
| Wed Oct 27
| Maximum flows and minimum cuts
|
| Fri Oct 29
| Maximum flow algorithms: augmenting path, push-relabel
|
| Mon Nov 1
|
| Homework 4
|
| Wed Nov 3
|
— Midterm 2
— 7:00-8:30
— location TBA
— No lecture —
greedy algorithms, approximation algorithms, randomized algorithms, treaps and skip lists, hashing, amplification
|
| Fri Nov 5
| Applications of maximum flow: maximum matching, edge-disjoint paths
| Wed Nov 10
| More applications: assignment, baseball
Generalizations of max-flow: edge demands, min-cost flow
|
| Fri Nov 12
| Linear programming: definitions, examples, geometry, duality
| Paper drop deadline
|
| Wed Nov 17
| Linear programming duality
|
| Fri Nov 19
| The simplex algorithm: falling marbles and rising bubbles
| Homework 5
|
| Wed Nov 24
|
— Thanksgiving break
— no lectures —
|
| Fri Nov 26
|
| Wed Dec 1
| Network simplex (maximum flows, shortest paths, etc.)
|
| Fri Dec 3
| Randomized rounding
|
| Wed Dec 8
| Any questions?
| Homework 6 (not graded)
|
| Tue Dec 14
|
— Final Exam — 7:00—10:00 — location TBA —
everything, with slightly more emphasis on maximum flows, minimum cuts, and linear programming
| |