1. [14] In this question, we wil study a pitfall of quadratic probing in open addressing. In the lecture, we showed for quadratic probing that 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) Suppose that we have an open addressing hash table of size m = 7, and that we are using linear probing of the following form h(k. i)- (h(k) + i) mod m, 0,1,2.. where h(k) is some arbitrary hash function. We claim that, as long as there is a free slot in this hash table, the insertion of a new key (a key that does not exist in the table) into the hash table is guaranteed to succeed, i.e., we will 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) Now, 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) i2) mod m, 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 (c) If either of your answers to (a) and (b) is "false", then it means that some of the slots in the hash table are essentially "wasted", i.e., they are free with no key occupying them, but the new keys to be inserted may not be able to use these free slots. In this part, we will show an encouraging result for quadratic probing that says "this waste cannot be too bad 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) 2) mod, 0,1,2 Prove that, if the hash table contains less than Im/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 Hint: What if the first |m/2] probe locations for a given key are all distinct? Try proof by contradiction 1. [14] In this question, we wil study a pitfall of quadratic probing in open addressing. In the lecture, we showed for quadratic probing that 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) Suppose that we have an open addressing hash table of size m = 7, and that we are using linear probing of the following form h(k. i)- (h(k) + i) mod m, 0,1,2.. where h(k) is some arbitrary hash function. We claim that, as long as there is a free slot in this hash table, the insertion of a new key (a key that does not exist in the table) into the hash table is guaranteed to succeed, i.e., we will 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) Now, 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) i2) mod m, 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 (c) If either of your answers to (a) and (b) is "false", then it means that some of the slots in the hash table are essentially "wasted", i.e., they are free with no key occupying them, but the new keys to be inserted may not be able to use these free slots. In this part, we will show an encouraging result for quadratic probing that says "this waste cannot be too bad 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) 2) mod, 0,1,2 Prove that, if the hash table contains less than Im/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 Hint: What if the first |m/2] probe locations for a given key are all distinct? Try proof by contradiction
