1. (M-U 2.3): Let X be a random variable given by the roll of a single die (that is, it is a number from 1 to 6 with probability 1/6 of each choice). Give examples of functions f for which E[f(x)] < f(E[X]), E[f(X)] = f(E[X]), and E[f(X)] > f(E[X]).

2. (M-U 2.16) Suppose we flip a fair coin 2^k times. What is the expected number of positions i within the sequence with the property that the k coin flips from position i-k+1 to position i are all heads?

3. In any execution of the quicksort algorithm, define a "bad split" to be the event that the pivot element chosen by the algorithm is in either the first 1/4 or the last 1/4 of the sorted output, and a "good split" to be the event that the chosen pivot does not form a bad split.

(a) Consider the sequence of recursive calls that starting with the topmost call made by the algorithm, and that continues at each step within the larger of the two recursive subproblems. What is the expected number of bad splits in this sequence, before reaching a subproblem that has a good split?

(b) Argue based on part (a) that the expected time for quicksort is O(n), plus the time for a set of calls on subproblems whose sizes add to n and whose individual sizes are all at most 3n/4.

(c) Prove by induction based on part (b) that quicksort takes time O(n log n).