Class  Day  Date  Topic  Notes 
1  Tue  Aug 26  Introduction Models of computation 

2  Thu  Aug 28  Models of computation Brent's scheduling principle 

3  Tue  Sep 2  Prefix sums  
4  Thu  Sep 4  Prefix sums  
5  Tue  Sep 9  Collaborative exercises  Handout 
6  Thu  Sep 11  Collaborative exercises  
7  Tue  Sep 16  Firstorder recurrences and segmented prefix sums  Notes (Sections 1.4 and 1.5) 
8  Thu  Sep 18  Segmented prefix sums: applications Discussion of the collaborative exercises 
Homework 1 out 
9  Tue  Sep 23  Searching  
10  Thu  Sep 25  Simple merging, mergesort  
11  Tue  Sep 30  O(log log n) merging Merging using ccovers 

12  Thu  Oct 2  Pipelined mergesort  Homework 1 due 
13  Tue  Oct 7  Pipelined mergesort Sorting Networks 

14  Thu  Oct 9  Sorting Networks 01 principle 

15  Tue  Oct 14  List Ranking  Homework 2 out 
16  Thu  Oct 16  List Ranking (cont.), Deterministic coin tossing  
17  Tue  Oct 21  O(log n) List Ranking  
18  Thu  Oct 23  Tree Contraction  
19  Tue  Oct 28  Expression Evaluation Lowest Common Ancestors (LCA), Range Minima Queries (RMQ) 

20  Thu  Oct 30  Connected Components on dense graphs  Homework 3 out, Homework 2 due 
  Tue  Nov 4  Holiday: Election Day  
21  Thu  Nov 6  Connected Components on sparse graphs  
  Tue  Nov 11  Holiday: Veterans' Day  
22  Thu  Nov 13  Minimum spanning tree, Allpairs shortest paths  Homework 3 due 
23  Tue  Nov 18  Convex hull, intersection of halfplanes, 2variable linear programming  
24  Thu  Nov 20  Plane sweep tree  Homework 4 out 
25  Tue  Nov 25  NO CLASS  
  Thu  Nov 27  Holiday: Thanksgiving Day  
26  Tue  Dec 2  2D Counting problems: Dominance counting, Orthogonal range counting, Orthogonal line segment intersection counting  
27  Thu  Dec 4  Advanced parallel models of computation: PEM, GPU, MapReduce  Homework 4 due 
28  Tue  Dec 9  Project presentations  
29  Thu  Dec 11  Project presentations  Project due 