Problem 2 - This is problem 11-3 in the CLRS textbook (page 308-309). Do only parts (b), (d), and (e). For each part, you can assume the previous parts, e.g., to prove part (d) you can assume the results of parts (a), (b), and (c). The problem is to determine the expected maximum size M of keys in a hash table of size n with n keys. The objective is to show that E[M] is O(clogn/loglogn). This is done in the following parts. (a) [0 pt] Don't do this part, but read it. This is straight forward since the probability of a key being in a particular slot is 1. (b) [1 pt] Do this part. Show Pk, the probability that the slot containing the most keys has k keys, is at most nQk (c) [0 pt] Don't do this part, but read it. Using Stirling's approximation, we can show Qk1 and N such that for nN,Qk01 such that Qk0lglgnclgn}n+Pr{Mlglgnclgn}lglgnclgn. Conclude that E[M]=O(lgn/lglgn)