Algorithms Sequential & Parallel A Unified Approach

by Miller, Russ; Boxer, Laurence

• ISBN13: 9781584504122
• ISBN10: 1584504129
• Edition: 2nd
• Format: Hardcover
• Copyright: 2005-08-03
• Publisher: Course Technology

Summary

With multi-core processors replacing traditional processors and the movement to multiprocessor workstations and servers, parallel computing has moved from a specialty area to the core of computer science. In order to provide efficient and cost-effective solutions to problems, algorithms must be designed for multiprocessor systems. Algorithms Sequential and Parallel: A Unified Approach 2/E provides a state-of-the-art approach to an algorithms course. The book considers algorithms, paradigms, and the analysis of solutions to critical problems for sequential and parallel models of computation in a unified fashion. This gives practicing engineers and scientists, undergraduates, and beginning graduate students a background in algorithms for sequential and parallel algorithms within one text. Prerequisites include fundamentals of data structures, discrete mathematics, and calculus.

Author Biography

Laurence Boxer is Professor and past chair of the Department of Computer and Information Sciences at Niagara University, and is Research Professor of Computer Science and Engineering at SUNY-Buffalo. Russ Miller is founding director of SUNY-Buffalo's Center for Computational Research, one of the leading supercomputing centers in the world.

Table of Contents

Preface	xv
Asymptotic Analysis	2	(32)
Notation and Terminology	4	(7)
Asymptotic Notation	6	(3)
More Notation	9	(2)
Asymptotic Relationships	11	(10)
Asymptotic Analysis and Limits	12	(2)
Summations and Integrals	14	(7)
Rules for Analysis of Algorithms	21	(6)
Limitations of Asymptotic Analysis	27	(2)
Common Terminology	29	(1)
Summary	29	(1)
Chapter Notes	30	(1)
Exercises	30	(4)
Induction and Recursion	34	(24)
Mathematical Induction	36	(1)
Induction Examples	37	(3)
Recursion	40	(3)
Binary Search	43	(4)
Merging and Mergesort	47	(7)
Summary	54	(1)
Chapter Notes	54	(1)
Exercises	54	(4)
The Master Method	58	(16)
Master Theorem	61	(12)
Proof of the Master Theorem (optional)	61	(5)
The General Case	66	(7)
Summary	73	(1)
Chapter Notes	73	(1)
Exercises	73	(1)
Combinational Circuits	74	(16)
Combinational Circuits and Sorting Networks	76	(4)
Sorting Networks	76	(4)
Bitonic Merge	80	(4)
BitonicSort	84	(3)
Summary	87	(1)
Chapter Notes	88	(1)
Exercises	88	(2)
Models of Computation	90	(56)
RAM (Random Access Machine)	92	(2)
PRAM (Parallel Random Access Machine)	94	(12)
Examples: Simple Algorithms	98	(8)
Fundamental Terminology	106	(2)
Distributed Memory versus Shared Memory	107	(1)
Distributed Address Space versus Shared Address Space	108	(1)
Interconnection Networks	108	(31)
Processor Organizations	109	(1)
Linear Array	110	(8)
Ring	118	(1)
Mesh	119	(4)
Tree	123	(2)
Pyramid	125	(2)
Mesh-of-trees	127	(4)
Hypercube	131	(5)
Coarse-Grained Parallel Computers	136	(3)
Additional Terminology	139	(3)
Summary	142	(1)
Chapter Notes	142	(1)
Exercises	143	(3)
Matrix Operations	146	(18)
Matrix Multiplication	148	(5)
Gaussian Elimination	153	(7)
Roundoff Error	160	(1)
Summary	161	(1)
Chapter Notes	161	(1)
Exercises	161	(3)
Parallel Prefix	164	(28)
Parallel Prefix	166	(10)
Parallel Algorithms	167	(1)
Parallel Prefix on the PRAM	167	(4)
Mesh	171	(3)
Hypercube	174	(2)
Analysis	176	(1)
Coarse-Grained Multicomputer	176	(1)
Application: Maximum Sum Subsequence	176	(3)
RAM	176	(1)
PRAM	177	(2)
Mesh	179	(1)
Array Packing	179	(3)
RAM	180	(1)
PRAM	181	(1)
Network Models	181	(1)
Interval (Segment) Broadcasting	182	(1)
Solution Strategy	182	(1)
Analysis	183	(1)
(Simple) Point Domination Query	183	(2)
RAM	185	(1)
PRAM and Network Models	185	(1)
Computing Overlapping Line Segments	185	(4)
RAM	186	(1)
PRAM	187	(1)
Mesh	188	(1)
Maximal Overlapping Point	188	(1)
Analysis	188	(1)
Summary	189	(1)
Chapter Notes	189	(1)
Exercises	189	(3)
Pointer Jumping	192	(8)
List Ranking	194	(2)
Linked List Parallel Prefix	196	(1)
Summary	197	(1)
Chapter Notes	198	(1)
Exercises	198	(2)
Divide-and-Conquer	200	(42)
MergeSort (Revisited)	202	(3)
RAM	202	(1)
Linear Array	203	(2)
Selection	205	(6)
RAM	206	(3)
Analysis of Running Time	209	(1)
Parallel Machines	210	(1)
QuickSort (Partition Sort)	211	(15)
Array Implementation	216	(5)
Analysis of QuickSort	221	(2)
Expected-Case Analysis of QuickSort	223	(3)
Improving QuickSort	226	(2)
Modifications of QuickSort for Parallel Models	228	(1)
HyperQuickSort	228	(1)
BitonicSort (Revisited)	229	(6)
BitonicSort on a Mesh	230	(4)
Sorting Data with Respect to Other Orderings	234	(1)
Concurrent Read/Write	235	(3)
Implementation of a Concurrent Read	236	(1)
Implementation of Concurrent Write (overview)	237	(1)
Concurrent Read/Write on a Mesh	238	(1)
Summary	238	(1)
Chapter Notes	238	(1)
Exercises	239	(3)
Computational Geometry	242	(34)
Convex Hull	244	(16)
Graham's Scan	246	(4)
Jarvis' March	250	(1)
Divide-and-Conquer Solution	251	(9)
Smallest Enclosing Box	260	(2)
RAM	261	(1)
PRAM	261	(1)
Mesh	261	(1)
All-Nearest Neighbor Problem	262	(2)
Running Time	264	(1)
Architecture-Independent Algorithm Development	264	(1)
Line Intersection Problems	265	(5)
Overlapping Line Segments	266	(4)
Summary	270	(1)
Chapter Notes	270	(2)
Exercises	272	(4)
Image Processing	276	(24)
Preliminaries	278	(2)
Component Labeling	280	(5)
RAM	280	(1)
Mesh	281	(4)
Convex Hull	285	(3)
Running Time	287	(1)
Distance Problems	288	(8)
All-Nearest Neighbor between Labeled Sets	288	(1)
Running Time	289	(1)
Minimum Internal Distance within Connected Components	290	(3)
Hausdorff Metric for Digital Images	293	(3)
Summary	296	(1)
Chapter Notes	296	(1)
Exercises	297	(3)
Graph Algorithms	300	(50)
Terminology	303	(3)
Representations	306	(3)
Adjacency Lists	307	(1)
Adjacency Matrix	308	(1)
Unordered Edges	309	(1)
Fundamental Algorithms	309	(7)
Breadth-First Search	309	(4)
Depth-First Search	313	(2)
Discussion of Depth-First and Breadth-First Search	315	(1)
Fundamental PRAM Graph Techniques	316	(7)
List Ranking via Pointer Jumping	316	(2)
Euler Tour Technique	318	(1)
Tree Contraction	318	(5)
Computing the Transitive Closure of an Adjacency Matrix	323	(2)
Connected Component Labeling	325	(5)
RAM	325	(1)
PRAM	325	(5)
Mesh	330	(1)
Minimum-Cost Spanning Trees	330	(9)
RAM	330	(4)
PRAM	334	(2)
Mesh	336	(3)
Shortest-Path Problems	339	(4)
RAM	339	(3)
PRAM and Mesh	342	(1)
Summary	343	(1)
Chapter Notes	344	(1)
Exercises	345	(5)
Numerical Problems	350	(18)
Primality	352	(2)
Greatest Common Divisor	354	(1)
Lame's Theorem	355	(1)
Integral Powers	355	(2)
Evaluating a Polynomial	357	(2)
Approximation by Taylor Series	359	(3)
Trapezoidal Integration	362	(3)
Summary	365	(1)
Chapter Notes	365	(1)
Exercises	366	(2)
Bibliography	368	(5)
Index	373