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

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

# 解释 Morris’ counter 背后的直觉。尝试应用 <math>(1+\alpha)^{-X}</math> 的思路得到更好的结果。
# 尝试把 median-trick 用到 FM 算法上，并分析你的算法的正确性和复杂度。
# 尝试分析 HyperLogLog 的正确性。
# 尝试完善和分析 fast Count Mean Sketch。
# 设计一个支持删除的 filter （即设计一个可以维护多重集的数据结构），并分析其复杂度。（复杂度越低，得分越高）
# 将 power of two choices 扩展到 power of <math>d</math> choices。此时 maximum load 是多少？试分析和证明你的结论。
# 我们在对 cuckoo hashing 的分析中假设了我们的哈希函数是真随机的。如果它是 pairwise independent，会有什么问题？尝试计算这些问题出现的概率。
# Feistel cipher / Feistel permutation 是一种双射，按如下方式运行： <math>(x_1,x_2) \mapsto (f(x_1)\oplus x_2,x_2)</math>。若假设所有的 <math>x_2</math> 都不相同，且哈希函数 <math>h</math> 是 <math>k</math>-universal ，则 Feistel cipher 可以把 <math>x_1\in\{0,1\}^t</math> 以 <math>k</math>-universal 的方式均匀随机地映射到 <math>\{0,1\}^t</math> 中。请构造一个一般的 Feistel cipher，若所有的 <math>x_2</math> 都不相同，则新的 Feistel cipher 将 <math>x_1\in[n]</math> 以 <math>k</math>-universal 的方式均匀随机地映射到 <math>[n]</math> 中，并证明它是 <math>k</math>-universal。