高级算法 (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 10: | Line 10: | ||
# The Method of Four Russians 说到底就是分块并打表。使用 The Method of Four Russians, 构造一个大小为 <math> O(n^{1/c}\log n) </math> bits 的 pre-computed look-up table（其中 <math>c</math> 是一个可以自由调节的参数）来在课堂上提到的大小为 <math> O(\log n) </math> bits 的 Trie 上以 <math> O(c) </math> 的时间快速查找Trie 中是否有一个串是查询串的前缀，并返回对应的串的在 Trie 中的字典序。 | # The Method of Four Russians 说到底就是分块并打表。使用 The Method of Four Russians, 构造一个大小为 <math> O(n^{1/c}\log n) </math> bits 的 pre-computed look-up table（其中 <math>c</math> 是一个可以自由调节的参数）来在课堂上提到的大小为 <math> O(\log n) </math> bits 的 Trie 上以 <math> O(c) </math> 的时间快速查找Trie 中是否有一个串是查询串的前缀，并返回对应的串的在 Trie 中的字典序。 | ||
# 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。 | ||
# Chernoff bound with limited independence: | |||
## occupancy problem 中如果使用的是 <math>k</math>-universal hash function family 来放置小球，那么在课堂中讲过的两种情况下 w.h.p. maximum load 分别是多少？ | |||
## 构造一组两两独立的 hash function family，使得 <math>n</math> balls into <math>n</math> bins 的情况下 maximum load 很高，并证明你的结论。 | |||
# 课程中介绍的 tabulation hashing 被称为 simple tabulation hashing。 tabulation hashing 还有不少别的扩展和强化。尝试调查并介绍其中一些（你需要使用正规 citation 指出该算法的来源），并尝试解释该 tabulation hashing 克服了其他 tabulation hashing 的什么问题，有什么优点和缺点，尝试解释为什么。你也可以调查一个你喜欢的哈希函数。你的分数取决于你的解释的详细程度和准确程度。 | |||
Revision as of 14:55, 26 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]）
- The Method of Four Russians 说到底就是分块并打表。使用 The Method of Four Russians, 构造一个大小为 [math]\displaystyle{ O(n^{1/c}\log n) }[/math] bits 的 pre-computed look-up table（其中 [math]\displaystyle{ c }[/math] 是一个可以自由调节的参数）来在课堂上提到的大小为 [math]\displaystyle{ O(\log n) }[/math] bits 的 Trie 上以 [math]\displaystyle{ O(c) }[/math] 的时间快速查找Trie 中是否有一个串是查询串的前缀，并返回对应的串的在 Trie 中的字典序。
- 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。
- Chernoff bound with limited independence:
- occupancy problem 中如果使用的是 [math]\displaystyle{ k }[/math]-universal hash function family 来放置小球，那么在课堂中讲过的两种情况下 w.h.p. maximum load 分别是多少？
- 构造一组两两独立的 hash function family，使得 [math]\displaystyle{ n }[/math] balls into [math]\displaystyle{ n }[/math] bins 的情况下 maximum load 很高，并证明你的结论。
- 课程中介绍的 tabulation hashing 被称为 simple tabulation hashing。 tabulation hashing 还有不少别的扩展和强化。尝试调查并介绍其中一些（你需要使用正规 citation 指出该算法的来源），并尝试解释该 tabulation hashing 克服了其他 tabulation hashing 的什么问题，有什么优点和缺点，尝试解释为什么。你也可以调查一个你喜欢的哈希函数。你的分数取决于你的解释的详细程度和准确程度。