| Num | Day | Date | Topic | Materials (Textbook) |
|---|---|---|---|---|
| 1 | Tu | 4 Sep | Parallelism | 1; 4.3-4.4; Readings 1 2 3 |
| 2 | Th | 6 Sep | Divide and Combine; Work/Span Analysis | 4.3-4.4; Readings 1 2 3 |
| 3 | Tu | 11 Sep | More divide and combine; contraction | Mergesort, Rebalance code Rebalance analysis |
| Th | 13 Sep | no class | ||
| 4 | Tu | 18 Sep | Genome Sequencing (Exhaustion) | 5:Genome Sequencing (not 5.6) |
| 5 | Th | 20 Sep | Sequences | code |
| 6 | Tu | 25 Sep | Genome II (Greedy); Max Contig Subseq D+C | 5.5, 5.7, 9.6, 9.7 superstring, MCS |
| 7 | Th | 27 Sep | Contraction: Reduce and scan, MCS | 7:Contraction, 9:MCS |
| 8 | Tu | 2 Oct | Randomization (max2) | 10, 11.2 |
| 9 | Th | 4 Oct | Randomized Quickselect | 11.3 |
| 10 | Tu | 9 Oct | Quickselect Analysis | 11.3 |
| 11 | Th | 11 Oct | Quicksort | 11.4 |
| 12 | Tu | 16 Oct | Treaps | 12 |
| 13 | Th | 18 Oct | MIDTERM | |
| Tu | 23 Oct | FALL BREAK | ||
| 14 | Th | 25 Oct | Tables, Graphs | 13,14 |
| 15 | Tu | 30 Oct | Breadth-First Search | 15 |
| 16 | Th | 1 Nov | Depth-First Search | 15 |
| 17 | Tu | 6 Nov | More DFS; Shortest Path | 15, 16 undirected cycle code |
| 18 | Th | 8 Nov | Shortest Paths II | 16 |
| 19 | Tu | 13 Nov | Graph Contraction | 17 |
| 20 | Th | 15 Nov | Graph Contraction II | 17 |
| 21 | Tu | 20 Nov | Minimum Spanning Trees | 18 |
| Th | 22 Nov | THANKSGIVING | ||
| 22 | Tu | 27 Nov | Dynamic Programming I | 19 |
| 23 | Th | 29 Nov | Dynamic Programming II | 19 |
| 24 | Tu | 4 Dec | Dynamic Programming III/P vs NP | 19 |
| 25 | Th | 6 Dec | ) | |
| Thursday | 13 Dec | FINAL EXAM Thursday 9am |
Note that the schedule is subject to change.