Chapter 11 problems
Table of Contents
ch11-problems
11-1
a.
Suppose the \(i\)th insertion requires strictly more than \(k\) probes, we know that for the happened \(i\) insertions, there must be more than one probes in each of the \(k\) insertions, and we have \(n\leq m/2\), thus each of the \(k\) events has at most \(1/2\) probability, and the probability of the intersection of the \(k\) events is at most \(2^{-k}\).
b.
Substitute the conclusion of a. with equation \(k = 2\lg n\), we got the probability \(O(1/n^2)\).
c.
We have
\begin{align*} \Pr\{X > 2\lg n\} &=\Pr\{X_0 > 2\lg n\cup X_1 > 2\lg n\cup\dots\cup X_n > 2\lg n\}\\ &\leq\sum_{i=1}^{n}\Pr\{X_i > 2\lg n\}\\ &=\sum_{i=1}^{n}O(1/n^2)\\ &=O(1/n) \end{align*}d.
We have
\begin{align*} E[X] &\leq 2\lg n\cdot\Pr\{X\leq 2\lg n\}+n\cdot\Pr\{X > 2\lg n\}\\ &\leq 2\lg n+n\cdot O(1/n)\\ &=O(\lg n) \end{align*}
11-2
a.
To hash exactly \(k\) keys to a particular slot, we need to choose \(k\) keys first, which contains \(\binom{n}{k}\) cases, then we put the \(k\) keys to the particular slot and the \(n - k\) keys to other slots, all the events of key hashing are distinct. Thus, the probability \(Q_k\) is
\begin{align*} Q_k=\bigg(\frac{1}{n}\bigg)^k\bigg(1-\frac{1}{n}\bigg)^{n-k}\binom{n}{k} \end{align*}b.
If the slot containing the most keys contains \(k\) keys, then there must be a slot contains exactly \(k\) keys, which means \(P_k \leq nQ_k\).
c.
We have
\begin{align*} Q_k &=\bigg(\frac{1}{n}\bigg)^k\bigg(1-\frac{1}{n}\bigg)^{n-k}\binom{n}{k}\\ &=\frac{(n-1)^{n-k}}{n^n}\cdot\frac{n!}{(n-k)!k!}\\ &< \frac{n!}{n^k(n-k)!k!}\\ &< \frac{1}{k!}\\ &=\frac{1}{\sqrt{2\pi k}(\frac{k}{e})^k\big(1+\Theta(\frac{1}{k})\big)}\\ &< \frac{e^k}{k^k} \end{align*}d.
Assume \(Q_{k_0} < e^{k_0}/k_0^{k_0} \leq 1/n^3\), then we have
\begin{align*} f(n)=\frac{c}{\lg\lg n}\cdot(\lg c-\lg \mathrm{e}+\lg\lg n-\lg\lg\lg n) > 3 \end{align*}Since \(f(n)\) is monotonically decreasing on the range \([3,\infty]\), we could obtain \(c > 3\) from \(\lim_{n\to\infty}f(n)>3\), and choose \(c = 4\) to satisfy the requirement. For \(k>k_0=c\lg n/\lg\lg n\), we have \(P_k\leq nQ_k\leq nQ_{k_0}<1/n^2\).
e.
We have
\begin{align*} E[M] &=\sum_{k=1}^{n}k\cdot P_k\\ &\leq n\cdot\sum_{k_0 < k\leq n}P_k+k_0\cdot\sum_{1\leq k\leq k_0}P_k\\ &=\Pr\bigg\{M > \frac{c\lg n}{\lg\lg n}\bigg\}\cdot n+\Pr\bigg\{M\leq \frac{c\lg n}{\lg\lg n}\bigg\}\cdot\frac{c\lg n}{\lg\lg n}\\ &\leq n\cdot\frac{1}{n^2}\cdot n+\frac{c\lg n}{\lg\lg n}\\ &=O(\lg n/\lg\lg n) \end{align*}
11-3
a.
Let \(j_i\) indicates the value of \(j\) after \(i\) iterations of steps 2-3, we have
\begin{align*} j_i= \begin{cases} h(k) &\text{, if $i=0$}\\ (j_{i-1}+i)\mod m &\text{, if $i>0$} \end{cases} \end{align*}By induction, we have \(j_i=h(k)+\frac{i(i+1)}{2}\), thus the given scheme is an instance of the general "quadratic probing" scheme, by exhibiting the appropriate constants \(c_1=1/2\) and \(c_2=1/2\).
b.
Assume the algorithm does not examine every table position in the worst case, then there must be \(0\leq x < y\leq m-1\) that \(j_x=j_y\), we have
\begin{align*} & h(k)+x(x+1)/2\equiv h(k)+y(y+1)/2\pmod{m}\\ \implies & y^2+y-x^2-x\equiv 0\pmod{2m}\\ \implies & (y-x)(y+x+1)\equiv 0\pmod{2m} \end{align*}Since \(m\) is a power of \(2\), if \(y-x\) is odd, then we have \((y+x+1)\equiv 0\pmod{2m}\), which is impossible because \(y+x+1< 2m\); if \(y-x\) is even, then \(y+x+1 = (y-x)+2x+1\) is odd, hence \((y-x)\equiv 0\pmod{2m}\), which is also impossible.
In conclusion, the algorithm examines every table position in the worst case.
11-4
a.
If the family \(\mathcal{H}\) of hash function is \(2\)-universal, then for each two distinct keys \(\langle x^{(1)},x^{(2)}\rangle\) and any \(h\in\mathcal{H}\), the sequence \(\langle h(x^{(1)}),h(x^{(2)})\rangle\) is equally likely to be any of the \(m^2\) sequences of length \(2\) with elements drawn from \(\{0,1,\dots,m-1\}\), that is, \(m\) collisions out of \(m^2\) pairs, the probability of collision is no more than \(1/m\), thus the family \(\mathcal{H}\) is universal.
b.
For each pair of distinct elements \(x,y\in U\) and a hash function \(h_a\) randomly chosen from \(\mathcal{H}\), if \(x\) and \(y\) collides, i.e. \(h_a(x) = h_a(y)\), then we have
\begin{align*} \Bigg(\sum_{j=0}^{n-1}a_j(x_j-y_j)\Bigg)\equiv 0\pmod{p} \end{align*}Since \(p\) is prime, the number of hash functions \(h_a\in\mathcal{H}\) for which \(h_a(x) = h_a(y)\) is at most \(|\mathcal{H}|/m\), hence \(\mathcal{H}\) is universal. However, for \(x=\langle 0,0,\cdots,0\rangle\), all hash functions in \(\mathcal{H}\) produce the same value \(0\), hence \(\mathcal{H}\) is not \(2\)-universal.
c.
For each pair of distinct elements \(x,y\in U\), the hash values \(h'_{ab}(x)\) and \(h'_{ab}(y)\) are both equally likely to be any of the values in \(\mathbb{Z}_p\), and are independent, hence the sequence \(\langle h'_{ab}(x),h'_{ab}(y) \rangle\) is equally likely to be any of the \(p^2\) sequences of length \(2\) with elements drawn from \(\mathbb{Z}_p\), thus \(\mathcal{H}\) is \(2\)-universal.
d.
Let \(\langle m, m'\rangle\) to be a sequence of two distinct keys drawn from \(U\), since \(\mathcal{H}\) is \(2\)-universal, for any \(h\) chosen at random from \(\mathcal{H}\), the sequence \(\langle h(m),h(m') \rangle\) is equally likely to be any of the \(p\)2 sequences of length \(2\) with elements drawn from \(\mathbb{Z}_p\). Thus, for fixed values \(m,t,m'\), the value of \(t'\) is equally likely to be any of \(\mathbb{Z}_p\), hence the probability that the adversary succeeds in fooling Bob is at most \(1/p\).