Randomized Algorithms by Rajeev MotwaniRandomized Algorithms by Rajeev Motwani

Randomized Algorithms

byRajeev Motwani, Prabhakar Raghavan

Hardcover | August 25, 1995

Pricing and Purchase Info


Earn 465 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


For many applications, a randomized algorithm is either the simplest or the fastest algorithm available, and sometimes both. This book introduces the basic concepts in the design and analysis of randomized algorithms. The first part of the text presents basic tools such as probability theory and probabilistic analysis that are frequently used in algorithmic applications. Algorithmic examples are also given to illustrate the use of each tool in a concrete setting. In the second part of the book, each chapter focuses on an important area to which randomized algorithms can be applied, providing a comprehensive and representative selection of the algorithms that might be used in each of these areas. Although written primarily as a text for advanced undergraduates and graduate students, this book should also prove invaluable as a reference for professionals and researchers.
Title:Randomized AlgorithmsFormat:HardcoverDimensions:492 pages, 9.96 × 6.97 × 1.26 inPublished:August 25, 1995Publisher:Cambridge University Press

The following ISBNs are associated with this title:

ISBN - 10:0521474655

ISBN - 13:9780521474658


Table of Contents

Part I. Tools and Techniques: 1. Introduction; 2. Game-theoretic techniques; 3. Moments and deviations; 4. Tail inequalities; 5. The probabilistic method; 6. Markov chains and random walks; 7. Algebraic techniques; Part II. Applications: 8. Data structures; 9. Geometric algorithms and linear programming; 10. Graph algorithms; 11. Approximate counting; 12. Parallel and distributed algorithms; 13. Online algorithms; 14. Number theory and algebra; Appendix A: notational index; Appendix B: mathematical background; Appendix C: basic probability theory.

Editorial Reviews

"...carefully written, with exact definitions and complete proofs.... I believe that the book, with its vast coverage, will be an invaluable source for active researchers in the field." Y. Aumann, Theory of Computation