Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis

by Michael Mitzenmacher, Eli Upfal

Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics including normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. Material relevant to machine learning and big data analysis enables students to learn modern techniques and applications. Among the many new exercises and examples are programming-related exercises that provide students with excellent training in solving relevant problems. This book provides an indispensable teaching tool to accompany a one- or two-semester course for advanced undergraduate students in computer science and applied mathematics.

Genres: Computer Science, Mathematics, Textbooks, Programming, Algorithms, Nonfiction, Technology

467 pages, Hardcover

First published January 31, 2005

Reviews

[Fatima · Rating 5 out of 5]

Great textbook on this subject and the perhaps the only book on this subject?

Very clear definitions. Yet so hard. Expect to spend lots of time on each chapter. I do wish there some solution to at least some of exercise at the end of each chapter.

Read this as part of CS265/CME309: Randomized Algorithms and Probabilistic Analysis at Stanford (Fall 2019).

[Emil Petersen · Rating 4 out of 5]

This is Randomized Algorithms, but better. It seems like an adaption, with many of the first chapters being the same in terms of content and examples. But of course newer, with updates with respect to applications. I read the first 5 chapters in detail as part of coursework, but have read the remaining in a leisurely fashion. Something that I appreciated was the relevance to other fields such as statistics or machine learning, as many of the examples are otherwise coins, balls and bins. It manages to capture and combine a lot of terrain, from the basics of the normal distribution and continuous random variables, to learning complexity, sampling, martingales and probabilistic proof techniques. I'm really happy about how it interrelates two of my favorite topics of algorithms and machine learning. There is also a small primer on entropy, but I would not start on that topic via this book. Actually, I think getting introductions elsewhere is better for most of the topics here. Then, subsequently, the corresponding chapters can be read here for applications and a formal treatment.

[Franta · Rating 5 out of 5]

Probability applied to computing is incredibly useful and powerful.

To study this book you need a good understanding of discrete probability and combinatorics, but knowledge of measure theory is not required.

The book contains introduction to many difficult topics in probability with applications in computing. including:

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

This is a beautiful theory applied to solve hard and important problems in computing.

[John · Rating 4 out of 5]

I was looking for a bit more advanced book to be honest, but this is a well-written undergrad level book for many topics in probability and randomized algorithms. Honestly, better than the books I read at that level.

And there were a few things I hadn't thought about in a while.

Overall, solid introduction to some core concepts in probability and bounding, but not like Motwani's and Raghavan's Randomized Algorithms, which is older now. I was more looking for a modern version of that.

[Dmitry Zinenko · Rating 5 out of 5]

A good introduction to the main uses of probability in computer science, mostly algorithm design and analysis. Based on some beautiful examples; easy to moderate difficulty reading.

[Zibo]

https://www.zhihu.com/question/196288...

[Nick Black · Rating 2 out of 5]

Amazon 2009-01-10. This will be our official book for CS7530, "Randomized Algorithms." I'm in there with a bunch of ACO phd's, a few CSMS kids who look lost, scared, and desperately loathing of the Theory requirement, and a precocious undergraduate who'll likely be among the competition for primacy (demographic notes: one female out of ~28 students. A higher proportion of caucasians than one expects in a phd-level CS class -- I'm one of 5 or maybe even 6 white kids, although I doubt that'll hold through drop day). This book got pretty well crapped on by Amazon reviewers, so I'm picking up the standard-bearer as well.

[Vhalros · Rating 2 out of 5]

This book is an okay introduction to probabilistic algorithms. However, the problems sets are nigh-impossible with out a strong background in probability (certainly nothing in the book helps in doing the problem sets). Its very poor at arming the student with technques to attack any of these problems.