This course is no longer offered

22906 Parallel Algorithms

Credits: 4 graduate credits in Computer Science

Prerequisite: Admission to the graduate program in Computer Science 1

The course is based on the following chapters from An Introduction to Parallel Algorithms, by J. Jaja (Addison-Wesley, 1992): Introduction; Basic techniques; Lists and trees; Search, merge and sort (sections 4.1, 4.2, 4.3.1, 4.4); Graphs (sections 5.1, 5.2); Limitations (sections 10.1, 10.5).

Parallel algorithms are primarily used to solve problems rapidly by using several processors simultaneously. The processors are usually of the same type, run at the same speed and located a short distance from each other. The need for fast solutions and for solving problems that demand particularly long computation time exists in several fields: image processing, searching large data sets, solving optimization problems, computer-aided manufacture, weather prediction, simulation of large-scale systems.

In recent years, much basic research has been performed dealing with defining basic concepts and formal models and developing basic techniques and algorithms for the relatively new field of parallel computation. The course surveys some of the results of this research; it covers basic techniques, presents parallel algorithms which are more efficient than sequential algorithms for solving various problems, and shows that for some problems, parallel algorithms are not more efficient than sequential algorithms. The course focuses on the theoretical basis for the field, and does not deal with topics such as the structure of parallel computers or programming languages.

---

1Students who have not fulfilled this requirement may, under certain circumstances, enroll in this course.