P1. Suppose we insert n = 2k − 1 keys from 1,...,n uniformly at random into a binary search tree. Let Pk probability that the tree is perfectly balanced: i.e, all paths from root to leaf are of the same length. Derive a recurrence for Pk. Calculate P5.
P2. Suppose there are n delicious sweets in front of you that you wish to consume. Each morning you toss a coin for each sweet that is left and consume it if the coin turns up heads or save it for another day if the coin turns up tails.
(A) What is the probability that after k days of this, there are still candies left.
Express your answer as a function of n,k and simplify as much as possible. (B) What is the expected time taken to consume all the candies? Hint: For a positive integer valued random variable X we have
E(X) = P(X ≥ 1) + P(X ≥ 2) + P(X ≥ 3) + ···
Express your answer as a function of n,k and simplify as much as possible.
(C) Use Bernoulli’s inequality (1 − x)r ≥ 1 + rx for any real valued x ≥ −1 and integer r ≥ 1 to prove that the expected time to consume all candies is ≤ log2(n)+c for some constant c for n ≥ 4.
1
