# Question

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 {0, 1, ..., m -1. The search scheme is as follows.

1. Compute the value i ← h(k), and set j ← 0.

2. Probe in position i for the desired key k. If you find it, or if this position is empty, terminate the search.

3. Set j ← (j + 1) mod m and i ← (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. Compute the value i ← h(k), and set j ← 0.

2. Probe in position i for the desired key k. If you find it, or if this position is empty, terminate the search.

3. Set j ← (j + 1) mod m and i ← (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.

## Answer to relevant Questions

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. Such a set is called persistent. One way to implement a persistent set is to copy the entire set ...Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and ...Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker ...Show how to solve the fractional knapsack problem in O (n) time. Assume that you have a solution to Problem 9-2.Suppose that a graph G has a minimum spanning tree already computed. How quickly can the minimum spanning tree be updated if a new vertex and incident edges are added to G?Post your question

0