View Full Document


Unformatted text preview:

Review3 of Probability and Computing Randomized Algorithms and Probabilitic Analysis Author of Book Michael Mitzenmacher and Eli Upfal Publisher Cambridge University Press 2005 Cost 55 00 hardcover Reviewer Jonathan Katz Dept of CS Univ of MD Randomized algorithms and basic techniques of probabilistic analysis are essential components of the theoretical computer scientist s tool kit indeed their applications have become so widespread that they should be and increasingly are part of every computer scientist s tool kit Randomization has of course proved useful in designing traditional algorithms interestingly here we don t actually know whether randomization truly helps at least in the sense that we don t have a proof that P 6 BPP but in practice randomized algorithms are often more efficient and or simpler than their deterministic counterparts Randomization is also essential in a provable sense for cryptography and for certain results in distributed computing Finally a good understanding of random processes is also needed any time one is trying to analyze a system that evolves probabilistically or trying to bound the performance of an algorithm even a deterministic one when the inputs are not chosen deterministically Because of the widespread interest in the subject a textbook covering randomization in computer science must be many things to many different people it should serve as an introduction to the area for an undergraduate or graduate student interested in randomized algorithms a survey of applications and techniques for the general computer scientist and also a solid reference for the advanced researcher I am pleased to say that Probability and Computing succeeds on all these fronts I found the book a joy to read the writing is clear and concise the proofs are well structured and the writing style invites the reader to explore the material The book is also organized very well and the selection of topics is excellent I have already used the book multiple times

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...

Join to view Probability and Computing and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Probability and Computing and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?