Question 1 [12 marks]
(a) Assume that we have the probe sequence h(k, i) = [h′(k) + 5i] mod m where h′(k) = k mod m.
Let m = 16. Calculate the probe sequence for i = 0, 1, 2, …,m − 1 for keys k = 35 and k = 87.
Write the sequences as comma separated values (you should have 16 values per sequences), each
on its own line.
(b) What are the home buckets for these two keys? Based only on the two probe sequences from
part (a), will there be a clustering problem in this table? Justify your answer carefully.
(c) Now assume that the probe sequence is h(k, i) = [h′(k) + 3i] mod m where h′(k) = k mod m.
Let m = 7. Calculate the probe sequence for i = 0, 1, 2, …,m − 1 for keys k = 35 and k = 87.
Write the sequences as comma separated values (you should have 7 values per sequences), each
on its own line.
(d) Will the probe sequence from part (c) lead to a clustering problem in the table? You do not
have to provide a formal proof. Test out a few keys and their probe sequences with a larger m
and draw on these observations to justify your answer.
(e) In quadratic probing, we use the following formula to find the next bucket in a hash table: h(k, i)
= [h′(k) + c1i + c2i
2] mod m where h′(k) = k mod m and i = 0, 1, 2, …,m− 1. Assume that we
drop the linear term from the probe sequence by setting c1 to 0. Our function for finding open
buckets becomes [h′(k)+c2i
2] mod m for i = 0, 1, 2, …,m−1. Is it OK to make this simplification?
If so, provide a proof. If not, explain if problems might arise due to this simplification. In either
case, provide a formal and generalizable proof (i.e. in terms of i, m, and c rather than through a
specific example or counterexample). HINT: set m to an odd number, work through an example,
and see what happens.
1