Problem 71

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

2-choice hashing worst case

Due: April 5
Points: 4

These are the same two very simple hash functions from Problem 70:

\[h_1(x) = x \bmod 10\] \[h_2(x) = \left\lfloor\frac{x}{10}\right\rfloor\]

Come up with the smallest possible set of numbers, in the range of 1 up to 100, whose insertions into a size-10 table with 2-choice hashing MUST result in at least one bucket with 4 elements in it.

(What would this be if we only had a single hash function?)