Joey

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 9 - Streaming and Sketching II, Week 9 - Tutorial 9 (Solutions)

---

Part 1: Tutorial 9 详细题解

Tutorial 9 开头说明：还应补做 Week 8 tutorial 的 Problems 3 和 4（上周未覆盖）。各题难度/要求如下：

• Problem 1（Warm-up）：Discussion，理解概念类。
• Problem 2（⋆ 选做）：ℓ_p 范数单调性证明，有用的数学事实，可跳过后看答案。
• Problems 3, 4：需看过讲义，但应自行尝试；对于理解算法很重要。
• Problem 5：有时间则做，否则可跳过后看答案。
• Problem 6：难度较高（⋆），值得做以理解 Misra-Gries 为何是 sketching 算法。
• Problem 7：有时间则做，否则可跳过。

---

Problem 1（Warm-up）：Bloom Filter vs Count-Min-Sketch 的类比

题目：讨论 Bloom Filter 和 Count-Min-Sketch 之间的相似性。

解答：

可以把 Count-Min-Sketch 看作 Bloom Filter 的"计数版本"：

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 6 - Hashing and Friends, Week 6 - Going further, Week 6 - Tutorial 6 (Solutions)

---

Part 1: Tutorial 6 详细题解

如果 dictionary / universe / bucket / collision / load factor / chaining / universal hashing / Bloom filter 这些词还不熟，先看下面 Part 2 的「0. 名词与符号速查」，再回来读题解。

本部分按官方 Solutions PDF（Week 6 - Tutorial 6 (Solutions)）整理：每题先给完整题目，再按官方解的思路逐步展开；所有结论与官方一致，比官方更细的推导步骤会标注 【展开】。与 Part 2 讲义详解的对应位置随处交叉引用。

Tutorial 开头的难度/要求说明

Tutorial 6 开头给了每题的建议投入程度（官方原话翻译）。先整理成总览，后面每道题标题下也单独标出。

题目	所属部分	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	Warm-up	需要读讲义或看 lecture，但应该 doable	先分清 hash table 与 Bloom filter 的 guarantee
Problem 2	Warm-up	需要读讲义或看 lecture，但应该 doable	必做，练 universal hashing + indicator 的标准分析
Problem 3	Problem Solving	可以在 lecture 前尝试；跳过也没关系	用来理解 universal 定义里的 不是
Problem 4	Problem Solving	需要几个 non-trivial ideas；概念和算法上都 interesting	值得认真做，练「用 hash table 砍掉一重循环」
Problem 5	Problem Solving	quite important；务必尝试并读 solution	重点题，perfect hashing 的 空间证明很常考
Problem 6	Problem Solving	quite important，尤其这题；务必尝试并读 solution	重点题，Bloom filter 错误率公式与最优 必须会推
Problem 7	Advanced	有时间值得做，但 not crucial	扩展题，理解删除如何破坏 one-sided error

Warm-up

Problem 1: Hash table 和 Bloom filter 的区别

Tutorial 难度/要求: Warm-up；需要读讲义或看 lecture，但应该 doable。

硅谷反思 AI 过度依赖引发深度讨论，Anthropic 首次完整公开 Claude 四层沙箱隔离体系，Cosmos Gravity Bridge 遭 540 万美元黑客攻击。