(a) (3 points) Consider a hash table with chaining using a hash function that is a good approximation to the simple uniform hashing assumption, and having a load factor a (= the total number of elements in the table n divided by the number of slots m). Give the expected time of an unsuccessful search (i.e., to search for a key that is not in the table); explain your answer (intuitively at least). (b) (3 points) Consider Randomized-Quicksort that picks the pivot uniformly at random. Is there some particular input that will always cause the worst-case runtime of O(n)? (c) (6 points) Show a formal proof that the height of a Red-Black Tree h with n nodes, is at most 2.log(n + 1), i.e. h