Project (Term Project) - 1.0 hours
Summary of Course Content
Types of parallel systems, and motivations for parallel systems. Discussion of general
techniques for designing parallel algorithms.
II. Classes of Parallel Algorithms
The class NC, P completeness and processor time trade-offs.
III. Parallel Algorithms for Comparison Problems
Algorithms for maximum finding, selection, merging and sorting.
IV. Parallel Graph Algorithms
Parallel algorithms for minimum spanning tree, connectivity, tree functions, ear decomposition,
and matching will be discussed.
V. Lower Bounds on Parallel Computations
Lower bounds for parallel algorithms for first maximum independent set and for Boolean or
Relationship to other problems.
The class has a substantial project involving in-depth study of a parallel system and application.
Selected papers from recent journals and conferences, and class notes.
Potential Course Overlap
This course does not have a significant overlap with any other course. ECS 201C also covers models of parallel systems, but the focus there is on the architecture and systems aspect, while this course looks at the algorithmic implications (and thus has a very different focus).