Site Map | College of Engineering | UC Davis | MyUCDavis

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%)

Catalog Description:

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.

Goals:

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:

  1. Overview
    Types of parallel systems, and motivations for parallel systems. Discussion of general techniques for designing parallel algorithms.
  2. Classes of Parallel Algorithms
    The class NC, P completeness and processor time trade-offs.
  3. Parallel Algorithms for Comparison Problems.
    Algorithms for maximum finding, selection, merging and sorting.
  4. Parallel Graph Algorithms
    Parallel algorithms for minimum spanning tree, connectivity, tree functions, ear decomposition, and matching will be discussed.
  5. Lower Bounds on Parallel Computations
    Lower bounds for parallel algorithms for first maximum independent set and for Boolean or Relationship to other problems.

References:

Selected papers from recent journals and conferences, and class notes.

Project/Design Statement:

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)

Overlap Statement:

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

12/01

Back to Course Descriptions