高级算法 (Spring 2025)/作业一

• 每道题目的解答都要有完整的解题过程，中英文不限。
• 我们推荐大家使用LaTeX, markdown等对作业进行排版。
• 没有条件的同学可以用纸笔完成作业之后拍照。

1. 解释 Morris’ counter 背后的直觉。尝试应用 [math]\displaystyle{ (1+\alpha)^{-X} }[/math] 的思路得到更好的结果。
2. 尝试把 median trick 用到 FM 算法上，并分析你的算法的正确性和复杂度。
3. 尝试分析 HyperLogLog 的正确性。
4. 尝试完善和分析 fast Count Min Sketch。
5. 设计一个支持删除的 filter （即设计一个可以维护多重集的数据结构），并分析其复杂度。（复杂度越低，得分越高）
6. 将 power of two choices 扩展到 power of [math]\displaystyle{ d }[/math] choices。此时 maximum load 是多少？试分析和证明你的结论。
7. 我们在对 cuckoo hashing 的分析中假设了我们的哈希函数是真随机的。如果它是 pairwise independent，会有什么问题？尝试计算这些问题出现的概率。
8. 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。