Illustrate the result of inserting the 16 values of k, 10, 22, 3, 31, 4, 67, 15, 34, 28, 17, 88, 59, 70, 11, 46, 75, in this order, into a hash table by each of the following methods. In the following, m is the array size and f(k, m) = m(fractional part of kA) = m(kA mod 1), A = (5 1)/2 0.6180339887.

a. chaining with division method: h(k) = k mod m, m = 23

b. chaining with multiplication method: h(k) = f(k, 23)

c. open addressing with linear probing: h(k, i) = (h'(k) + i) mod m, h'(k) = f(k, m), m = 32

d. open addressing with quadratic probing: h(k, i) = (h'(k) + i(i+1)/2) mod m, h'(k) = f(k, m), m = 32

e. open addressing with double hashing: h(k, i) = (h₁(k) + i h₂(k)) mod m, h₁(k) = f(k, m), h₂(k) = k mod m if k mod m is odd, (k mod m)+1 if k mod m is even, m = 32

In open addressing, the number of probes performed is defined as the number of array positions examined to insert the key. That is, if h(k, 0), , h(k, i1) are examined to insert k, the number of probes performed is i. For each of (c), (d), (e), compute the number of probes performed for each of the 16 keys along with the average number of probes performed over the 16 keys. You might solve this exercise by writing a program in your favorite programming language; no need to hand in the program if you elect to do so.