Fundamentals of Sequential and Parallel Algorithms

Abstract

Kenneth A. Berman and Jerome L. Paul 
PWS Publishing Company, Boston, MA, 1997, 730 pp. 
ISBN 0-534-94674-7, $73.95

Sequential and Parallel Algorithms is a superbly organized, comprehensive exposition of fundamental algorithms. The content of this text is impressive, covering the subject of algorithms from many perspectives: sequential, parallel, formal (analysis), conceptual (design), all the while supporting what is discussed with detailed examples. Hence, this book can be used in an upper-level undergraduate course on algorithms, whether that class takes the more traditional (sequential) approach or a more ambitious attempt to incorporate parallelism. This book could also be used in an introductory graduate level course, or, as a reference, by the working professional.

From the beginning, the authors motivate the study of this subject well, providing entertaining but relevant examples. Part I provides necessary background material, in the form of essential data structures, mathematical notation and theory, standard parallel architectures, and sorting algorithms. The presentation does not depend on previous knowledge, and can be covered in a variety of orders. Part II, the "Algorithms Toolkit", expands on the material covered in Part I by exploring more intricate mathematical concepts (recurrence relations, probablistic analysis, lower bound theory), data structures (graphs and their traversals, sets and their implementation), and parallel processing (parallel prefix computation and matrix multiplication). In this manner, Part II prepares the student nicely for the major design strategies delineated in Part III.

Each major approach: divide-and-conquer, greedy, dynamic programming, backtracking and branch-and-bound, is discussed via recognizable problems. Many classic problems are examined in the context of design strategy. Even problems considered difficult, most notably FFT and the selection problem, are covered thoroughly. Complexity measures are derived for both time and space performance. Comparative strategies are frequently noted. Parallelization of sequential algorithms is examined at the tail end of all but one chapter in this section. Curiously, the authors sometimes omit comments indicating when or how easily a sequential algorithm can be parallelized. The careful, or experienced, reader can easily make such projections, but not the novice.

The last section of the book, Part IV, appropriately contains more specialized, or advanced, topics such as game trees, balanced trees, probablistic algorithms, graph (network) algorithms, and a discussion of NP-completeness. As in earlier sections, the writing style remains consistently balanced and thorough. Except for the last chapter’s treatment of NP reductions, illustrations are well-placed and reinforce the concepts covered.

In sum, this book is a well-organized and thoroughly developed text with plenty of supportive examples and illustrations. The major sections of the book are ordered nicely, as is each individual chapter. End-of-chapter exercises are challenging and pertain directly to the content just covered. Moreover, a nice mix of theory, analysis, design and even implementation is included in these exercises. The only (small) disappointment is that the chapter-end references point primarily to other texts or original citations and are rather sketchy in the area of current research. Overall, this text would be a valuable tool to professionals or to students enrolled in an algorithms, advanced algorithms, or introductory graduate level course.

Adair Dingle ,
Seattle University