Date  Lecture topics  Deadlines

Wed Aug 25 
Introduction, history, and administrivia
Additional notes on induction and recurrences

Fri Aug 27 
P vs NP, NPhardness, Cook's theorem, SAT, 3SAT

Wed Sep 1
 More NPhardness: Independent Set, Clique, Vertex Cover, 3Color (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 divideandconquer, exploiting sparseness

Fri Sep 24
 Greedy algorithms: Tape sorting, scheduling, Huffman codes

Mon Sep 27

 Homework 2

Wed Sep 29

— Midterm 1
— 7:008:30
— David Kinley Hall 119 and 123
— No lecture —
prerequisite material, NPhardness, 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: kcenter 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, pushrelabel

Mon Nov 1

 Homework 4

Wed Nov 3

— Midterm 2
— 7:008: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, edgedisjoint paths

Wed Nov 10
 More applications: assignment, baseball Generalizations of maxflow: edge demands, mincost 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
