Specific topics will be filled in the schedule as they are covered during the semester.
This semester's scribe notes will be posted in Laulima.
Week  Day  Date  Topic  Reading  Assignments 
1  Mon  Aug 21  Introduction, prereq assessment  
Wed  Aug 23  Models of parallel computation  [BM04, sections 1.1] [J92, section 1.11.3] 

2  Mon  Aug 28  Models of parallel computation (cont.) Parallel Summation 
[BM04, sections 1.11.3, 2.1] [J92, section 1.31.4] 

Wed  Aug 30  Brent's scheduling principle  [BM04, sections 1.21.4] [J92, section 1.41.6] 
Homework 1 out  
3  Mon  Sep 4  HOLIDAY: Labor Day  
Wed  Sep 6  Parallel Prefix Sums  [HS86] [J92, section 2.1] [B93, sections 1.11.2] 

4  Mon  Sep 11  Iterative Prefix Sums, Applications  [B93, sections 1.3, 1.5.1]  
Wed  Sep 13  Segmented Prefix Sums  [B93, sections 1.4.1, 1.5]  Homework 1 due Homework 2 out 

5  Mon  Sep 18  Segmented Prefix Sums (cont.)  [B93, sections 1.4.1]  
Wed  Sep 20  Finding Minimum  [J92, section 2.6]  
6  Mon  Sep 25  Parallel Searching  [J92, section 4.1]  
Wed  Sep 27  Mergesort, parallel merging  [J92, sections 2.4, 4.3.1]  Homework 2 due Homework 3 out 

7  Mon  Oct 2  Workefficient parallel merging  [J92, section 2.4]  
Wed  Oct 4  Parallel merging analysis  [J92, section 2.4]  
8  Mon  Oct 9  O(log log n) merging  [J92, sections 4.2, 4.3.1]  
Wed  Oct 11  Homework 2 review. Premidterm review  Homework 3 due Homework 4 out 

9  Mon  Oct 16  Midterm Exam  
Wed  Oct 18  Sorting networks  [J92, section 4.4] [01 Notes] [BSN] 

10  Mon  Oct 23  Bitonic Merge  [J92, section 4.4] [01 Notes] [BSN] 

Wed  Oct 25  List Ranking, pointer hopping  [J92, section 3.1]  Homework 4 due Homework 5 out 

11  Mon  Oct 30  Randomized List Ranking  [J92, section 3.1]  
Wed  Nov 1  Deterministic symmetry breaking via coloring  [J92, section 2.7]  
12  Mon  Nov 6  O(log n)time, O(n)work List Ranking  [J92, section 3.1]  
Wed  Nov 8  Euler Tour Technique  [J92, section 3.2]  Homework 5 due  
13  Mon  Nov 13  Tree contraction  [J92, section 3.3]  Homework 6 out 
Wed  Nov 15  Expression tree evaluation  [J92, section 3.3]  
14  Mon  Nov 20  Lowest Common Ancestor (LCA)  [J92, section 3.4.13.4.2]  
Wed  Nov 22  Range Minima Queries (RMQ)  [J92, section 3.4.3]  
15  Mon  Nov 27  Introduction to Computational Geometry, Parallel Convex Hull  [J92, sections 2.3.1, 6.1]  
Wed  Nov 29  Parallel Convex Hull (cont.)  [J92, section 6.1]  Homework 6 due  
16  Mon  Dec 4  Parallel Algorithms Workshop  
Wed  Dec 6  Parallel Algorithms Workshop 