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.


Algorithmics, by Gilles Brassard and Paul Bratley, Prentice Hall, 1988
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995