算法导论11 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

11-1

a

令随机变量$Xi$表示第$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{Xi>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{Xi>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 Ai\right}\
&\le \sum{i=1}^n \Pr{Ai}\
&= \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
2
3
4
5
6
7
8
9
10
ORDERED-SEAECH(A, n, k)
  l = 1
  r = n
  while l < r
    mid = ⌊(l + r) / 2⌋
    if A[mid] >= k
      l = mid
    else
      r = mid - 1
  return l <= n and A[l] == 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}$的二项分布，即

b

令随机变量$Xi$表示第$i$个槽中的链的长度。令事件$A_i$表示$X_i=k$，事件$A=\displaystyle{\bigcap{i=1}^n A_i}$。那么有

$\begin{aligned}
Pk&\le \Pr{A} &\qquad(A)\
&=\Pr\left{\bigcap{i=1}^n Ai\right}\
&\le \sum{i=1}^n \Pr{Ai}\
&= \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$取对数，移项后得到

代入$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$，令$k0=\dfrac{c\lg n}{\lg\lg n},Q{k_0}<\dfrac{1}{n^3}$总成立。

由于$c>1,n>2$，那么可以知道$k0\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{k0}< nQ{k_0}<\dfrac{1}{n^2}$均成立。

e

$\begin{aligned}
E[M]&=\sum{k=1}^n k\cdot P_k\
&=\sum{k=1}^{k0} k\cdot P_k+\sum{k=k0+1}^n k\cdot P_k\
&\le\sum{k=1}^{k0} 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>k0}$的上限，有$\displaystyle{\Pr{M>k_0}=\sum{i=k0+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(k1)=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$，考虑$ha(x)=h_a(y)$的概率$\Pr{h_a(x)=h_a(y)}$，即$\displaystyle{\sum{i=0}^{n-1}aix_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.$

这个线性方程组一共只有两个方程，并且$ai,b$都是未知数。由于$x\neq y$，因此这个方程组对应的系数矩阵对值的秩和增广矩阵的秩相等，均为$2$。因此，这个线性方程组有$n-1$个自由元，也就是说，有$p^{n-1}$个解。即$\mathscr{H}’$中有$p^{n-1}$个函数使得$h{ab}’(x)=dx\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}$的概率伪造出来。