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 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 19
25 Th 6 Dec )
Thursday 13 Dec FINAL EXAM Thursday 9am

Note that the schedule is subject to change.