COMP3121 Design & Analysis of Algorithms 是 UNSW 计算机系最难的必修课之一，也是留学生挂科率最高的课程之一。本文从实战角度解析每个核心模块，帮助你在 Assignment 和 Final Exam 中脱颖而出。
课程为什么这么难？
COMP3121 的难点不在于"背算法"，而在于证明和推导：
- 你需要证明一个贪心策略是正确的（而不只是给出答案）
- 你需要给出动态规划的状态定义和转移方程，并分析时间复杂度
- Reduction 题目要求你把新问题"归约"到已知 NP 完全问题
很多同学 LeetCode 刷题很熟练，但 COMP3121 Assignment 依然拿不到高分——因为这门课考的是理论推导能力，而不是代码实现。
核心模块详解
1. Greedy Algorithms（贪心算法）
贪心最难的部分是证明最优子结构和贪心选择性。考试常见证明方法：
Exchange Argument（交换论证）：假设最优解与贪心解不同，找出第一个差异点，证明交换后不会变差，从而推出贪心解也是最优解。
常见题型：
- Interval Scheduling（区间调度）
- Job Scheduling with deadlines
- Huffman Coding 的最优前缀编码
考试踩分点：仅给出贪心策略但不证明，通常只得部分分。证明框架必须完整。
2. Dynamic Programming（动态规划）
DP 的标准答题结构：
- 定义状态
dp[i][j]——要说清楚这个值代表什么 - 写出递推关系——base case + transition
- 分析时间/空间复杂度
- 给出伪代码或最终结果提取方式
COMP3121 中常考的 DP 模型：
| 题型 | 状态 | 转移关键 |
|---|---|---|
| LCS / Edit Distance | dp[i][j] = 前i/j个的最优解 | 匹配/不匹配两种情况 |
| Knapsack（背包） | dp[i][w] = 前i物品总重≤w的最大价值 | 选/不选当前物品 |
| Interval DP | dp[l][r] = 区间[l,r]的最优解 | 枚举分割点k |
| Sequence Alignment | dp[i][j] = 对齐前i/j个字符的最小代价 | Gap/Match/Mismatch |
高分技巧：在写递推时，用中文或英文都清楚地注释每一步的含义，教授/助教打分时会给过程分。
3. Network Flow（网络流）
网络流是 COMP3121 Assignment 里最综合的题型，考察：
- 最大流最小割定理（Max-flow Min-cut Theorem）
- 二分图匹配（将匹配问题建模为流问题）
- Ford-Fulkerson / Edmonds-Karp 算法复杂度分析
建模套路：
- 识别"谁给谁提供资源"——建有向边
- 加源点 S（连接所有供给节点）和汇点 T（连接所有需求节点）
- 容量设置为约束条件的数量
- 跑最大流，解读结果
经典 Assignment 题型：用网络流证明某个调度/匹配问题的可行性，或求最大匹配数。
4. NP-Completeness & Reductions（NP完全与归约）
这部分纯考理论，Assignment 和 Final 都占大比重：
Polynomial-time Reduction 的标准写法：
给定问题 A 的实例，构造问题 B 的实例，使得 A 有解 ⟺ B 有解。
常考基础问题（需要熟记其 NP 完全性）：
- 3-SAT
- Vertex Cover
- Independent Set
- Clique
- Hamiltonian Path
- Subset Sum
典型错误：方向搞反了——应该把"新问题"归约到"已知 NP 完全问题"，不是反过来。
Assignment 写作策略
COMP3121 的 Assignment 通常有 6–8 道题，每题 10–15 分。
时间分配建议：
- 先看所有题目，把有把握的先做完
- 贪心/DP 题：先给出解法再证明，别因为证明卡住而放弃后面的题
- NP 归约题：画出归约图再写文字，更清晰
格式要求：
- 使用 LaTeX 或 PDF 提交（不接受手写照片）
- 证明要分步骤，逻辑连贯
- 伪代码需要有注释
Final Exam 备考
COMP3121 期末考试 2 小时，通常 5–6 道大题，每题包含多个子问题。
历年高频考点：
- Greedy + 证明（每年必有）
- DP 状态设计
- 网络流建模
- NP 归约
复习资源：
- 看 Lecture Notes 里的 Theorem 和 Proof，理解思路比背答案重要
- 做 Tutorial 题，自己写完整证明再对答案
- 历年 Final 真题（Ed 或 CSESoc 有分享）
常见作业类型和代写/辅导服务
如果你在 COMP3121 遇到以下情况，建议及时寻求专业帮助：
- Assignment 不知道如何开始证明
- DP 状态定义写不出来
- NP 归约方向搞不清楚
- Deadline 临近但完成度不够
我们提供 COMP3121 全周期辅导和代写服务，覆盖 Assignment 解题思路讲解、完整证明撰写、Final Exam 备考，由 UNSW CS 硕士/博士担任，深度了解本课程出题风格。
欢迎通过微信 ZYFD 联系，提供作业 Brief 后 30 分钟内回复报价。
