+612 9045 4394
Efficient Parallel Algorithms - Alan Gibbons

Efficient Parallel Algorithms

Paperback Published: 2nd April 1990
ISBN: 9780521388412
Number Of Pages: 268

Share This Book:


RRP $69.95
Ships in 10 to 15 business days

This largely self-contained text is an introduction to the field of efficient parallel algorithms and to the techniques for efficient parallelism, that presumes no special knowledge of parallel computers or particular mathematics. The book emphasizes designing algorithms within the timeless and abstracted context of a high-level programming language rather than within highly specific computer architectures. This is an approach that concentrates on the essence of algorithmic theory, determining and taking advantage of the inherently parallel nature of certain types of problems. The authors present regularly-used techniques and a range of algorithms including some of the more celebrated ones. Nonspecialists considering entering the field of parallel algorithms, as well as advanced undergraduate or postgraduate students of computer science and mathematics will find this book helpful.

Industry Reviews

"...a coherent introduction for all those who wish to enter this new field of research...a valuable contribution to the expository literature and will certainly become a favoured introduction to the field of parallel algorithms." Mathematical Reviews "Highly recommended." Choice "...a successful introduction to the area of parallel algorithms and to methods for parallelisation." N. I. Yanev, Mathematical Reviews

Prefacep. vii
Introductionp. 1
The model of parallel computationp. 2
Some general algorithmic techniquesp. 6
Reducing the number of processorsp. 11
Examples of fast parallel computations on vectors and listsp. 13
Bibliographyp. 19
Graph algorithmsp. 20
Parallel computations on treesp. 21
Paths, spanning trees, connected components and blocksp. 24
Eulerian circuits and maximal matchingsp. 40
Colouring of graphsp. 56
Bibliographic notesp. 85
Bibliographyp. 85
Expression evaluationp. 88
Constructing the expression treep. 88
A parallel pebble game with applications to expression evaluationp. 95
An optimal parallel algorithm for expression evaluationp. 103
The optimal parallel transformation of regular expressions to non-deterministic finite automatap. 112
Evaluation of generalised expressions: straight-line programsp. 122
More efficient algorithms for dynamic programmingp. 133
A more algebraic point of view: a method of simultaneous substitutionsp. 138
Bibliographic notesp. 139
Bibliographyp. 140
Parallel recognition and parsing of context-free languagesp. 142
Parallel recognition of general context-free languagesp. 143
Parallel recognition of unambiguous context-free languagesp. 154
Parallel parsing of general context-free languagesp. 158
Optimal parallel recognition and parsing of bracket languagesp. 165
Optimal parallel recognition of input-driven languagesp. 175
Bibliographic notesp. 178
Bibliographyp. 179
Fast parallel sortingp. 180
Batcher's sorting networksp. 181
Cole's optimal parallel merge sortp. 188
A theoretical optimal sorting network: Paterson's version of the algorithm of Ajtai, Komlos and Szemeredip. 198
Bibliographic notesp. 215
Bibliographyp. 215
Parallel string matchingp. 217
Analysis of the textp. 219
Preprocessing the patternp. 225
Complexity of the whole pattern-matching algorithmp. 233
Bibliographic notesp. 234
Bibliographyp. 234
P-completeness: hardly parallelisable problemsp. 235
A first P-complete problemp. 236
A selection of P-complete problemsp. 240
Bibliographic notesp. 254
Bibliographyp. 255
Index of definitions, techniques and algorithmsp. 257
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780521388412
ISBN-10: 0521388414
Audience: Tertiary; University or College
Format: Paperback
Language: English
Number Of Pages: 268
Published: 2nd April 1990
Country of Publication: GB
Dimensions (cm): 24.77 x 17.78  x 1.27
Weight (kg): 0.48