Joey

COMP5270 Assignment 1 marked solutions 中文题解，覆盖随机集合、离散随机比特、balls into bins 和星形图采样。

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 5 - Graph algorithms, Week 5 - Tutorial 5 (Solutions)

---

这周到底在学什么？（先看这里）

Week 5 的关键词是 随机化图算法。这周不只是在学 Karger 算法的步骤，而是在训练一种分析思维：

随机做一个看似危险的操作（随机选边、收缩），然后证明它破坏最优解的概率不大。概率不大 → 重复几次就能成功。

这周有两条主线：

1. Minimum Cut（最小割）：用随机 contraction（收缩边）来找图里最小的 cut。
2. Minimum Spanning Tree（最小生成树，MST）：用随机采样 + cut/cycle property 来删除不可能属于 MST 的边，做到期望线性时间。

别被名词吓到。下面把每个概念都用大白话解释清楚。

先统一语言：图论基础词汇

• 图记作 。 是顶点（点）的集合， 是边（连线）的集合。
• （有多少个点）， （有多少条边）。
• cut（割）：把顶点分成两组，比如 。"把一群人分成两队"就是 cut。
• crossing edge（跨割边）：一端在左边组、一端在右边组的边。
• cut 的大小：crossing edges 的数量。加权图里是 crossing edges 的权重和。
• min-cut（最小割）：大小最小的 cut。记最小割的值为 。

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 12 - Learning from Experts, Week 12 - Tutorial 12 (Solutions)

---

Part 1: Tutorial 12 详细题解

各题难度/要求说明：

• Problems 1–3：课后可自行尝试，有困难时可在 tutorial 求助，但之后应自己完成。
• Problem 4（⋆）：技术性较强，好练习，时间有限时可跳过只看答案。
• Problems 5, 6（进阶）：好练习，较长、引导较少，在 tutorial 中讨论，有时间则自行或小组完成。

---

Problem 1（Warm-up）：Theorem 61 和 62 的参数绘图

题目：对 绘制 Theorem 61 和 Theorem 62 的误差界，考察不同的 ， 。

解答：

（编程练习，Mathematica 代码如下）