Randomized Algorithms

By Prabhakar Raghavan and Rajeev Motwani

Book Overview

For many applications a randomized algorithm is either the simplest algorithm available, or the fastest, or both. This tutorial presents the basic concepts in the design and analysis of randomized algorithms. The first part of the book presents tools from probability theory and probabilistic analysis that are recurrent in algorithmic applications. Algorithmic examples are given to illustrate the use of each tool in a concrete setting. In the second part of the book, each of the seven chapters focuses on one important area of application of randomized algorithms: data structures; geometric algorithms; graph algorithms; number theory; enumeration; parallel algorithms; and on-line algorithms. A comprehensive and representative selection of the algorithms in these areas is also given. This book should prove invaluable as a reference for researchers and professional programmers, as well as for students.

• Format: Hardcover
• Language: English
• ISBN: 0521474655
• ISBN13: 9780521474658
• Release Date: August 1995
• Publisher: Cambridge University Press
• Length: 496 Pages
• Weight: 2.35 lbs.
• Dimensions: 1.2" x 7.0" x 10.4"

Customer Reviews

Great exploration of randomized algorithms

A mathematician at heart in the world of software engineering, this is one of those few books that I take out from time to time and leave beside my bed. With it's wide scope it is sometimes terse and needs careful reading. Yet the world of randomized algorithms comes through with strength on a good formal basis. It is an entertaining and yet highly educational book.

A subtle introduction to probablistic algoritms

This book is a jewel. It demonstrates how clever and beautifully simple probabilistic ideas can lead to the design of very efficient algorithms. I like its very verbal intuitive style, with proof strategies being always transparently explained. For computer scientists, this is *the* reference work in randomized algorithms, by now a major paradigm of algorithms design. For classical probabilists, this could serve as an eye-opener...

An enciclopedia for randomized algorithms.

The book has an exoustive amount of algorithms. Not everything is proved. Sometimes the proof contains to few steps to be understood. There are many algorithms explained well. After reading this book it is easy to create your own randomized algorithms.

extremely informative but obscure

I've taken two CS classes that use this book and I always felt like this book was very informative. The algorithms and concepts that Motwani brings forth are extremely insightful and interesting. However, the presentation of the proofs has a lot of room for improvement. Notation is carried over from previous chapters and is sometimes unexplained, which makes it very difficult for someone who does not have a lot of familiarity...

A very good high-level survey of Randomized Algorithms

I have just completed a graduate course using this book. At times the book is a bit terse (not necessarily a negative!) and overall I can highly recommend it.Wolf Bein, UNLV