Chapter 24
Probabilistic and Randomized Algorithms
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Lecture Notes
Overview
In chapter 24 we discuss probabilistic algorithms. We begin the chapter by defining the
concepts of expected worst-case, best-case and average complexities, Wexp(n), Bexp(n) and
Aexp(n), respectively. We then discuss the technique of randomizing deterministic
algorithms to cause the expected worst-case behavior of the algorithm for any fixed input
to approach the average behavior of the deterministic algorithm, and illustrate this
technique for the algorithms LinearSearch, ProbLinSrch, and Quicksort.
Following our discussion of randomizing deterministic algorithms, we introduce the two
important types of probabilistic algorithms known as Monte Carlo and Las Vegas
algorithms; a Monte Carlo algorithm has a certain probability of returning the correct
answer whatever input is considered, whereas, a Las Vegas algorithm never returns an
estimating the size of sets. We finish the chapter with a discussion of probabilistic
parallel and distributed algorithms, including the design of a parallel algorithm for the so-
called marriage problem and a randomized protocol for breaking deterministic deadlock.
Chapter Objectives
After completing the chapter the student will know:
• Las Vegas algorithm for searching a list
• The probabilistic algorithms for numerical integration and estimating the size of
sets
• Design and analysis of the parallel algorithm MCMarriage for the marriage
problem
• Design and analysis of the randomized protocol for breaking deterministic
deadlock
Instructor Notes
The string matching algorithm KR can be discussed here as an example of a Las Vegas
algorithm.
Solutions to Selected Exercises
Section 24.2 Randomizing Deterministic Algorithms
24.1 Applying the formula for the variance (see Formula E.3.13 of Appendix E) on Page
905, we have
V[τ[I]] = E[(τ(I))2] – (E[τ(I)]) 2 = E[(τ(I))2] – (τexp(I)) 2.
24.2 a) Complexities are the same as LinearSearch, i.e.,
B(n) = 1, A(n) = (n + 1)/2, W(n) = n.
b) τexp(I) = E[τ(I)]) = ½×1 + ¼×2 + ….+ (1/2n – 1)×(n – 1) + (1/2n – 1)×(n – 1)
c) V[τ[I]] = E[(τ(I))2] – (τexp(I)) 2. Now,
E[(τ(I))2] = ½×12 + ¼×22 + ….+ (1/2n – 1)×(n – 1) 2 + (1/2n – 1)×(n – 1) 2
Section 24.3 Monte Carlo and Las Vegas Algorithms
24.4 We prove the formula using mathematical induction.
Basis Step. Formula is true for n = 2, i.e., P(E1 ∩ E2) = P(E1) P(E1 | E2).
24.5 If the multi-graph G is represented by its adjacency matrix A = (aij) , where aij
equals the multiplicity of the multi-edge joining i and j and 0 if there is no multi-edge
joining i and j. Then the new adjacency matrix A’ = (a’ij) after contracting edge ij is
24.6 We approximate the recurrence in Formula (24.3.5) by the recurrence relation:
T(n) = 2T(n/
2
) + cn2, T(1) = d.
24.7 Correction: Formula (24.3.6) should have been an inequality rather than an
equality, i.e., it should be replaced with
)1(
−
kk
1
2
1)|( 1
1+−
−
−
=in
EEP i
jji
. We obtain:
)1(
)1(
)
1
2
1()(
1
1−
−
=
+−
−=
−
=
−
=nn
kk
in
EPq kn
i
kn
iik
.
the right-hand side we have
./21
2
)1(
)2)(1( n
n
n
nn
nn −=
−
=
−
−−
Assume true for k + 1, i.e.,
)1(
)
2
1(
1
+
=
−
−−
kk
kn
24.10 We describe a Las Vegas algorithm for solving the problem. Let R denote the set
of remainder indices, where R is initialized to {0, 1, …, n – 1}.
Step 1. Choose an index i at random element at random from R.
Step 2. Scan the list to compute the frequency of x = L[i].
If x occurs more than n/2 times then return x. Stop.
24.19 It would be linear if and only if m and ρ(n,m) are constants. Now ρ(n,m) denotes
the expected number of repetitions of DrawStraws(n,m) that are required for
termination. Let p denote the probability of success (i.e., only one processors
24.20 We prove the result using the strong form of mathematical induction.
Basis Step. ρ(2) = 2 < e.
Induction Step. Assume true for n < k, i.e., ρ(j) < e for all j < k, and consider the
24.21 In this question we assume the value of P at any particular point can be
computed in logarithmic time using a polynomial number of processors.
function TestMultivariatePolyEqual(P(x1,…,xm))
Input: P(x1,…,xm) (represented for example as a determinant and can be computed
at any point in logarithmic time using a polynomial number of processors)