A major thrust of computer science is the design, analysis, implementation, and scicntific
evaluation of algorithms to solve critical problems. In addition, new challenges are being
offered to computer scientists in the field of computational science and engineering, which
includes challenging problems in computational biology, computational fluid dynamics, and
computational chemistry, to name a few. As parallel computing continues to merge into the
mainstream of computing, it becomcs more and more important for students and scientists
to understand the application and analysis of algorithmic paradigms to both the (tradition
al) sequential model of computing and to a variety of parallel models.
Many computer science departments offer courses in "Analysis of Algorithms," "Al
gorithms," "An Introduction to Algorithms," or "Data Structures and their Algorithms" at
the junior or senior level. In addition, a course in "Analysis of Algorithms" is required of
most graduate students pursuing a degree in computer science. Throughout the 1980s, the
vast majority of these course offerings focused on algorithms for sequential (von Neumann)
computers. In fact, not until the late-1980's did courses covering an introduction to paral
lel algorithms begin to appear in research-oriented departments. Furthermore, these cours
es in parallel algorithms were typically presented to advanced graduate students. However,
by the early 1990s, courses in parallel computing began to emerge at the undergraduate
level, especially at progressive 4-year colleges.
It is interesting to note that throughout much of the 1990's, traditional algorithms-
based courses changed very little. Gradually, such courses began to incorporate a compo
nent of parallel algorithms, typically one to three weeks near the end of the semester. During
the later part of the 1990s, however, it was not uncommon to find algorithms courses that
contained as much as 1/3 of the material devoted to parallel algorithms.
In this book, we take a very different approach to a traditional algorithms-based course.
Parallel computing has become more mainstream, with small multiprocessor machines
(which can be ordered by mail from your favorite catalog vendor) flooding the marketplace
and with distributed computing systems being efficiently exploited. Therefore, we believe
the time is right to teach a fundamental course in algorithms that covers paradigms for both
the sequential and parallel models. In fact, the approach we take is to integrate the cover
age of parallel and sequential algorithms throughout the course.
The philosophy taken in this book is to cover a paradigm, such as divide-and-con-
quer, and then cover implementation issues for both the sequential and parallel models. Due
to the fact that we present design and analysis of paradigms for sequential and parallel mod
els, the reader might notice that the number of paradigms we can treat within a semester
Several offerings of a course based on a preliminary version of this book have been
taught successfully at both the undergraduate and graduate levels at the State University of
New York at Buffalo.