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  Old Scribe Notes  Notes 
1  Mon  Aug 21  Introduction, prereq assessment  
Wed  Aug 23  Models of parallel computation  Scribe Notes  Reading: [BM04, sections 1.1], [J92, section 1.11.3]  
2  Mon  Aug 28  Models of parallel computation (cont.) Parallel Summation 
Scribe Notes  Reading: [BM04, sections 1.11.3, 2.1], [J92, section 1.31.4] DROP DATE (without W) 
Wed  Aug 30  Brent's scheduling principle  Scribe Notes  Reading: [BM04, sections 1.21.4], [J92, section 1.41.6] Homework 1 out ADD DATE 

3  Mon  Sep 4  HOLIDAY: Labor Day  
Wed  Sep 6  Parallel Prefix Sums  Scribe Notes 1 Scribe Notes 2 Slides 
Reading: [HS86][J92, section 2.1][B93, sections 1.11.2]  
4  Mon  Sep 11  Iterative Prefix Sums, Applications  Slides  Reading: [B93, sections 1.3, 1.5.1] 
Wed  Sep 13  Segmented Prefix Sums  Scribe Notes  Reading: [B93, sections 1.4.1, 1.5] Homework 1 due Homework 2 out 

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

7  Mon  Oct 2  Workefficient parallel merging  Reading: [J92, section 2.4]  
Wed  Oct 4  Parallel merging analysis  Reading: [J92, section 2.4]  
8  Mon  Oct 9  O(log log n) merging  Reading: [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  Reading: [J92, section 4.4] [01 Notes] [BSN]  
Fri  Oct 20  DROP DATE (with W)  
10  Mon  Oct 23  Bitonic Merge  Reading: [J92, section 4.4] [01 Notes] [BSN]  
Wed  Oct 25  List Ranking, pointer hopping  Reading: [J92, section 3.1] Homework 4 due Homework 5 out 

11  Mon  Oct 30  Randomized List Ranking  Reading: [J92, section 3.1]  
Wed  Nov 1  Deterministic symmetry breaking via coloring  Reading: [J92, section 2.7]  
12  Mon  Nov 6  O(log n)time, O(n)work List Ranking  Reading: [J92, section 3.1]  
Wed  Nov 8  Euler Tour Technique  Reading: [J92, section 3.2] Homework 5 due 

13  Mon  Nov 13  Tree contraction  Reading: [J92, section 3.3] Homework 6 out 

Wed  Nov 15  Expression tree evaluation  Reading: [J92, section 3.3]  
14  Mon  Nov 20  
Wed  Nov 22  
15  Mon  Nov 27  
Wed  Nov 29  Homework 6 due  
16  Mon  Dec 4  Parallel Algorithms Workshop  
Wed  Dec 6  Parallel Algorithms Workshop 