A major thrust of computer science is the design, analysis, implementation, and scientific 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 becomes more and more important for students and scientists to understand the application and analysis of algorithmic paradigms to both the (traditional) sequential model of computing and to a variety of parallel models.
Many computer science departments offer courses in "Analysis of Algorithms," "Algorithms," "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 parallel algorithms begin to appear in research-oriented departments. Furthermore, these courses 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 component 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 coverage of parallel and sequential algorithms throughout the course.
The philosophy taken in this book is to cover a paradigm, such as divide-and-conquer, 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 models, the reader might notice that the number of paradigms we can treat within a semester is limited.
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.
Prerequisites: We assume that the reader has a basic knowledge of data structures. That is, the reader should be comfortable with the notion of a stack, queue, list, and binary tree, at a level that is typically taught in a CS2 course. The reader should also be familiar with fundamentals of discrete mathematics and Calculus. Specifically, the reader should be comfortable with limits, summations, and integrals.
