见招拆招，逢水架桥

图：本文生成式概念插画。六座城市的道具不同，铁路却都在追问同一件事：可能性应当怎样被处理。

六种算法，起初像住在不同的城市

第一次把 COMP3121 的材料全部摊开，桌面很像一张尚未修通铁路的地图。

Greedy 在安排活动，DP 忙着填表，Divide and Conquer 把整数和多项式切开；Flow Networks 里水沿着边流，到了 Intractability，画风忽然变成 SAT、Clique 与一串方向很容易写反的 reductions。Foundations 坐在最前面，表情严肃地提醒每个人：先把 O、Ω、Θ 分清楚。

它们看起来像六门小课，甚至拥有不同的道具。于是复习时最自然的做法，是给每座城市发一张清单：

清单没有错，却解释不了一件更有意思的事：为什么同一道 Activity Selection，目标从“数量最多”换成“总时长最大”，Greedy 就要把位置让给 DP？ 为什么 Max Flow 的 reverse edge 与 DP 的 backpointer 都在保存过去，却一个用于撤销、一个用于重建？ 为什么 Merge Sort 与 FFT 拥有相同形状的 recurrence，语义却相距甚远？

铁路从这些问题里出现。

COMP3121 的几种方法，其实都在管理一个共同的东西：possibility space。

- Greedy 证明某些未来可以永久删掉； - Dynamic Programming 把对未来等价的过去合并成一个 state； - Divide and Conquer 把彼此独立的部分分开，再处理边界上的重逢； - Flow Networks 把允许与禁止、供给与容量写成一张守恒的图； - Intractability 研究当可能性无法被上述结构充分压缩时，难度怎样在问题之间传递； - Foundations 则规定，所有这些“删掉”“合并”“更快”“正确”必须怎样被清楚地证明。

算法设计因此不是一柜子招式，更像一套治理可能性的制度。学到最后，真正希望留下的也不只是“看到某个词就调用某个算法”，而是能在算法名字出现以前，先看见题目怎样允许它的未来存在。

图：课程模块不是六只互不相干的抽屉，而是五种处理 possibility space 的动作，加上一套负责衡量和证明的语法。作者自制。

Foundations：先规定“快”与“对”的语法

Asymptotic Notation

对充分大的 n：

- f ∈ O(g)：f 最终不超过 g 的常数倍； - f ∈ Ω(g)：f 最终不小于 g 的常数倍； - f ∈ Θ(g)：两者同时成立，即同阶增长。

几个必须稳定的关系：

其中 ε 0 为常数。对数底数在裸 log n 的 Θ 关系中通常只差常数倍，但 exponent 里的底数不能随意抹掉：

不能把 2 换成别的底数当作同一函数。

顺序执行与嵌套执行

- 顺序执行：复杂度相加，最后由最大项支配； - 嵌套执行：通常相乘； - 分支：worst-case 取最慢分支； - recursion：先写 recurrence，再分析； - graph input size：通常是 |V| + |E|，linear-time graph algorithm 为 O(|V| + |E|)。

Input Size：数字有两副面孔

整数 C 的数值可能很大，但 binary encoding 只需 Θ(log C) bits。

因此：

- O(nC) Knapsack DP 是 pseudo-polynomial； - large integer multiplication 必须按 bit width n 计成本； - weighted graph 的 edge weights 也贡献输入位数。

“关于数值是 polynomial”与“关于输入长度是 polynomial”不是同一句话。

数据结构不是附录

课程 prerequsite materials 复习了 array、linked list、stack、queue、deque、heap、BST、frequency table 与 hash table。它们直接改变算法 bound：

- Dijkstra 用 array：O(n² + m)； - 用 augmented heap：O((n + m) log n)； - Kruskal 用 Union-Find：O(m log n)； - Kahn 用 queue：O(V + E)； - BFS / DFS：O(V + E)。

算法的抽象选择与 data structure 的实现选择要分开分析，但二者最终会在复杂度里相遇。

Proof 的三种基本动作

Induction：证明 size n 的答案由更小 sizes 的正确答案构成。

Invariant：

1. initialization：开始前成立； 2. maintenance：每步后保持； 3. termination：结束时 invariant 推出目标结论。

Contradiction：假设算法结论错误，利用最早分歧、最短反例、cycle 或更优方案推出矛盾。

Welcome slides 的判断很直接：testing 很好，proof 才能覆盖那些尚未想到的 inputs。测试会找到 bug；证明要解释为什么某一整类 bug 无处可藏。

Stable Matching：Foundations 里的完整证明样本

Foundations slides 用 Gale-Shapley 展示一份算法怎样同时证明 termination、feasibility 与 correctness。

有 n 位 developers 与 n 位 clients，每个人都给出对另一侧的严格 preference order。Matching 是 stable 的，当且仅当不存在一对没有匹配在一起的 developer d 与 client c，使二者都更偏好彼此而非当前 partner。这样的二人组叫 blocking pair。

Developer-proposing Gale-Shapley：

1. 初始所有 developers 都 solo； 2. 任取一位仍 solo、且尚未向所有 clients 提议的 developer； 3. 他向尚未提议过的、最偏好的 client 提议； 4. 若 client 当前 solo，就暂时接受； 5. 若 client 已有 partner，就在当前 partner 与新 proposer 中保留更偏好者，另一位变为 solo； 6. 重复直到没有可继续提议的 solo developer。

三项证明：

- Termination：每个 developer 对每个 client 至多提议一次，总 proposals 至多 n²； - Perfect matching：若结束时仍有 solo developer，他必已向所有 clients 提议；于是所有 clients 都曾收到提议并处于匹配中，这与仍有 developer solo 矛盾； - Stability：假设最终存在 blocking pair (d,c)。既然 d 更喜欢 c 而非最终 partner，他一定更早向 c 提议过。c 当时拒绝 d，或后来换掉 d，只可能是因为她拥有一个更偏好的 partner；此后她的 partner 只会越来越符合她的偏好，因此最终不可能更喜欢 d，矛盾。

在适当的数据结构下，proposal 次数主导运行时间，得到 O(n²)。这组证明很值得迁移：算法可以 revise 临时决定，但某个 monotone property 始终向前——developers 的选择逐渐变差，clients 手中的 partner 逐渐变好。

一张方法选择图

面对陌生 optimisation / counting / graph problem，可以先问：

这不是自动分类器。很多题有多种正确方法；Activity Selection 就同时展示了：

- 最大数量版本：Greedy； - 最大总 duration 版本：DP。

题目的 nouns 没换，objective 一换，方法便换了。

Greedy：把删除 possibilities 变成可证明的动作

Greedy 每个 stage 只作当前最好的选择。它的核心不是 selection rule，而是 safe-choice proof。

两类证明

Exchange argument：

- 取任意 optimal solution； - 找到与 greedy 的第一个不同点； - 把该位置换成 greedy choice； - 证明 feasibility 保持、objective 不变差； - 重复直到得到 greedy solution。

Greedy stays ahead：

- 定义每完成 k 个选择后的 progress； - 用 induction 证明 greedy 对每个 k 都不落后； - 在终点推出 greedy 不可能使用更多资源或取得更差 objective。

课程主线

| Problem | Rule | Complexity | Proof hinge | |---|---|---|---| | Activity Selection | earliest finish | O(n log n) | exchange | | Cell Towers | tower 放在最左未覆盖房屋右侧 r | sorted 时 O(n) | stays ahead | | Tape Storage | pᵢ/Lᵢ 递减 | O(n log n) | adjacent swap | | Min Maximum Lateness | deadline 递增 | O(n log n) | adjacent swap | | Huffman | 合并两个最小频率 | O(n log n) | sibling lemma | | Dijkstra | 最小 tentative distance | O((V+E) log V) with heap | non-negative edge invariant | | Kruskal | 最轻 non-cycle edge | O(m log n) | cut property |

Graph structure

Greedy module还覆盖：

- SCC：Tarjan / Kosaraju，O(V + E)； - condensation graph：把 SCC 压成 DAG； - topological order：Kahn，O(V + E)。

它们不必都称为 greedy，但常用于简化 graph structure 或为 DP 提供 computation order。

最近的陷阱

- Fractional Knapsack 可按 value density greedy；0-1 Knapsack 不行； - Dijkstra 要求 non-negative edge weights； - shortest-path tree 与 MST 的 objective 不同； - edge weight ties 下 MST 未必唯一； - “选最短活动”不等于“最早结束”。

Greedy 的辨认问题永远是：

哪个 exchange 或 invariant 证明我删掉的未来真的不再需要？

Dynamic Programming：把历史折叠成 state

DP 适合 overlapping subproblems 与 optimal substructure。完整 scaffold：

State 设计

State 必须保存未来判断 transition 所需的信息。

LIS 若只记录“前 i 项的 LIS 长度”，就不知道最优 subsequence 的结尾，无法判断 A[i + 1] 能否接上。改成：

recurrence 才出现：

高频 templates

| Problem | State | Time | |---|---|---| | Hopscotch | ways(i) | O(n) | | LIS | ending index i | O(n²) | | 0-1 Knapsack | capacity c、前 k items | O(nC) | | LCS / Edit Distance | 两个 prefix lengths | O(nm) | | Matrix Chain | interval (i, j) | O(n³) | | DAG shortest path | vertex | O(V + E) | | Bellman-Ford | edge budget、vertex | O(VE) | | Floyd-Warshall | endpoints、allowed intermediates | O(V³) | | Tree DP | subtree root、boundary state | 依 transition |

Correctness

证明 recurrence：

1. 每个候选 transition 都构造合法 parent solution； 2. 任意最优 parent solution 的最后一步必属于某个候选； 3. 若其 child 部分不最优，可替换后改进 parent，矛盾。

再检查 base cases、dependency order 与 overall answer。

Reconstruction

若题目要求 actual sequence / path / choices，同时保存使 recurrence 取优的 predecessor。先算 value，再沿 backpointers 回溯。

把整条方案直接塞进每个 state 不仅笨重，也容易让复杂度分析失真。

同一模块末尾的 String Matching

官方 DP slides 末尾还讲到：

- Rabin-Karp：用 rolling hash 在常数时间更新相邻 text windows 的 hash；hash 相同仍需处理 collision； - KMP：用 failure function 保存 pattern prefix 与当前 matched suffix 的重叠，使 text scan 不回退，预处理加扫描为 O(n + m)。

它们不属于经典的 optimisation DP，但共享同一种节约：已经确认的结构不重复支付。复习时应知道它们位于 Module 3，同时不要把所有“复用信息”的算法都称为 DP。

Divide and Conquer：独立解决，再在边界相见

D&C 的结构：

若 size n 的 instance 产生 a 个 size n/b 的 children，本层额外工作 f(n)：

课程主线

- Binary Search：Θ(log n)； - discrete binary search：decision cost g(n)、答案范围宽度 K，总时间 O(g(n) log K)； - Merge Sort：Θ(n log n)； - Inversion Counting：modified merge，Θ(n log n)； - Quicksort：平均 Θ(n log n)，最坏 Θ(n²)； - Karatsuba：T(n)=3T(n/2)+Θ(n)，所以 Θ(n^(log₂3))； - FFT：T(n)=2T(n/2)+Θ(n)，所以 Θ(n log n)； - convolution / polynomial multiplication：借 FFT 达到 Θ(n log n)。

Master Theorem

令：

比较 f(n) 与 n^c：

- 小一个 polynomial factor：Θ(n^c)； - 同阶：Θ(n^c log n)； - 大一个 polynomial factor且满足 regularity：Θ(f(n))。

它不直接覆盖 T(n - 1)、unequal splits，也不覆盖所有多一个 log 的情况。用不了时改用 recursion tree、expansion 或 substitution。

Correctness hinge

D&C 题最容易漏的是 cross-boundary cases。Inversion Counting 的左右内部 inversions 可递归处理，但跨 halves 的 inversions 必须在 merge 中完整计数。Combine 不是例行收尾，而往往是整道题真正的新算法。

Flow Networks：把资源守恒写进图里

Flow 是这门课里最像工程系统的一章：source 送出资源，sink 接收资源，edge capacities 限制通行量，intermediate vertices 遵守 conservation。

定义

Flow network 是 directed graph G=(V,E)，每条 edge 有 positive integer capacity c(u,v)，并有 source s 与 sink t。

Flow f 满足：

以及对所有 v ≠ s,t：

Residual Network：算法保留后悔的方式

若原 edge (u,v) capacity 为 c、当前 flow 为 f，residual graph 中：

forward edge 表示还能多送多少；reverse edge 表示可以撤回多少既有 flow。

没有 reverse capacity，早期增广选错一条路后，算法将无法重排已有 flow。Residual graph 保存的不是额外资源，而是改判一次旧决定的权利。

Ford-Fulkerson

1. 初始 flow 为 0； 2. 在 residual graph 找任意 s→t augmenting path； 3. 取该路径最小 residual capacity 作为 bottleneck； 4. 沿路径增广，并更新 forward / reverse residual capacities； 5. 直到不存在 augmenting path。

整数 capacities 下，Integrality Theorem 保证存在 integer maximum flow。

复杂度：

其中 |f| 是 maximum-flow value。它不是只由 graph size 构成的 strongly polynomial bound。

Edmonds-Karp

固定用 BFS 选择 edge 数最少的 augmenting path：

它牺牲了 path 选择自由，换来只依赖 V,E 的 polynomial bound。

Max-Flow Min-Cut

任意 s-t cut (S,T) 的 capacity 是所有从 S 指向 T 的原图 edges capacities 之和。

任何 flow value 都不超过任何 cut capacity。Ford-Fulkerson 终止时，从 s 在 residual graph 中可达的 vertices 构成 S，其余构成 T；跨 cut 的 forward edges 已饱和、reverse 方向净流被正确扣除，于是：

max flow 是算法找到的成就，min cut 是系统不允许再大的证书。

Modeling Tricks

Multiple sources / sinks：

- 添加 super-source 连向各 source； - 各 sink 连向 super-sink； - capacities 取各自供给/需求或足够大的上界。

Vertex capacity：

把 vertex v 拆成：

中间 edge capacity 等于 vertex capacity；原 incoming edges 指向 vin，outgoing edges 从 vout 发出。

Bipartite Matching：

所有 capacities 为 1。Integrality 保证 flow 对应离散 matching。通过 Ford-Fulkerson 可在课程口径下达到 O(VE)。

建模正确性的双向要求

一张 flow network 正确，不只要说明“每个现实方案能变成 flow”，还要说明：

错误 construction 常允许 flow 穿过现实中不存在的转运路线，或让同一单位资源被重复使用。额外期末题中的 banana network 正是在考这一点：看起来 capacities 都放上去了，不代表每个 valid flow 都忠实对应一次合法 delivery。

Intractability：当“更聪明地搜索”仍不够

Decision Problems

P、NP、NP-hard、NP-complete 的正式讨论通常从 YES/NO problem 开始。

- P：可在 polynomial time 决定； - NP：YES instances 存在 polynomial-length certificate，可由 polynomial-time verifier 检查； - NP-hard：NP 中每个问题都能 polynomially reduce 到它； - NP-complete：既在 NP，又 NP-hard。

NP 不是“non-polynomial”，也不是“很难验证”。Verifier 收到 certificate；它不用自己把 certificate 找出来。

Polynomial Reduction

表示能在 polynomial time 把每个 A-instance x 转为 B-instance g(x)，并保持：

方向跟随 hypothetical solver：

因此要证明 target problem B NP-hard，应从 known NP-hard problem A reduce to B。因为“B 看起来更难”而把箭头反过来，是复杂性章节最昂贵的一次转身。

NP-completeness Proof Scaffold

只证明 intended source solution 能产生 target solution，完成了 (⇒)；还必须证明任何 target solution 都能 decode 回 source solution，即 (⇐)。Gadget 不能偷偷拥有一种额外状态绕开原问题约束。

课程中的 known-hard problems

课程总结列出：

- CliqueCover； - Colouring； - VertexCover； - Independent Set； - HittingSet； - SetCover； - Partition； - SubsetSum； - SAT / 3SAT； - LongestPath； - Hamiltonian Path / Cycle； - Travelling Salesperson。

考试中选择 source problem 时，优先选择结构贴近 target constraint 的那个，而不是名字听起来最著名的那个。

Optimisation 与 Decision

NP-completeness 针对 decision problems。面对 optimisation：

- 先写 threshold decision version； - 说明 optimisation solver 怎样回答 decision； - 或说明 decision oracle 如何通过 binary search 等方式恢复 optimum。

不要直接写“这个 optimisation problem 是 NP-complete”，除非课程语境已经明确采用相应定义。更稳妥的是区分“NP-hard optimisation problem”与其“NP-complete decision version”。

面对 NP-hardness 的三条路

1. Exact but superpolynomial：meet-in-the-middle、subset DP、TSP DP； 2. Pseudo-polynomial：如 O(nC) Knapsack，适合 numeric parameter 较小； 3. Approximation：polynomial time 返回有保证的 feasible solution。

课程总结提到 Minimum Vertex Cover、Maximum 0-1 Knapsack 与 Metric TSP 的 approximation。Approximation ratio 的方向要随 minimisation / maximisation 区分，不能一概写 A/OPT ≤ r。

NP-hard 不代表每个 instance 都难，也不代表实践中只能投降。它给出的是一张路线警告：那条对所有 inputs 都 polynomial、又保证 exact optimum 的通用道路，至少目前没有被发现。

Graph Algorithms 放在一起看

| 目标 | 条件 | 算法 | 时间 | |---|---|---|---| | BFS reachability / unweighted shortest | unweighted | BFS | O(V+E) | | SCC | directed | Tarjan / Kosaraju | O(V+E) | | Topological order | DAG | Kahn / DFS | O(V+E) | | SSSP | non-negative weights | Dijkstra | O((V+E) log V) with heap | | SSSP | negative edges, no reachable negative cycle | Bellman-Ford | O(VE) | | APSP | negative edges allowed, no negative cycle | Floyd-Warshall | O(V³) | | MST | connected undirected weighted | Kruskal | O(E log V) | | Maximum flow | integer capacities | Ford-Fulkerson | O(E|f|) | | Maximum flow | general course bound | Edmonds-Karp | O(VE²) | | Bipartite matching | bipartite | flow reduction | O(VE) in course analysis |

选算法前先读 assumptions。Dijkstra、Bellman-Ford、DAG shortest paths 都回答 shortest path，但负权、cycles、source 数量与输出范围不同。

一份完整的算法设计答案

Problem Restatement

用一两句明确：

- input； - desired output； - feasibility； - optimisation objective。

Algorithm Description

按题型选择结构：

Greedy

DP

D&C

Flow

Reduction

Correctness

先写精确 claim，再证明：

证明结束时明确回到 claim。不要让最后一句停在一个局部 lemma 上。

Complexity

先定义：

再列各阶段成本：

最后化简。若题目要求特定 bound，需要展示你的 construction 代入后确实满足，而非只引用通用算法名字。

Proof Toolbox：看到结构就拿对应工具

| 证明目标 | 常用工具 | 典型 hinge | |---|---|---| | Greedy selection safe | exchange | 第一个分歧 | | Greedy progress optimal | stays ahead | 第 k 步比较 | | Iterative algorithm | invariant | initialization/maintenance/termination | | Recursive algorithm | strong induction | combine | | DP recurrence | optimal substructure | 最后一步分类 | | Dijkstra | contradiction | 最短假想路径第一次离开 settled set | | MST | cut/cycle exchange | 用轻 edge 替换重 edge | | Max flow | cut certificate | 无 augmenting path | | Reduction | iff | encode 与 decode | | NP membership | certificate | 长度与 verifier 时间 |

这张表不是为了让证明模板化，而是帮助你尽快找到“哪一个细节正在承担正确性”。

复杂度自检表

Sorting

comparison sort 通常 O(n log n)。若 input 已排序，别重复付费。

Heap

- build：课程某些分析采用 O(n log n) 的直接插入；更快 build-heap 也存在； - extract-min：O(log n)； - decrease-key：augmented heap O(log n)； - 次数通常按 vertices 或 edges 计。

DP

再加 reconstruction。

Recursion

写清：

不要只写 Master Theorem case 编号。

Flow Construction

若原题有 n 个对象、m 个关系，construction 后可能是：

把 V', E' 代入 Ford-Fulkerson / Edmonds-Karp。若 capacities 导致 |f| ≤ k，Ford-Fulkerson 可能给出更好 bound。

Reductions

除了运行 transformation 的时间，还要检查 output encoding size。构造一个指数大小 target instance，再说每一步 polynomial，并没有完成 polynomial reduction。

最容易把相邻概念揉成一团的地方

Maximal 与 Maximum

- maximal：无法再加入元素； - maximum：size/value 全局最大。

一个 maximal matching 未必 maximum matching。

Minimum Spanning Tree 与 Shortest-Path Tree

- MST 最小化全体 selected edges 的总权重； - shortest-path tree 最小化固定 source 到每个 vertex 的路径长度。

它们都叫 tree，也都喜欢小 edge，但账本不是同一本。

Subsequence 与 Substring

- subsequence 可跳过字符； - substring 必须连续。

LCS recurrence 不能直接回答 longest common substring。

Pseudo-polynomial 与 Polynomial

O(nC) 若 C binary encoded，不是 input-length polynomial。

NP-hard 与 NP-complete

NP-complete 还要求 membership in NP；optimization problems 常只说 NP-hard。

Residual Reverse Edge 与原图反向通道

Residual reverse capacity 表示撤销已有 flow，不代表现实网络新增了一条可运送资源的物理 edge。

按题目动词分配注意力

题目写 design，你需要给完整 algorithm，不只是名字。

写 justify，要指出 correctness hinge，不是复述步骤。

写 analyse，要把操作次数与 input size 对上。

写 construct a flow network，要给 vertices、edges、capacities、source/sink、运行的算法与答案判定。

写 prove NP-complete，必须同时有 NP membership 与 NP-hardness。

写 find the sequence，value-only DP 不够，要保存 predecessors。

写 use the best possible bound，要比较可用算法并结合 construction 的特殊参数，而非机械引用最熟的那一个。

学算法，不只是把算法放进记忆

重读一页熟悉的 slides，会产生一种很温柔的错觉：每行都看得懂，于是仿佛自己也能从空白纸上写出来。可 recognition 与 generation 并不是同一件事。

学习科学不能替我们证明 Dijkstra，也不会自动设计 DP state。它能做的是提醒我们：怎样安排练习，才更可能让知识在需要时被取出、区分和迁移。

先读懂一个 worked example，但不要只观看

对 novice，直接在空白题面上同时寻找 state、recurrence、proof 与 complexity，可能让 problem-solving search 占满认知资源。Sweller 的早期研究据此讨论了 means-ends problem solving 与 schema acquisition 之间的张力；这个结论不能被粗暴翻译成“不要探索”，更合理的用法是：第一次建立 representation 时给足支架，随后逐渐撤掉。 Sweller, 1988

阅读 worked example 时，每一步都补一句 self-explanation：

Chi 等人对 mechanics examples 的 think-aloud 研究观察到，表现较好的学习者会更常把 solution steps 连接到 principles，并形成较少依赖原例的知识。它不是一项针对算法课程的随机实验，但足以让“边看边点头”显得不太可靠。 Chi et al., 1989

把书合上，让知识自己回来

Roediger 与 Karpicke 的两项 prose-learning experiments 显示：反复阅读在五分钟后的测试更占优势，但在两天和一周后的测试中，先前进行 free-recall tests 的组保持得更好；反复阅读还提高了学习者对自己记忆的信心。材料与延迟范围都有边界，不能把结果机械外推到每一种算法能力，但它准确指出了“看起来熟”与“之后取得出”之间的裂缝。 Roediger & Karpicke, 2006

因此每章都做一次 blank-page reconstruction：

- 问题定义； - algorithm； - correctness hinge； - complexity derivation； - 一个会破坏算法的 constraint change。

想不起来时先努力恢复结构，再查看资料。目标不是制造挫败，而是让缺口变得可见。

不要把同类题永远关在同一个抽屉

若十道题都在标题上写着“DP”，练习只要求完成 recurrence；真正的考试却先要求判断它是不是 DP。

Rohrer 与 Taylor 在 college mathematics learning 的 experiments 中比较了集中与 shuffled practice；他们报告，一周后的测试中，分散或混合安排在相应实验里带来更好的表现。具体任务与安排限制了外推范围，但对算法复习有一个合理启发：后期练习应交错 Greedy、DP、D&C 与 Flow，让“选择方法”本身也成为被练习的技能。 Rohrer & Taylor, 2007

可以把以下题目混在同一页，不标章节：

- 最大数量的 compatible activities； - 最大总时长的 compatible activities； - 非负权最短路； - DAG 上允许负权的最短路； - vertex-disjoint paths； - 一个带 monotone decision predicate 的 optimisation problem。

每题先只写“为什么是这种方法，为什么不是最近的 sibling method”。

把相似故事换开，把相同结构叠起来

Gentner、Loewenstein 与 Thompson 的 analogical-encoding studies 发现，在他们的 negotiation-learning tasks 中，比较两个 cases 有助于 novice 抽取并迁移 relational schema。它不能直接充当算法教育效果证明，但给了我们一项具体练习：对两个题建立 mapping，而不是各写一份摘要。 Gentner, Loewenstein & Thompson, 2003

题目的 nouns 可以换。mapping 的关系不能含糊。

最后，用反例给边界上色

主动击穿错误直觉：

- shortest activity first； - 0-1 Knapsack 按 value density； - Dijkstra 加一条 negative edge； - LIS 把 len(n) 当 overall answer； - flow construction 允许现实中非法转运； - reduction 箭头反向。

一个小反例不只告诉你“这招错了”。它会指出正确方法究竟依赖哪个 assumption。那条 assumption，往往就是之后最容易被检索出来的 proof hinge。

考前优先级

资料口径

这份整理综合了本地的官方 course slides、Course Notes.pdf、prerequisite review、每周题目，以及额外的中文期末复习讲义。

- 官方 welcome slides 明确期末包含 multiple choice、short answer 与 algorithm design problems，并要求算法以清晰的 plain English 表达，配套 correctness 与 time complexity； - 额外复习讲义把 max flow 标作“必考”，并把 Master Theorem、Greedy、DP、Flow、P/NP/NP-hard/NP-complete 等列为复习主轴。

后者适合用来安排复习优先级，但不应当作官方范围承诺。本文的定义、算法与复杂度以官方 slides 和课程总结为准；“高频”只作为学习导航。

结合官方课程结构与额外复习资料，可以按以下层次复习，但应以当期正式公告为最终依据。

第一层：必须能从空白写出

- asymptotic analysis 与 recurrence； - exchange / stays-ahead； - DP scaffold 与 state design； - Dijkstra、Kruskal； - residual graph、Ford-Fulkerson、min-cut； - P / NP / NP-hard / NP-complete； - reduction direction 与双向证明。

第二层：必须能迁移

- Activity Selection 的 objective 变化； - 0-1 与 unbounded Knapsack； - LIS / Edit Distance / interval DP； - discrete binary search； - inversion counting； - super-source/sink、vertex splitting、bipartite matching； - certificate 与 gadget consistency。

第三层：必须能解释核心机制

- Karatsuba 为什么从四次递归变三次； - FFT 为什么用 roots of unity 与 even/odd split； - Bellman-Ford / Floyd-Warshall 的 state 参数； - approximation ratio 与 pseudo-polynomial algorithm 的边界。

课程最后留下的

Greedy 教你删掉未来，但要先证明它安全； DP 教你保存未来，但只保存仍能被区分的部分； D&C 教你拆开问题，却把最难的思考留给 Combine； Flow 把现实约束改写成容量与守恒； Complexity theory 则提醒我们，有些搜索空间不是换一个更聪明的循环就会消失。

这些方法的共同点，是它们都在问同一件事：

面对数量惊人的可能性，哪些差异是真实的，哪些只是重复，哪些可以被结构一次性处理？

当你能回答这个问题，算法名字通常已经不远了。 更重要的是，即使题目换了故事、换了变量、换了一层看似很新的皮，你仍然知道从哪里下手。

更进一步说，当我们面对不是纸面上的问题，而是现实里的真实的问题时，我们又该如何面对。 这才是算法真正想留下的东西——见招拆招，逢水架桥。