Description
1. Last month, while attempting to take a picture of the wild turkeys across the FXB, Daphne
got chased by some very angry turkeys. As a result, her doctor said that she is at risk of
contracting meleagrisphobia (a phobia of turkeys).
Unfortunately, the scientists at Michigan
Medicine who studied meleagrisphobia don’t have a very good way to determine if someone
has meleagrisphobia: on each trial, their test produces a false negative with probability 1
3
and a false positive with probability 1
3
.
Assume that each trial is completely randomized and
independent of other trials.
(a) Having recognized the danger of contracting meleagrisphobia due to her scary encounter
with the turkeys, Daphne asks the scientists to run the test on her n times. Let A be the
number of times the test comes back positive (i.e., it says “Daphne has meleagrisphobia”).
Assuming Daphne does not have meleagrisphobia, compute E[A].
Solution:
(b) Suppose that Daphne does have meleagrisphobia. Let Y be a random variable for the
number of trials that come back positive, out of n trials.
i. Find a closed-form expression for E[Y ] in terms of n.
Solution:
ii. To handle the false negatives, the scientists decide to run n tests and give a diagnosis
based on the result which happens strictly more than n/2 times. Using the lowertail Chernoff bound, find the minimum (odd) value of n such that Y > n/2 with
probability at least 95%, given that Daphne does have meleagrisphobia.
Solution:
2. One way to estimate √
2 is by “throwing darts” uniformly at random into a 1 × 1 square.
(0, 0) (1, 0)
(0, 1) (1, 1)
(a) Let p be the probability that a uniformly random point Q in the unit square is closer to
the diagonal between (0, 1) and (1, 0) than to all of the sides of the square. Prove that
p =
√
2 − 1.
Hint: Consider the diagram below. The region of points that are closer to the diagonal
than to every side of the square form a rhombus with vertices (0, 1), ( √
1
2
, √
1
2
), (1, 0),
(1 − √
1
2
, 1 − √
1
2
). (You do not have to prove this.)
(0, 0) (1, 0)
(0, 1) (1, 1)
Solution:
(b) Using the previous part, design a randomized algorithm that works by throwing n darts
randomly in the square, and outputs a value depending on where the darts land. Let
τ be the random variable representing the output of your algorithm. Prove that the
expected value of τ is √
2.
Solution:
(c) Let τ be the random variable representing the output of your algorithm from part (b).
Use the appropriate Chernoff bound to find the minimum number of darts that should
be thrown to ensure each of the following accuracies for τ with at least 99% confidence.
i. |τ −
√
2| < 0.1
Solution:
ii. |τ −
√
2| < 0.01
Solution:
iii. |τ −
√
2| < 0.001
Solution:
3. In class we proved that the expected time of RQuickSort is O(n log n), but this does not
necessarily imply that its running time is O(n log n) with probability close to 1. In this
problem you’ll prove that it does, in fact, run in O(n log n) time with high probability.
In RQuickSort, call a pivot p “good” if Partition(A[1..n], p) returns (L, R) with |L| ≤ (2/3)n
and |R| ≤ (2/3)n. The probability that p is a good pivot is at least 1/3; any pivot in the
middle third of the sorted order is a good pivot.
(a) Consider all the recursive calls to RQuickSort containing a particular input element e.
Prove that there are at most log3/2 n calls to Partition of the form Partition(B[1..m], p)
where e ∈ B[1..m], p is a good pivot, and B[1..m] is a subarray of A.
Solution:
(b) Define X = X1 + · · · + Xt
, where Xi
’s are independent indicator random variables with
Pr[Xi = 1] = 1/3. For any positive integer t, argue that
Pr[e is involved in ≥ t recursive calls] ≤ Pr[X ≤ log3/2 n].
Note: If an event p implies an event q, then Pr[p] ≤ Pr[q], since q could either happen
because p happened, or q could happen some other way.
Solution:
(c) Using parts (a) and (b), show that Pr[e is involved in ≥ t recursive calls] < 1/n2
, where
t = c ln n and c is some constant. You can make c as large a constant as you like.
Solution:
(d) Using part (b), argue that with probability at least 1 − 1/n, every element e is (simultaneously) involved in less than some t = c ln n recursive calls.
Solution:
(e) Conclude that with probability at least 1 − 1/n, RQuicksort takes O(n log n) time.
Solution: