Product Description
Assuming only an elementary background in discrete mathematics, this textbook is an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It includes random sampling, expectations, Markov's and Chevyshev's inequalities, Chernoff bounds, balls and bins models, the probabilistic method, Markov chains, MCMC, martingales, entropy, and other topics. The book is designed to accompany a one- or two-semester course for graduate students in computer science and applied mathematics.

CUSTOMER REVIEWS (Average Customer Rating: 3.0 based on 6 reviews)

doesn't deliver what's promised

I found this book after I decided I wasn't tough enough for Motwani & Raghavan's famous book on the same subject. Mitzenmacher & Upfal's sales pitch at their preface perfectly fit the bill: they say their book is a stepping stone to M & R 's classic text.

Four chapters into the book, however, it became clear that the preface was a lie.

Just take the chapter on Chernoff bounds for an example. It's terrific that they devoted a whole chapter to this result, as M & R's classic assumes you already know it by heart. But the execution is ridiculous: they deliver through 10 theorems/corollaries 10 variations of the Chernoff bound, and the proofs of all of them look like just a bunch of fortunate coincidences that happen one after the other. It is as though the authors have tried to obscure what is essentially a very intuitive result by a bunch of pompous formalisms.

Even in the very first chapters, when laying out the most elementary and intuitive concepts, M&U seem devoid of any feeling for their subject, as they just dump a bunch of dry formulas in front of the reader. Yes, E[E[X|Y]] = E[X], but what the heck does that really mean? How should the reader think of it?

In sum, Mitzenmacher and Upfal may be hotshot researchers, but they don't deliver what they promise in this book. I recommend the book by Bertsekas and Tsitsiklis instead of this one. Once you're through that book, I suggest you gather up your courage and go straight to Motwani & Raghavan. And let this book go out of print.

December 19, 2008

Great Book!

I have used this book over and over again. As a gentle introduction to Randomised Algorithms, the book succeeds very well. Anyone complaining about the book not explaining stuff are entitled to their opinion. This is the best introduction to Randomised Algorithms you will ever find.
November 09, 2007

Advanced probability topics without measure theory

This book is underestimated by two reviewers below. I totally do not agree with them. This book covers a wide range of topics in a very readable style. The contents in this book is complementary to the book of Motwani and Raghavan (but this book is much easier to digest).

It, without requiring any knowledge on measure theory, contains excellent introductions to many difficult topics in probability including

- concentration bounds (Chernoff, Azuma-Hoeffding, etc.)
- applications of stochastic processes such as queuing theory
- martingale (Wald's equation)
- coupling of Markov chains and their mixing times
- Shannon's source coding and noisy channel theorems
- Erdos' probabilistic method
- etc.

All of these topics are provided with excellent applications in computing.
The authors illustrate many clever tricks for proving theorems, and these tricks give insights to the readers as well.
August 18, 2007

Just unnecessary

This book, while written by two renowned computer scientists, is truly disappointing. In trying to discuss randomness and computation, this book just does a mediocre job on discussing randomized computation and also an equally poor job discussing relevant aspects of probability theory. Their approach is not novel and many of their examples can be found in other texts. If you really want to learn randomized computation, get Motwani et al's book on Randomized Algorithms. If you want to learn probability theory, get any advanced probability theory book like Spencer and Alon on the probabilistic method, one of Sheldon Ross's books, or even Grimmett and Stirzaker. Whatever you do don't get this weak hybrid of a book that will require you to get another book at some point to supplement your understanding.
May 17, 2007

Another poorly written text book

The authors must be smart guys. They obviously understand alot about this subject but make the mistake that you do too! As a result, the book is inadequate as a teaching tool.

They use only half to a third of the narrative they need to adequately explain a subject. They also like to leave out proof steps or not explain them. The problems at the end of chapters are poor as well, since the authors seem to have forgotten to teach the techniques needed to solve most them in the chapter they belong to.

I am sure to them it is intuitive.
March 19, 2006

SIMILAR PRODUCTS

Randomized Algorithms
by Rajeev Motwani, Prabhakar Raghavan

Approximation Algorithms
by Vijay V. Vazirani

Algorithmic Game Theory
by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani

Introduction to Algorithms
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

Combinatorial Optimization: Algorithms and Complexity
by Christos H. Papadimitriou, Kenneth Steiglitz