Tentative Calendar
| Week of | Topic | Problem Sets | Recitations |
Reading |
| Jan 3 | Administrivia; Introduction: Insertion sort; RAM model; loop invariants | 1, 2 | ||
| Jan 10 |
Discrete math review: induction, summations; Mathematical foundations: correctness proofs, asymptotic notation | PS1 out | Review
1 |
3, Appendix A |
| Jan 17 |
Mathematical foundations: recurrences | PS1 due | Review
2 |
4 |
| Jan 24 | Snow Week |
PS2
out SS1 |
6, 7, 5.1-5.3 | |
| Jan 31 |
Sorting: Heapsort, mergesort and quicksort; Mathematical foundations:elementary probability theory | Review 3 |
||
| Feb 7 |
Divide-and-conquer: Selection; Data structures: Binary search trees | PS2 due PS3 out SS2 |
Review 4 |
9.1-9.2 11 |
| Feb 14 |
Hashing; Greedy algorithms: Activity selection, Huffman coding | PS3 due SS3 |
12.1-12.3 16.1-16.3 |
|
| Feb 21 |
Dynamic programming: Longest common subsequence, Matrix chain multiplication | PS4
out |
15.1-15.4 | |
| Feb 28 |
Spring break | Sample
midterm |
||
| Mar 7 | Catch-up; Review; Midterm | PS4 due SS4 |
||
| Mar 14 | Graphs and graph traversals: depth-first and breadth-first search, topological sort, strongly connected components | PS5 out | ||
| Mar 21 |
Minimum spanning trees: Prim's and Kruskal's algorithm | Midterm
solution |
22 |
|
| Mar 28 |
Shortest paths: Single-source and all-pairs | PS5 due SS5 PS6 out |
23 | |
| Apr 4 |
Introduction to information theory; data compression | 24, 25 |
||
| Apr 11 |
Introduction to NP-completeness |
PS6 due Practice Final SS6 |
34 |
|
| Apr 18 | Final exam week |