COMP5270 Lecture Summary, Week 1 to Week 7
COMP5270 Lecture Summary, Week 1 to Week 7
这篇笔记根据老师前七周 lecture transcript 整理，目标不是逐字复述，而是把课程真正反复强调的核心思想、方法、工具和作业相关点提炼出来，方便复习和考试前回看。
Week 1, Randomness, Probability, and Algorithms
本周主线
第一周主要做了三件事：
- 介绍课程安排、考核、资源和学习预期
- 用扑克牌同花相邻对的例子引出 linearity of expectation
- 介绍 randomised algorithms 的基本概念，以及 Las Vegas 和 Monte Carlo 两类随机算法
课程安排与考核要点
老师在第一周反复强调了这些事情：
- lecture 有录屏，tutorial 不录屏
- quiz 每周一次，取 best 10 out of 12
- assignment 有 marked part 和 feedback-only optional part
- feedback-only 虽然不计分，但会和 final exam 很接近
- final exam 占比很高，而且有 exam barrier
- simple extension 默认就有 5 天
对做作业最重要的提醒
- marked part 的答案通常应该非常短
- optional 部分是练习题，适合用来准备 final
- 老师更看重你是否真正理解，而不是机械完成
扑克牌例子与 linearity of expectation
老师用 52 张牌洗牌后的“相邻两张同花色”的数量作为例子。
问题是：
在一副均匀随机洗牌后的牌堆里，连续两张牌花色相同的相邻对，期望有多少个？
核心技巧
定义 indicator random variable：
\[ Y_i = \mathbf{1}[\text{第 } i \text{ 张与第 } i+1 \text{ 张同花色}] \]
总数就是：
\[ Y = \sum_{i=1}^{51} Y_i \]
由线性期望：
\[ \mathbb{E}[Y] = \sum_{i=1}^{51} \mathbb{E}[Y_i] \]
而每一项：
\[ \mathbb{E}[Y_i] = \Pr[Y_i = 1] = \frac{12}{51} \]
所以：
\[ \mathbb{E}[Y] = 51 \cdot \frac{12}{51} = 12 \]
真正要学到的东西
这一段最重要的不是 12 这个答案，而是：
- 复杂计数问题可以拆成许多 indicator variables
- linearity of expectation 不需要 independence
- 先做实验、再猜结论、再证明，是很健康的工作流
这是整门课最常反复出现的思想之一。
什么是 randomised algorithm
老师把 deterministic algorithm 和 randomised algorithm 的区别讲得很直白：
- deterministic：同样输入，总是同样输出
- randomised：同样输入，算法过程中还会使用随机位，因此行为可能不同
形式化一点，随机算法可以看成：
- 输入是 \(x\)
- 再额外给一串随机比特 \(r\)
- 输出是 \(A(x,r)\)
也可以理解成：
一个随机算法，其实就是一大族 deterministic algorithms；一旦随机种子固定，算法就固定了。
这个视角在后面讲 derandomisation 时非常重要。
Las Vegas vs Monte Carlo
老师特别强调了这两种随机算法的区别。
Las Vegas
- 输出永远正确
- 但运行时间是随机的
- 只保证 expected running time 小
Monte Carlo
- 运行时间有明确上界
- 但输出可能小概率错误
- 只保证 correct with high probability
老师还强调：
- 课程里默认输入是 worst-case 的，不假设输入随机
- 随机的是算法过程，不是问题实例
为什么要学随机算法
老师在第一周给出的动机很实在：
- 避开 pathological corner cases
- 用更简单的方法得到不错的近似结果
- 有时随机算法比 deterministic 版本更短、更易实现、更快
这其实也奠定了整门课的风格：
不是为了“随机而随机”，而是为了用随机性换取简单性、效率、或可分析性。
Week 2, Concentration Bounds and Tricks
本周主线
第二周主要讲：
- 为什么 expectation 不够
- 如何从 expectation 走向 high-probability guarantee
- 三个核心工具：
- Markov inequality
- Chebyshev inequality
- Chernoff/Hoeffding bounds
- union bound
- Las Vegas / Monte Carlo 之间的转换
- probability amplification
expectation 不够
老师先指出：两个随机变量可以有相同 expectation，但波动完全不同。
所以只知道：
\[ \mathbb{E}[X] \]
还不够。我们还想知道：
- 偏离 expectation 的概率有多大
- 是否大概率集中在 expectation 附近
这就是 concentration bounds 的作用。
Markov inequality
适用条件：
- \(X \ge 0\)
- 已知 \(\mathbb{E}[X]\)
结论：
\[ \Pr[X \ge t] \le \frac{\mathbb{E}[X]}{t} \]
用途
- 很弱，但几乎不要条件
- 常用来把 expected-time Las Vegas algorithm 截断成 Monte Carlo algorithm
老师给的典型应用是：
- 如果算法 expected running time 至多为 \(T\)
- 就运行它最多 \(100T\) 步
- 超时就 abort
- 则失败概率至多 \(1\%\)
这就是 Las Vegas \(\to\) Monte Carlo 的第一个标准方法。
Chebyshev inequality
适用条件：
- 已知 expectation
- 已知 variance
结论：
\[ \Pr[|X - \mathbb{E}[X]| \ge t] \le \frac{\mathrm{Var}(X)}{t^2} \]
特点
- 比 Markov 强
- 双侧控制偏差
- 但需要 variance
老师也强调了一个很重要的分析现实：
expectation 常常比较好算，variance 往往更麻烦。
因此课程里后来经常会用一些技巧来避免硬算 variance，比如：
- negative correlation
- second moment bound
- pairwise independence 足够推出 variance additivity
Chernoff / Hoeffding
这两个 bound 的场景更强：
- 变量通常是独立的
- 并且可以写成一堆 bounded random variables 的和
直觉上它们告诉你
如果很多独立小随机变量相加，那么结果会以指数速度集中在期望附近。
也就是说偏离很大时，概率不是多项式级别小，而是指数级别小。
这是后面所有高概率算法分析的关键。
union bound
这是老师反复强调的另一个万能工具：
\[ \Pr\left[\bigcup_i E_i\right] \le \sum_i \Pr[E_i] \]
它看起来很朴素，但课程里几乎所有“把单个对象的成功概率扩展到所有对象同时成功”的地方，都会用到它。
后面包括：
- Karger 列举所有 minimum cuts
- 多点同时保距的 JL lemma
- 各种 high-probability argument
都会反复出现 union bound。
probability amplification
如果一个 Monte Carlo algorithm 成功概率只是常数，比如：
\[ \Pr[\text{success}] \ge \frac{2}{3} \]
那怎么办？
老师给的套路是：
- 独立重复运行多次
- decision problem 取 majority vote
- numerical output 取 median
这样可以把失败概率压到：
\[ \delta \]
同时只增加：
\[ O(\log(1/\delta)) \]
倍的开销。
这个思想后面会反复见到。
birthday paradox 与 balls-in-bins
老师用 birthday paradox 引出 balls-in-bins 的经典估计：
- 把 \(m\) 个球随机扔进 \(n\) 个箱子
- 什么时候开始大概率出现碰撞？
结论量级是：
\[ m = \Theta(\sqrt{n}) \]
而且老师还进一步总结出：
- 出现 \(k\)-way collision 的量级大约是
\[ m = \Theta\left(n^{(k-1)/k}\right) \]
这些结论对 hashing 和后续作业题都很有帮助。
Week 3, Balls in Bins and Broader Motivation
本周主线
第三周延续 balls-in-bins，并开始把课程内容和 industry / real-world use cases 联系起来。
老师特别强调：
- 课程虽然理论味很重
- 但 hashing、dimension reduction、nearest neighbour、streaming/sketching 都和工业界密切相关
balls-in-bins 的核心训练目标
这部分不是为了让你背结论，而是训练你：
- 先看 expectation
- 再看 variance / concentration
- 学会估计 threshold 和 phase transition
例如：
- collision 何时出现
- coupon collector 何时覆盖全部 bins
- 高阶 collision 何时开始出现
这些都在训练“规模量级感”。
与 industry 的联系
老师在这一周主动补充了很多现实应用：
Hashing
- 基础数据结构实现
- consistent hashing
- CDN / large-scale infrastructure
- Akamai 等系统背后的关键思想
Dimension reduction
- 高维数据分析
- embedding
- 文本向量
- 医疗记录等多维特征处理
Nearest neighbours
- clustering
- retrieval
- 向量搜索
- 大模型推理加速中的相关思想
Streaming / Sketching
- IoT
- 分布式系统
- 在内存有限或不能完整存储输入时做近似统计
这周的意义很大，因为它告诉你：
这门课不是只为了“考题”，而是在讲很多现代计算系统里真的会用到的方法论。
Week 4, Derandomisation
本周主线
第四周讲的是：
如果随机算法很好用，那能不能把随机性去掉？
也就是 derandomisation。
老师主要讲了三条路：
- pseudorandom generators (PRGs)
- brute-force over all random seeds
- 减少算法真正需要的随机位数
derandomisation 的总问题
老师提出的核心问题是：
- 已知存在一个随机算法，运行时间为 \(T(n)\)
- 能否推出存在一个 deterministic algorithm？
- 最好的 running time 能做到多少？
一般来说，我们只知道很弱的结论：
- 若随机算法用了 \(r\) 个随机比特
- 那么可以枚举所有 \(2^r\) 个随机种子
- 因此能得到一个 deterministic algorithm
- 但时间会指数爆炸
这就是最朴素的 derandomisation。
PRG 的思想
PRG 的核心是：
- 用很短的 truly random seed
- 生成看起来很长、很随机的 bit string
- 只要它“骗过”目标算法，就够用了
老师强调的重点不是构造细节，而是思想：
你不需要真的拥有那么多随机性，你只需要拥有“足够骗过算法”的随机性。
如果 PRG 足够强，那么：
- 原来需要 polynomially many random bits 的算法
- 只需要 logarithmically many true random bits
- 再配合 brute force over all seeds
- 就可能得到 polynomial-time derandomisation
但老师也明确说了：
- 这依赖一些复杂的 complexity-theoretic assumptions
- 不是课程里要你构造出来的东西
brute force over seeds
如果一个算法只用了 \(r\) 个随机比特，那么总共只有：
\[ 2^r \]
种可能运行。
所以只要满足下面任一条件，就可以尝试枚举：
情况 1，有 verifier
- 能验证给定输出是否正确
- 那就枚举所有种子
- 一旦找到合法输出就停
情况 2，是 decision problem
- 输出只有 yes / no
- 若算法成功概率严格大于 \(1/2\)
- 则正确答案会在所有种子中占多数
- 直接 majority vote 即可
情况 3，输出是数值且存在 good interval
- 可用 median trick
- 大部分结果落在正确区间里
- 则中位数也会落在区间里
这三类技巧构成了课程里非常重要的一组模板。
pairwise independence 的作用
本周另一个对作业非常关键的点，是老师强调：
很多地方其实不需要 full independence，只需要 pairwise independence。
例如 MaxCut 随机划分分析里，真正用到的只是：
- 对任意一条边两端点的随机位彼此独立
并不需要所有顶点的随机位全部 jointly independent。
这就给了 derandomisation 的空间：
- 不必用 \(n\) 个真随机位
- 用一个小 seed 定义一族 pairwise independent hash functions
- 就足够模拟算法分析所需的独立性
这正是 Assignment 2 的关键背景。
Week 5, Graph Algorithms and Karger Min-Cut
本周主线
第五周讲图算法，核心是：
- minimum cut
- Karger’s contraction algorithm
- amplification by repetition
- Karger–Stein 的改进思路
这周和 Assignment 2 Problem 1 直接相关。
MaxCut vs MinCut
老师先强调：
- MaxCut 是 NP-hard 的，通常只能做 approximation
- MinCut 则是 polynomial-time solvable 的
所以虽然名字只差一个 max / min，但问题性质完全不同。
contraction 的核心思想
Karger 算法的最精彩之处在于它非常短：
- 每次随机选一条边
- 把它 contraction
- 重复直到只剩 2 个 supernodes
- 返回这两个 supernodes 诱导的 cut
算法本身非常简单，但分析很漂亮。
为什么 random contraction 倾向于保留 min-cut
如果固定一个 minimum cut \(C\)，那么：
- 只要算法从头到尾都没有 contraction 到 \(C\) 上的边
- 那么这个 minimum cut 就会一直活到最后
- 最终被返回
于是分析就转化为：
在每一步，选到“坏边”（即 cut 边）的概率有多大？
由于 minimum cut 的边数最少，所以它最不容易被破坏。
经典结论
对于一个有 \(n\) 个顶点的图，任意固定 minimum cut 被 Karger 算法输出的概率至少是：
\[ \frac{2}{n(n-1)} \]
这虽然不高，但至少是：
\[ \Omega(1/n^2) \]
不是指数级小。
amplification
因为单次成功概率偏低，所以老师介绍了重复放大：
- 独立运行很多次 Karger
- 返回其中最小的 cut
要把成功率压到 \(1-\delta\)，大约需要：
\[ T = \Theta(n^2 \log(1/\delta)) \]
这就是 Assignment 2 Problem 1 的核心基础。
而如果题目进一步要求：
- 不是找一个 min-cut
- 而是列举所有 min-cuts
那自然的延伸就是：
- 重复运行 Algorithm 10
- 收集所有最小值相同的 cuts
- 去重
- 再用 union bound 控制漏掉任意一个 min-cut 的概率
额外收获：min-cut 数量上界
老师在分析 Karger 时顺便得到一个结构结论：
- 一个图的 minimum cuts 总数至多为
\[ \binom{n}{2} \]
这个结论在 Assignment 2 Problem 1 的“列举所有 minimum cuts”分析里也正好用上。
Week 6, Hashing and Hash Tables
本周主线
第六周系统讲 hashing：
- dictionary ADT
- array / list / BST 的局限
- hash table 的核心思想
- collisions 与 collision-handling
- universal hashing
- strongly universal / pairwise independent hash family
这周和 Assignment 2 的 hash functions 部分高度相关。
dictionary problem
老师先用 SID 的例子讲 motivation：
- universe 很大
- 实际存储的数据集很小
- 需要高效支持
- insert
- lookup
- remove
朴素结构的局限
- list：空间好，但查询慢
- array：查询快，但空间太浪费
- balanced BST：两边都还行，但还不是最优
哈希表的目标就是希望兼顾：
- 接近 \(O(1)\) 的操作时间
- 接近线性的空间
hash function 不该是真随机函数
老师特别强调了一个重要建模点：
- 真正随机地从所有函数 \(X \to Y\) 里均匀挑一个函数
- 虽然“最随机”
- 但根本不可存储，也不可实现
因为所有函数的总数是：
\[ |Y|^{|X|} \]
只存一个完全随机函数本身就要巨大空间。
所以真正可行的方案是：
- 选一个 小得多的函数族 \(\mathcal H\)
- 再从中均匀随机选一个 \(h\)
关键在于这个函数族要够小，但也要够“随机”。
universal hashing
老师给出的定义重点是 collision control：
若对任意不同 \(x,x'\)，都有
\[ \Pr_{h\sim \mathcal H}[h(x)=h(x')] \le \frac{1}{|Y|} \]
那么 \(\mathcal H\) 是一个 universal hash family。
如果更强一些，对任意不同 \(x,x'\) 和任意 \(y,y'\)，都有
\[ \Pr[h(x)=y,\ h(x')=y'] = \frac{1}{|Y|^2} \]
那就是 strongly universal，也就是 pairwise independent。
线性模素数构造
老师给出的经典构造就是：
\[ h_{a,b}(x) = ((ax+b) \bmod p) \bmod m \]
这类构造的优点是：
- 参数只需存 \(a,b\)
- 存储成本低
- 计算快
- 能提供所需的碰撞上界或更强性质
这正是 Assignment 2(a) 代码与讲义的连接点。
collision handling
老师接着说明：
- collisions 不可避免
- 所以 hash table 不只是“一个数组”
- 还必须有处理碰撞的策略
最自然的策略之一是 chaining：
- 每个 bucket 不只存一个 bit
- 而是挂一个 list / chain
- 所有 hash 到这里的元素串起来
另一类思路是 open addressing。
课程这里更重要的是思想：
hash table 的本质不是“没有碰撞”，而是“碰撞可控且可处理”。
Week 7, Nearest Neighbours and Dimensionality Reduction
本周主线
第七周进入高维算法：
- nearest neighbour search
- approximate nearest neighbour (ANN)
- metric space 观点
- Johnson–Lindenstrauss (JL) lemma
- locality-sensitive hashing (LSH) 的动机
nearest neighbour 的问题背景
老师用“毒蜘蛛图片检索”来做 motivation：
- 有一个很大的数据库
- 每个对象都是高维向量
- 来了一个 query point
- 希望快速找到最相近的数据库点
这就是 nearest neighbour problem。
为什么高维难
在高维里，最直接的方法往往很糟糕：
- 用 list：查询时间 \(O(nd)\)
- 用 Voronoi / computational geometry 结构：空间会爆炸
- 维度一大，很多低维直觉失效
老师明确说了：
exact nearest neighbour 在高维里很难，deterministic 方法通常既不快也不省空间。
所以自然会想到：
- 放宽问题
- 做 approximate nearest neighbour
approximate nearest neighbour (ANN)
ANN 的定义是：
- 不要求返回真正最近的点
- 只要求返回一个距离至多是最优距离 \(c\) 倍的点
也就是说，如果最近距离是 \(r\)，返回距离至多 \(cr\) 的点就行。
这个放宽常常能带来极大算法收益。
metric space 的角度
老师还专门统一了语言：
- 之前 hashing 一节里，底层集合几乎没几何结构
- 现在 nearest neighbour 必须有距离
- 所以问题自然放在 metric space 里描述
常见例子包括：
- Hamming distance
- Euclidean distance
- \(L_1\) / Manhattan distance
- \(L_\infty\) distance
这个视角在后面也很重要。
JL lemma
JL lemma 的核心信息是：
- 给定 \(n\) 个高维欧氏空间中的点
- 可以把它们映射到维度仅为
\[ O\left(\frac{\log n}{\varepsilon^2}\right) \]
的低维空间里
- 并且所有 pairwise distances 都只失真一个 \(1\pm \varepsilon\) 因子
也就是说：
只要你关心的是有限数据集上的距离，而不是整个空间的所有点，那么维度可以大幅降低。
这是现代高维数据处理里极其核心的结论。
为什么 JL lemma 很强
它强在两个地方：
- 新维度只依赖 \(\log n\)，不依赖原始维度 \(d\)
- 映射可以取成随机线性映射，非常简单
老师强调：
- 不是神秘黑箱
- 就是一张随机矩阵
- 把向量乘过去就行
这使得它不仅是理论结论，也具备工程可实现性。
LSH 的动机
老师还顺手说明了：
普通 hashing 不适合 nearest neighbour，因为它不保“近的点更容易撞到一起”。
而我们真正想要的是一种 hashing：
- 近的点更容易 collision
- 远的点更不容易 collision
这就是 locality-sensitive hashing 的动机。
这部分虽然 transcript 里主要还是 motivation，但你已经可以把它和 Week 6 的 hashing 联系起来：
Week 6 关注碰撞少不少妇，Week 7 开始要求碰撞要“有几何意义”。
前七周最重要的主线总结
如果把 Week 1 到 Week 7 串起来，老师其实一直在反复讲同一件事：
1. 随机性是算法资源
随机性不是噱头，而是一种资源。它可以用来：
- 简化算法
- 打破最坏输入结构
- 获得近似解
- 构造更省空间或更快的数据结构
2. expectation 只是起点，不是终点
- 只会算 expectation 不够
- 真正重要的是 concentration
- 真正需要的是 high-probability guarantee
所以 Week 2 的 concentration bounds 是后面所有分析的底层工具。
3. independence 要用得刚刚好
- full independence 往往昂贵
- pairwise independence 常常已经足够
- 这是 derandomisation 和 compact randomness 的关键
Week 4 和 Assignment 2 里的 hash family 都在围绕这点。
4. 有时候不追求 exact，追求 approximate 更合理
从 MaxCut 到 ANN，课程不断说明：
- exact 可能太难
- 但近似可以做得很强
- 只要误差可控，工程上就非常有价值
5. 课程一直在练“分析模板”
前七周最值得你真正记住的，不只是某道题结论，而是这些模板：
- indicator random variable
- linearity of expectation
- variance / second moment
- Markov / Chebyshev / Chernoff
- union bound
- repetition and amplification
- brute force over random seeds
- pairwise independence 代替 full independence
- 随机采样后再分析结构
这些模板在 assignment、final 和后面几周都会继续出现。
对 Assignment 2 最有帮助的对应关系
如果你现在的目标是做 Assignment 2，那么前七周里最直接相关的是：
Problem 1, Karger min-cut
主要对应：
- Week 5
- Karger contraction algorithm
- amplification by repetition
- minimum cut 数量上界
- union bound
Problem 2(a), pairwise independent hash functions
主要对应：
- Week 4
- Week 6
- pairwise independence
- strongly universal hashing
- 小随机种子代替大量独立随机位
Problem 2(c)(d)(e), MaxCut randomised / derandomised
主要对应：
- Week 4
- pairwise independence for derandomisation
- method of conditional expectations
- random partition gives expected half of edges
Problem 2(f), running time comparison
主要对应：
- Week 1, 为什么比较 Las Vegas / Monte Carlo / deterministic
- Week 2, amplification 的代价
- Week 4, derandomisation 往往要付额外复杂度
最后一段建议
如果你要拿这篇做复习提纲，我建议这样使用：
- 先看每周主线，确认课程整体地图
- 再看前七周主线总结，抓住老师不断重复的思想
- 最后看 Assignment 2 对应关系，把 lecture 和作业直接对上
如果要更进一步，最值得单独展开成专题笔记的三个主题是：
- Karger min-cut
- pairwise independent hashing
- concentration bounds 工具箱
这三个基本就是前半学期最核心的知识支柱。