Algorithms Sequential & Parallel: A Unified Approach

Abstract

Algorithms Sequential & Parallel: A Unified Approach
Russ Miller and Laurence Boxer
Prentice Hall, Upper Saddle River, New Jersey 07458
330 pages, $40.77
ISBN: 0-13-086373-4

This book covers some fundamental computer science algorithms and discusses the implementation issues for both sequential and parallel models. The book is aimed to be used for a senior-level undergraduate or an introductory-level graduate course in computer science in order to help the students to understand the application and analysis of algorithmic paradigms to both sequential and parallel models of computing. It can be viewed as a complementary course to Data Structure & Algorithms or Introduction to Algorithms, which are offered in undergraduate level.

The book is organized in three parts. The first part is some background materials for the course and is comprised of three chapters. The first chapter introduces the concept of asymptotic analysis which is used frequently through out the book for analysis of algorithms. Chapter 2 briefly reviews fundamentals of induction and recursion and Chapter 3 introduces the Master method as a powerful system for evaluating recurrence equations that are used for analysis of many algorithms in the book.

The second part of the book gives an introduction to models of computation. Chapter 4 motivates the natural use of parallel models of computing by presenting the sorting networks and analyzing the Bitonic-sort algorithm using sequential and parallel models. Chapter 5 introduces basic models of computation. It starts out with RAM as a traditional sequential model of computation and then introduces PRAM as a shared memory model of parallel computing and gives several examples of algorithms that utilize this model. The chapter ends up by introducing the distributed memory machines and some interconnection networks including linear array, ring, mesh, tree, pyramid and hypercube. In addition, this chapter introduces terminology such as granularity, cost, speed up and efficiency.

The third part of the book is the main part of the book and consists of chapter 6 to 13. This part covers a variety of algorithms in several application domains and discusses the implementation and analysis of these algorithms using different computational models introduced in chapter 5. Chapter 6 considers the problem of matrix multiplication and Gaussian Elimination on RAM, PRAM and mesh models. Chapter 7 introduces the parallel prefix operation and discusses the implementation and analysis of its sample applications for a number of computation models such as RAM, PRAM, mesh and hypercube. Chapter 8 covers the pointer jumping techniques and shows how some list based algorithms can be efficiently implemented in parallel. Chapter 9 presents the divide-and-conquer and shows the application of divide-and-conquer to problems involving data movement including sort, concurrent read and write and so forth. These algorithms and their analysis are presented for a number of sequential and parallel models. Chapters 10, 11 focus on the implementation and analysis of basic algorithms in the area of computational geometry and image processing. Chapter 12 dwells on implementation of some fundamental graph algorithms such as graph traversal, labeling, minimum cost and shortest path on RAM, PRAM and mesh models. Finally chapter 13, which is an optional chapter, concerns with some basic numerical problems such as evaluating a polynomial, approximation by Taylor series, trapezoidal integration and so forth. The focus of chapter is on sequential algorithms for polynomial evaluation and approximation of definite integrals.

The book is well-organized and covers a wide variety of fundamental computer science algorithms in several application domains. It helps the students to understand the implementation of algorithms in different parallel models and compare them to their sequential counterparts. However, there are some drawbacks that could be noted. Although the analysis of parallel algorithms deals with communication models and performance measurement, the book does not cover these areas in sufficient details. The number of parallel models and interconnection networks mentioned in the book are limited and the book does not include the methodology of designing parallel algorithms. Conclusively, while the book is useful to give an introduction to parallel models and algorithms and compare them to sequential ones, students would still need to utilize other sources on parallel computing to obtain more knowledge on this domain.

Elham S. Khorasani,
Department of Computer Science
Southern Illinois University
Carbondale, IL 62901, USA