### Types of algorithms:

**Monte Carlo **algorithms - may return an answer that is not
correct.

Example: primality testing

Subtypes: one-sided vs. two-sided errors

**Las Vegas** algorithms - may not return an answer at all, but
if they do the answer is guaranteed to be correct.

Example: factoring

**Sherwood** algorithms-
- always give the correct answer.
(Sometimes also called Las Vegas.)

Example: Quicksort

### Complexity classes:

- Randomized Polynomial time (
**RP**):
- A language is in RP if there is a polynomial-time (Monte Carlo) algorithm
that never accepts words that are not in the language, and
has probability at least 1/2 of accepting words in the language

- Zero-error Probabilistic Polynomial (
**ZPP**)
- Like RP, except the algorithm is Sherwood, so it always accepts
if the word is in the language

- Bounded-error Probabilistic Polynomial (
**BPP**)
- Like RP, except that the algorithm has probability at least 3/4 of
accepting if the word is in the language, and probability at most 1/4
of accepting if the word is not in the language.

### References:

Algorithmics, by Gilles Brassard and Paul Bratley,
Prentice Hall, 1988

Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan,
Cambridge University Press, 1995