高级算法 (Spring 2026)/作业2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Newer edit →
Liumingmou (talk | contribs)
321 edits
VisualWikitext
Liumingmou (talk | contribs)
321 edits
Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 *没有条件的同学可以用纸笔完成作业之后拍照。 *本门课的所有作业中如果出现了课程中（包括课件中和作业题目中）的算法或者概念或者符号，则<font color='red'>'''禁止使用自己发明的说法或者符号'''</font>，必须与课程内容保持一致。 # 将 power of two ch..."
 
Liumingmou (talk | contribs)
321 edits
No edit summary
Line 5: Line 5:


# 将 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>.
## 分别使用朴素的真随机哈希函数和power of two choices构造基于拉链法的哈希表。假设我们插入 n keys，哈希表有 n slots，那么每次查询的时候的时间开销的期望和方差大约是多少？时间开销以高概率不会超过多少？
# 当 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>）
## 基于桶的哈希表按照如下方式运行：假设哈希表有 m slots，这个时候我们可以把哈希表分成 <math>m/c</math> 个桶，每个桶容量为 <math>c</math>。每次插入的时候选择一个桶，再到桶内选择一个空的 slots 放入。查询时则遍历桶内所有的 slots，删除则是简单移除对应的 key。 <br/> 分别使用朴素的真随机哈希函数和power of two choices构造基于桶的哈希表。当你的负载率达到大约多少的时候，一次插入的失败概率会高于 <math>1/m^{10}</math>?

Revision as of 14:28, 15 April 2026

  • 每道题目的解答都要有完整的解题过程，中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。
  • 没有条件的同学可以用纸笔完成作业之后拍照。
  • 本门课的所有作业中如果出现了课程中（包括课件中和作业题目中）的算法或者概念或者符号，则禁止使用自己发明的说法或者符号，必须与课程内容保持一致。
  1. 将 power of two choices 扩展到 power of [math]\displaystyle{ d }[/math] choices。此时 maximum load 是多少？尝试分析和证明你的结论。
  2. 计算 FKS perfect hashing 的空间开销的期望和方差，并使用切比雪夫不等式证明其空间开销以高概率不超过 [math]\displaystyle{ 10n }[/math].
  3. 当 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]）
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Spring_2026)/作业2&oldid=13633"