ECS 223 PARALLEL ALGORITHMS (4) II
Lecture: 3 hours
Project: 1 hour
Prerequisite: Course ECS 222A
Grading: Letter; homework assignments (30%), project (35%), final (35%)
Models of parallel computer systems including PRAMs, loosely coupled systems and interconnection networks. Parallel algorithms for classical problems are studied as well as general techniques for their design and analysis. Lower bounds on parallel computation are proved in several settings.
Students learn about a variety of parallel models and algorithms and how the models relate to the types of algorithms which are effective.
Expanded Course Description:
Types of parallel systems, and motivations for parallel systems. Discussion of general techniques for designing parallel algorithms.
- Classes of Parallel Algorithms
The class NC, P completeness and processor time trade-offs.
- Parallel Algorithms for Comparison Problems.
Algorithms for maximum finding, selection, merging and sorting.
- Parallel Graph Algorithms
Parallel algorithms for minimum spanning tree, connectivity, tree functions, ear decomposition, and matching will be discussed.
- Lower Bounds on Parallel Computations
Lower bounds for parallel algorithms for first maximum independent set and for Boolean or Relationship to other problems.
Selected papers from recent journals and conferences, and class notes.
The class has a substantial project involving in depth study of a parallel system and application.
Instructor: C. Martel
Prepared by: C. Martel (December 2001)
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).