# Question

A hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used for collision resolution.

a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2-k.

b. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n2. Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.

c. Show that Pr{X > 2lg n} ≤ 1/n.

d. Show that the expected length E[X] of the longest probe sequence is O (lg n).

a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2-k.

b. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n2. Let the random variable Xi denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.

c. Show that Pr{X > 2lg n} ≤ 1/n.

d. Show that the expected length E[X] of the longest probe sequence is O (lg n).

## Answer to relevant Questions

Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of ...The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7- point problem. The general problem ...Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraph neatly on a number of lines that ...Give a dynamic-programming solution to the 0–1 knapsack problem that runs in O (n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack.The incidence matrix of a directed graph G = (V, E) is a |V| × |E| matrix B = (bij) such thatDescribe what the entries of the matrix product B BT represent, where BT is the transpose of B.Post your question

0