Analysis of Algorithms : An Active Learning Approach

9.2 PROBABILISTIC ALGORITHMS 245

function would be looking for a series of repeated true answers to increase the
chance that true is really correct. The algorithm for this would be
MultipleMonte( x )

if not Monte( x ) then
return false
end if
if not Monte( x ) then
return false
end if
return Monte( x )

The only way for this algorithm to return true is if we get three true
answers in a row. In this situation, if the original Monte Carlo algorithm was
correct overall 55% of the time, calling this function improves its accuracy to
90%. This is also possible for "numeric" algorithms that will be biased toward
some number for the correct answer.

Majority Element

A problem to which this technique can be applied is finding if there is a major-
ity element in an array. An array has a majority element if there is one element
that is stored in more than half of the array locations. If solved by the most
obvious means, this process would take O(N^2 ) comparisons because we would
have to potentially compare every element to every other element until we
found one that was in more than half of the array locations. Because there is a
known linear algorithm to solve this problem that is similar to the selection
algorithm discussed in Chapter 2, this version is merely another illustration of
the Monte Carlo technique.
A Monte Carlo algorithm for this process would be

Majority( list, N )
list the list of elements
N the number of elements

choice = uniform( 1, N )
count = 0
for i = 1 to N do
if list[i] = list[choice] then
count = count + 1
end if
end for
return (count > n/2)