Tentative Calendar
Dates  Topic  Handouts  Reading 
Sep 8 
Administrivia Introduction: The Stable Marriage Problem 
PS1 out  1 
Sep 12, 15 
Introduction: Some other representative
problems Mathematical foundations: Correctness proofs, asymptotic notation, running times 
Reference
books Review 1 
2.1, 2.2, 2.4 
Sep 19, 22 
Divideandconquer: Mergesort Mathematical foundations: Recurrences 
Math
Review PS1 due 
5.1, 5.2 
Sep 26, 29 
Divideandconquer:
Finding the closest pair of points Divideandconquer: Convolutions Greedy algorithms: Interval scheduling 
PS2
out Review 2 PS1 solutions Review2 solutions 
5.4, 5.6, 4.1 
Oct 3, 6 
Graphs and graph
traversals: depthfirst and breadthfirst search, topological sort Greedy algorithms: Shortest paths 
PS2 due PS2 solutions PS3 out 
3, 4.4 
Oct 10, 13 
Greedy algorithms: Minimum spanning trees Dynamic Programming: Weighted interval scheduling 
PS3 due PS4 out 
4.5, 6.16.2 
Oct 17, 20 
Dynamic
programming: Shortest paths Catchup 
PS4 due Review 4 PS3 solutions 
6.66.7 
Oct 24, 27 
No class Tue,
Oct 24 Midterm 
Midterm
Review PS4 due PS4 solutions Midterm solutions 
6.8, 7.1 
Oct 31, Nov 3 
Dynamic
Programming:
Sequence alignment Network flows: Applications & FordFulkerson theorem 
PS5 out  7.27.3, 7.9, 7.12 
Nov 7, 10 
Network
flows:
Maxflow Mincut theorem Mathematical foundations: Elementary probability theory Randomization: Randomized Quicksort 
PS5 due PS6 out PS5 solutions 
13.3, 13.5 
Nov 14, 17 
Randomization: Hashing Randomization: Finding the closest pair of points 
13.613.7  
Nov 21 
Introduction to information
theory Data compression: Huffman coding 
PS6 due PS7 out 
4.8 
Nov 28, Dec 1 
Numbertheoretic
algorithms: GCD, primality, and RSA NP and computational intractability 
PS6 solutions  8.18.7 
Dec 5, 8 
Catchup and review 
PS7 due Final review solutions 

Dec 14 
Final exam 
PS7
solutions 