高级算法 (Spring 2025)/作业一: Difference between revisions
Jump to navigation
Jump to search
Liumingmou (talk | contribs) Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 *没有条件的同学可以用纸笔完成作业之后拍照。 # 解释 Morris’ counter 背后的直觉。尝试应用 <math>(1+\alpha)^{-X}</math> 的思路得到更好的结果。 # 尝试把 median-trick 用到 FM 算法上，并分析你的算法的正确性和复杂度。 # 尝试分析 HyperLogLog 的正确性。 # 尝..." |
Liumingmou (talk | contribs) No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 4: | Line 4: | ||
# 解释 Morris’ counter 背后的直觉。尝试应用 <math>(1+\alpha)^{-X}</math> 的思路得到更好的结果。 | # 解释 Morris’ counter 背后的直觉。尝试应用 <math>(1+\alpha)^{-X}</math> 的思路得到更好的结果。 | ||
# 尝试把 median | # 尝试把 median trick 用到 FM 算法上，并分析你的算法的正确性和复杂度。 | ||
# 尝试分析 HyperLogLog 的正确性。 | # 尝试分析 HyperLogLog 的正确性。 | ||
# 尝试完善和分析 fast Count | # 尝试完善和分析 fast Count Min Sketch。 | ||
# 设计一个支持删除的 filter （即设计一个可以维护多重集的数据结构），并分析其复杂度。（复杂度越低，得分越高） | # 设计一个支持删除的 filter （即设计一个可以维护多重集的数据结构），并分析其复杂度。（复杂度越低，得分越高） | ||
# 将 power of two choices 扩展到 power of <math>d</math> choices。此时 maximum load 是多少？试分析和证明你的结论。 | # 将 power of two choices 扩展到 power of <math>d</math> choices。此时 maximum load 是多少？试分析和证明你的结论。 | ||
# 我们在对 cuckoo hashing 的分析中假设了我们的哈希函数是真随机的。如果它是 pairwise independent，会有什么问题？尝试计算这些问题出现的概率。 | # 我们在对 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。 | # 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。 | ||
Latest revision as of 16:20, 24 April 2025
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用LaTeX, markdown等对作业进行排版。
- 没有条件的同学可以用纸笔完成作业之后拍照。
- 解释 Morris’ counter 背后的直觉。尝试应用 [math]\displaystyle{ (1+\alpha)^{-X} }[/math] 的思路得到更好的结果。
- 尝试把 median trick 用到 FM 算法上，并分析你的算法的正确性和复杂度。
- 尝试分析 HyperLogLog 的正确性。
- 尝试完善和分析 fast Count Min Sketch。
- 设计一个支持删除的 filter （即设计一个可以维护多重集的数据结构），并分析其复杂度。（复杂度越低，得分越高）
- 将 power of two choices 扩展到 power of [math]\displaystyle{ d }[/math] choices。此时 maximum load 是多少？试分析和证明你的结论。
- 我们在对 cuckoo hashing 的分析中假设了我们的哈希函数是真随机的。如果它是 pairwise independent，会有什么问题？尝试计算这些问题出现的概率。
- 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。