CISC 821: Parallel Algorithms

Catalog Description:
Study of design and analysis techniques for parallel algorithms is conducted. Topics include: basic techniques of parallel algorithm design; searching and sorting in parallel; parallel tree and graph algorithms; and complexity issues, including the relationships among PRAM models, the class NC, and P-completeness.

Current Text:
An Introduction to Parallel Algorithms
JaJa
Addison-Wesley

Goals:
This is a course on the design and analysis of parallel algorithms. The aim is to provide a good working knowledge of important parallel algorithms, and techniques used in the design of parallel algorithms, as well as an understanding of various complexity issues associated with parallel algorithm design.

Content:

• Basic techniques of parallel algorithm design: prefix sums, partitioning, accelerated cascading, pipelining, symmetry breaking, and pointer jumping.
• Searching, merging and sorting in parallel.
• Parallel tree algorithms: Euler tours, the rake operation, nearest common ancestors, and range minima.
• Parallel graph algorithms: Connected components, minimum spanning trees and ear decomposition.
• Complexity relationships between PRAM models.
• The class NC and P-completeness

Required Background: CISC 621 (Algorithm design and analysis).