| Date | Topic | Reference |
|---|---|---|
| Tue Sep 1 | Introduction to Algorithms (1) (postscript) | Ch. 1, 29.4.2 |
| Thu Sep 3 | Asymptotic Growth (2) (postscript) | Ch. 2.1, 2.2, 4.1 |
| Tue Sep 8 | Master Method (4) (postscript) | Ch. 4.1, 4.2, 4.3 |
| Thu Sep 10 | Sorting (5) (postscript) | Ch. 1.2, 1.3, 8.1, 8.2, 9.1, 9.3 |
| Tue Sep 15 | Analysis of Quicksort (6) (postscript) | Ch. 6.1, 6.2, 6.3, 8.2, 8.3, 8.4 |
| Thu Sep 17 | Potential Function Analysis (6b) (postscript) | Ch. 18.3 |
| Tue Sep 22 (RH) | Recurrence Review | - |
| Thu Sep 24 | Computing Statistics (7) (postscript) | Ch. 10 |
| Tue Sep 29 | Heaps (8) (postscript) | Ch. 7 |
| Thu Oct 1 | Binary Search Trees (9) (postscript) | Ch. 13.1, 13.2, 13.3 |
| Tue Oct 6 | Exam 1: Putting Things in Order | |
| Thu Oct 8 | Splay Trees (10) (postscript) | handout |
| Tue Oct 13 | Fall Break | - |
| Thu Oct 15 | Hashing (11) (postscript) | Ch. 12 |
| Tue Oct 20 | Exam Review | - |
| Thu Oct 22 | Stable Marriage (13) (postscript) | - |
| Tue Oct 27 | Graph Algorithms (16) (postscript) | Ch. 23 |
| Thu Oct 29 | Bipartite Matching (17) (postscript) | Ch. 27.2, 27.3 |
| Tue Nov 3 | Review | Ch. |
| Thu Nov 5 | Minimum Spanning Trees (18) (postscript) | Ch. 27.2, 24, 24.2, 22 |
| Tue Nov 10 | Shortest Paths (20) (postscript) | Ch. 25.1, 25.2 |
| Thu Nov 12 (Guest) | String Matching (14) (postscript) | Ch. 34.1, 34.5, 34.3, 34.4 |
| Tue Nov 17 | Review | - |
| Thu Nov 19 | Exam 2: Graphs and Stuff | |
| Tue Nov 24 | Matrix Algorithms (15) (postscript) | Ch. 31.1, 31.4, 31.6 |
| Thu Nov 26 | Thanksgiving | - |
| Tue Dec 1 | Dynamic Programming: Segmentation (21) (postscript) | Ch. 16.1, 16.2 |
| Thu Dec 3 | Dynamic Programming: LCS (22) (postscript) | Ch. 16.3 |
| Tue Dec 8 | Complexity (23) (postscript) | Ch. 36.1, 36.2, 36.4, 37.3 |
| Thu Dec 10 | Traveling Salesperson (24) (postscript) | Ch. 36.5.5, 37.2 |
| Thu Dec 17 | Final Exam (9am-noon) | |