Skip to content

Efficient Parallel Algorithms

Spend $50 to get a free movie!

ISBN-10: 0521388414

ISBN-13: 9780521388412

Edition: N/A

Authors: Alan Gibbons, Wojciech Rytter

List price: $59.99
Blue ribbon 30 day, 100% satisfaction guarantee!
Out of stock
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


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.…    
Customers also bought

Book details

List price: $59.99
Publisher: Cambridge University Press
Publication date: 11/24/1989
Binding: Paperback
Pages: 268
Size: 7.52" wide x 9.25" long x 0.55" tall
Weight: 1.100
Language: English

Alan Gibbons is a full-time writer and a visiting speaker and lecturer at schools, colleges and literary events nationwide, including the major book festivals: Edinburgh, Northern Children's Book Festival, Swansea, Cheltenham, Sheffield and Salford. Alan has recently embarked on a high-profile, nationwide campaign to champion libraries and librarianship and to reevaluate government commitment to educational spending. He lives in Liverpool with his wife and four children. Visit his website at, read his blog at, follow him on Twitter at, Facebook at and Flickr at…    

Rytter, Institute of Informatics, Warsaw University.

The model of parallel computation
Some general algorithmic techniques
Reducing the number of processors
Examples of fast parallel computations on vectors and lists
Graph algorithms
Parallel computations on trees
Paths, spanning trees, connected components and blocks
Eulerian circuits and maximal matchings
Colouring of graphs
Bibliographic notes
Expression evaluation
Constructing the expression tree
A parallel pebble game with applications to expression evaluation
An optimal parallel algorithm for expression evaluation
The optimal parallel transformation of regular expressions to non-deterministic finite automata
Evaluation of generalised expressions: straight-line programs
More efficient algorithms for dynamic programming
A more algebraic point of view: a method of simultaneous substitutions
Bibliographic notes
Parallel recognition and parsing of context-free languages
Parallel recognition of general context-free languages
Parallel recognition of unambiguous context-free languages
Parallel parsing of general context-free languages
Optimal parallel recognition and parsing of bracket languages
Optimal parallel recognition of input-driven languages
Bibliographic notes
Fast parallel sorting
Batcher's sorting networks
Cole's optimal parallel merge sort
A theoretical optimal sorting network: Paterson's version of the algorithm of Ajtai, Komlos and Szemeredi
Bibliographic notes
Parallel string matching
Analysis of the text
Preprocessing the pattern
Complexity of the whole pattern-matching algorithm
Bibliographic notes
P-completeness: hardly parallelisable problems
A first P-complete problem
A selection of P-complete problems
Bibliographic notes
Index of definitions, techniques and algorithms