|
Abstract:
If a computer is allowed access to random coin-flips, can it solve
problems more efficiently than before? While randomization at first
seems
antithetical to the notion of a program (the epitome of regularity),
we will consider some problems where randomness *does* seem to help.
The question then becomes, can we quantify how much randomness gains
us,
and how much it costs? We'll look at probabilistic algorithms for
problems
including sorting lists, testing primality, and even just remembering
how to rotate a mattress.
(No previous background in computer science is presumed.)
|