Joey

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 9 Lecture Notes & Tutorial 9 Solutions

---

Part 1: Tutorial 9 详细题解

本部分按官方 Solutions PDF整理，每题含完整题目和逐步展开的详细解答。 注：Tutorial 9 也要求完成 Week 8 的 Problem 3 和 Problem 4（关于 BJKST）。

Tutorial 难度总览

题目	所属部分	难度	复习建议
Problem 1	Warm-up	需读讲义；Bloom Filter ↔︎ CountMinSketch 类比	概念题：理解 AND(bits) = MIN(bits)
Problem 2	Warm-up	不必读讲义；ℓ_p 范数单调性	理解即可：
Problem 3	Warm-up	需读讲义；MG vs CMS 对比	重点：理解优缺取舍
Problem 4	Problem Solving	重要；CS vs CMS 同空间预算	重点：误差比较
Problem 5	Problem Solving	可选；CMS 在 turnstile 模型	理解 Markov 需要非负
Problem 6	Advanced	重要；证明 MG 是 sketching	重点：如何合并两个 MG sketch
Problem 7	Advanced	扩展；CMS 求 ℓ₁ Heavy Hitters	了解思路即可

---

Problem 1: Bloom Filter ↔︎ CountMinSketch 类比

题目: 讨论 Bloom Filter 和 CountMinSketch 之间的平行关系。

题解:

来源: Sample Exam #2.pdf
说明: 原 PDF 是 sample exam 题目册，没有附官方 solutions。下面是按课程讲义和 tutorial/assignment 思路整理的中文详细题解。
重点: SetCover 的 LP rounding、Las Vegas expected time 的坑、dyadic intervals + CountMinSketch 做 range counting。

---

总览

题目	分值	主题
Problem 1	10	MCQ，覆盖 LV/MC、balls in bins、hashing、KKT、LSH、Max-Cut
Problem 2	15	SetCover 的 ILP/LP relaxation 和 randomized rounding
Problem 3	15	条件期望运行时间 的 Las Vegas algorithm
Problem 4	20	streaming range counting，dyadic intervals，CountMinSketch

---

Problem 1: Multiple Choice

每小题 1 分，答错 0 分，不答 0.5 分。

(1)

题意：如果这 10 道 MCQ 只回答自己非常有把握的题，期望分数是否至少 5？

答案：True。

来源: Sample Exam #1.pdf
说明: 原 PDF 是 sample exam 题目册，没有附官方 solutions。下面是按课程讲义和 tutorial/assignment 思路整理的中文详细题解。
重点: MIS 的 LP relaxation + randomized rounding、triangle counting estimator、streaming reservoir sampling。

---

总览

这份 sample exam 一共 4 题：

题目	分值	主题
Problem 1	10	MCQ，覆盖随机算法、hashing、Bloom filter、LP、LSH
Problem 2	15	Maximum Independent Set 的 ILP/LP relaxation 和 randomized rounding
Problem 3	15	在 query access 下估计 triangle 数量
Problem 4	20	one-pass streaming 下 uniform edge sampling，并接上 Problem 3 的 triangle estimator

---

Problem 1: Multiple Choice

每小题 1 分，答错 0 分，不答 0.5 分。

(1)

题意：如果一道 MCQ 有 3 个选项，随机猜是否比不答更好？