算法导论第十一章思考题参考答案(21)

Ploblem 11-1

a.从所有可能的索引中统一计算每个探针的索引。由于我们有 n≤m/2，我们知道在任何阶段至少有一半的指标是空的。因此，对于需要超过 k 个探针，我们需要在每 k 个第一个探针中，我们探测到一个已经有一个入口的顶点，这个概率小于 1/2，所以每次发生的概率小于 1/(2k)。

b.使用前一部分k=2lg (n)的结果，我们得到需要这么多探针的概率是

c.我们应用上一部分结果后的联合界

d.探测序列的最长可能长度是 n，因为我们会尝试检查数组中已经放置的每一个条目。我们还知道，需要长度大于 2lg (n)的序列的概率≤1/n。所以，我们知道期望值的最大值是

Ploblem 11-2

a.设 Qk 表示恰好有 k 个键散列到特定槽的概率。有 $\binom{n}{k}$ 种方法可以选择 k 个键，它们以 $(\frac{1}{n})^{k}$ 的概率散列到那个位置，并将剩余的 n− k 个键散列到剩余的 n− 1 个槽的概率。因此，。

b.包含最多键的槽恰好包含 k 个键的概率在上面以某个槽包含 k 个键的概率为界。我们可以选择 n 个槽来包含这 k 个键，所以 Pk ≤nQk。

c.利用，我们有。

d.我们想让 Qk0 < n^3，对两边取对数，用对数法则展开，这就变成了

两边同时除以- lglgn 就等于

当 n→∞时，除最后一项外的所有项都趋于 0，因此对于 N 的某个固定值，选择 c = 4 适用于所有 n > N，设 ci 表示 n = i 时适用的值，然后通过令 ci= maxi(ci, 4)我们得到 c 的期望值，通过(b)部分，我们得到 Pk0≤nQk0< n/n^3 = 1/n^2。由于 Qk 是 k 的递减函数，我们得出对于所有 k≥k0, Pk< 1/n^2。

e.这来自于通过条件作用计算期望，并在第一项中将 M 从上到下限定为 n。从(d)中的边界我们得到nP(M >clgn / lglgn) < 1。对于第二项，，其中，因此有渐近期望。

Ploblem 11-3

a.在每一步中，我们增加的量增加1，因此，这导致了公式 $\frac{i^{2}+i}{2}$ 的“高斯数”。我们有c1=c2=1/2

b.为了证明这个算法检查每个数字，我们将证明它检查的每个数字都是不同的。然后，由于它总共检查了 m 个数字，这意味着每个数字都被访问了。假设我们在两个不同的回合 $i<i'<m$ ，则

。

这意味着

因此，

重新排列,

所以，

现在，我们根据 i - i' 是偶数还是奇数分成两种情况。如果 i' - i是奇数，那么我们可以在两边消去它，因为它和 2m 没有公因数 (因为 m 是 2 的幂)，这就留给我们

因为 i < i'，我们有 i+ i' + 1≤ 2i' < 2 m，所以，我们必须有 i+ i' + 1 = 0，这与我们假设这样的 i 和 i' 存在的假设相矛盾。

如果我们有 i'- i 是偶数，那么 i+ i' + 1 是奇数，所以它与 2m 没有公因式。类似地，这意味着我们可以消去这个因子得到 i' - i ≡ 0 mod 2m。然而，我们有 |i' − i|≤ i' +i <2i' < 2m。因此，我们必须有 i' - i = 0，这与我们选择 i 和 i' 的方式相矛盾。

Ploblem 11-4

a.设 k, l∈U 是任意的。然后 P(h(k) = h(l)) = P(<h(k), h(l)> = < x, x >)对于一些 x∈[m]。由于 h 来自一组 2-全域哈希函数，因此这同样有可能是其中 m^2 的任何一个结果。有m个可能的 x值会导致碰撞，所以碰撞的概率是。

b.碰撞的概率是1/p，所以H是全称的。现在考虑元组 z =< 0, 0，… ， 0 >。则 ha (x) = hb (x) = 0，对于任意 a, b∈ U，因此序列< z, x^(2) >等可能是从 0 开始的 p 个序列中的任何一个，但不可能是其他 p^2 − p 个序列中的任何一个，因此 h 不是 2-全称的。

c.设 x , y∈ U 是固定的、不同的 n 元组。当 ai 和 b 的取值范围在 Zp 上时，同样有可能达到从 1 到 p 的所有值，因为对于任何序列 a，我们可以让 b 从 1 变化到 p − 1。因此，< h'ab(x)，h'ab(y)> 同样有可能是 p^2 个序列中的任意一个序列，因此 H 是 2-全域的。

d.由于 H 是 2-全称的，因此有 p 个其他函数将 m映射到 h (m)，并且对手无法知道 Alice 和 Bob 事先同意了其中的哪一个，因此他能做的最好的事情就是尝试其中的一个，这将成功地以 1/p 的概率愚弄 Bob。