算法导论11 Problems 答案
11-1
a
令随机变量\(X_i\)表示第\(i\)个键插入所期望的时间。在第\(i\)次插入时，哈希表中已经有\(i-1\)个键，执行一次插入操作相当于执行了一次不成功查找。令随机变量\(Y_i\)表示当填充因子为\(\dfrac{i}{m}(0\le i< m)\)时，进行一次不成功查找的时间，那么可以知道\(X_i=Y_{i+1}\)。考虑计算\(\Pr\{Y_i>p\}\)的值，根据定理11.6，有
\(\begin{aligned} \Pr\{Y_i>p\} &= \Pr\{Y_i\ge p+1\}\\ &\le \left(\dfrac{n}{m}\right)^p\\ &\le 2^{-p} &\qquad(A) \end{aligned}\)
其中步骤\((A)\)使用了假设\(n\le m/2\)。
那么，进行一次插入操作时使用了严格多于\(p\)次探测的概率为\(\Pr\{X_i>p\}=\Pr\{Y_{i+1}>p\}=2^{-p}\)。
b
考虑计算\(\Pr\{Y_i>p\}\)的值，根据定理11.6，有
\(\begin{aligned} \Pr\{Y_i>2\lg n\} &= \Pr\{Y_i\ge 2\lg n+1\}\\ &\le \left(\dfrac{n}{m}\right)^{2\lg n}\\ &\le \left(\dfrac{1}{2}\right)^{2\lg n}\\ &=\dfrac{1}{n^2} \end{aligned}\)
因此有\(\Pr\{X_i>2\lg n\}=\Pr\{Y_{i+1}>2\lg n\}=O(1/n^2)\)。
c
令事件\(A_i\)表示\(X_i>2\lg n\)。那么有
\(\begin{aligned} \Pr\{X>2\lg n\} &= \Pr\left\{\max_{i=1}^n X_i>2\lg n\right\}\\ &=\Pr\left\{\bigcup_{i=1}^n A_i\right\}\\ &\le \sum_{i=1}^n \Pr\{A_i\}\\ &= \sum_{i=1}^n \Pr\{X_i>2\lg n\}\\ &\le n\cdot \dfrac{1}{n^2}\\ &= \dfrac{1}{n} \end{aligned}\)
因此有\(\Pr\{X>2\lg n\}=O(1/n)\)。
d
\(\begin{aligned} E[X] &= \sum_{i=1}^{\infty} \Pr\{X\ge i\}\\ &=\sum_{i=1}^{2\lg n} \Pr\{X\ge i\}+\sum_{i=2\lg n+1}^{n} \Pr\{X\ge i\}+\sum_{i=n+1}^{\infty} \Pr\{X\ge i\}\\ &\le\sum_{i=1}^{2\lg n} 1+\sum_{i=2\lg n+1}^{n} \dfrac{1}{n}+0\\ &\le\sum_{i=1}^{2\lg n} 1+\sum_{i=1}^{n} \dfrac{1}{n}\\ &=2\lg n+1\\ &\le 3\lg n &\qquad(A) \end{aligned}\)
其中，步骤\((A)\)假设了\(n> 1\)，那么有\(\lg n\ge 1\)。因此有\(E[X]=O(\lg n)\)。
11-2
a
离线操作：将所有元素先进行排序，需要\(O(n\lg n)\)的运行时间。
在线操作：使用二分法可以在\(O(\lg
n)\)的时间内查找一个数是否在这个有序序列中，由算法ORDERED-SEAECH给出。
1 | ORDERED-SEAECH(A, n, k) |
b
令随机变量\(X\)表示进行一次不成功的查找时，所需要进行探测次数的期望值。根据定理11.6，有\(E[X]\le \dfrac{1}{1-\alpha}=\dfrac{m}{m-n}\)。
如果使用开放寻址法的运行事件至少和题目11-2-a的效率一致，那么考虑解方程\(\dfrac{m}{m-n}\le c\lg n\)，最终得到\(m\ge \dfrac{n\lg n}{\lg n - 1}-n\)。
经过变换，得到\(m-n\ge \dfrac{n}{\lg n - 1}\ge \dfrac{n}{2\lg n}\)。
因此，最终只有当额外的空间满足\(m-n=\Omega(n/\lg n)\)时，使用开放寻址法的效率才会接近二分法。
11-3
a
对于某一特定槽而言，一个键被插入该槽的概率为\(\dfrac{1}{n}\)，不被插入该槽的概率为\(1-\dfrac{1}{n}\)。这\(n\)个键的插入过程都是独立的，某一键插入该槽的情况可以看作是做一次概率为\(\dfrac{1}{n}\)的伯努利实验，那么这\(n\)个键对该槽插入的情况相当于是做\(n\)次相同的伯努利实验。因此\(k\)服从参数为\(n,\dfrac{1}{n}\)的二项分布，即
\[Q_k=b\left(k,n,\dfrac{1}{n}\right)=\left(\dfrac{1}{n}\right)^k\left(1-\dfrac{1}{n}\right)^{n-k}\dbinom{n}{k}\]
b
令随机变量\(X_i\)表示第\(i\)个槽中的链的长度。令事件\(A_i\)表示\(X_i=k\)，事件\(A=\displaystyle{\bigcap_{i=1}^n A_i}\)。那么有
\(\begin{aligned} P_k&\le \Pr\{A\} &\qquad(A)\\ &=\Pr\left\{\bigcap_{i=1}^n A_i\right\}\\ &\le \sum_{i=1}^n \Pr\{A_i\}\\ &= \sum_{i=1}^n Q_k\\ &= nQ_k \end{aligned}\)
其中，步骤\(A\)扩大了事件所代表的空间：\(\{X_i\}\)的最大值为\(k\)，可以推出所有随机变量中存在一个随机变量取值为\(k\)，而不能反向推出。
c
使用不等式C.6：\(\dbinom{n}{k}\le \left(\dfrac{en}{k}\right)^k\)，有
\(\begin{aligned} Q_k&=\left(\dfrac{1}{n}\right)^k\left(\dfrac{n-1}{n}\right)^{n-k}\dbinom{n}{k}\\ &\le \dfrac{(n-1)^{n-k}}{n^n} \cdot \dfrac{e^kn^k}{k^k}\\ &< \dfrac{n^{n-k}}{n^n} \cdot \dfrac{e^kn^k}{k^k}\\ &=\dfrac{e^k}{k^k} \end{aligned}\)
d
考虑求满足条件的\(k_0\)使得\(\dfrac{e^{k_0}}{k_0^{k_0}}<\dfrac{1}{n^3}\).两边对\(2\)取对数，移项后得到
\[3\lg n<k_0(\lg k_0-\lg e)\]
代入\(k_0=\dfrac{c\lg n}{\lg\lg n}\)，那么得到\(3\lg n<\dfrac{c\lg n}{\lg \lg n}\left(\lg \dfrac{c\lg n}{\lg\lg n}-\lg e\right)\)。
假设\(n>2\)，更进一步，可以化简到\(\dfrac{c}{\lg\lg n}\left(\lg c-\lg\lg\lg n-\lg e\right)+c>3\)。
令\(g(n)=\dfrac{c}{\lg\lg n}\left(\lg c-\lg\lg\lg n-\lg e\right)+c\)，可以发现\(\displaystyle{\lim_{n\rightarrow\infty}g(n)=c}\)。如果\(c=4\)，\(\exists n_0>3,\forall n\ge n_0,g(n)>3\)恒成立。当\(n< n_0\)时，令\(c(n)\)是满足\(g(n)>3\)的最小\(c\)。那么构造出\(c=\displaystyle{\max\left\{4,\max_{n=3}^{n-1}\{h(i)\}\right\}}\)。此时对于\(\forall n\ge 3,g(n)> 3\)都将成立。
按照如上方式，我们构造出了一个\(c\)，使得\(\forall n\ge 3\)，令\(k_0=\dfrac{c\lg n}{\lg\lg n},Q_{k_0}<\dfrac{1}{n^3}\)总成立。
由于\(c>1,n>2\)，那么可以知道\(k_0\ge 1\)。根据等式C.45，可以得知当\(k\ge k_0\)时，\(Q_k\)是一个递减函数，因此\(\forall k\ge k_0,Q_k<\dfrac{1}{n^3}\)均成立。因此按照题目11-3-b的结论，\(\forall k\ge k_0,P_{k_0}< nQ_{k_0}<\dfrac{1}{n^2}\)均成立。
e
\(\begin{aligned} E[M]&=\sum_{k=1}^n k\cdot P_k\\ &=\sum_{k=1}^{k_0} k\cdot P_k+\sum_{k=k_0+1}^n k\cdot P_k\\ &\le\sum_{k=1}^{k_0} k_0\cdot P_k+\sum_{k=k_0+1}^n n\cdot P_k\\ &=\Pr\{M\le k_0\}\cdot k_0 + \Pr\{M>k_0\}\cdot n \end{aligned}\)
令\(k_0=\dfrac{c\lg n}{\lg\lg n}\)，得证关于\(E[M]\)的表达式。
考虑计算\(\Pr\{M>k_0\}\)的上限，有\(\displaystyle{\Pr\{M>k_0\}=\sum_{i=k_0+1}^nP_k\le\sum_{i=k_0+1}^n\dfrac{1}{n^2}}\le n\cdot \dfrac{1}{n^2}=\dfrac{1}{n}\)
\(\begin{aligned} E[M]&\le \Pr\{M\le k_0\}\cdot k_0 + \Pr\{M>k_0\}\cdot n\\ &\le 1\cdot k_0+\dfrac{1}{n}\cdot n\\ &=k_0+1 \end{aligned}\)
因此有\(E[M]=O\left(\dfrac{\lg n}{\lg\lg n}\right)\)。
11-4
a
由于函数簇\(\mathscr{H}\)是\(2\)-独立的，因此对任意不同的\(k_1,k_2\in U,\forall d_1,d_2\in \mathbb{Z}_m,\Pr\{h(k_1)=d_1\land h(k_2)=d_2\}=\dfrac{1}{m^2}\)。
那么\(\displaystyle{\Pr\{h(k_1)=h(k_2)\}=\sum_{d\in\mathbb{Z}_m}\Pr\{h(k_1)=d\land h(k_2)=d\}=m\cdot \dfrac{1}{m^2}=\dfrac{1}{m}}\)。因此函数簇\(\mathscr{H}\)是全域的。
b
对于\(x,y\in U,x\neq y\)，考虑\(h_a(x)=h_a(y)\)的概率\(\Pr\{h_a(x)=h_a(y)\}\)，即\(\displaystyle{\sum_{i=0}^{n-1}a_ix_i\equiv\sum_{i=0}^{n-1}a_iy_i \pmod p}\)的概率。
令\(\displaystyle{f(a)=\left(\sum_{i=0}^{n-1}a_i(x_i-y_i)\right)\bmod{p}}\)。由于\(x\neq y\)，因此\(\exists k\in\{0,1,2,\dots,n-1\},x_k\not\equiv y_k \pmod p\)成立。令\(c=a_k(x_k-y_k)\bmod p\)，随机变量\(X=(f(a)-c)\bmod p,Y=f(a)\)。
考虑随机变量\(Y\)的分布。无论\(X\)的分布如何，可知有\(\displaystyle{\sum_{i=0}^{p-1} \Pr\{X=i\}=1}\)。由于\(a\)向量是从\(U\)中均匀随机选择的，因此\(a_k\)和\(a\)中的其它值相互独立，并且\(a_k\)取到\(\mathbb{Z}_p\)中的数也是等概率的。由于\((x_k-y_k)\)是一个固定的非零整数，并且\(p\)是质数，那么\(\gcd(p,x_k-y_k)=1\)，因此如果\(a_k\)取遍\(\mathbb{Z}_p\)中的所有数，\(c\)也会取便\(\mathbb{Z}_p\)中的所有数。也就是说，\(\forall i\in \mathbb{Z}_p,\Pr\{c=i\}=\dfrac{1}{p}\)。
那么考虑计算\(\Pr\{Y=j\}\)的值，其中\(j\in \mathbb{Z}_p\)：
\(\begin{aligned} \Pr\{Y=j\}&=\sum_{i=0}^{p-1} \Pr\{X=(j-i)\bmod p\land c=i\}\\ &=\sum_{i=0}^{p-1} \Pr\{X=(j-i)\bmod p\}\cdot \Pr\{c=i\}\\ &=\sum_{i=0}^{p-1} \Pr\{X=(j-i)\bmod p\}\cdot \dfrac{1}{p}\\ &=\dfrac{1}{p} \sum_{i=0}^{p-1} \Pr\{X=i\}\\ &=\dfrac{1}{p} \end{aligned}\)
注意在整个步骤中，\(X\)的分布是什么并不关心。那么得到\(\Pr\{Y=0\}=\dfrac{1}{p}\)，也就是说，\(\Pr\{h_a(x)=h_a(y)\}=\Pr\{Y=0\}=\dfrac{1}{p}\)。
因此，函数簇\(\mathscr{H}\)是全域的。
当\(x\)是一个全\(0\)元组\(x_z\)时，\(\mathscr{H}\)不再是\(2\)-独立的。因为无论\(n\)元组\(a\)如何取值，\(h_a(x_z)=0\)总是成立的。那么对于任意\(x'\in U-\{x_z\},d_1\in \mathbb{Z}_p-\{0\},d_2\in\mathbb{Z}_p\)，都有\(\Pr\{h(x_z)=d_1\land h(x')=d_2\}=0\neq\dfrac{1}{m^2}\)。因此函数簇\(\mathscr{H}\)不满足\(2\)-独立性。
c
可以看出，函数簇\(\mathscr{H}'\)一共有\(p^{n+1}\)个函数。
令\(x,y\in U,x\neq y\)。那么对于任意\(d_x,d_y\in \mathbb{Z_p}\)，可以列出一个\(n+1\)元方程组：
\(\left \{\begin{aligned} & \sum_{i=0}^{n-1}a_ix_i+b\equiv d_x\pmod p\\ & \sum_{i=0}^{n-1}a_iy_i+b\equiv d_y \pmod p\\ \end{aligned}\right.\)
这个线性方程组一共只有两个方程，并且\(a_i,b\)都是未知数。由于\(x\neq y\)，因此这个方程组对应的系数矩阵对值的秩和增广矩阵的秩相等，均为\(2\)。因此，这个线性方程组有\(n-1\)个自由元，也就是说，有\(p^{n-1}\)个解。即\(\mathscr{H}'\)中有\(p^{n-1}\)个函数使得\(h_{ab}'(x)=d_x\land h_{ab}'(y)=d_{y}\).
因此\(\Pr\{h_{ab}'(x)=d_x\land h_{ab}'(y)=d_{y}\}=\dfrac{p^{n-1}}{p^{n+1}}=\dfrac{1}{p^2}\)。
可以看出，函数簇\(\mathscr{H}'\)满足\(2\)-独立性。
d
由于函数簇\(\mathscr{H}\)满足\(2\)-独立性，因此对于任意一对不同消息\(\langle m,m'\rangle\)，它们出现成对的标签\(\langle t,t'\rangle\)在统计上的概率都是相同的，为\(\dfrac{1}{p^2}\)，由于\(t\)是固定的，标签\(t'\)是\(\mathbb{Z}_p\)中等可能的任意一个，因此最多只能以\(\dfrac{1}{p}\)的概率伪造出来。