Contents -- Preface -- 1 Asymptotic Analysis -- Notation and Terminology -- Asymptotic Notation -- More Notation -- Asymptotic Relationships -- Asymptotic Analysis and Limits -- Summations and Integrals -- Rules for Analysis of Algorithms -- Limitations of Asymptotic Analysis -- Common Terminology -- Summary -- Chapter Notes -- Exercises -- 2 Induction and Recursion -- Mathematical Induction -- Induction Examples -- Recursion -- Binary Search -- Merging and Mergesort -- Summary -- Chapter Notes -- Exercises -- 3 The Master Method -- Master Theorem -- Proof of the Master Theorem (optional) -- The General Case -- Summary -- Chapter Notes -- Exercises -- 4 Combinational Circuits -- Combinational Circuits and Sorting Networks -- Sorting Networks -- Bitonic Merge -- BitonicSort -- Summary -- Chapter Notes -- Exercises -- 5 Models of Computation -- RAM (Random Access Machine) -- PRAM (Parallel Random Access Machine) -- Examples: Simple Algorithms -- Fundamental Terminology -- Distributed Memory versus Shared Memory -- Distributed Address Space versus Shared Address Space -- Interconnection Networks -- Processor Organizations -- Linear Array -- Ring -- Mesh -- Tree -- Pyramid -- Mesh-of-trees -- Hypercube -- Coarse-Grained Parallel Computers -- Additional Terminology -- Summary -- Chapter Notes -- Exercises -- 6 Matrix Operations -- Matrix Multiplication -- Gaussian Elimination -- Roundoff Error -- Summary -- Chapter Notes -- Exercises -- 7 Parallel Prefix -- Parallel Prefix -- Parallel Algorithms -- Parallel Prefix on the PRAM -- Mesh -- Hypercube -- Analysis -- Coarse-Grained Multicomputer -- Application: Maximum Sum Subsequence -- RAM -- PRAM -- Mesh -- Array Packing -- RAM -- PRAM -- Network Models -- Interval (Segment) Broadcasting -- Solution Strategy -- Analysis -- (Simple) Point Domination Query -- RAM -- PRAM and Network Models.

Computing Overlapping Line Segments -- RAM -- PRAM -- Mesh -- Maximal Overlapping Point -- Analysis -- Summary -- Chapter Notes -- Exercises -- 8 Pointer Jumping -- List Ranking -- Linked List Parallel Prefix -- Summary -- Chapter Notes -- Exercises -- 9 Divide-and-Conquer -- MergeSort (Revisited) -- RAM -- Linear Array -- Selection -- RAM -- Analysis of Running Time -- Parallel Machines -- QuickSort (Partition Sort) -- Array Implementation -- Analysis of QuickSort -- Expected-Case Analysis of QuickSort -- Improving QuickSort -- Modifications of QuickSort for Parallel Models -- HyperQuickSort -- BitonicSort (Revisited) -- BitonicSort on a Mesh -- Sorting Data with Respect to Other Orderings -- Concurrent Read/Write -- Implementation of a Concurrent Read -- Implementation of Concurrent Write (overview) -- Concurrent Read/Write on a Mesh -- Summary -- Chapter Notes -- Exercises -- 10 Computational Geometry -- Convex Hull -- Graham's Scan -- Jarvis' March -- Divide-and-Conquer Solution -- Smallest Enclosing Box -- RAM -- PRAM -- Mesh -- All-Nearest Neighbor Problem -- Running Time -- Architecture-Independent Algorithm Development -- Line Intersection Problems -- Overlapping Line Segments -- Summary -- Chapter Notes -- Exercises -- 11 Image Processing -- Preliminaries -- Component Labeling -- RAM -- Mesh -- Convex Hull -- Running Time -- Distance Problems -- All-Nearest Neighbor between Labeled Sets -- Running Time -- Minimum Internal Distance within Connected Components -- Hausdorff Metric for Digital Images -- Summary -- Chapter Notes -- Exercises -- 12 Graph Algorithms -- Terminology -- Representations -- Adjacency Lists -- Adjacency Matrix -- Unordered Edges -- Fundamental Algorithms -- Breadth-First Search -- Depth-First Search -- Discussion of Depth-First and Breadth-First Search -- Fundamental PRAM Graph Techniques.

List Ranking via Pointer Jumping -- Euler Tour Technique -- Tree Contraction -- Computing the Transitive Closure of an Adjacency Matrix -- Connected Component Labeling -- RAM -- PRAM -- Mesh -- Minimum-Cost Spanning Trees -- RAM -- PRAM -- Mesh -- Shortest-Path Problems -- RAM -- PRAM and Mesh -- Summary -- Chapter Notes -- Exercises -- 13 Numerical Problems -- Primality -- Greatest Common Divisor -- Lamé's Theorem -- Integral Powers -- Evaluating a Polynomial -- Approximation by Taylor Series -- Trapezoidal Integration -- Summary -- Chapter Notes -- Exercises -- Bibliography -- Index -- A -- B -- C -- D -- E -- F -- G -- H -- I -- J -- K -- L -- M -- N -- O -- P -- Q -- R -- S -- T -- U -- V -- W.