高级算法 (Spring 2026)/作业2
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用LaTeX, markdown等对作业进行排版。
- 没有条件的同学可以用纸笔完成作业之后拍照。
- 本门课的所有作业中如果出现了课程中（包括课件中和作业题目中）的算法或者概念或者符号，则禁止使用自己发明的说法或者符号，必须与课程内容保持一致。
- 将 power of two choices 扩展到 power of [math]\displaystyle{ d }[/math] choices。此时 maximum load 是多少？尝试分析和证明你的结论。
- 计算 FKS perfect hashing 的空间开销的期望和方差，并使用切比雪夫不等式证明其空间开销以高概率不超过 [math]\displaystyle{ 10n }[/math].
- 对于 FKS perfect hashing 如果调整第一层的桶的数目（不是 [math]\displaystyle{ n }[/math] 而是另一个供你自由调节的参数 [math]\displaystyle{ n' }[/math]），你可以得到空间复杂度更优秀的哈希表吗？
- 当 Cuckoo hashing 的 负载率超过 1/2 时，插入失败的概率是多少？（Hint. Let [math]\displaystyle{ G(m, c/m) }[/math] be Erdős–Rényi random graph with [math]\displaystyle{ c\gt 1 }[/math]. Then with probability [math]\displaystyle{ 1-o(1) }[/math], there exists a connected component [math]\displaystyle{ H }[/math] satisfying [math]\displaystyle{ |V(H)| \ge \Omega(m) }[/math] and [math]\displaystyle{ |E(H)| - |V(H)| = \Omega( m). }[/math]）
- The Method of Four Russians 说到底就是分块并打表。使用 The Method of Four Russians, 构造一个大小为 [math]\displaystyle{ O(n^{1/c}\log n) }[/math] bits 的 pre-computed look-up table（其中 [math]\displaystyle{ c }[/math] 是一个可以自由调节的参数）来在课堂上提到的大小为 [math]\displaystyle{ O(\log n) }[/math] bits 的 Trie 上以 [math]\displaystyle{ O(c) }[/math] 的时间快速查找是否有一个 Trie 的串是查询串的前缀，并返回对应的串的在 Trie 中的字典序。
- Feistel cipher / Feistel permutation 是一种双射，按如下方式运行： [math]\displaystyle{ (x_1,x_2) \mapsto (f(x_1)\oplus x_2,x_2) }[/math]。若假设所有的 [math]\displaystyle{ x_2 }[/math] 都不相同，且哈希函数 [math]\displaystyle{ h }[/math] 是 [math]\displaystyle{ k }[/math]-universal ，则 Feistel cipher 可以把 [math]\displaystyle{ x_1\in\{0,1\}^t }[/math] 以 [math]\displaystyle{ k }[/math]-universal 的方式均匀随机地映射到 [math]\displaystyle{ \{0,1\}^t }[/math] 中。请构造一个一般的 Feistel cipher，若所有的 [math]\displaystyle{ x_2 }[/math] 都不相同，则新的 Feistel cipher 将 [math]\displaystyle{ x_1\in[n] }[/math] 以 [math]\displaystyle{ k }[/math]-universal 的方式均匀随机地映射到 [math]\displaystyle{ [n] }[/math] 中，并证明它是 [math]\displaystyle{ k }[/math]-universal。