高级算法 (Spring 2026)/作业2: Difference between revisions
Jump to navigation
Jump to search
Liumingmou (talk | contribs) No edit summary |
Liumingmou (talk | contribs) No edit summary |
||
| Line 6: | Line 6: | ||
# 将 power of two choices 扩展到 power of <math>d</math> choices。此时 maximum load 是多少？尝试分析和证明你的结论。 | # 将 power of two choices 扩展到 power of <math>d</math> choices。此时 maximum load 是多少？尝试分析和证明你的结论。 | ||
# 计算 FKS perfect hashing 的空间开销的期望和方差，并使用切比雪夫不等式证明其空间开销以高概率不超过 <math>10n</math>. | # 计算 FKS perfect hashing 的空间开销的期望和方差，并使用切比雪夫不等式证明其空间开销以高概率不超过 <math>10n</math>. | ||
# 对于 FKS perfect hashing 如果调整第一层的桶的数目（不是 <math>n</math> 而是另一个供你自由调节的参数 <math>n'</math>），你可以得到空间复杂度更优秀的哈希表吗？ | |||
# 当 Cuckoo hashing 的 负载率超过 1/2 时，插入失败的概率是多少？（Hint. Let <math> G(m, c/m)</math> be Erdős–Rényi random graph with <math>c>1</math>. Then with probability <math>1-o(1)</math>, there exists a connected component <math>H</math> satisfying <math>|V(H)| \ge \Omega(m)</math> and <math>|E(H)| - |V(H)| = \Omega( m). </math>） | # 当 Cuckoo hashing 的 负载率超过 1/2 时，插入失败的概率是多少？（Hint. Let <math> G(m, c/m)</math> be Erdős–Rényi random graph with <math>c>1</math>. Then with probability <math>1-o(1)</math>, there exists a connected component <math>H</math> satisfying <math>|V(H)| \ge \Omega(m)</math> and <math>|E(H)| - |V(H)| = \Omega( m). </math>） | ||
Revision as of 16:19, 19 April 2026
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用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]）