**Publisher : **
Addison-Wesley Publishing Co. - Reading, Mass.

**Bibliographic : **

- Hardcover
- ISBN: 0-201-54856-9
- © 1992
- x, 566 p. : ill. ; 25 cm.
- Dewey No.: 004/.35 20

- Parallel processing (Electronic computers) * Computer algorithms
- Algorithms

An introduction to the design and analysis of parallel algorithms. 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.

INTRODUCTION: Parallel Processing * Background * Parallel Models * Performance of Parallel Algorithms * The Work-Time (WT) Presentation Framework of PRAM Algorithms * The Optimality Notion * Communication Complexity * Summary * Exercises

SOME BASIC TECHNIQUES: Balanced Trees * Pointer Jumping * Divide-and-Conquer * Partitioning * Pipelining * Accelerated Cascading * Breaking Symmetry * Summary * Exercises

LISTS AND TREES: List Ranking * The Euler Tour Technique * Tree Contraction * Lowest Common Ancestors * Summary * Exercises

SEARCHING, MERGING, AND SORTING: Searching * Merging * Sorting * Sorting Networks * Lower Bounds for Comparison Problems * Summary * Exercises

GRAPHS: Connected Components * Minimum Spanning Trees * Bioconnected Components * Ear Decomposition * Directed Graphs * Summary * Exercises

PLANAR GEOMETRY: The Convex Hull Problem Revisited * Intersections of Convex Sets * Plane Sweeping * Visibility Problems * Dominance Counting * Summary * Exercises

STRINGS: Preliminary Facts About Strings * String Matching * Text Analysis * Pattern Analysis * Suffix Trees * Some Applications of Suffix Trees * Summary * Exercises

ARITHMETIC COMPUTATIONS: Linear Recurrences * 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: Introduction * Pattern Matching * Verification of Polynomial Identities * Point Location in Planar Subdivisions * Randomized Quicksort * Exercises

LIMITATIONS OF PRAMs: Simulations Between PRAM Models * Lower Bounds for the CREW PRAM * Lower Bounds for the EREW PRAM * Lower Bounds for the CRCW PRAM * Introduction to P-Completeness * Exercises

Includes bibliographical references and index.

Changed 30/01/1997. Comments: monika@cs.ioc.ee