Quadratic probing. This is problem 11-3 in the book. Suppose that we are given a key k to search for in a hash table with positions 0; 1; :::; m − 1, and suppose that we have a hash function h mapping the key space into the set f0; 1; :::; m−1g. The search scheme is as follows: 1. Compute the value j = h(k) and set i = 0. 2. Probe in position j for the desired key k. If you find it, or if this position is empty, terminate the search. 3. Set i = i+1. If i now equals m, the table is full, so terminate the search. Otherwise, set j = (i+j) mod m and return to step 2. Assume that m is a power of 2. a. Show that this scheme is an instance of the general \quadratic probing" scheme by exhibiting the appropriate constants c1 and c2 for equation (11.5). b. Prove that this algorithm examines every table position in the worst case. 1
