Algorithms Sequential & Parallel

by Miller, Russ; Boxer, Laurence

• ISBN13: 9780130863737
• ISBN10: 0130863734
• Format: Hardcover
• Copyright: 1999-12-01
• Publisher: Prentice Hall

Summary

For a one-semester, junior/senior-level course in Algorithms.Attuned to the rapidly changing landscape in computer technology, this unique and very progressive text helps students understand the application and analysis of algorithmic paradigms to both the traditional sequential model of computing and to a variety of parallel models offering a unified, fully integrated coverage of both model types so that students can learn to recognize how solution strategies may be shared among computer paradigms and architectures.

Author Biography

Russ Miller is Director of the Center for Computational Research, Professor of Computer Science and Engineering, and Adjunct Professor of Electrical Engineering at the State University of New York at Buffalo (SUNY-Buffalo). He is also Senior Research Scientist at the Hauptman-Woodward Medical Research Institute. Laurence Boxer is a faculty member at Niagara University in the Department of Computer and Information Sciences, which he chairs. He is also an Adjunct Professor at SUNY-Buffalo. Dr. Boxer sits on the editorial board of the Journal of Computing and Information.

Table of Contents

Asymptotic Analysis	2	(28)
Notation and Terminology	4	(1)
Asymptotic Notation	5	(4)
Asymptotic Relationships	9	(1)
Asymptotic Analysis and Limits	9	(3)
Summations and Integrals	12	(5)
Rules for Analysis of Algorithms	17	(4)
Binsort	21	(2)
Limitations of Asymptotic Analysis	23	(1)
Common Terminology	24	(1)
Chapter Notes	25	(1)
Exercises	25	(5)
Induction and Recursion	30	(20)
Mathematical Induction	32	(1)
Induction Examples	33	(2)
Recursion	35	(2)
Binary Search	37	(4)
Merging and Mergesort	41	(6)
Chapter Notes	47	(1)
Exercises	47	(3)
The Master Method	50	(14)
Proof of the Master Theorem (Optional)	53	(9)
Chapter Notes	62	(1)
Exercises	62	(2)
Combinational Circuits	64	(12)
Chapter Notes	75	(1)
Exercises	75	(1)
Models of Computation	76	(46)
Examples: Simple Algorithms	83	(7)
Fundamental Terminology	90	(1)
Interconnection Networks	91	(1)
Processor Organizations	92	(21)
Additional Terminology	113	(5)
Chapter Notes	118	(1)
Exercises	118	(4)
Matrix Operations	122	(14)
Matrix Multiplication	124	(5)
Gaussian Elimination	129	(5)
Chapter Notes	134	(1)
Exercises	135	(1)
Parallel Prefix	136	(22)
Application: Maximum Sum Subsequence	145	(3)
Array Packing	148	(2)
Interval (Segment) Broadcasting	150	(2)
(Simple) Point Domination Query	152	(1)
Computing Overlapping Line Segments	153	(3)
Chapter Notes	156	(1)
Exercises	156	(2)
Pointer Jumping	158	(8)
List Ranking	160	(2)
Linked List Parallel Prefix	162	(1)
Chapter Notes	163	(1)
Exercises	163	(3)
Divide-and-Conquer	166	(36)
MergeSort (Revisited)	168	(3)
Selection	171	(5)
QuickSort (Partition Sort)	176	(14)
HyperQuickSort	190	(1)
Bitonic Sort (Revisited)	191	(5)
Concurrent Read/Write	196	(3)
Chapter Notes	199	(1)
Exercises	200	(2)
Computational Geometry	202	(30)
Convex Hull	203	(2)
Graham's Scan	205	(5)
Divide-and-Conquer Solution	210	(8)
Smallest Enclosing Box	218	(2)
All-Nearest Neighbor Problem	220	(1)
Architecture-Independent Algorithm Development	221	(1)
Line Intersection Problems	222	(1)
Overlapping Line Segments	223	(4)
Chapter Notes	227	(1)
Exercises	228	(4)
Image Processing	232	(20)
Preliminaries	233	(2)
Component Labeling	235	(4)
Convex Hull	239	(2)
Distance Problems	241	(5)
Hausdorff Metric for Digital Images	246	(2)
Chapter Notes	248	(1)
Exercises	249	(3)
Graph Algorithms	252	(44)
Terminology	255	(3)
Representations	258	(2)
Fundamental Algorithms	260	(15)
Connected Component Labeling	275	(4)
Minimum-Cost Spanning Trees	279	(7)
Shortest-Path Problems	286	(4)
Chapter Notes	290	(2)
Exercises	292	(4)
Numerical Problems	296	(16)
Primality	298	(1)
Greatest Common Divisor	299	(2)
Integral Powers	301	(1)
Evaluating a Polymomial	302	(2)
Approximation by Taylor Series	304	(3)
Trapezoidal Integration	307	(2)
Chapter Notes	309	(1)
Exercises	310	(2)
Bibliography	312	(5)
Index	317