Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Probability and computing: randomization and probabilistic techniques in algorithms and data analysis (2nd ed.)
Mitzenmacher M., Upfal E., Cambridge University Press, New York, NY, 2017. 484 pp. Type: Book (978-1-107154-88-9)
Date Reviewed: Jul 10 2018

Probability in computer science plays the same role as in physics: while there is a large corpus of theories and methodologies based on a purely deterministic underpinning, the introduction of probability opens the door to a vast field of new theories, methods, and related applications. However, scientific rigor and methodological care are mandatory for dealing with probabilistic techniques in algorithms and data analysis. This book perfectly fits the need for mathematical accuracy with a strong emphasis on real computer science problems.

Probability is actually ubiquitous in computer science. The book gives a demonstration of this pervasiveness with many examples in which specific probabilistic techniques are applied with success. Software verification, computational complexity, packet routing, hashing, graph theory, and data mining are just a few examples reported in which probability plays a pivotal role. In this sense, the book is unique in the panorama of scientific literature: there are several texts concerning probability in computer science, but many of them are mainly focused on data analysis; it is hard to find a book with a comprehensive foundation like this one.

Mitzenmacher and Upfal’s textbook is for advanced students. It is structured with a core part (the first seven chapters) and advanced material (the other chapters). The authors give some suggestions on the chapters to select according to the teaching needs. Although the first chapter starts with elementary probability theory, it is recommended that students have a basic background in discrete mathematics; a stronger background is required for the advanced part. Also, the authors make heavy use of Bachmann–Landau notation, which readers are assumed to know. (An appendix explaining this notation would have been a nice addition.) Each chapter includes examples and final exercises of varying difficulty. There is no supplemental material with exercise solutions; this is a pity because most exercises do require ingenuity and comparing solutions (or even looking at solutions for more difficult problems) could be a benefit in some cases.

The core part of the book starts with an introduction to the basic concepts of probability theory, random variables, some well-known bounds like Chernoff’s and Hoeffding’s, combinatorial arguments, and the probabilistic method for proving the existence of objects. The last chapter of this part is about Markov chains and random walks. This material is enough for a good introductory course on probability and computing.

The remaining chapters cover more advanced material, even though some of them are advisable for completing a graduate-level background. In particular, the chapters on the normal distribution, Poisson processes, entropy and information, and the Monte Carlo method are highly recommended. In some cases a chapter covers the basic aspects of a topic, making other textbooks better for a more in-depth study. This is the case for the chapter related to entropy, randomness, and information, which is just enough to have a glance at information theory. This is justifiable due to space constraints, but a reasoned bibliography at the end of each chapter would have been a nice way to point to other cornerstone textbooks in the field of probability and computing.

I am happy to have this book on my bookshelf. Its scientific rigor--comprehending the mathematical proof of almost all reported statements--and comprehensive collection of topics accompanied by many nontrivial examples make this book a precious gem in the literature of computer science.

More reviews about this item: Amazon, Goodreads

Reviewer:  Corrado Mencar Review #: CR146136 (1809-0483)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
 
Probabilistic Computation (F.1.2 ... )
 
 
Content Analysis And Indexing (H.3.1 )
 
 
Modes Of Computation (F.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Probabilistic Algorithms (Including Monte Carlo)": Date

Type: Article
Jul 1 1987
A probabilistic lower bound for checking disjointness of sets
Manber U. (ed) Information Processing Letters 19(1): 51-53, 1984. Type: Article
Feb 1 1985
On iterative methods in Markov modelling
Schatte P. Journal of Information Processing and Cybernetics 23(1): 49-51, 1987. Type: Article
Oct 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy