CS170 Final · Problem-Driven Review

Berkeley Spring 2026 · Final on May 15 · multi-pass, narrow-then-deep, exam-shaped

How to use this site (4 passes, ~12h total)

每个 topic 都被切成 3 轮。先把所有 topic 的 Round 1 全走一遍（拿到全景），再回头做 Round 2 → Round 3。考试当晚 7 PM 开始，目标是 Round 3 在前一晚完成。

Pass 1
全部 Topic 的 Round 1（直觉 / 一句话总结 / 图）。目标：30 秒能说出"这是干嘛的"。约 2h。
Pass 2
Q4/Q5/Q6 三个高优先 Topic 的 Round 2（套路 / 题型）。约 3h。
Pass 3
Q4/Q5/Q6 的 Round 3（难题，看题先盖答案）+ LP 的 Round 2。约 4h。
Pass 4
Pre-MT2 内容 Round 1+2 扫雷（DP / Graph / D&C 套路化），cheat sheet 收尾。约 3h。

1. Zero-Sum Games Q4 focus

为什么必考：Carolyn 已公布 Q4 = "写 payoff + 写 LP for Alice/Bob 最优混合策略 + 分析 value"。这是固定模板题，全班都能答完，区分度在熟练度。
1直觉：30 秒说清楚 5 min

设定：两个玩家 Alice (行 / row, 最大化者) 和 Bob (列 / column, 最小化者)。一个 payoff 矩阵 $M$，$M_{ij}$ = 当 Alice 选行 $i$、Bob 选列 $j$ 时，Bob 付给 Alice 的钱。

关键问题：纯策略下 Alice 和 Bob 看到对方落子才决定，结果完全不一样（先手吃亏）。引入混合策略：Alice 公布概率分布 $x$（$\sum x_i = 1$），Bob 在看到 $x$ 后选最佳 column。

Minimax 定理：Alice 先公布 vs Bob 先公布 — 得到的最优期望相同，这个公共值叫 game value $v^*$。

Alice (max) picks row dist $x$ maximize worst column Bob (min) picks col dist $y$ minimize worst row value $v^*$ same number!
Minimax: 两边都"打最坏情况"，最优值相同。

Solving via LP：因为 Bob 看到 $x$ 后会挑那个让自己 expected payoff 最小的 column，所以 Alice 的"最坏期望"是 所有 column 期望中的最小值。Alice 想最大化这个最小值 — 经典 max-of-mins，引入辅助变量 $v$ 即可线性化。

2套路：Alice 与 Bob 的 LP 模板 15 min

Alice 的 LP (max-min)：

maximize    v
subject to  ∑_i  M_{ij} · x_i  ≥  v     ∀ j  (every Bob column)
            ∑_i  x_i = 1
            x_i ≥ 0

关键：约束的方向。Alice 是 max，所以她要保证 无论 Bob 选哪个 column，期望 payoff 都至少是 $v$。

Bob 的 LP (min-max)：

minimize    u
subject to  ∑_j  M_{ij} · y_j  ≤  u     ∀ i  (every Alice row)
            ∑_j  y_j = 1
            y_j ≥ 0

对偶关系：Alice's LP 和 Bob's LP 互为 dual。强对偶 ⇒ $v = u = v^*$。这就是 Minimax 定理在 CS170 里的"现代"证明。

Quick-fire 套路总结

  • 题目给你 $M$ → 直接套两个 LP 模板。
  • 问"the value of the game" → 强对偶，两边最优都是 $v^*$。
  • 问"optimal mixed strategy" → 解 LP 得到 $x^*$ 或 $y^*$。
  • 问"some pure strategies could be dropped" → 受 dominated（被另一行 entry-wise 弱占优）的行/列概率必为 0。
  • $2 \times n$ 或 $n \times 2$ 的小游戏：可以画 column-vs-prob 图，每条线表示 Bob 一个 column 的期望，Alice 想最大化 lower envelope — 几何解。
3难题：完整 exam-style 一题打通 25 min
Exam-style Problem
Rock-Paper-Scissors-Lizard. Alice 和 Bob 玩一个改良的猜拳：Alice 是行玩家，Bob 是列玩家，payoff matrix（Bob 付给 Alice）为：
RPS
R0-12
P10-1
S-210
(a) 写出 Alice's LP. (b) 写出 Bob's LP. (c) Argue what the value of the game is.
解答

(a) Let $x_R, x_P, x_S$ 是 Alice 选 R/P/S 的概率。

max  v
s.t. 0·x_R + 1·x_P + (-2)·x_S ≥ v    (Bob plays R)
     -1·x_R + 0·x_P + 1·x_S    ≥ v    (Bob plays P)
     2·x_R + (-1)·x_P + 0·x_S  ≥ v    (Bob plays S)
     x_R + x_P + x_S = 1,   x_i ≥ 0

(b) Let $y_R, y_P, y_S$ 为 Bob 的概率。

min  u
s.t. 0·y_R + (-1)·y_P + 2·y_S  ≤ u    (Alice plays R)
     1·y_R + 0·y_P + (-1)·y_S  ≤ u    (Alice plays P)
     -2·y_R + 1·y_P + 0·y_S    ≤ u    (Alice plays S)
     y_R + y_P + y_S = 1,   y_j ≥ 0

(c) 矩阵反对称（$M^T = -M$）。在反对称游戏中，由对称性 Alice 和 Bob 角色可互换，故 $v^* = -v^*$，即 $v^* = 0$。最优混合策略可解出（不要求计算）：$x = y = (1/4, 1/2, 1/4)$ —— 验证一下：对 column R 的 Alice 期望 $= 0\cdot \tfrac14 + 1\cdot \tfrac12 + (-2)\cdot \tfrac14 = 0$. ✓

讲题 takeaway：遇到反对称矩阵直接报 $v^* = 0$，能节省 10 分钟。

Trap to avoid
如果题目把矩阵定义成"Alice 付给 Bob"，所有不等号方向都要翻；考试紧张容易翻车。读题先把 "who pays whom" 圈出来。

2. Multiplicative Weights (MWU) may appear in Q4

为什么相关：MWU 是解 zero-sum game 的算法替代品（不用解 LP 也能逼近 $v^*$）。Ed 上助教说 "mwu may show up in zero-sum game question"，至少要会解读它的更新公式。
1直觉：专家建议 + 自适应权重 5 min

问题：每一轮 $t = 1, \dots, T$，$n$ 位"专家"给出预测。你要选一位专家跟随。你不知道谁靠谱。一轮结束后揭晓每位专家的 loss $\ell_i^{(t)} \in [0,1]$。能否保证你的总损失 ≈ 最强单专家？

MWU 算法：

w_i^(1) = 1 for all i
for t = 1..T:
  sample i with prob  p_i^(t) = w_i^(t) / ∑_j w_j^(t)
  observe losses ℓ_i^(t)
  w_i^(t+1) = w_i^(t) · (1 - η · ℓ_i^(t))

保证：$\mathbb{E}[\text{total loss}] \le (1+\eta) \min_i L_i^* + \frac{\ln n}{\eta}$。取 $\eta = \sqrt{\ln n / T}$，regret $= O(\sqrt{T \ln n})$。

Experts n total Weights $w_i$, normalize → $p_i$ Loss vec update: $w_i \leftarrow w_i(1-\eta \ell_i)$
高 loss 的专家权重被指数级压低；后悔值随 $\sqrt{T \log n}$ 增长。
2套路：MWU ↔ Zero-Sum Game 10 min

How to use MWU to solve a zero-sum game:

  1. Alice 把 每个 row 当做一个"专家"。
  2. 每轮 $t$：Alice 由当前权重抽一行 $i$。Bob 看到 Alice 的分布 $p^{(t)}$ 后选最优 column $j_t = \arg\min_j \mathbb{E}_{i \sim p}[M_{ij}]$。
  3. 把 Alice 第 $i$ 行的 loss 设为 $\ell_i^{(t)} = (1 - M_{i,j_t})/2$（squeeze 到 $[0,1]$）。
  4. 用 MWU 更新权重。
  5. 跑 $T = O(\log n / \epsilon^2)$ 轮，输出 $\bar{x} = \frac{1}{T}\sum_t p^{(t)}$ 与 $\bar y =$ 对应的 column 频率。

结论：$(\bar x, \bar y)$ 是 $\epsilon$-近似 minimax 平衡，不解 LP 也能得到 game value。

  • 考试若问"如何用 MWU 解 ZSG" → 上述 5 步。
  • 问 regret bound → $O(\sqrt{T \ln n})$ 是核心数。
  • 问 $\eta$ 怎么选 → 学习率，$\sqrt{\ln n / T}$ 平衡两项。
3难题：regret 推导框架 15 min
Exam-style Problem
定义"势函数" $\Phi_t = \sum_i w_i^{(t)}$。证明 $\Phi_{t+1} \le \Phi_t \cdot (1 - \eta \cdot \langle p^{(t)}, \ell^{(t)} \rangle)$，并用此推出 MWU 的 regret bound。
关键步骤

Step 1 (upper bound $\Phi_{T+1}$)： $$\Phi_{t+1} = \sum_i w_i^{(t)}(1 - \eta \ell_i^{(t)}) = \Phi_t - \eta \sum_i w_i^{(t)} \ell_i^{(t)} = \Phi_t(1 - \eta \langle p^{(t)}, \ell^{(t)}\rangle).$$ 连乘得 $\Phi_{T+1} \le n \exp(-\eta L_{\text{alg}})$，其中 $L_{\text{alg}} = \sum_t \langle p^{(t)}, \ell^{(t)}\rangle$ 是算法期望总损失。

Step 2 (lower bound)：$\Phi_{T+1} \ge w_{i^*}^{(T+1)} = \prod_t (1 - \eta \ell_{i^*}^{(t)}) \ge \exp(-\eta L_{i^*} - \eta^2 L_{i^*})$，对 $i^* = \arg\min L_i$ 成立（用 $\ln(1-x) \ge -x - x^2$, $x \in [0, 1/2]$）。

Step 3：两式取 log 比较 → $L_{\text{alg}} \le (1+\eta) L_{i^*} + \frac{\ln n}{\eta}$. □

3. NP-Completeness & Reductions Q5 focus

为什么必考：Q5 = "Prove X is NP-complete. You may use Y is NP-complete." 这是纯模板题，找对 Y 拿 80%+ 分。
1直觉：NP-complete 是什么 5 min

P：多项式时间能 解决 的判定问题。

NP：多项式时间能 验证证书 的判定问题。3-SAT 的 certificate = 满足赋值；TSP-decision 的 certificate = 一条 tour。

NP-hard：所有 NP 问题都能多项式归约到它（一旦解决它，整个 NP 都被解决）。

NP-complete：既在 NP 中，又是 NP-hard。也就是说 NP 中"最难的"那一类。

NP P NP- complete assuming P ≠ NP

证明 X 是 NP-complete 的两步：

  1. X ∈ NP：给一个 polynomial-time verifier 和 certificate。这一步一句话搞定。
  2. X is NP-hard：找一个已知 NP-complete 问题 $Y$，构造多项式归约 $Y \le_p X$。意思是：把任意 Y 的实例转换成 X 的实例，且两者答案一致。

⚠ 注意归约方向！是 Y → X（用 X 解 Y），不是反过来。说错方向直接 0 分。

2套路：4 个万能起点 + 双向证明模板 20 min

4 个常用 starting Y

  • 3-SAT：CNF 公式，每子句 3 literal，问是否可满足。最万能。要构造 gadget 模拟变量 / 子句时用。
  • Independent Set：图中找 $k$ 个互不相邻的点。用于图论问题（Vertex Cover, Clique, Dominating Set 等）。
  • Vertex Cover：和 IS 互补（$S$ 是 IS ↔ $V \setminus S$ 是 VC）。常用做桥梁。
  • Subset Sum / Knapsack-decision：数值类问题（partition, bin packing）。
  • (其他) Hamiltonian Cycle / Path 用于路径问题；3-Coloring 用于图染色。

归约的"双向证明"模板（必背）

设你要证 $Y \le_p X$。构造一个映射 $f$：$Y$-instance $\to$ $X$-instance。

  1. 多项式时间：$f$ 可在多项式时间计算。一句话。
  2. (⇒) Yes-instance 映到 Yes-instance：If $Y$-instance has solution $\sigma$, then $f(\text{instance})$ has solution $\sigma'$ — 显式构造 $\sigma' = \dots$。
  3. (⇐) No-instance 映到 No-instance：contrapositive — if $f(\text{instance})$ has solution $\sigma'$, then $Y$-instance has solution $\sigma$ — 显式从 $\sigma'$ 解出 $\sigma$。

常见错误：只证一个方向（"显然另一边也对" — 扣分）。必须明确写出 $\sigma'$ 和 $\sigma$ 的对应关系。

选 Y 的快速决策树

  • 问题是图上的 subset 问题 (independent / cover / clique) → Independent Set 或 Vertex Cover。
  • 问题涉及 path / cycle / Hamiltonian 性质 → Hamiltonian Cycle。
  • 问题涉及子集求和 / 整数 partition → Subset Sum。
  • 问题逻辑性强、变量约束多 → 3-SAT。
  • 染色 / partition into k groups → 3-Coloring 或 Graph k-Coloring。
3难题：两个完整 walkthrough 30 min
Exam-style Problem #1
Dominating Set. 给定无向图 $G = (V, E)$ 和整数 $k$，问是否存在一个大小 $\le k$ 的点集 $S$，使得每个 $v \in V$ 要么 $\in S$，要么有邻居 $\in S$。证明 Dominating Set is NP-complete. (可使用 Vertex Cover 是 NP-complete 的事实)
解答 (全文)

Step 1: Dominating Set ∈ NP. Certificate 是大小 $\le k$ 的点集 $S$。Verifier 遍历每个 $v \in V$ 检查 $v \in S$ 或 $v$ 有邻居在 $S$ 中。$O(|V|+|E|)$ 时间。

Step 2: Vertex Cover $\le_p$ Dominating Set.

归约：给定 VC 实例 $(G, k)$，$G = (V, E)$。构造 DS 实例 $(G', k)$：

  • $V(G') = V \cup \{u_e : e \in E\}$ — 为每条边 $e = (a,b)$ 加一个新点 $u_e$。
  • $E(G') = E \cup \{(u_e, a), (u_e, b) : e = (a,b) \in E\}$ — 把 $u_e$ 连到 $e$ 的两个端点，并保留原图。
  • $k' = k$.
  • (防御性细节) 移除 $G$ 中所有孤立点（不影响 VC 答案；防止 DS 必须 cover 它们）。

显然这是多项式时间。

(⇒) 若 $G$ 有 vertex cover $C$，$|C| \le k$，则 $C$ 也是 $G'$ 的 dominating set： - 每个 $v \in V \setminus C$ 在 $G$ 中有边，那条边的另一端必在 $C$（因为 $C$ 是 cover），所以 $v$ 被 dominate。 - 每个 $u_e$（$e = (a,b)$）：$a$ 或 $b$ 在 $C$ 中（cover 性质），$u_e$ 与它相邻，被 dominate。 ✓

(⇐) 若 $G'$ 有 dominating set $D$，$|D| \le k$，要在 $G$ 中找到大小 $\le k$ 的 vertex cover。

对每个 $u_e \in D$，把它替换成 $e$ 的任一端点（替换后大小不变或减小）。得到的 $D' \subseteq V$，$|D'| \le k$。Claim: $D'$ 是 $G$ 的 vertex cover。

证：取任意 $e = (a,b) \in E$。$u_e$ 在 $G'$ 中要被 $D$ dominate ⇒ $u_e \in D$ 或 $a \in D$ 或 $b \in D$。前者经过替换后 $a$ 或 $b$ 已经 ∈ $D'$。后两种本来就 ∈ $D'$。故 $e$ 被 $D'$ cover。 ✓

由两方向得 $G$ 有 size-$k$ VC ⇔ $G'$ 有 size-$k$ DS。Q.E.D.

Exam-style Problem #2 (harder)
k-Spanning-Subgraph. 给定加权无向图 $G$ 和整数 $W$，问能否找到 $G$ 的一个连通生成子图，总边权 $\le W$。 这个问题是 P 还是 NP-complete?
解答

P。这是 Minimum Spanning Tree —— 跑 Kruskal/Prim 得到 MST 权重 $W^*$，比较 $W^* \le W$。$O(E \log V)$。

陷阱："connected spanning subgraph" 听起来很像 NP 问题，但去掉环可以只让权重变小，故最优解一定是树。这种"伪 NP"问题在期末上常出现。

变种：如果限制 "包含某个特定点集 $S$ 的最小连通子图" → 这就是 Steiner Tree，NP-complete。区别只在多了 "必须包含 $S$" 一句。考试细读题目。

  • 常见扣分点：(1) 没写 X ∈ NP；(2) 归约方向反了；(3) 只证一个方向；(4) 用了非 NP-hard 的 Y（如 MST）。
  • 时间分配建议：识别 Y 用 3 分钟，写归约 + 双向 12 分钟，留 5 分钟检查方向。

4. Hashing & Streaming Q6 focus

为什么必考：Q6 明确是 hashing/streaming。这是新内容，最容易因不熟练丢分。重点掌握 Bloom filter, Count-Min sketch, reservoir sampling, HyperLogLog 中至少 2-3 个。
1直觉：trade exactness for space 10 min

Streaming model：数据流 $a_1, a_2, \dots, a_m$ 一个一个进来，每个 $a_i \in \{1, \dots, n\}$。空间预算 $\ll n, m$（典型是 $O(\log n)$ 或 $O(\sqrt{n})$）。每个元素只能扫一次。

典型查询：

  • "$x$ 在流中出现过吗？" → Bloom Filter
  • "$x$ 出现了多少次？" → Count-Min Sketch
  • "distinct 元素的个数？" → HyperLogLog / Flajolet-Martin
  • "随机抽 $k$ 个？" → Reservoir Sampling
  • "frequent items（出现 $> m/k$ 次的）？" → Misra-Gries / Heavy Hitters
$a_1$ $a_2$ … $a_m$ sketch / state $O(\log n)$ space answer approx
流式算法：单次扫描，小空间，输出近似答案。

"近似"的两个维度：$(\epsilon, \delta)$ —— 误差不超 $\epsilon$ 的概率至少 $1 - \delta$。空间和时间通常都依赖于 $1/\epsilon$ 和 $\log(1/\delta)$。

2套路：4 大 sketch 的内部机理 25 min

A. Bloom Filter (membership, no false negatives)

  • 大小 $m$ 的 bit array，$k$ 个独立哈希函数 $h_1, \dots, h_k : U \to [m]$.
  • Insert $x$：对每个 $j$, 把 $A[h_j(x)] = 1$.
  • Query $x$：所有 $h_j(x)$ 位都是 1 → "可能在"；任一为 0 → "确定不在".
  • FP rate $\approx (1 - e^{-kn/m})^k$. 最优 $k = (m/n) \ln 2$.

B. Count-Min Sketch (frequency, overestimate only)

  • $d \times w$ 的 counter table，每行有一个哈希函数 $h_i : U \to [w]$.
  • Insert $x$：每行做 $C[i][h_i(x)] \mathrel{+}= 1$.
  • Query $\hat{f}(x) = \min_i C[i][h_i(x)]$ — always $\ge$ 真频率（hash 冲突只可能高估）。
  • 取 $w = e/\epsilon$, $d = \ln(1/\delta)$ → $\hat f(x) \le f(x) + \epsilon m$ w.p. $1-\delta$.

C. Reservoir Sampling (random k from stream of unknown length)

  • 前 $k$ 个直接进 reservoir.
  • 第 $i > k$ 个元素：以概率 $k/i$ 替换 reservoir 中一个随机位置。
  • 不变量：扫到第 $i$ 个时，每个元素在 reservoir 里的概率恰好是 $k/i$.

D. HyperLogLog / Flajolet-Martin (distinct count)

  • 对每个 $a_i$ 计算 $h(a_i)$ 的二进制最低位 trailing-zero 数 $\rho(a_i)$.
  • 维护 $\max \rho$。distinct 数估计为 $2^{\max \rho}$（指数级，方差很大）.
  • HLL 改进：用多个独立 bucket 取调和平均，减小方差。空间 $O(\log \log n)$.

速查表 (面试 / 考试常用 trade-off)

            |  query         |  space            |  error type
------------|----------------|-------------------|----------------------
Bloom       |  ∈ S?          |  O(n log 1/δ)     |  false positive only
CMS         |  freq(x)       |  O((1/ε) log 1/δ) |  overestimate only
Reservoir   |  rand k        |  O(k)             |  exact (sampling)
HLL         |  |distinct|    |  O(log log n)     |  ~2% relative
Misra-Gries |  heavy hitters |  O(k)             |  bias ≤ m/k
3难题：分析 + 设计 20 min
Exam-style Problem #1 (analysis)
Bloom filter 有 $m = 8n$ bits, $k = 5$ hash 函数. 插入 $n$ 个元素后，对一个不在集合中的元素 $x$，false positive 概率约为多少？
解答

某 bit 在所有插入后仍为 0 的概率 $\approx e^{-kn/m} = e^{-5/8} \approx 0.535$.

所有 $k=5$ 个 hash 位都为 1 的概率（即 FP）$\approx (1 - 0.535)^5 = (0.465)^5 \approx 0.022$.

FP rate $\approx 2.2\%$。

Exam-style Problem #2 (design)
给定一个长度 $m$ 的整数流。设计一个流式算法，$O(\log m)$ 空间，输出一个 ID，使得每个出现过的 ID 都有非零概率被输出，且重复出现的 ID 不增加被选中概率（即 distinct-uniform 抽样）。
解答 sketch

用 min-hash 抽样：维护当前的 $(x^*, h(x^*))$。流入新元素 $a_i$，计算 $h(a_i)$；若 $h(a_i) < h(x^*)$ 则更新 $x^* \leftarrow a_i$。最后输出 $x^*$。

关键 invariant：$x^*$ 是 distinct 元素中 hash 值最小的那个，与重复次数无关。空间 $O(\log m)$ for ID + hash 值。

Reservoir 不行：reservoir 偏向高频元素，被重复推入的元素被选中概率更高。

Exam-style Problem #3 (Markov / Chebyshev 分析)
Count-Min sketch 中证明：$\Pr[\hat f(x) - f(x) > \epsilon m] \le \delta$ 当 $w = e/\epsilon, d = \ln(1/\delta)$.
解答 sketch

固定行 $i$：$C[i][h_i(x)] = f(x) + \sum_{y \ne x: h_i(y) = h_i(x)} f(y)$. 期望溢出 $\mathbb{E}[\text{noise}] \le m/w = \epsilon m/e$.

Markov: $\Pr[\text{noise} > \epsilon m] \le 1/e$. 取 $d = \ln(1/\delta)$ 行各自独立 → $\hat f$ 取 min → 失败概率 $\le (1/e)^d = \delta$. □

5. Linear Programming in Q1-Q3 scope

为什么相关：LP 既会单独在 Q1-Q3 出现，又是 Q4 (ZSG) 和 NP-Hard 的近似算法工具。模板化掌握，少花时间。
1直觉：把问题翻成 max c·x s.t. Ax ≤ b 5 min

标准型： $\max c^T x$ s.t. $Ax \le b$, $x \ge 0$. 多面体上的线性函数极值在顶点取到 → 单纯形法。

常见技巧：

  • "max of min" → 引入 $v$, max $v$ s.t. (each term) $\ge v$.
  • "absolute value $|x|$" → 用 $x = x^+ - x^-$, $x^\pm \ge 0$. 目标里 $|x|$ 替换为 $x^+ + x^-$.
  • "L1 norm 最小化" → 上一条的推广。
  • 等式约束 → 拆成两个 $\le$ 不等式。
  • 变量无符号约束 → 拆 $x = x^+ - x^-$.
2套路：对偶 + max-flow / min-cut LP 15 min

对偶 (mechanical)：

Primal:                          Dual:
max c^T x                        min b^T y
A x ≤ b                          A^T y ≥ c
x ≥ 0                            y ≥ 0

对偶口诀：每个 primal constraint ↔ 一个 dual 变量；每个 primal 变量 ↔ 一个 dual constraint。

Max-flow 的 LP

max  ∑_e∈δ^+(s) f_e
s.t. f_e ≤ c_e                    ∀e
     ∑_{e∈δ^+(v)} f_e = ∑_{e∈δ^-(v)} f_e   ∀v ≠ s,t
     f_e ≥ 0

对偶：min cut LP。LP duality ⇒ max-flow = min-cut.

题型套路

  • "将以下问题写成 LP" → 标识 decision variable、目标函数、约束。
  • "写出 dual" → 对偶口诀。
  • "用 LP duality 证明 X = Y" → 找一对 primal/dual 都达到最优。
  • 整数 IP → LP relaxation，舍入分析。
3难题：建模 + 对偶解读 15 min
Exam-style Problem
$n$ 个工人，$m$ 个任务，工人 $i$ 完成任务 $j$ 需要时间 $t_{ij}$。每个工人每天 8 小时，每个任务最多由一个工人做（可分配小数比例）。最大化完成的任务总数。 (a) 写 LP。(b) 写 dual。(c) Dual 变量的经济意义。
解答

(a) 变量 $x_{ij} \in [0,1]$ = 工人 $i$ 做任务 $j$ 的比例。

max  ∑_{i,j} x_{ij}
s.t. ∑_j t_{ij} · x_{ij} ≤ 8         ∀i  (worker time)
     ∑_i x_{ij}          ≤ 1         ∀j  (task once)
     x_{ij} ≥ 0

(b) 每个 worker 约束对应 $u_i \ge 0$，每个 task 约束对应 $v_j \ge 0$。

min  ∑_i 8u_i + ∑_j v_j
s.t. t_{ij} u_i + v_j ≥ 1     ∀(i,j)
     u_i, v_j ≥ 0

(c) $u_i$ = 工人 $i$ 一小时时间的"影子价格"；$v_j$ = 任务 $j$ 的"完成价格"。约束 $t_{ij} u_i + v_j \ge 1$ 意思：用 $u_i$ 给工人付时间费 + $v_j$ 给任务付完工费，至少能买下做一单位 $x_{ij}$ 的"产能"。

6. Pre-MT2 一页扫雷 Q1-Q3 cover

为什么轻：你说 MT2 之前的内容有基础。这里只放遗忘曲线快速恢复用的"一句话定理"和典型陷阱，不深入。
1D&C / DP / Greedy / Graphs 一页 cheat 15 min

Divide & Conquer

  • Master theorem：$T(n) = aT(n/b) + O(n^d)$. 比较 $\log_b a$ vs $d$. 三种 case.
  • Karatsuba: $O(n^{\log_2 3})$. 矩阵 Strassen: $O(n^{\log_2 7})$.
  • FFT: $O(n \log n)$ 多项式乘法。butterfly 不考。
  • Median of medians: 线性 selection。

Dynamic Programming

  • 识别：递归子问题 + 重叠子问题。
  • 套路问题：LIS, LCS, edit distance, knapsack, matrix chain, 区间 DP, 树形 DP, bitmask DP (TSP $O(n^2 2^n)$).
  • 陷阱：定义 state 必须 self-contained，不要漏维度。

Greedy

  • 证明套路：exchange argument 或 stay-ahead。
  • 经典：interval scheduling, MST (Kruskal/Prim), Huffman, Dijkstra（≥0 边权）.

Graphs

  • BFS / DFS / DAG / topological sort / SCC (Tarjan or Kosaraju).
  • SSSP: BFS (unweighted), Dijkstra (non-neg), Bellman-Ford (negative ok, $O(VE)$), Floyd-Warshall (APSP, $O(V^3)$).
  • Max-flow: Ford-Fulkerson, Edmonds-Karp $O(VE^2)$. Min-cut. Bipartite matching via flow.

易翻车的陷阱

  • "Dijkstra on graph with negative edges" → 一律错。用 Bellman-Ford。
  • "MST is unique iff all edge weights distinct" — 充分非必要。考试别写反。
  • "在 DAG 上找最长路" → 一次拓扑序 DP，$O(V+E)$。不要试着把 Dijkstra 取负权。
  • "Max-flow integral 当容量整数" — Ford-Fulkerson 自动整数性。

Cheat Sheet 排版建议（3 张 letter, 双面 = 6 面）

★6 个面分别放什么 必看
  • 面 1：Zero-sum game LP 双模板 + minimax + 反对称 trick + Q4 流程图。
  • 面 2：MWU 更新公式 + regret bound + 用 MWU 解 ZSG 的 5 步。
  • 面 3：NP-completeness 双向证明模板 + 4 个 starting Y 的精确陈述 + 决策树。
  • 面 4：Bloom / CMS / Reservoir / HLL 4 个 sketch 表格 + Markov/Chebyshev 公式 + Concentration 不等式集合。
  • 面 5：LP 标准型 + 对偶口诀 + max-flow / min-cut LP + 常见建模 trick（max-of-min / L1）。
  • 面 6：Master theorem 三 case + DP 模板 + 最短路算法表 + max-flow 算法表 + "Dijkstra 不能负权" 等 5 个易错点。

必须手写。"凡是要查的都写大字"。"不熟的公式才上 cheat sheet，熟的就别浪费版面"。

Q1-3 复习 基于 MT1+MT2 反推

高频组合：贪心 / DP（区间·树形·单调队列）/ 图论（最短路·MST·SCC·max-flow）/ FFT-卷积

反推依据。MT1: Q1 fractional knapsack（贪心） · Q2 scheduling · Q3 shortest path · Q4 decimal-to-binary（D&C / FFT 风格）。MT2: Q1 running minimum（单调队列） · Q2 matching subarrays（FFT 卷积） · Q3 arithmetic trees（树形 DP） · Q4 job scheduling（DP / LP 建模）。

Final Q1-3 大概率从同一池子里抽。下面 6 题各覆盖一类。

dis06 Q1

Interval Scheduling（贪心 · exchange argument）

MT1 Q2 风格：scheduling 类贪心

$n$ 个区间，区间 $i$ 的起止时间 $(s_i, f_i)$。两个区间 compatible iff 不重叠。求最大兼容子集。

算法：按 $f_i$ 升序排，贪心扫描，若与上一选区间不冲突就选。证明用 exchange argument。

dis06 Q2

Knapsack with Repetition（DP）

MT1 Q1 风格：DP 选择子问题 + 状态设计

容量 $W$、$n$ 种物品（每种无限供应），物品 $i$ 重 $w_i$、价值 $v_i$。最大化装入总价值。

dis06 Q3

Eat Before Class（最短路 + 状态扩展）

MT1 Q3 风格：最短路必经某集合

有向带正权图 $G = (V, E)$，源 $s$、汇 $t$，食物点集合 $F \subseteq V$。求 $s \to t$ 且至少经过一个 $f \in F$ 的最短路长度。

dis06 (D&C 1)

Maximum Subarray Sum（分治）

D&C 模板，Master theorem case 1

给定数组 $A[0..n-1]$（含负数），求 $\max_{i \le j} \sum_{k=i}^{j} A[k]$（含空子数组 $= 0$）。设计 $O(n \log n)$ 分治。

hw06 Q3

Polynomial From Roots（FFT + D&C）

MT1 Q4 风格：FFT 应用

$p(x) = \prod_{i=1}^n (x - r_i)$ 有 $n$ 个不同根。求展开后系数 $a_0, \dots, a_n$，时间 $O(n \log^2 n)$。

hw07 Q3

Cyclic Shifts（FFT 卷积）

MT2 Q2 风格：用 FFT 把 shift 内积转成卷积

给两个长 $n$ 向量 $u, v$。第 $j$ 次 forward shift of $u$ 是把每个元素往后挪 $j$ 步、前 $j$ 位补 0；第 $j$ 次 cyclic shift 是 wrap-around。

  1. $O(n \log n)$ 算 $v$ 与 $u$ 所有 forward shift 的内积（共 $n + 1$ 个值）。
  2. (a) 推广到 cyclic shift。

Round 1 — 打底入门 ~5h

把 Q4-Q6 的"基本动作"建立起来 · 卡 30min 没思路就翻答案，不要硬磕
dis11 Q3

Zero-Sum Games（2×2 LP 入门）

Q4 入门：写 Alice/Bob LP + 看 primal-dual 结构

Alice (行) 想最大化、Bob (列) 想最小化，payoff 矩阵：

Alice \ Bob12
141
225

设 $x_1, x_2$ 为 Alice 的行混合策略概率、$p$ 为她的期望 payoff。

  1. 写 LP 让 Alice 选 $x_1, x_2$ 最大化最坏情况下的 $p$。
  2. 从 Bob 视角写 LP（变量 $y_1, y_2, p$），他想最小化 Alice 的 payoff。
  3. 说明 (a) 和 (b) 互为对偶。
  4. 给出最优解和 game value。
dis13 Q1+Q2

Runtime of NP & 2-coloring → 3-coloring

Q5 入门：搞清 P / NP / NP-hard 的方向感

Q1 (True/False)。若某 NP-complete 问题 $P$ 存在 $O(n^k)$ 算法（$k$ 固定），是否所有 NP 问题都有 $O(n^k)$ 算法？

Q2. $G$ 是 $k$-colorable 当且仅当顶点能用 $\{1,\dots,k\}$ 染色且相邻不同色。

  1. 给出 2-coloring → 3-coloring 的 reduction：构造 $G'$ 使 $G$ 是 2-colorable iff $G'$ 是 3-colorable。说明双向。
  2. 已知 2-coloring 有 $O(|V|+|E|)$ 算法。这能给 3-coloring 一个高效算法吗？
dis14 Q1

Hamiltonian Cycle → Hamiltonian Path

Q5 模板：经典 gadget 式 reduction（split 顶点）

已知 Hamiltonian Cycle（有向图中是否存在恰好访问每个顶点一次的环）是 NP-complete。证明 Hamiltonian Path（恰好访问每个顶点一次的路径）也是 NP-complete。

  1. 证明 Hamiltonian Path $\in$ NP。
  2. 给出从 Hamiltonian Cycle 的多项式归约（双向证明）。
hw15 Q3 (a)(b)

Streaming：求和 mod $N$

Q6 入门：log 比特流式状态

给定无限正整数流 $x_1, x_2, \dots$，每来一个数都要做计算，目标是限制总内存。

  1. 用 1 bit 内存判定目前为止所有整数的和是奇是偶。
  2. 用 $O(\log N)$ bit 内存判定目前为止的和是否被某固定整数 $N$ 整除。
dis15 Q2

TikTok Audit（找缺失/重复）

Q6 入门：求和 / 平方和 trick

视频 ID 集合 $[n] = \{1, 2, \dots, n\}$，流只能从左到右读一次。用 $O(\log n)$ bit 内存：

  1. 流长 $n-1$、含 $n-1$ 个不同 ID，恰有一个 $m \in [n]$ 缺失，输出 $m$。
  2. 流长 $n$，恰一个 ID $m$ 缺失，恰一个 ID $d$ 出现两次，其余各出现一次。输出 $m$ 和 $d$。
dis11 Q1

Dual as a Certificate of Optimality

Q4/Q1-Q3 LP 对偶感觉回温

考虑 LP：

$$\max\ 3x_1 + 2x_2 \quad \text{s.t.}\quad x_1 + x_2 \le 4,\ \ x_1 + 3x_2 \le 6,\ \ x_1, x_2 \ge 0.$$

有人声称最优值是 12，在 $(x_1, x_2) = (4, 0)$ 处取得。

  1. 验证 $(4, 0)$ primal feasible。
  2. 用非负系数 $y_1, y_2$ 乘约束并相加得到 primal 目标的上界，写出对偶 LP。
  3. 找一个 dual feasible $(y_1, y_2)$，目标值 $= 12$。
  4. 解释为什么 $((x_1,x_2),(y_1,y_2))$ 是最优性证书。

Round 2 — 强化巩固 ~7h

中等难度 · 覆盖 multiplicative weights · dis16 Q7+Q3 要能合上书独立写完
dis16 Q7

Penalty Kicks（Q4 模考题）

完整 dominated → 2×2 → LP 流程

Kicker（行）想最大化进球概率，goalie（列）想最小化。Payoff 矩阵：

Dive LeftStay CenterDive Right
Shoot Left0.20.70.8
Shoot Center0.40.50.4
Shoot Right0.80.70.2
  1. 消去 dominated strategy，把 3×3 化简为 2×2（提示：可能被混合策略 dominate）。
  2. 解 2×2 zero-sum game：双方最优混合策略 + game value。
  3. 写原 3×3 game kicker 的 LP 并给出最优解。
  4. 若改 payoff 把 Shoot Left 第一行变成 $(0.3, 0.8, 0.9)$，此时是否还需要混合策略？
hw11 Q3

Domination（不解 LP）

Q4：用对偶/dominated 推策略，避开机械解 LP

Zero-sum game，row 是 Maximizer：

ABC
D12-3
E32-2
F-1-22
  1. 不直接求解，能否说出 row player 选 D 的概率？
  2. 承 (a)，column 选 A 的概率？
  3. 给出双方最优策略。
hw12 Q2

Realizable Experts（Halving）

Multiplicative weights / Halving 唯一可能命题点

$n$ 个专家每天预测 rain/shine。至少一个 expert 是 perfect（永远对）。每天我们要选一个预测；目标：mistake 数最少。

  1. 每天跟"目前为止全对的专家"中的多数走（任意 tie-break）。证 mistake 数 $\le \log n$。
  2. 若有 $k$ 个 perfect 专家（不止 1 个），给一个更紧的 bound。
  3. 若不保证有 perfect 专家，但保证有一个专家最多犯 $k$ 次错。算法：设 $m$ 为目前最少错次数；跟"目前为止错次数 $\le m$ 的专家"的多数走。给 mistake bound。
dis14 Q2

Vertex Cover → Set Cover

Q5：set/cover 类 reduction

Vertex Cover：无向图 $G=(V,E)$，找最小 $C_V \subseteq V$ 使每条边至少有一端在 $C_V$ 中。Set Cover：universe $U$ + 集合族 $\mathcal{S} = \{S_1, \dots, S_m\}$，找最小 $\mathcal{C}_S \subseteq \mathcal{S}$ 并集 $= U$。

  1. 给出 minimum vertex cover → minimum set cover 的高效归约，证明正确性。
  2. 归约对 set cover 的复杂度意味着什么？
dis16 Q9

Exact 4-SAT（双向归约）

Q5：SAT 变体的标准操作

Exact 4-SAT：每个 clause 恰好 4 个不同 literals。

  1. 3-SAT $\to$ Exact 4-SAT。
  2. Exact 4-SAT $\to$ 3-SAT。
  3. Exact 4-SAT 的复杂度？
dis15 Q1

Kazaam（Rabin-Karp）

Q6 hashing analysis 经典题

给定字符串 $L$（歌词）和 query $Q$，判断 $Q$ 是否为 $L$ 的连续子串。所有字符 ASCII 码 $\in [0, 127]$。Brute force $O(|L| |Q|)$。

  1. 定义 $R(S) = \sum_{i=0}^{|S|-1} 128^{|S|-1-i} s_i$（base-128 整数）。$O(|S|)$ 算 $R(S)$。
  2. 给 $R(L_i)$（$L$ 的第 $i$ 个长 $|Q|$ 子串），$O(1)$ 算 $R(L_{i+1})$。$f = 128^{|Q|}$ 已预处理。
  3. 给 $O(|L|)$ 算法判断 $Q$ 是否在 $L$ 中。
  4. 取 $R'(S) = R(S) \bmod p$（$p$ 随机大素数，$\le 1$ machine word）。给 $R'(L_i)$ 和 $f' = 128^{|Q|} \bmod p$，$O(1)$ 算 $R'(L_{i+1})$。
  5. 给 expected $O(|L|)$ 算法。Pr[假阳性] $\le 1/|Q|$。
dis16 Q3

Streaming Algebra（Q6 模考题）

Q6：维护多个 prefix 极值

数据流 $a_1, \dots, a_N$（$N$ 未知，$N \ge 4$），单遍读，不能存数组。计算

$$\max_{1 \le i < j < k < l \le N} (a_i - 2a_j + 3a_k - 4a_l).$$

限制 $O(\log S)$ bit 内存（$S$ 是结果绝对值上界）。给出确定性流式算法（变量 / 更新 / 正确性 / 内存）。

Round 3 — 综合冲刺 ~8h

限时模考 · 错的题立刻整理到 cheat sheet
dis16 Q6

Review Planning（max-min LP）

Q1-Q3 LP 建模 + 对偶

剩 $T$ 小时复习 $k$ 个 topic。$m$ 种活动，活动 $j$ 上 1 小时给 topic $i$ 提供 $a_{ij}$ 单位准备。$x_j \ge 0$ 表示在 $j$ 上花的小时数。希望最大化最弱的 topic 准备：

$$\max_{x \ge 0,\ \sum x_j = T}\ \min_{i \in [k]} \sum_{j=1}^m a_{ij} x_j.$$
  1. 写成 LP。
  2. 写对偶 LP，从 examiner 角度解释。
dis16 Q13

My Dog Ate My Homework（DP）

Q1-Q3 经典 DP 题型

$\ell \times w$ 网格纸，部分格子被狗咬出洞（$A[i,j] = 1$）。每次只能横切或竖切一张纸一刀。求把所有"被咬"格子和"干净"格子彻底分开的最少切数。设计 $O(\ell^3 w^3)$ DP。

dis16 Q10

Dominating Set NP-complete（Q5 模考题）

完整 in-NP + NP-hard 双段证明

Dominating set $S \subseteq V$：每个 $v \notin S$ 至少有一个邻居 $\in S$。问：是否存在 dominating set $|S| \le k$？证明 NP-complete（$G$ 连通）。

  1. 证 in NP。
  2. 证 NP-hard（提示：从 Vertex Cover 或 Set Cover 归约）。
hw14 Q2

(3,3)-SAT → 3D Matching

最难的 gadget 类 reduction（练手感）

3D Matching：professor $\times$ student $\times$ room 的允许 triple 集合，找一组 triple 使每个 P/S/R 恰好用一次。

  1. 对下面的 gadget（$P_1, P_2, S_1, S_2$ 各只在两个允许 triple 中）描述两种状态。
  2. 对 (3,3)-SAT clause $x \vee y \vee \bar{z}$，如何在三个变量 gadget 上 enforce？
  3. 完成完整归约。
dis16 Q1

Open Addressing 分析

Q6 hashing 分析模板

表大小 $m = 11$，$h(x) = x \bmod 11$，linear probing $h_t(x) = (h(x) + t) \bmod 11$。当前表：

012345678910
1223155182921
  1. 插入 34 的 probe sequence、更新后的表。
  2. 更新后的表中查找 56：probe 序列、成功还是失败。
  3. 假设 probe sequence 是均匀随机的（独立模型），load factor $\alpha = n/m$ 时第一次 probe 碰撞概率？插入新 key 期望 probe 数？
  4. 解释为什么 $\alpha \to 1$ 时 open addressing 变慢，对比 chaining。
hw15 Q5

Streaming Majority（Boyer-Moore）

Q6：经典 deterministic 流式

流 $z_1, \dots, z_m \in [m]$，假设某值 $y$ 出现 $> m/2$ 次（严格多数）。设计确定性算法用 $\mathrm{poly}(\log m)$ 空间输出 $y$。若不存在多数则可输出任意。

hw15 Q4

Reservoir + 重复元素

Q6：随机 + 生日悖论结合
  1. 流 $z_1, \dots, z_T \in [m]$，设计算法在任意时刻 $t$ 输出 $z_1, \dots, z_t$ 的均匀随机元素，空间 $\mathrm{poly}(\log m, \log T)$，单遍。
  2. 流 $z_1, \dots, z_{2m} \in [m]$。$y$ 是 duplicate 当且仅当出现 $\ge 2$ 次。设计算法以概率 $\ge 1 - 1/m$ 输出某 duplicate，空间 $\mathrm{poly}(\log m)$，单遍。
复盘

2026 Spring Midterm 2 KEY 复盘

校准 Q1-Q3 的风格 / 难度

把 Midterm 2 KEY 完整翻一遍，特别看 Q1-Q3：

  • Q1 Running Minimum：单调队列 / sliding window 结构。要点：每个元素 amortized $O(1)$ 入队出队、维护单调性。
  • Q2 Matching Subarrays：把字符串/序列匹配转成 FFT/卷积形式。要点：把"等于"判定转成乘法（指示函数 dot product）。
  • Q3 Arithmetic Trees：树形 DP，子问题按子树定义，由子节点向上 merge。

本题不展开答案——直接打开 PDF 自检。如果某题写不出来，拉到该 topic 的 cheat sheet 加一行模板。

Cheat Sheet 6 页分配

  • 第 1 页：DC / Master Thm / FFT 三件套 + DP 套路
  • 第 2 页：图论模板（DFS/BFS/Dijkstra/Bellman/MST/SCC/Max-Flow）
  • 第 3 页：LP 标准型 + 取对偶机械步骤 + 互补松弛
  • 第 4 页：Zero-sum 游戏 LP 模板（Alice / Bob 两套写法 + value of game）
  • 第 5 页：NPC 已知列表 + 常见 reduction gadget（SAT 变体、3-coloring、Vertex Cover、Hamiltonian）
  • 第 6 页：Hashing（universal / Rabin-Karp / open addressing 期望 $1/(1-\alpha)$）+ Streaming 套路（XOR、求和、Boyer-Moore、reservoir）

节奏建议

5/12 周一 → 5/13 周二
Round 1
5/13 晚 → 5/14 周三
Round 2 + cheat sheet 第 4-6 页
5/15 周五白天
Round 3 限时 + 复盘 Midterm 2 KEY
考前 1h
翻 cheat sheet，不再做新题

如果时间真的紧：丢掉 hw14 Q2 和 dis16 Q13（最长最难、但都不是最高频考点），优先保 Round 2 全部 + Round 3 的 3/5/6/7。