Description
Question 1. Hash functions.
(i) Consider the hash function h1 : K1 → {0, 1, . . . , 7} given by h1(k) = (k
2 mod 8), where
K1 = {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]
(ii) Consider the hash function h2 : K2 → {0, 1, . . . , 126} given by h2(k) = (k mod 127), and
suppose the domain K2 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. [3 points]
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.) [5 points]
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).
(i) Draw A immediately before A is re-hashed for the second time. [2 points]
(ii) 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.
(i) Suppose the hash function h(k, i) is defined using linear probing, with auxiliary hash
function h
0
(k) = (k mod 100). [1 point]
(ii) Suppose the hash function h(k, i) is defined using quadratic probing, with auxiliary hash
function h
0
(k) = (k mod 100) and auxiliary constants c1 = 1, c2 = 1. [2 points]
(iii) Suppose the hash function h(k, i) is defined using double hashing, with two auxiliary hash
functions h1(k) = (k mod 100) and h2(k) = 1 + (k mod 103). [2 points]
1