This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 68

2-choice hashing worst case

Due: March 22
Points: 2

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

\[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?)