Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

The first nuts and bolts appeared in the middle 1400’s. The bolts were just screws with straightsides and a blunt end. The nuts were hand-made, and very crude. When a match was foundbetween a nut and a bolt, they were kept together until they were finally assembled.
In the Industrial Revolution, it soon became obvious that threaded fasteners made it easier
to assemble products, and they also meant more reliable products. But the next big step camein 1801, with Eli Whitney, the inventor of the cotton gin. The lathe had been recently improved.
Batches of bolts could now be cut on different lathes, and they would all fit the same nut.
Whitney set up a demonstration for President Adams, and Vice-President Jefferson. He had
piles of musket parts on a table. There were 10 similar parts in each pile. He went from pile topile, picking up a part at random. Using these completely random parts, he quickly put together aworking musket.
— Karl S. Kruszelnicki (“Dr. Karl”), Karl Trek, December 1997
Dr [John von] Neumann in his Theory of Games and Economic Behavior introduces the cut-up
method of random action into game and military strategy: Assume that the worst has happened
and act accordingly. If your strategy is at some point determined. . . by random factor your opponent
will gain no advantage from knowing your strategy since he cannot predict the move.
— William S. Burroughs, “The Cut-Up Method of Brion Gysin”
in The Third Mind by William S. Burroughs and Brion Gysin (1978)

2

Randomized Algorithms

2.1

Nuts and Bolts

The following interesting problem was first proposed by Gregory Rawlins around 1992. Suppose
we are given n nuts and n bolts of different sizes. Each nut matches exactly one bolt and viceversa. The nuts and bolts are all almost exactly the same size, and we’re playing with them inthe dark, so we can’t tell if one bolt is bigger than the other, or if one nut is bigger than the other.
If we try to match a nut witch a bolt, however, the nut will be either too big, too small, or justright for the bolt. How quickly can we match each but to the corresponding bolt?
Before we attack this problem, let’s think about something simpler. Suppose we want to findthe nut that matches a particular bolt. The obvious algorithm — test every nut until we find amatch — requires exactly n − 1 tests in the worst case. We might have to check every but except
one; if we get to the last nut without finding a match, we know that the last nut is the one we’relooking for.
Intuitively, in the “average” case, this algorithm will look at approximately n/2 nuts. But
what exactly does “average case” mean?

2.2

Deterministic vs. Randomized Algorithms

Normally, when we talk about the running time of an algorithm, we mean its worst-case running
time. This is the maximum, over all problems of a certain size, of the running time of thatalgorithm on that input:
Tworst-case (n) = max T (X ).
|X |=nThe average-case running time is best defined by the expected value, over all inputs X of a certain
size, of the algorithm’s running time for input X :XTaverage-case (n) = E [T (X )] =T (X ) · Pr[X ].
|X |=n|X |=n© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

The problem with this definition is that we rarely, if ever, know the probability of getting any
particular input X . We could compute average-case running times by assuming a particularprobability distribution—for example, every possible input is equally likely—but this assumption
doesn’t describe reality very well. Most real-life data, if it can be considered random at all, israndom in some interesting way that can’t be predicted in advance.
Instead of considering the rather questionable notion of average case running time, wewill make a distinction between two kinds of algorithms: deterministic and randomized. A
deterministic algorithm is one that always behaves the same way given the same input; the input
completely determines the sequence of computations performed by the algorithm. Randomized
algorithms, on the other hand, base their behavior not only on the input but also on several
random choices. The same randomized algorithm, given the same input multiple times, may
perform different computations in each invocation.
This definition implies that the running time of a randomized algorithm on a given input is
no longer fixed, but is itself a random variable. When we analyze randomized algorithms, we are
typically interested in the worst-case expected running time. That is, we consider the expectedrunning time for each input, and then choose the maximum over all inputs of a certain size:
Tworst-case expected (n) = max E[T (X )].
|X |=nIt’s important to note here that we are making no assumptions about the probability distributionof possible inputs. All the randomness is inside the algorithm, where we can control it!

2.3

Back to Nuts and Bolts

Let’s go back to the problem of finding the nut that matches a given bolt. Suppose we use
the same algorithm as before, but at each step we choose a nut uniformly at random from theuntested nuts. So if there are k nuts left to test, each one will be chosen with probability 1/k.
Now what’s the expected number of comparisons we have to perform? Intuitively, it should be
about n/2, but let’s formalize our intuition.
Let T (n) denote the number of comparisons our algorithm uses to find a match for a single
bolt out of n nuts.1 We still have some simple base cases T (1) = 0 and T (2) = 1, but when n > 2,
T (n) is a random variable. T (n) is always between 1 and n − 1; it’s actual value depends on ouralgorithm’s random choices. We are interested in the expected value or expectation of T (n), which
is defined as follows:n−1X
E[T (n)] =k · Pr[T (n) = k]
k=1

If the target nut is the kth nut tested, our algorithm performs min{k, n − 1} comparisons. In
particular, if the target nut is the last nut chosen, we don’t actually test it. Because we choose thenext nut to test uniformly at random, the target nut is equally likely—with probability exactly
1/n—to be the first, second, third, or kth bolt tested, for any k. Thus:¨
1/n if k < n − 1,
Pr[T (n) = k] =2/n if k = n − 1.
1Note that for this algorithm, the input is completely specified by the number n. Since we’re choosing the nuts totest at random, even the order in which the nuts and bolts are presented doesn’t matter. That’s why I’m using thesimpler notation T (n) instead of T (X ).

2

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

Plugging this into the definition of expectation gives us our answer.
E[T (n)] =
=
=

n−2
X
k

n
k=1
n
X
k

n
k=1

+

2(n − 1)
n

−

1
n

n+1 1
−
2
n

We can get exactly the same answer by thinking of this algorithm recursively. We always
have to perform at least one test. With probability 1/n, we successfully find the matching nut
and halt. With the remaining probability 1 − 1/n, we recursively solve the same problem butwith one fewer nut. We get the following recurrence for the expected number of tests:
T (1) = 0,

E[T (n)] = 1 +n−1
E[T (n − 1)]nTo get the solution, we define a new function t(n) = n E[T (n)] and rewrite:t(1) = 0,t(n) = n + t(n − 1)This recurrence translates into a simple summation, which we can easily solve.
t(n) =

n
X

k=

k=2

=⇒ E[T (n)] =2.4n(n + 1)
−1
2

t(n)
n+1 1
=
−
n
2
n

Finding All Matches

Not let’s go back to the problem introduced at the beginning of the lecture: finding the matching
nut for every bolt. The simplest algorithm simply compares every nut with every bolt, for a totalof n2 comparisons. The next thing we might try is repeatedly finding an arbitrary matched pair,using our very first nuts and bolts algorithm. This requiresnXn2 − n(i − 1) =2
i=1

comparisons in the worst case. So we save roughly a factor of two over the really stupid algorithm.
Not very exciting.
Here’s a more interesting strategy, which Rawlins proposed when he introduced the problem.
Choose a pivot bolt, and test it against every nut. Then test the matching pivot nut against every
other bolt. After these 2n − 1 tests, we have one matched pair, and the remaining nuts and bolts
are partitioned into two subsets: those smaller than the pivot pair and those larger than the pivot
pair. Finally, recursively match up the two subsets. The worst-case number of tests made by thisalgorithm is given by the recurrenceT (n) = 2n − 1 + max T (k − 1) + T (n − k)1≤k≤n

= 2n − 1 + T (n − 1)3

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

Along with the trivial base case T (0) = 0, this recurrence solves toT (n) =nX
(2n − 1) = n2 .
i=1

In the worst case, this algorithm tests every nut-bolt pair! We could have been a little moreclever—for example, if the pivot bolt is the smallest bolt, we only need n − 1 tests to partition
everything, not 2n − 1—but cleverness doesn’t actually help that much. We still end up with
about n2 /2 tests in the worst case.
However, since this recursive algorithm looks almost exactly like quicksort, and everybody‘knows’ that the ‘average-case’ running time of quicksort is Θ(n log n), it seems reasonable toguess that the average number of nut-bolt comparisons is also Θ(n log n). As we shall see shortly,
if the pivot bolt is always chosen uniformly at random, this intuition is exactly right.

2.5

Reductions to and from Sorting

Rawlins’ algorithm for matching the nuts and bolts strongly resembles quicksort. The algorithm
not only matches up the nuts and bolts, but also sorts them by size.
In fact, the problems of sorting and matching nuts and bolts are equivalent, in the following
sense. If the bolts were sorted, we could match the nuts and bolts in O(n log n) time by performing
a binary search with each nut. Thus, if we had an algorithm to sort the bolts in O(n log n) time,
we would immediately have an algorithm to match the nuts and bolts, starting from scratch, inO(n log n) time. This process of assuming a solution to one problem and using it to solve anotheris called reduction—we can reduce the matching problem to the sorting problem in O(n log n)time.
There is a reduction in the other direction, too. If the nuts and bolts were matched, we could
sort them in O(n log n) time using, for example, merge sort. Thus, if we have an O(n log n) timealgorithm for either sorting or matching nuts and bolts, we automatically have an O(n log n) timealgorithm for the other problem.
Unfortunately, since we aren’t allowed to directly compare two bolts or two nuts, we can’t
use heapsort or mergesort to sort the nuts and bolts in O(n log n) worst case time. In fact, theproblem of sorting nuts and bolts deterministically in O(n log n) time was only “solved” in 19952,
but both the algorithms and their analysis are incredibly technical and the constant hidden in theO(·) notation is quite large.

2.6

Recursive Analysis

Intuitively, we can argue that our quicksort-like algorithm will usually choose a bolt of approximately median size, and so the average numbers of tests should be O(n log n). We can now
finally formalize this intuition. To simplify the notation slightly, I’ll write T (n) in place of E[T (n)]everywhere.
Our randomized matching/sorting algorithm chooses its pivot bolt uniformly at random fromthe set of unmatched bolts. Since the pivot bolt is equally likely to be the smallest, second
smallest, or kth smallest for any k, the expected number of tests performed by our algorithm is
2János Komlós, Yuan Ma, and Endre Szemerédi, Sorting nuts and bolts in O(n log n) time, SIAM J. Discrete Math11(3):347–372, 1998. See also Phillip G. Bradford, Matching nuts and bolts optimally, Technical Report MPI-I-95-1-025,
Max-Planck-Institut für Informatik, September 1995. Bradford’s algorithm is slightly simpler.

4

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

given by the following recurrence:
T (n) = 2n − 1 + Ek T (k − 1) + T (n − k)
= 2n − 1 +n1XT (k − 1) + T (n − k)n k=1

The base case is T (0) = 0. (We can save a few tests by setting T (1) = 0 instead of 1, but theanalysis will be easier if we’re a little stupid.)
Yuck. At this point, we could simply guess the solution, based on the incessant rumors thatquicksort runs in O(n log n) time in the average case, and prove our guess correct by induction.
(See Section 2.8 below for details.)
However, if we’re only interested in asymptotic bounds, we can afford to be a little conservative.
What we’d really like is for the pivot bolt to be the median bolt, so that half the bolts are bigger
and half the bolts are smaller. This isn’t very likely, but there is a good chance that the pivot bolt
is close to the median bolt. Let’s say that a pivot bolt is good if it’s in the middle half of the final
sorted set of bolts, that is, bigger than at least n/4 bolts and smaller than at least n/4 bolts. If
the pivot bolt is good, then the worst split we can have is into one set of 3n/4 pairs and one setof n/4 pairs. If the pivot bolt is bad, then our algorithm is still better than starting over fromscratch. Finally, a randomly chosen pivot bolt is good with probability 1/2.
These simple observations give us the following simple recursive upper bound for the expectedrunning time of our algorithm:   n  1
13n
T (n) ≤ 2n − 1 +T+T+ · T (n)2442
A little algebra simplifies this even further:
T (n) ≤ 4n − 2 + T 3n 
4

+T

n
4

We can solve this recurrence using the recursion tree method, giving us the unsurprising
upper bound T (n) = O(n log n). A similar argument gives us the matching lower boundT (n) = Ω(n log n).
Unfortunately, while this argument may be convincing, it is not a formal proof, because it relieson the unproven assumption that T (n) is a convex function, which means that T (n+1)+T (n−1) ≥2T (n) for all n. T (n) is actually convex, but we never proved it. Convexity follows form theclosed-form solution of the recurrence, but using that fact would be circular logic. Sadly, formallyproving convexity seems to be almost as hard as solving the recurrence. If we want a proof of the
expected cost of our algorithm, we need another way to proceed.

2.7

Iterative Analysis

By making a simple change to our algorithm, which has no effect on the number of tests, we cananalyze it much more directly and exactly, without solving a recurrence or relying on hand-wavy
intuition.
The recursive subproblems solved by quicksort can be laid out in a binary tree, where eachnode corresponds to a subset of the nuts and bolts. In the usual recursive formulation, thealgorithm partitions the nuts and bolts at the root, then the left child of the root, then the leftmost
grandchild, and so forth, recursively sorting everything on the left before starting on the right
subproblem.
5

Algorithms

ÆÆÆLecture 2: Randomized Algorithms [Sp’17]

FigureBut we don’t have to solve the subproblems in this order. In fact, we can visit the nodes in
the recursion tree in any order we like, as long as the root is visited first, and any other node isvisited after its parent. Thus, we can recast quicksort in the following iterative form. Choose apivot bolt, find its match, and partition the remaining nuts and bolts into two subsets. Then picka second pivot bolt and partition whichever of the two subsets contains it. At this point, we have
two matched pairs and three subsets of nuts and bolts. Continue choosing new pivot bolts andpartitioning subsets, each time finding one match and increasing the number of subsets by one,
until every bolt has been chosen as the pivot. At the end, every bolt has been matched, and thenuts and bolts are sorted.
Suppose we always choose the next pivot bolt uniformly at random from the bolts that haven’t
been pivots yet. Then no matter which subset contains this bolt, the pivot bolt is equally likely
to be any bolt in that subset. It follows (by induction) that our randomized iterative algorithm
performs exactly the same set of tests as our randomized recursive algorithm, but possibly in adifferent order.
Now let Bi denote the ith smallest bolt, and N j denote the jth smallest nut. For each i and j,
define an indicator variable X i j that equals 1 if our algorithm compares Bi with N j and zerootherwise. Then the total number of nut/bolt comparisons is exactly
T (n) =

n X
n
X

Xi j.

i=1 j=1

We are interested in the expected value of this double summation; linearity of expectation allows
us to write this expected value as follows:


n X
n
n X
n
X
X


E[T (n)] = E
Xi j =
E[X i j ].
i=1 j=1i=1 j=1

By definition of expectation,
E[X i j ] = 0 · Pr[X i j = 0] + 1 · Pr[X i j = 1] = Pr[X i j = 1].
Thus, to analyze our algorithm, we only need to calculate Pr[X i j = 1] for all i and j.
First let’s assume that i < j. The only comparisons our algorithm performs are between some
pivot bolt (or its partner) and a nut (or bolt) in the same subset. The only event that can preventa comparison between Bi and N j is choosing some intermediate pivot bolt Bk , with i < k < j,before Bi or B j . In other words:
Our algorithm compares Bi and N j if and only if the first pivot
chosen from the set {Bi , Bi+1 , . . . , B j } is either Bi or B j .
Since the set {Bi , Bi+1 , . . . , B j } contains j − i + 1 bolts, each of which is equally likely to be chosen
first, we immediately haveE[X i j ] =

2
j−i+1
6

for all i < j.

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

Symmetric arguments give us E[X i j ] = i− 2j+1 for all i > j. Since our algorithm is a little stupid,
every bolt is compared with its partner, so X ii = 1 for all i. (In fact, if a pivot bolt is the only bolt
in its subset, we don’t need to compare it against its partner, but this improvement complicatesthe analysis.)
Putting everything together, we get the following summation.
E[T (n)] =

n X
n
X

E[X i j ]i=1 j=1=n
X

E[X ii ] + 2

i=1

n X
n
X

E[X i j ]i=1 j=i+1

= n+4

n X
n
X

1
j−i+1
i=1 j=i+1

This is quite a bit simpler than our earlier recurrence. Just a few more lines of algebra gives us
an exact, closed-form expression for the expected number of comparisons.
E[T (n)] = n + 4= n+4

n n−i+1XX 1
i=1 k=2n n−k+1XX
k=2 i=1nX[substitute k = j − i + 1]k1
k[reorder summations]

n−k+1
k
k=2


n
n
X
1 X
= n + 4 (n + 1)
−
1
k k=2
k=2

= n+4

= n + 4((n + 1)(H n − 1) − (n − 1))= 4nH n − 7n + 4H n
Sure enough, it’s Θ(n log n).
?

2.8

Masochistic Analysis

If we’re feeling particularly masochistic, we can actually solve the recurrence directly, all the way
to an exact closed-form solution. I’m including this only to show you it can be done; this won’t
be on the test.
First we simplify the recurrence slightly by combining symmetric terms.
n
n−1

1X
2X
T (n) =T (k − 1) + T (n − k) + 2n − 1 =T (k) + 2n − 1
n k=1
n k=0

We then convert this ‘full history’ recurrence into a ‘limited history’ recurrence by shifting andsubtracting away common terms. (I call this “Magic step #1”.) To make this step slightly easier,we first multiply both sides of the recurrence by n to get rid of the fractions.
nT (n) = 2

n−1
X
k=0

7

T (k) + 2n2 − nAlgorithms

Lecture 2: Randomized Algorithms [Sp’17](n − 1)T (n − 1) = 2

n−2
XT (k) + 2(n − 1)2 − (n − 1)

k=0

=2

n−2
X

T (k) + 2n2 − 5n + 3

k=0

nT (n) − (n − 1)T (n − 1) = 2T (n − 1) + 4n − 3
n+13
T (n) =T (n − 1) + 4 −nn
To solve this limited-history recurrence, we define a new function t(n) = T (n)/(n + 1). (I callthis “Magic step #2”.) This gives us an even simpler recurrence for t(n) in terms of t(n − 1):
T (n)
n+1 

1
T (n − 1)3=(n + 1)
+4−
n+1
n
n
4
3
= t(n − 1) +−n + 1 n(n + 1)
7
3
= t(n − 1) +−n+1 nt(n) =

1
1
I used the technique of partial fractions (remember calculus?) to replace n(n+1)
with 1n − n+1
inthe last step. The base case for this recurrence is t(0) = 0. Once again, we have a recurrence
that translates directly into a summation, which we can solve with just a few lines of algebra.


n 
X
7
3
−
t(n) =
i+1 i
i=1
n
n
X
X
1
1
=7
−3
i
+
1
i
i=1
i=1

= 7(H n+1 − 1) − 3H n
7
= 4H n − 7 +n+1
1
The last step uses the recursive definition of the harmonic numbers: H n+1 = H n + n+1. Finally,
substituting T (n) = (n + 1)t(n) and simplifying gives us the exact solution to the originalrecurrence.
T (n) = 4(n + 1)H n − 7(n + 1) + 7 = 4nH n − 7n + 4H n

Surprise, surprise, we get exactly the same solution!

Exercises
Unless explicitly stated otherwise, you may assume there is a function Random that, given any
positive integer k as input, returns an integer chosen independently and uniformly at random
from the set {1, 2, . . . , k} as output, in O(1) time. For example, to perform a fair coin flip, one
could call Random(2).
1. The following algorithm finds the second smallest element in an unsorted array:8

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

Random2ndMin(A[1 .. n]):min1 ← ∞min2 ← ∞for i ← 1 to n in random orderif A[i] < min1
min2 ← min1(?)
min1 ← A[i]else if A[i] < min2
min2 ← A[i](??)
return min2(a) In the worst case, how many times does Random2ndMin execute line (?)?
(b) What is the probability that line (?) is executed during the nth iteration of the loop?
(c) What is the exact expected number of executions of line (?)?
(d) In the worst case, how many times does Random2ndMin execute line (??)?
(e) What is the probability that line (??) is executed during the nth iteration of the loop?
(f) What is the exact expected number of executions of line (??)?
2. Consider the following randomized algorithm for choosing the largest bolt. Draw a bolt
uniformly at random from the set of n bolts, and draw a nut uniformly at random from theset of n nuts. If the bolt is smaller than the nut, discard the bolt, draw a new bolt uniformly
at random from the unchosen bolts, and repeat. Otherwise, discard the nut, draw a newnut uniformly at random from the unchosen nuts, and repeat. Stop either when every nut
has been discarded, or every bolt except the one in your hand has been discarded.
What is the exact expected number of nut-bolt tests performed by this algorithm? Prove
your answer is correct. [Hint: What is the expected number of unchosen nuts and bolts
when the algorithm terminates?]
3. Let S be a set of n points in the plane. A point p in S is called Pareto-optimal if no otherpoint in S is both above and to the right of p.
(a) Describe and analyze a deterministic algorithm that computes the Pareto-optimal
points in S in O(n log n) time.
(b) Suppose each point in S is chosen independently and uniformly at random fromthe unit square [0, 1] × [0, 1]. What is the exact expected number of Pareto-optimal
points in S?
4. A data stream is an extremely long sequence of items that you can only read only once, inorder. A good example of a data stream is the sequence of packets that pass through arouter. Data stream algorithms must process each item in the stream quickly, using very
little memory; there is simply too much data to store, and it arrives too quickly for any
complex computations. Every data stream algorithm looks roughly like this:9

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

DoSomethingInteresting(stream S):
repeatx ← next item in S〈〈do something fast with x〉〉
until S ends
return 〈〈something〉〉(a) Describe and analyze an algorithm that chooses one element uniformly at random
from a data stream, without knowing the length of the stream in advance. Youralgorithm should spend O(1) time per stream element and use O(1) space (notcounting the stream itself). You may assume that the stream is non-empty.
(b) Describe and analyze an algorithm that chooses k elements uniformly at random froma data stream, without knowing the length of the stream in advance. Your algorithm
should spend O(1) time per stream element and use O(k) space (not counting thestream itself). You may assume that the stream has at least k elements.
5. Consider the following randomized variant of one-armed quicksort, which selects the kth
smallest element in an unsorted array A[1 .. n]. As usual, Partition(A[1 .. n], p) partitions
the array A into three parts by comparing the pivot element A[p] to every other element,using n − 1 comparisons, and returns the new index of the pivot element.
QuickSelect(A[1 .. n], k) :r ← Partition(A[1 .. n], Random(n))
if k < rreturn QuickSelect(A[1 .. r − 1], k)else if k > r
return QuickSelect(A[r + 1 .. n], k − r)else
return A[k](a) State a recurrence for the expected running time of QuickSelect, as a function of nand k.
(b) What is the exact probability that QuickSelect compares the ith smallest and jth
smallest elements in the input array? The correct answer is a simple function of i, j,
and k. [Hint: Check your answer by trying a few small examples.](c) What is the exact probability that in one of the recursive calls to QuickSelect, thefirst argument is the subarray A[i .. j]? The correct answer is a simple function of i, j,
and k. [Hint: Check your answer by trying a few small examples.](d) Show that for any n and k, the expected running time of QuickSelect is Θ(n). You
can use either the recurrence from part (a) or the probabilities from part (b) or (c).
For extra credit, find the exact expected number of comparisons, as a function of nand k.
(e) What is the expected number of times that QuickSelect calls itself recursively?
6. Suppose we are given a two-dimensional array M [1 .. n, 1 .. n] in which every row andevery column is sorted in increasing order and no two elements are equal.

10

Algorithms

Lecture 2: Randomized Algorithms [Sp’17](a) Describe and analyze an algorithm to solve the following problem in O(n) time: Given
indices i, j, i 0 , j 0 as input, compute the number of elements of M smaller than M [i, j]
and larger than M [i 0 , j 0 ].
(b) Describe and analyze an algorithm to solve the following problem in O(n) time: Given
indices i, j, i 0 , j 0 as input, return an element of M chosen uniformly at random fromthe elements smaller than M [i, j] and larger than M [i 0 , j 0 ]. Assume the requested
range is always non-empty.
(c) Describe and analyze a randomized algorithm to compute the median element of M
in O(n log n) expected time.
7. Suppose we are given a sorted circular linked list of numbers, implemented as a pair ofarrays, one storing the actual numbers and the other storing successor pointers. Specifically,
we are given an array X [1 .. n] of distinct real numbers and an array next[1 .. n] be an arrayof indices with the following property:• If X [i] is the largest element of X , then X [next[i]] is the smallest element of X
• Otherwise, X [next[i]] is the smallest element of X that is larger than X [i].
For example:
1
2
3
4
5
6
7
8
9
83 54 16 31 45 99 78 62 27
6
8
9
5
2
3
1
7
4

i
X [i]
next[i]

Describe and analyze a randomized algorithm that determines whether a given number xpappears in the array X in O( n) expected time without modifying the input arrays.
8. Death knocks on your door one cold blustery morning and challenges you to a game. Deathknows that you are an algorithms student, so instead of the traditional game of chess,
Death presents you with a complete binary tree with 4n leaves, each colored either blackor white. There is a token at the root of the tree. To play the game, you and Death willtake turns moving the token from its current node to one of its children. The game willend after 2n moves, when the token lands on a leaf. If the final leaf is black, you die; if it’swhite, you will live forever. You move first, so Death gets the last turn.
∨
∧

∧
∨

∨
∧

∧

∧

∨
∧

∧

∨
∧

∧

∧

You can decide whether it’s worth playing or not as follows. Imagine that the nodes ateven levels (where it’s your turn) are Or gates, the nodes at odd levels (where it’s Death’sturn) are And gates. Each gate gets its input from its children and passes its output to its
parent. White and black stand for True and False. If the output at the top of the tree isTrue, then you can win and live forever! If the output at the top of the tree is False, you
should challenge Death to a game of Twister instead.
11

Algorithms

Lecture 2: Randomized Algorithms [Sp’17](a) Describe and analyze a deterministic algorithm to determine whether or not you canwin. [Hint: This is easy!](b) Unfortunately, Death won’t give you enough time to look at every node in the tree.
Describe a randomized algorithm that determines whether you can win in O(3n )expected time. [Hint: Consider the case n = 1.]? (c)Describe and analyze a randomized algorithm that determines whether you can winin O(c n ) expected time, for some constant c < 3. [Hint: You may not need to change
your algorithm from part (b) at all!]

9. Death knocks on Dirk Gently’s door one cold blustery morning and challenges him to agame. Emboldened by his experience with algorithms students, Death presents Dirk with acomplete binary tree with 4n leaves, each colored either black or white. There is a token at
the root of the tree. To play the game, Dirk and Death will take turns moving the token
from its current node to one of its children. The game will end after 2n moves, when thetoken lands on a leaf. If the final leaf is black, Dirk dies; if it’s white, Dirk lives forever.
Dirk moves first, so Death gets the last turn.3
∨
∧

∧
∨

∨
∧

∧

∧

∨
∧

∧

∨
∧

∧

∧

Unfortunately, Dirk slept through Death’s explanation of the rules, so he decides tojust play randomly. Whenever it’s Dirk’s turn, he flips a fair coin and moves left on heads,
or right on tails, confident that the Fundamental Interconnectedness of All Things willkeep him alive, unless it doesn’t. Death plays much more purposefully, of course, always
choosing the move that maximizes the probability that Dirk loses the game.
(a) Describe an algorithm that computes the probability that Dirk wins the game against
Death.
(b) Realizing that Dirk is not taking the game seriously, Death gives up in desperation anddecides to play randomly as well! Describe an algorithm that computes the probability
that Dirk wins the game again Death, assuming both players flip fair coins to decide
their moves.
10. A majority tree is a complete ternary tree with depth n, where every leaf is labeled either 0
or 1. The value of a leaf is its label; the value of any internal node is the majority of thevalues of its three children. Consider the problem of computing the value of the root of amajority tree, given the sequence of 3n leaf labels as input. For example, if n = 2 and theleaves are labeled 1, 0, 0, 0, 1, 0, 1, 1, 1, the root has value 0.
3Yes, this is precisely the same game from the previous exercise.

12

Algorithms

Lecture 2: Randomized Algorithms [Sp’17]

0

0
0

0

1
1

1

0

0
1

1

0

0

A majority tree with depth n = 2.

(a) Prove that any deterministic algorithm that computes the value of the root of amajority tree must examine every leaf. [Hint: Consider the special case n = 1.
Recurse.](b) Describe and analyze a randomized algorithm that computes the value of the root inworst-case expected time O(c n ) for some constant c < 3. [Hint: Consider the special
case n = 1. Recurse.](c) Suppose each node in the given tree has five children instead of three. Describe andanalyze a randomized algorithm that computes the value of the root in worst-case
expected time O(c n ) for some constant c < 5.

© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

13