Randomized algorithms. (English) Zbl 0849.68039

Motwani, Rajeev; Raghavan, Prabhakar

Cambridge: Cambridge Univ. Press. xiv, 476 p. (1995).

This is a 476 page collection of the random aspects of nearly all sorts of algorithms in diverse fields. The emphasis is on explaining the algorithm rigorously, rather than proving it with probability and statistical reasoning. So the mathematical part is reduced to the 13 pages of Appendices B and C and, of course, to the statement of the definitions, lemmas, and theorems. The book covers, among other areas, Markov chains and random walks, algebraic techniques such as perfect pattern matching and fingerprinting, hashing in connection with data structures, geometric questions from Voronoi to convex hulls and linear programming, online algorithms, and parallel algorithms such as for independent sets, Byzantine generals etc., and not least number theory and algebra algorithms for RSA, quadratic residues and primality testing. While designated for undergraduate and graduate courses, for which further hints are given, I found the book also valuable for quick reference after had no contact to this or that problem for a couple of years.

Reviewer: G.Schmidt (Neubiberg)

MSC:

68W10	Parallel algorithms in computer science
68R05	Combinatorics in computer science
60B99	Probability theory on algebraic and topological structures
52C99	Discrete geometry

Keywords:

Markov chains; random walks; perfect pattern matching; fingerprinting; hashing