Publisher : Addison-Wesley Publishing Co. - Reading, Mass.
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.
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.