2. [6 points] In this question, we will study a pitfall of quadratic probing in open addressing. In the lecture, we mentioned that, for quadratic probing, we need to be careful choosing the probe sequence, since it could jump in such a way that some of the slots in the hash table are never reached. (a) (3 points) Suppose that we have an open addressing hash table of size m = 7, and that we are using quadratic probing of the following form h(k,i) = (h(k) + 32) mod m, i = 0,1,2... where h(k) is some arbitrary hash function. We claim again that, as long as there is a free slot in this hash table, the insertion of a new key into the hash table is guaranteed to succeed, i.e., we must be able to find a free slot for the new key. Is this claim true? If true, concisely explain why; if not true, give a detailed counterexample and justify why it shows that the claim is false. (b) (3 points) Suppose that we have an open addressing hash table whose size m is a prime number greater than 3, and that we are using quadratic probing of the following form h(k, i) = (h(k) +32) mod m, i = 0,1,2... Prove that, if the hash table contains less than [m/2] keys (i.e., the table is less than half full), then the insertion of a new key is guaranteed to be successful, i.e., the probing must be able to reach a free slot