1. The two keys 0 and 3 are mapped either to a pair of cells of the form
(i,i) or (i,i+3). So among the 36 possible ordered pairs of cells in the
hash table, there are only 12 they could actually be mapped to, and they
have probability 1/12 of being mapped to these pairs cells instead of
probability 1/36 of being mapped to any pair. Therefore, this choice of
hash function is not 2-independent.

(It would be a valid answer to pick any other pair of keys that do not
map to the same pair of cells, or to write a program to calculate the
probabilities for all possible pairs of keys mod 6.)


2 (a). Let the three numbers be x, y, and z, and choose a byte position
i at which they do not all have the same byte value. Then for byte i,
either all three numbers have different byte values x_i, y_i, and z_i,
or two of them are equal and one of them is unequal to the other two. In
the first case, all of x_i, y_i, and z_i are used only by their key; in
the second case, the one that is unequal is used only by its key.

(Many other proofs are possible.)

(b) Let S be the four numbers whose four bytes are 0000, 0001, 0010, and
0011.

(Many similar patterns in which there are at most two different byte
patterns per byte will work.)


3. Apply the cuckoo-linear algorithm to the given input sequence, and
then use the ordering that it produces (starting at the beginning of any
contiguous block of cells and then wrapping around) as your new input ordering.
(An older version of this answer suggested just reversing the input
ordering, but this does not always work correctly.)