高级算法 (Spring 2026)/作业2

• 每道题目的解答都要有完整的解题过程，中英文不限。
• 我们推荐大家使用LaTeX, markdown等对作业进行排版。
• 没有条件的同学可以用纸笔完成作业之后拍照。
• 本门课的所有作业中如果出现了课程中（包括课件中和作业题目中）的算法或者概念或者符号，则禁止使用自己发明的说法或者符号，必须与课程内容保持一致。

1. 将 power of two choices 扩展到 power of [math]\displaystyle{ d }[/math] choices。此时 maximum load 是多少？分析和证明你的结论。
2. 计算 FKS perfect hashing 的空间开销的期望和方差，并使用切比雪夫不等式证明其空间开销以高概率不超过 [math]\displaystyle{ 10n }[/math].
3. 对于 FKS perfect hashing 如果调整第一层的桶的数目（不是 [math]\displaystyle{ n }[/math] 而是另一个供你自由调节的参数 [math]\displaystyle{ n' }[/math]），你可以得到空间复杂度更优秀的哈希表吗？分析并证明你的结论。
4. 当 Cuckoo hashing 的 负载率达到 [math]\displaystyle{ 0.500001 }[/math] 时，插入失败的概率是多少？（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]）
5. 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 中的字典序。
6. 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。
7. Limited independence meets occupancy:
   • Occupancy problem 中如果使用的是 [math]\displaystyle{ k }[/math]-universal hash function family 来放置小球，那么在课堂中讲过的两种情况下以至少 [math]\displaystyle{ 1-o(1) }[/math] 的概率 maximum load 分别是多少？
   • 构造一组两两独立的 hash function family，使得 [math]\displaystyle{ n }[/math] balls into [math]\displaystyle{ n }[/math] bins 的情况下 maximum load 很高，并证明你的结论。
8. 课程中介绍的 tabulation hashing 被称为 simple tabulation hashing。 tabulation hashing 还有不少别的扩展和强化。尝试调查并介绍其中一些（你需要使用正规 citation 指出该算法的来源），并尝试解释该 tabulation hashing 克服了其他 tabulation hashing 的什么问题，有什么优点和缺点，尝试解释为什么。你也可以调查一个你喜欢的哈希函数。你的分数取决于你的解释的详细程度和准确程度。