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.