Algorithms Sequential & Parallel: A Unified Approach (Charles River Media Computer Engineering) [Hardcover]

Laurence Boxer (Author), Russ Miller (Author)

Book Description

ISBN-10: 1584504129 | ISBN-13: 978-1584504122 | Publication Date: August 3, 2005 | Edition: 2

With multi-core processors replacing traditional processors and the movement to multiprocessor workstations and servers, parallel computing has moved from a specialty area to the core of computer science. In order to provide efficient and cost-effective solutions to problems, algorithms must be designed for multiprocessor systems. Algorithms Sequential and Parallel: A Unified Approach 2/E provides a state-of-the-art approach to an algorithms course. The book considers algorithms, paradigms, and the analysis of solutions to critical problems for sequential and parallel models of computation in a unified fashion. This gives practicing engineers and scientists, undergraduates, and beginning graduate students a background in algorithms for sequential and parallel algorithms within one text. Prerequisites include fundamentals of data structures, discrete mathematics, and calculus.

Editorial Reviews

From the Inside Flap

Preface

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.

OVERVIEW OF CHAPTERS

Background material for the course is presented in Chapters 1, 2, & 3. Chapter 1 introduces the concept of asymptotic analysis. While the reader might have seen some of this material in a course on data structures, we present this material in a fair amount of detail. The reader who is uncomfortable with some of the fundamental material from a Freshman-level Calculus sequence might want to brush up on notions such as limits, summations and integrals, and derivatives, as they naturally arise in the presentation and application of asymptotic analysis. Chapter 2 focuses on fundamentals of induction and recursion. While many students have seen this material in previous courses in computer science and/or mathematics, we have found it important to review this material briefly and to provide the students with a reference for performing the necessary review. In Chapter 3, we present the Master Method, a very useful cookbook-type of system for evaluating recurrence equations that are common in an algorithms-based setting.

Chapter 4 presents an overview of combinational circuits and sorting networks. This work is used to motivate the natural use of parallel models and to demonstrate the blending of architectural and algorithmic approaches. In Chapter 5, we introduce fundamental models of computation, including the RAM (a formal sequential architecture) and a variety of parallel models of computation. The parallel models introduced include the PRAM, mesh, and hypercube, to name a few. In addition, Chapter 5 introduces terminology such as shared-memory and distributed memory.

The focus of Chapter 6 is the important problem of matrix multiplication, which is considered for a variety of models of computation. In Chapter 7, we introduce the parallel prefix operation. This is a very powerful operation with a wide variety of applications. We discuss implementations and analysis for a number of the models presented in Chapter 5 and give sample applications. In Chapter 8, we introduce pointer jumping techniques and show how some list-based algorithms can be efficiently implemented in parallel.

In Chapter 9, we introduce the powerful divide-and-conquer paradigm. We discuss applications of divide-and-conquer to problems involving data movement, including sorting, concurrent reads/writes, and so forth. Algorithms and their analysis are presented for a variety of models.

Chapters 10 & 11 focus on two important application areas, namely, computational geometry and image processing. In these chapters, we focus on interesting problems chosen from these important domains as a way of solidifying the approach of this book in terms of developing machine independent solution strategies, which can then be tailored for specific models, as required.

Chapter 12 focuses on fundamental graph theoretic problems. Initially, we present standard traversal techniques, including breadth-first search, depth-first search, and pointer jumping. We then discuss fundamental problems, including tree contraction and transitive closure. Finally, we couple these techniques with greedy algorithms to solve problems, such as labeling the connected components of a graph, determining a minimal spanning forest of a graph, and problems involving shortest or minimal-weight paths in a graph.

Chapter 13 is an optional chapter concerned with some fundamental numerical problems. The focus of the chapter is on sequential algorithms for polynomial evaluation and approximations of definite integrals.

RECOMMENDED USE

This book has been used in both a junior/senior-level elective and a required first year graduate level course in the Department of Computer Science and Engineering at the State University of New York at Buffalo (SUNY Buffalo). The course was presented in 14 weeks, consisting of twenty-four (24) 75-minute lectures, two review classes, and two exams. Recitations were conducted by an advanced graduate student and were used to help the students with homework sets and an understanding of the material. The recitations were especially important early in the semester when mathematically-based background material was being presented. This course is tailored towards students who are not advanced in a mathematical sense, but have a basic, fundamental, background.

CORRESPONDENCE

Please feel free to contact the authors directly with any comments or criticisms (constructive or otherwise) of this book. Russ Miller may be reached at [e-mail] and Laurence Boxer may be reached at [e-mail] Web site contains information related to the book, including pointers to education-based pages, relevant parallel computing links, and errata. --This text refers to an out of print or unavailable edition of this title.

From the Back Cover

• The text offers a unified approach that relates sequential and parallel algorithms where appropriate and contrasts where appropriate
.
• Mathematical tools are developed in early chapters
.
• A variety of examples are worked out in great detail with multiple methods of solutions
.
• Sequential and parallel examples and exercises are featured
.
• Supplemental material is available for instructors
.
• A Prentice Hall Companion Website with additional material is available at http://www.prenhall.com/millerboxer.

--This text refers to an out of print or unavailable edition of this title.

See all Editorial Reviews

Product Details

• Hardcover: 382 pages
• Publisher: Charles River Media; 2 edition (August 3, 2005)
• Language: English
• ISBN-10: 1584504129
• ISBN-13: 978-1584504122
• Product Dimensions: 9.5 x 7.6 x 1.2 inches
• Shipping Weight: 2.6 pounds (View shipping rates and policies)
• Average Customer Review: 5.0 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #587,792 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

11 of 14 people found the following review helpful:

5.0 out of 5 stars Not unbiased, but ..., August 19, 2005

By 

Laurence Boxer (Niagara University, NY) - See all my reviews
(REAL NAME)   

This review is from: Algorithms Sequential & Parallel: A Unified Approach (Charles River Media Computer Engineering) (Hardcover)

I'm coauthor, so I'm not unbiased. Having said that....

The dominant textbook in the field of computer algorithms is Introduction to Algorithms, by Cormen et al. This is a very fine book. However, we have written Algorithms Sequential and Parallel in a very different style, which we feel will give significant advantages to many who use our book. Points of difference between these texts include the following:

1. Algorithms Sequential and Parallel has a unified approach to the presentation of sequential and parallel algorithms. Students of 21st Century computing will need to learn parallel algorithms, which are often closely related to their sequential analogs. Ours is the first algorithms text to integrate presentation of sequential and parallel algorithms so that readers can understand their relationships. This integrated treatment also frees the instructor from the common practice of spending most of an algorithms course on the study of sequential algorithms, with the last 2 or 3 weeks devoted to parallel algorithms - a practice that may mislead students into thinking that parallel computing is still the immature specialization of researchers, rather than a core technology for the 21st Century.

2. Algorithms Sequential and Parallel does not compete with Cormen et al. in the scope of topics covered. The Cormen et al. text, whose 2nd edition is well over 1100 pages, seems designed for at least a year sequence in the study of algorithms. By contrast, Algorithms Sequential and Parallel, 2nd edition, is under 400 pages. This makes it suitable for a one-semester study of algorithms, appropriate for many undergraduate and first- or second-year graduate programs; also, it makes Algorithms Sequential and Parallel significantly less costly.

Algorithms Sequential and Parallel discusses mathematical tools used in the analysis of algorithms, a variety of sequential and parallel models of computation (including the RAM, PRAM, linear array, mesh, hypercube, pyramid, mesh-of-trees, and coarse-grained models), fundamental algorithms (including broadcast, semigroup computations, parallel prefix, sorting, searching) and their sequential and parallel implementations, paradigms such as recursive divide-and-conquer, and algorithms for a variety of applications areas (matrix operations and a variety of other numerical problems, computational geometry, image processing, graph problems, etc). Each chapter concludes with exercises at varying levels of difficulty.

Note that a disinterested reviewer gave the first edition of Algorithms Sequential and Parallel a rating of 5 stars (out of 5) in SIGACT News 34 #2, June, 2003, pp. 3-5.

2 of 2 people found the following review helpful:

5.0 out of 5 stars An easy transition from sequential to parrallel, June 25, 2008

By 

Vyacheslav Imameyev "sl1234" (Russia) - See all my reviews
(REAL NAME)   

This review is from: Algorithms Sequential & Parallel: A Unified Approach (Charles River Media Computer Engineering) (Hardcover)

The book represents a very decent approach for a transition from the sequential algorithms design ( RAM model ) to parallel algorithms for different models of parallel machines( not only SMP for which most of the software engineers get accustomed ).

The book is an introduction for a person with a good background in a sequential algorithms design. The proof of the Master Theorem is somehow overcomplicated - it would have been better if there had been a sketch of the proof before the authors delve into the mathematically rigorous part. Before reading the proof in this book I recommend to read a proof of a simplified version of the Master Theorem as given in "Algorithms" by Dasgupta, Papadimitriou and Vazirani - it takes less than a page compared with 11 pages for the complete case in this book.

I first came across the first edition's translation on Russian nearly 2 years ago ( the author's site says it was translated in 2007, but actually it was in the first quarter of 2006 ), then I bought the original 2nd edition - the book worth it.

P.S. I've found nothing about Python language, as one of the review says, the authors use easily understandable pseudo-language. The book is not a cook book with code - this is virtually impossible for such a type of book as an algorithm realization heavily depends on a parallel machine architecture.

4 of 8 people found the following review helpful:

5.0 out of 5 stars A GRAND COMPUTATIONAL AND ENGINEERING APPROACH, November 29, 2005

By 

John R. Vacca "Tech Write Independent Reviewer" (Pomeroy, Ohio) - See all my reviews
(REAL NAME)   

This review is from: Algorithms Sequential & Parallel: A Unified Approach (Charles River Media Computer Engineering) (Hardcover)

Have you been trying to find a way of to integrate the presentation of sequential and parallel algorithms? If you are, this book is for you! Authors Russ Miller and Laurence Boxer, have done an outstanding job of writing a great book on how to employ a philosophy of presenting a paradigm, such as divide and conquer, and then discussing implementation issues for both sequential and parallel models.

Miller and Laurence Boxer begin by introducing the concept of asymptotic analysis.
Next, the authors explain the Python programming language to write scripts. Then, they focus on fundamentals of induction and recursion. The authors continue by presenting the Master Method, a very useful cookbook-type of system for evaluating recurrence equations that are common in an algorithms-based setting. In addition, the authors next present an overview of combinational circuits and sorting networks. They also introduce fundamental models of computation, including the RAM and a variety of parallel models of computation. Next, the authors focus on the important problem of matrix multiplication, which is considered for a variety of models of computation. Then, they introduce the parallel prefix operation. The authors continue by introducing pointer jumping techniques and show how some list-based algorithms can be efficiently implemented in parallel. In addition, the authors next present the powerful divide and conquer paradigm. They also focus on two important application areas, namely, Computational Geometry and Image Processing. Next, the authors focus on fundamental graph theoretic problems. Finally, they cover sequential algorithms for polynomial evaluation and approximation of definite integrals.

Due to the fact that authors of this excellent book present design and analysis of paradigms for sequential and parallel models, the reader will notice that the number of paradigms that can be treated is limited. But, that limitation is of no consequence when compared to a traditional sequential algorithms text.