Algorithms Sequential and Parallel : A Unified Approach

Hardcover (Print)
Used and New from Other Sellers
Used and New from Other Sellers
from $2.93
Usually ships in 1-2 business days
(Save 95%)
Other sellers (Hardcover)
  • All (10) from $2.93   
  • New (2) from $37.18   
  • Used (8) from $2.93   
Close
Sort by
Page 1 of 1
Showing All
Note: Marketplace items are not eligible for any BN.com coupons and promotions
$37.18
Seller since 2014

Feedback rating:

(265)

Condition:

New — never opened or used in original packaging.

Like New — packaging may have been opened. A "Like New" item is suitable to give as a gift.

Very Good — may have minor signs of wear on packaging but item works perfectly and has no damage.

Good — item is in good condition but packaging may have signs of shelf wear/aging or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Acceptable — item is in working order but may show signs of wear such as scratches or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Used — An item that has been opened and may show signs of wear. All specific defects should be noted in the Comments section associated with each item.

Refurbished — A used item that has been renewed or updated and verified to be in proper working condition. Not necessarily completed by the original manufacturer.

New
Brand New Item.

Ships from: Chatham, NJ

Usually ships in 1-2 business days

  • Canadian
  • International
  • Standard, 48 States
  • Standard (AK, HI)
  • Express, 48 States
  • Express (AK, HI)
$60.00
Seller since 2014

Feedback rating:

(147)

Condition: New
Brand new.

Ships from: acton, MA

Usually ships in 1-2 business days

  • Standard, 48 States
  • Standard (AK, HI)
Page 1 of 1
Showing All
Close
Sort by

Overview

  • 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 ...
Read More Show Less

Product Details

  • ISBN-13: 9780130863737
  • Publisher: Pearson Education
  • Publication date: 12/27/1999
  • Pages: 330
  • Product dimensions: 7.26 (w) x 9.58 (h) x 0.78 (d)

Meet the Author

Russ Miller

Russ Miller (Buffalo, NY) is the Director of the Center for Computational Research and a Distinguished Professor of Computer Science and Engineering at the State University of New York at Buffalo (SUNY-Buffalo). He co-authored Parallel Algorithms for Regular Architectures: Meshes and Pyramids (The MIT Press, 1996) with Q.F. Stout.

Laurence Boxer (Niagara Falls, NY) is Professor of Computer and Information Sciences at Niagara University, and Research Professor of Computer Science and Engineering at the State University of New York at Buffalo (SUNY-Buffalo).

Read More Show Less

Read an Excerpt

PREFACE:

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 verylittle. 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 miller@cse.buffalo.edu and Laurence Boxer may be reached at boxer@niagara.edu. In addition, a Web site for the book is available at ...

Read More Show Less

Table of Contents

1. Asymptotic Analysis.
2. Induction and Recursion.
3. The Master Method.
4. Combinational Circuits.
5. Models of Computation.
6. Matrix Operations.
7. Parallel Prefix.
8. Pointer Jumping.
9. Divide-and-Conquer.
10. Computational Geometry.
11. Image Processing.
12. Graph Algorithms.
13. Numerical Problems.
Bibliography.
Index.
Read More Show Less

Preface

PREFACE:

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 changedverylittle. 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 miller@cse.buffalo.edu and Laurence Boxer may be reached at boxer@niagara.edu. In addition, a Web site for the book is available at ...

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)