[Solved] 50.004 Homework Set3

Question 1. Hash functions.

• Consider the hash function h₁ : K₁ → {0,1,…,7} given by h₁(k) = (k² mod 8), where K₁ = {0,1,…,100} is the set of all possible key values, with each key value being equally likely to occur. Is this a “good” hash function? Explain your answer. [2 points]
• Consider the hash function h₂ : K₂ →{0,1,…,126} given by h₂(k) = (k mod 127), and suppose the domain K₂ consists of all 8-character password ASCII strings, treated as base128 integers. Explain why the ASCII string ‘PASSWORD’ and all of its permutations

(e.g. ‘PAWORSSD’) would be mapped to the same hash value.

Question 2. Design an algorithm that takes as its input a singly linked list L with n elements, and returns as its output a singly linked list whose elements are in reverse order. (For example, if L is non-empty, then the first element L.head should now be the last element in your output linked list. You may assume that if L is an empty linked list, then L.head = NIL.) Your algorithm should run in Θ(n) time, and it should use no more that O(1) space beyond what is needed to store the linked list L itself. Please give your algorithm in pseudocode. (Hint: It is easy to give a recursive algorithm.) [5 points]

Question 3. Initialize A as a hash table with 4 slots, and suppose its hash function is created using the multiplication method with constant 0.618. Assume that collisions are resolved by chaining. Suppose we insert the following key values 1.3, 2.5, 3.1, 4.2, 5.7 into A, in this given order. Draw the final hash table A after these insertions. (Hint: When drawing a hash table, you should draw all slots, even if some slots contain the NIL object. Remember also to indicate the indices for your hash table.)

Question 4. Initialize a hash table A with 3 slots, whose hash function is created using the division method. Assume that collisions are resolved by chaining. Also, assume that the load factor cannot exceed γ = 0.7, and that re-hashing is done by doubling. Suppose we insert the following eleven integer key values into A: 2,3,5,6,7,10,26,27,30,32,35 (in this given order).

• Draw A immediately before A is re-hashed for the second time. [2 points]
• Draw the final hash table after the insertion of all eleven key values. [3 points] (Hint: When drawing a hash table, you should draw all slots, even if some slots contain the NIL object. Remember also to indicate the indices for your hash table.)

Question 5. Let A be an empty open address hash table with 100 slots. Suppose we insert the key values 101,201,301,401,501 into A in this given order. For each of the three following probing strategies, please give all non-empty slots of the hash table with their corresponding key values. For example, if you think that slots 0,1,2,3,4 are the only non-empty slots, with key values 101,201,301,401,501 respectively, then you can write A[0] = 101,A[1] = 201,A[2] = 301,A[3] = 401,A[4] = 501 as your answer.

• Suppose the hash function h(k,i) is defined using linear probing, with auxiliary hash function h⁰(k) = (k mod 100). [1 point]
• Suppose the hash function h(k,i) is defined using quadratic probing, with auxiliary hash function h⁰(k) = (k mod 100) and auxiliary constants c₁ = 1, c₂ = 1. [2 points]
• Suppose the hash function h(k,i) is defined using double hashing, with two auxiliary hash functions h₁(k) = (k mod 100) and h₂(k) = 1 + (k mod 103). [2 points]

1