About
Parallel processors are everywhere: servers, desktops, tablets, even cell phones. However, writing programs that take advantage of all the available parallelism is challenging, in part because it requires different techniques than what we have learned in the sequential algorithms courses.
In this course you will learn the techniques for designing and analyzing parallel algorithms – algorithms to solve a problem if it is implemented on a system with multiple processors.
Topics and Schedule
The following is a tentative schedule of the topics that will be covered in this class and is subject to change. The students are expected to know the material from the undergraduate algorithms course (e.g., ICS 311) and are encouraged to review it prior to the start of the semester.
This course is run concurrently with ICS 443 – an undergraduate version of this course. Neither course assumes any prior knowledge of parallel algorithms and there is quite a bit of overlap in topics between the two courses. However, as a graduate course, this course will progress at a faster pace than ICS 443 and will cover topics more indepth.
Week  Day  Date  Topic  Lecture Notes Reading  Assignments 
1  Mon  Jan 10  Introduction  Slides [E19, Appendix I] [E19, Appendix II]  
 Wed  Jan 12  Models of parallel computation  Slides [BM04, sections 1.1] [J92, sections 1.11.3, 2.6.1]  
2  Mon  Jan 17  HOLIDAY: MLK Day   
 Wed  Jan 19  Workdepth analysis Brent's scheduling principle  Slides [BM04, sections 1.11.4, 2.1] [J92, section 1.31.6]  Homework 1 due 
3  Mon  Jan 24  Parallel prefix sums  Slides [J92, section 2.1] [B93, sections 1.11.2] [HS86]  
 Wed  Jan 26  Applications of prefix sums  Slides [B93, sections 1.3, 1.5.1]  
4  Mon  Jan 31  Segmented prefix sums  [B93, sections 1.4.1, 1.5]  
 Wed  Feb 2  Segmented prefix sums (cont.) Applications of segmented prefix sums  Slides [B93, section 1.4.1, 1.5]  Homework 2 due DROP Without W 
5  Mon  Feb 7  Iterative Quicksort  Slides [J92, sections 1.5 ]  
 Wed  Feb 9  Finding Minimum Parallel Search  [J92, sections 2.6, 4.1]  
6  Mon  Feb 14  Simple Parallel Mergesort  [J92, sections 2.4, 4.3.1]  
 Wed  Feb 16  Workoptimal Merge  [J92, section 4.2, 4.3.1]  Homework 3 due 
7  Mon  Feb 21  HOLIDAY: President's Day   
 Wed  Feb 23  O(log log n) merging  [J92, section 4.2, 4.3.1]  
8  Mon  Feb 28  Optimal O(log n) mergesort  [J92, section 4.3.2]  
 Wed  Mar 2  Sorting networks  [J92, section 4.4] [L01] [L02] [L03]  Homework 4 due 
9  Mon  Mar 7  Takehome Midterm Exam   
 Wed  Mar 9  Takehome Midterm Exam   Midterm Exam due 
 Mon  Mar 14  SPRING RECESS   
 Wed  Mar 16  SPRING RECESS   
10  Mon  Mar 21  Sorting networks (cont.)  [J92, section 4.4] [L01] [L02] [L03]  
 Wed  Mar 23  Pointer hopping  Slides [J92, section 3.1]  
11  Mon  Mar 28  Randomized list ranking  [J92, sections 3.1, 9.2.1]  DROP With W 
 Wed  Mar 30  Deterministic symmetry breaking  [J92, sections 2.7.12.7.2, 3.1.1]  
12  Mon  Apr 4  Workoptimal 3coloring  [J92, sections 2.7.3, 3.1.1]  
 Wed  Apr 6  Workoptimal list ranking Euler Tour technique  [J92, section 3.1.2, 3.2]  Homework 5 due 
13  Mon  Apr 11  Euler Tour technique Simple tree problems  [J92, section 3.2]  
 Wed  Apr 13  Tree contraction Expression tree evaluation  [J92, sections 3.3]  
14  Mon  Apr 18  Lowest Common Ancestor (LCA) Range minima queries  [J92, section 3.4]  
 Wed  Apr 20  Connected Components  [J92, sections 5.15.2]  Homework 6 due 
15  Mon  Apr 25  Minimum Spanning Tree Matrix multiplication Allpairs shortest paths  [J92, sections, 5.2, 5.5]  
 Wed  Apr 27  Student Presentations   
16  Mon  May 2  Student Presentations   
 Wed  May 4  Student Presentations   

Reading Material
[B93] Guy Blelloch: Prefix Sums and Their Applications. A chapter from Synthesis of Parallel Algorithms, John Reif (Editor).
[BM04] Guy Blelloch and Bruce Maggs: Parallel Algorithms. A chapter from Computer Science Handbook, Second Edition, Allen B. Tucker (Editor).
[E19] Jeff Erickson, Algorithms, 1st Edition. Available free online, 2019.
[HS86] W. Daniel Hillis, Guy L. Steele, Data Parallel Algorithms, Communications of the ACM 29(12): 11701183, 1986.
[J92] Joseph JáJá, Introduction to Parallel Algorithms. Addison Wesley, 1992. ISBN: 9780201548563. Availability at UH Library.
[L01] Hans Werner Lang: Sorting Networks.
[L02] Hans Werner Lang: Proof of 01 Principle.
[L03] Hans Werner Lang: Bitonic Sort Notes.
