Joey

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

课程: 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 - 存在多项式时间算法（单纯形法、内点法等）高效求解