ICS 443 Spring 2022 Parallel Algorithms

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.

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.1-1.3, 2.6.1]
2	Mon	Jan 17	HOLIDAY: MLK Day
	Wed	Jan 19	Work-depth analysis Brent's scheduling principle	Slides [BM04, sections 1.1-1.4, 2.1] [J92, section 1.4-1.6]	Homework 1 due
3	Mon	Jan 24	Parallel prefix sums	Slides [J92, section 2.1] [B93, sections 1.1-1.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.)	Slides [B93, sections 1.4.1, 1.5]	Homework 2 due DROP Without W
5	Mon	Feb 7	Segmented prefix sums (cont.) Quicksort	Slides [B93, section 1.5]
	Wed	Feb 9	Finding minimum	Slides [J92, sections 2.6]
6	Mon	Feb 14	Parallel Search	[J92, sections 4.1, 2.4, 4.3.1]
	Wed	Feb 16	Mergesort, parallel merging	[J92, sections 4.1, 2.4, 4.3.1]	Homework 3 due
7	Mon	Feb 21	HOLIDAY: President's Day
	Wed	Feb 23	Work-efficient parallel merging	[J92, sections 4.2, 4.3.1]
8	Mon	Feb 28	Work-efficient parallel merging (cont.)	[J92, section 4.2, 4.3.1]
	Wed	Mar 2	O(log log n) merging	[J92, section 4.2, 4.3.1]	Homework 4 due
9	Mon	Mar 7	Take-home Midterm Exam
	Wed	Mar 9	Take-home Midterm Exam		Midterm Exam due
	Mon	Mar 14	SPRING RECESS
	Wed	Mar 16	SPRING RECESS
10	Mon	Mar 21	Midterm Review Graph represenations	[E19, section 5.4]
	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.1-2.7.2, 3.1.1]
12	Mon	Apr 4	Work-optimal 3-coloring	[J92, sections 2.7.3, 3.1.1]
	Wed	Apr 6	Euler Tour technique	[J92, section 3.2]	Homework 5 due
13	Mon	Apr 11	Simple Tree problems	[J92, section 3.2]
	Wed	Apr 13	Tree contraction Expression tree evaluation	[J92, section 3.3]
14	Mon	Apr 18	Lowest Common Ancestor (LCA)	[J92, section 3.4.1]
	Wed	Apr 20	Range minima queries	[J92, section 3.4.2-3.4.3]	Homework 6 due
15	Mon	Apr 25	Connected Components Minimum Spanning Tree	[J92, section 5.1-5.2]
	Wed	Apr 27	Matrix multiplication All-pairs shortest paths	[J92, section 5.5]
16	Mon	May 2	Take-home Final Exam
	Wed	May 4	Take-home Final Exam		Final Exam due

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): 1170-1183, 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 0-1 Principle.

[L03] Hans Werner Lang: Bitonic Sort Notes.