COMP 312: Parallel and Sequential Algorithms

Schedule of Lectures

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 Genome II (Greedy), Sequences 5.5, 5.7, 6, code
6 Tu 25 Sep Contraction: Reduce and scan 7:Contraction
7 Th 27 Sep Maximum Contiguous Subsequence 9.MCS
8 Tu 2 Oct Randomization (max2) 10.Probability, 11.Randomized Algorithms
9 Th 4 Oct Randomized Quicksort 10.Probability, 11.Randomized Algorithms
10 Tu 9 Oct Quicksort Analysis I 11.Randomized Algorithms
11 Th 11 Oct Quicksort Analysis II 11.Randomized Algorithms
12 Tu 16 Oct Tables and Treaps 12,13
13 Th 18 Oct MIDTERM
Tu 23 Oct FALL BREAK
14 Th 25 Oct Graphs 14
15 Tu 30 Oct Breadth-First Search 15
16 Th 1 Nov Depth-First Search 15
17 Tu 6 Nov Shortest Path 16
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 29 Nov Dynamic Programming I 19
23 Th 1 Dec Dynamic Programming II 19
24 Tu 6 Dec Dynamic Programming III 19
25 Th 8 Dec )
Thursday 15 Dec FINAL EXAM Thursday 9am

Note that the schedule is subject to change.