高级算法 (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]）