Introduction

Goal of Deterministic Algorithm: To prove that the algorithm solves the problem correctly (always) and quickly (typically, the number of steps should be polynomial in the size of the input) (see fig. .

Figure: (a) Deterministic algorithm, (b) Random algorithm

Goal of Randomized Algorithm: In addition to input, algorithm takes a source of random numbers and makes random choices during execution. The behavior can vary even on a fixed input. The design of the algorithm and the analysis show that this behavior is likely to be good, on every input. The likely hood is over the random numbers only. While analyzing the algorithm, we should not be confused with the probabilistic analysis of the algorithms, where input is assumed to be from a probability distribution, which show that the algorithm works for most inputs.

There are two approaches:

• Monte Carlo: A Monte Carlo algorithm runs for a fixed number of steps, and produces an answer that is correct with probability $\geq$ 1 / 3.

• Las Vegas: A Las Vegas algorithm always produces the correct answer; its running time is a random variable whose expectation is bounded (say by a polynomial).

For both, the probabilities/expectations are only over the random choices made by the algorithm, i.e., independent of the input. Thus independent repetitions of Monte Carlo algorithms drive down the failure probability exponentially.

The advantages of both are: Simplicity, and Performance. For many problems, a randomized algorithm is the simplest, the fastest, or both

Scope: Following are some applications of randomized (also called probabilistic) algorithms.

• Number-theoretic algorithms: Primality testing (Monte Carlo).

• Data structures: Sorting, order statistics, searching, computational geometry.

• Algebraic identities: Polynomial and matrix identity verification. Interactive proof systems.

• Mathematical programming: Faster algorithms for linear programming. Rounding linear program solutions to integer program solutions.

• Graph algorithms: Minimum spanning trees, shortest paths, minimum cuts.

• Counting and enumeration: Matrix permanent. Counting combinatorial structures.

• Parallel and distributed computing: Deadlock avoidance, distributed consensus.

• Probabilistic existence proofs: Show that a combinatorial object arises with non-zero probability among objects drawn from a suitable probability space.

• Derandomization: First devise a randomized algorithm, then argue that it can be “derandomized” to yield a deterministic algorithm.