While everything we’ve looked at so far can be called a “randomized algorithm,” in computer science the phrase refers to two broad categories of algorithms—the subject of this chapter.

A randomized algorithm employs randomness as part of its operation. The algorithm succeeds in accomplishing its goal, either by producing the correct answer quickly, but sometimes not, or by running rapidly with some probability of returning a false or nonoptimal result.

We’ll begin by defining the two broad categories of randomized algorithms with examples. Next, we’ll learn about estimating the number of animals in a population. Following ...

Get The Art of Randomness now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.