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