ECS 223: Parallel Algorithms

Subject
ECS 223
Title
Parallel Algorithms
Status
Active
Units
4.0
Effective Term
2016 Spring Quarter
Learning Activities
Discussion/Laboratory - 3.0 hours
Project (Term Project) - 1.0 hours
Description
Models of parallel computer systems including PRAMs, loosely coupled systems and interconnection networks. Parallel algorithms for classical problems and general techniques for their design and analysis. Proving lower bounds on parallel computation in several settings.
Prerequisites
ECS 222A
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.

Summary of Course Content
I. Overview
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.

Project/Design Statement:
The class has a substantial project involving in-depth study of a parallel system and application.



Illustrative Reading
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).

Course Category

Graduate