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 |
Divide-and-conquer: Mergesort Mathematical foundations: Recurrences |
Math
Review PS1 due |
5.1, 5.2 |
| Sep 26, 29 |
Divide-and-conquer:
Finding the closest pair of points Divide-and-conquer: 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: depth-first and breadth-first 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.1-6.2 |
| Oct 17, 20 |
Dynamic
programming: Shortest paths Catchup |
PS4 due Review 4 PS3 solutions |
6.6-6.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 & Ford-Fulkerson theorem |
PS5 out | 7.2-7.3, 7.9, 7.12 |
| Nov 7, 10 |
Network
flows:
Max-flow Min-cut 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.6-13.7 | |
| Nov 21 |
Introduction to information
theory Data compression: Huffman coding |
PS6 due PS7 out |
4.8 |
| Nov 28, Dec 1 |
Number-theoretic
algorithms: GCD, primality, and RSA NP and computational intractability |
PS6 solutions | 8.1-8.7 |
| Dec 5, 8 |
Catchup and review |
PS7 due Final review solutions |
|
| Dec 14 |
Final exam |
PS7
solutions |