For question 2c) Assume the table is regular Double-Hashing with pass-bits and not Ordered hashing.

2. (a) Use Ordered hashing (bully algorithm) with pass bits to insert the following keys in the order shown into a hash table of size m=7 using the probe sequences below. (b) Calculate the actual cost of unsuccessful search for key 50 with and without using pass bits (assuming probe sequence for 50 is 1 2 3 4 5 60). (c) Derive the expected cost for an unsuccessful search in this table assuming probe sequence is uniform random. Key hk,0 9 2 12 5 6 6 2 2 15 1 16 2 h{k,1) b(k,2) h(k,3) h(k,4) 0 5 3 1 1 4 0 3 1 3 5 0 5 1 4 0 2 3 4 5 4 6 1 3 h(k,5) h(k,6) 6 4 6 2 2 4 3 6 6 5 2. (a) Use Ordered hashing (bully algorithm) with pass bits to insert the following keys in the order shown into a hash table of size m=7 using the probe sequences below. (b) Calculate the actual cost of unsuccessful search for key 50 with and without using pass bits (assuming probe sequence for 50 is 1 2 3 4 5 60). (c) Derive the expected cost for an unsuccessful search in this table assuming probe sequence is uniform random. Key hk,0 9 2 12 5 6 6 2 2 15 1 16 2 h{k,1) b(k,2) h(k,3) h(k,4) 0 5 3 1 1 4 0 3 1 3 5 0 5 1 4 0 2 3 4 5 4 6 1 3 h(k,5) h(k,6) 6 4 6 2 2 4 3 6 6 5