Addison-Wesley / Prentice Hall
Computer Science
My Instructor Resource Center : Log in or request access
Introduction to Parallel Algorithms
ISBN-10: 0201548569
ISBN-13: 9780201548563
Publisher: Addison-Wesley Professional
Copyright: 1992
Format: Paper; 576 pp
Published: 03/24/1992
Status: Available on Demand
What's this?
Written by an authority in the field, this book provides an introduction to the design and analysis of parallel algorithms. The emphasis is on the application of the PRAM (parallel random access machine) model of parallel computation, with all its variants, to algorithm analysis. Introduction.
Background.
Parallel Models.
Performance of Parallel Algorithms.
The Work-Time Presentation Framework of Parallel Algorithms.
The Optimality Notion.
Communication Complexity.
Summary.
Exercises.
Basic Techniques.
Pointer Jumping.
Divide and Conquer.
Partitioning.
Pipelining.
Accelerated Cascading.
Symmetry Breaking.
Summary.
Exercises.
Lists and Trees.
The Euler-Tour Technique.
Tree Contraction.
Lowest Common Ancestors.
Summary.
Exercises.
Searching, Merging, and Sorting.
Merging.
Sorting.
Sorting Networks.
Selection.
Lower Bounds for Comparison Problems.
Summary.
Exercises.
Graphs.
Minimum Spanning Trees.
Bioconnected Components.
Ear Decomposition.
Directed Graphs.
Summary.
Exercises.
Planar Geometry.
Intersections of Convex Sets.
Plane Sweeping.
Visibility Problems.
Dominance Counting.
Summary.
Exercises.
Strings.
String Matching.
Text Analysis.
Pattern Analysis.
Suffix Trees.
Applications of Suffix Trees.
Summary.
Exercises.
Arithmetic Computations.
Triangular Linear Systems.
The Discrete Fourier Transform.
Polynomial Multiplication and Convolution.
Toeplitz Matrices.
Polynomial Division.
Polynomial Evaluation and Interpolation.
General Dense Matrices.
Dense Structured Matrices.
Summary.
Exercises.
Randomized Algorithms.
The Problem of the Fractional Independent Set.
Point Location in Triangulated Planar Subdivisions.
Pattern Matching.
Verification of Polynomial Identities.
Point Location in Planar Subdivisions.
Randomized Quicksort.
Exercises.
Limitations of PRAMs
Lower Bounds for the CREW PRAM.
Lower Bounds for the EREW PRAM.
Lower Bounds for the CRCW PRAM.
Introduction to P-Completeness.
Exercises. 0201548569T04062001
Written by an authority in the field, this book provides an introduction to the design and analysis of parallel algorithms. The emphasis is on the application of the PRAM (parallel random access machine) model of parallel computation, with all its variants, to algorithm analysis. Special attention is given to the selection of relevant data structures and to algorithm design principles that have proved to be useful.
Features- Uses PRAM (parallel random access machine) as the model for parallel computation.
- Covers all essential classes of parallel algorithms.
- Rich exercise sets.
- Written by a highly respected author within the field.
0201548569B04062001
Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.
