Customer Reviews

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

5 star:		(6)
4 star:		(0)
3 star:		(0)
2 star:		(1)
1 star:		(1)

 

 

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.

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.

Far from being "unnecessary", this book does a wonderful job at making randomized algorithms accessible and fun. It is great for self-learners because it first motivates a concept, then states relevant theorems, then provides full proofs of these theorems, and then provides an example where the theorem is used. Rather than leaving the proofs of theorems as an "exercise for the reader", it fully proves the theorems stated in the text. Each chapter also includes a section with an interesting application of how the material in the chapter can be utilized. Although not as advanced as the Motwani Randomized Algorithms book, it provides an excellent introduction and is much more accessible.

I found this book to be one of the better mathematics texts that I've ever read.
The authors do an excellent job in combining mathematical rigor with
good intuitive explanations of why a given theorem ought to be true.

I felt very impressed with how the authors have included just about every important
area of probability that has relevance to computing, and helped make them all accessible.

A good example of this is the chapter on Information Theory. Rather than prove the more difficult
and time consuming general cases of Shannon's Coding and Channel-Coding Theorems, the authors
presented special cases of these results, without losing much of the flavor of how the more general
proofs proceed. For example, in the case of the Channel-Coding Theorem, the authors assume that the
channel independently changes a single bit of the codeword with probability p.

Now despite all the stated positives, I would not recommend this book to anyone with no prior knowledge of probability.
For such a reader, a good prerequisite read is "Probability Models" by Sheldon Ross, which provides an excellent
introduction to applied probability.

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.

This book is really interesting and helpful to beginners and also has advanced topics. Besides that has good explanations.

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.

It's pretty easy to get computers to do things where the answer is yes or no, or 4 or 6, given that the inputs to the problem are known. It's much harder to get an answer to a problem where the answer is that their is a 62% chance that the answer is yes. Unfortunately, in real life it's this second class of problems that predominates.

This book is oriented to solving these kinds of real world problems. The exercises in the book are chosen from real world examples -- what we used to call story problems. This tends to give the student a better understanding of not only the mathematics and programming involved but experience in looking at problems with a view to understanding this approach to solving the problem.

This book is suitable for a one or two semester introductory class at the upper undergraduate or beginning graduate level.

Just a word about the illustration on the front of the book. At the end of the book Alice in Wonderland the queen is about to order Alice beheaded. Alice says, "You're nothing but a pack of cards." At this, the whole pack rose up into the air and came flying down around her. This illustration is by John Tenniel from the original book of 1899. A deck of flying playing cards is a good way to illustrate random and probability.