Chapter 11, Problem 1P

(a)

Program Plan Intro

To determine the longest probe while performing insertion in hash table.

Explanation of Solution

Given Information: The probability of i^th insertion in hash table by using uniform hashing is atmost 2-k.

Explanation:

In the uniform hashing, where keys are inserted uniformly in available hashes. Suppose there is an open address hash table and keys are inserted one by one then average probe will be (1/(1-a)), where a is equals to load factor. So, while inserting keys into empty hash table, for the first hash slot, unsuccessful expected number of probe will be

  $Pr\{X\ge i\}<={\alpha }^{i-1}$ .

Since $n<=m/2,\alpha \le 1/2$ are given. Putting $i=k+1$ , in the given equation.

  $Pr\{X\ge k+1\}\le {\left(1/2\right)}^{k+1-1}$

So, the at most probability will be $Pr\{X\ge k+1\}=2^{-k}$ .

(b)

Program Plan Intro

Show that the ith insertion requires more than 2lg n probe and probability $Pr\left\{X_i>2lgn\right\}$ in the hash table of size m is $=O\left(1/n2\right)$ .

Explanation of Solution

Given Information: An open addressing hash table having size m and contains $n\le m/2$ items.

Explanation: From the above section, where the probability of i^th insertion of an item in the hash table by using uniform hashing is at most 2-k.

Where k is the no. of probes. Now from the given condition, put the value of probe k is equals to 2 logn.

  $\begin{array}{l}=2^{-k}\hfill \\ =2^{-2lgn}\hfill \\ ={\left(2lgn\right)}^{-2}\hfill \\ =n^{-2}\hfill \\ =1/n^2 \hfill \end{array}$

So, the complexity will be $O\left(1/n^2\right)$ .

(c)

Program Plan Intro

To show the asymptotic bounds for the probes required is equals to $O\left(1/n\right)$ .

Explanation of Solution

Given Information: For a particular event A, probability of probes required $Pr\left\{A_i\right\}\le 1/n^2$ .

Explanation: For an event A, required probes X>2lg n, and for the ith insertion, required probes for an event $A_i,X_i>2logn$ . From the above explanation, probability of an event A_i for i^th insertion is less than or equals to 1/n².

An event $A_i=A1\cup A2\cup A3\cup A4\cup \dots \cup An$ , where $1\le i\le n$

  $Pr\left(A\right)\le Pr\left(A_1\right)+Pr\left(A_2\right)+Pr\left(A_3\right)+Pr\left(A_4\right)+\dots \dots \dots .+Pr\left(A_n\right)$ ,

by Boole’s inequality

  $\begin{array}{l}\le n.1/n^2\hfill \\ =1/n\hfill \end{array}$

So, the asymptotic bound for the probe required is equals to $O\left(1/n\right)$ .

(d)

Program Plan Intro

To determine the expected length of the longest probe sequence is $O\left(lgn\right)$ .

Explanation of Solution

Given Information: Probability of number of probes required $Pr\left\{X=k\right\},$ where k is equals to no. of probes.

Explanation:The expected length of the longest probe E[X] can be dependent on the given probability $Pr\left\{X=k\right\}$ . To get the desired outcome, expected length E[X] can be divided in such a way that the total sum would not affected.

  $E\left[X\right]=\sum k.Pr\left\{X=k\right\},1\le k<n$

Here,break the above equation into two parts by using some breaking point, in this case its 2lg n.

  $E\left[X\right]=\sum k.Pr\left\{X=k\right\}+\sum k.Pr\left\{X=k\right\},1\le k<n$