Question: An alternative collision resolution strategy is to define a sequence, , where and is a random permutation of the first integers (recall that the table size is M).
a. Prove that under this strategy, if the table is not full, the collision can always be resolved.
b. Would this strategy be expected to eliminate primary clustering?
c. Would this strategy be expected to eliminate secondary clustering?
d. If the load factor of the table is λ, what is the expected time to perform an insertion?
e. Generating a random permutation using the algorithm in Section 9.4 involves a large number of (expensive) calls to a random number generator. Give an efficient algorithm to generate a random-looking permutation that avoids calling a random number generator.