Suppose you are presented with a very large set S of real numbers, and you'd like to approximate the median of these numbers by sampling. You may assume all the numbers in S are distinct. Let n ISI; we will say that a number x is an e-approximate median of S if at least nmbers in S are less than x, and at least -en numbers in S are greater than x. Consider an algorithm that works as follows. You select a subset scs uniformly at random, compute the median of S, and return this as an approximate median of S. Show that there is an absolute constant c, independent of n, so that if you apply this algorithm with a sample S' of size c, then with probability at least .99, the number returned will be a (.05-approximate median of S. (You may consider either the version of the algorithm that constructs S' by sampling with replacement, so that an element of S can be selected multiple times, or one without replacement.)