Joey

来源: 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 个选项，随机猜是否比不答更好？

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 10 - Linear Programming and Randomised Rounding, Week 10 - Tutorial 10 (Solutions)

---

Part 1: Tutorial 10 详细题解

各题难度/要求说明：

• Problems 1, 2, 3：需看过讲义，应自行尝试，对理解算法很重要。（Problem 3 将本周内容与第 4 章的去随机化联系起来。）
• Problem 4：需用 Matlab 比较算法，实践线性规划库。
• Problem 5：大体可做，子题 c) 较难（⋆）。
• Problem 6：技术性较强、难度较高，是检验是否理解讲义证明的好题。
• Problem 7：有时间则做，进阶练习，题解未提供。

---

Problem 1（Warm-up）：LP vs ILP

题目：回顾定义，总结 LP 和 ILP 的关键区别。

解答：

线性规划（LP，Linear Program）： - 在连续域上优化线性目标函数，满足线性约束 - 数学形式：，约束 ， - LP 是 P-complete：每个多项式时间可解的决策问题都可以表示为某个 LP - 存在多项式时间算法（单纯形法、内点法等）高效求解

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

---

Part 1: Tutorial 8 详细题解

本部分按官方 Solutions PDF整理，每题含完整题目和逐步展开的详细解答。

Tutorial 难度总览

题目	所属部分	难度	复习建议
Problem 1	Warm-up	需读讲义；median-of-means 证明梳理	必做：理解为什么要"均值的中位数"
Problem 2	Warm-up	需读讲义；"mean-of-medians" 对比	概念题：理解顺序不能互换
Problem 3	Warm-up	需读讲义；BJKST 真随机 vs 强 universal	概念题：理解强 universal 省空间的作用
Problem 4	Warm-up	需读讲义；BJKST 用 的原因	概念题：理解两层哈希省空间
Problem 5	Problem Solving	重要，必须检查是否理解 Morris Counter	重点：逐步推导 careful variant 的期望、方差和空间
Problem 6	Problem Solving	短但需要关键想法；若没思路可直接看解答	推荐：Heavy Hitters 如何从 Misra-Gries 修改得到
Problem 7	Problem Solving	较复杂，但有价值；可以跳过但要看算法和解答	推荐：Bottom- 算法的 distinct elements 分析
Problem 8	Advanced	了解即可	扩展：流式 JL 降维计算均值向量大小

---

Problem 1: Morris Counter 的 median-of-means 证明梳理

题目: 过一遍 Morris Counter 的"median-of-means"证明，理解为什么需要这个技巧。

题解: