Week 1算法分析基础与渐近记号
📖核心知识点：算法分析的意义与基本方法；渐近记号O/Ω/Θ的严格数学定义与直觉理解；增长率比较——常数<对数<线性<nlogn<多项式<指数<阶乘；递归算法的时间复杂度分析——递归树方法与Master Theorem（主定理）的三种情形及适用条件。⏰本周节奏：第一周概念密度适中但数学严谨性要求高，建议重点掌握Master Theorem的应用并做5-8道递推式求解练习。🎯考试关联：渐近记号的形式化证明和Master Theorem应用是期末必考计算题，通常占10-15分。🧪Tutorial/Lab：练习渐近记号的形式化证明（用极限法或定义法）；用递归树和Master Theorem分析归并排序、快排的复杂度。📌作业关联：所有Assignment都要求写出算法复杂度分析，本周的符号规范直接影响后续作业得分。⚠️易错点：Master Theorem的第三种情形需要验证正则条件；混淆O（上界）和Θ（紧界）导致分析不精确。
Week 2分治策略
📖核心知识点：分治法（Divide and Conquer）三步框架——分解、解决、合并；经典分治算法深入分析——归并排序（稳定性与O(nlogn)保证）、快速排序（期望vs最坏复杂度、随机化pivot选择）；分治法的非平凡应用——最近点对问题O(nlogn)解法、大整数乘法（Karatsuba算法从O(n²)到O(n^1.585)）；逆序对计数（归并排序变体）。⏰本周节奏：分治是后续所有高级算法的基石，建议每个经典问题都手写伪代码并分析复杂度，至少完成6道分治练习题。🎯考试关联：分治设计题是期末大题常客——给定新问题要求设计分治方案并证明正确性和复杂度。🧪Tutorial/Lab：实现Karatsuba大整数乘法；分析最近点对问题的合并步骤为何是O(n)而非O(n²)。📌作业关联：Assignment 1通常包含分治设计题，要求给出完整的伪代码+正确性论证+复杂度分析。⚠️易错点：快排最坏情况O(n²)的触发条件；最近点对合并步骤中strip区域的常数因子证明。
Week 3贪心算法
📖核心知识点：贪心策略的核心思想——局部最优选择导向全局最优；贪心正确性证明技术——交换论证（Exchange Argument）和贪心保持性（Greedy Stays Ahead）；经典贪心问题——活动选择（按结束时间排序）、Huffman编码（最优前缀码）、区间调度最大化、最小生成树（Kruskal/Prim）。⏰本周节奏：贪心的难点不在实现而在证明，建议每个算法都完整写出交换论证或归纳证明，本周至少做6道贪心证明题。🎯考试关联：期末必考贪心设计+证明题——给定问题要求设计贪心策略并用交换论证证明最优性，分值通常15-20分。🧪Tutorial/Lab：用交换论证证明活动选择的贪心策略最优；分析反例说明为何按开始时间排序的贪心不正确。📌作业关联：Assignment中贪心题的评分重点是证明质量而非代码——没有正确性证明的贪心方案不得分。⚠️易错点：贪心不适用时强行使用导致错误（如0-1背包不能用贪心）；交换论证中忘记处理「交换后不变差「的严格论证。
Week 4动态规划（一）：基础与一维DP
📖核心知识点：动态规划核心四要素——最优子结构、重叠子问题、状态定义、转移方程；自顶向下（记忆化递归）vs自底向上（迭代填表）两种实现方式；经典一维DP——斐波那契数列、爬楼梯、最大子数组和（Kadane算法）、最长递增子序列（LIS的O(n²)和O(nlogn)解法）。⏰本周节奏：DP是全课最核心也最难的主题，本周务必建立「状态定义→转移方程→边界条件→填表顺序「的思维框架，至少做10道一维DP题。🎯考试关联：DP设计题是期末压轴大题（20-30分），要求写出状态定义、转移方程、复杂度分析和正确性论证。🧪Tutorial/Lab：实现LIS的两种解法并对比时间复杂度；练习从问题描述中提取DP状态的技巧。📌作业关联：Assignment 1/2几乎必有DP题，状态定义的清晰度和转移方程的正确性是核心评分点。⚠️易错点：DP状态定义不够精确导致转移方程出错；忽略边界条件（base case）初始化；混淆子问题的依赖方向导致填表顺序错误。
Week 5动态规划（二）：二维DP与经典问题
📖核心知识点：二维DP状态设计——编辑距离（Edit Distance）的dp[i][j]含义与三种操作对应的转移；最长公共子序列（LCS）的dp表构造与回溯路径恢复；0-1背包问题的状态转移与空间优化（滚动数组）；矩阵链乘法的区间DP思想——dp[i][j]表示矩阵Ai到Aj的最优括号化方案。⏰本周节奏：二维DP的难度陡增，建议每道题都手画dp表格，理解填表过程后再写代码，本周目标是能独立推导编辑距离和LCS的转移方程。🎯考试关联：编辑距离和LCS是期末高频考题，要求手填dp表并回溯最优解路径；背包问题变体（完全背包、多重背包）常作为设计题出现。🧪Tutorial/Lab：手动填写编辑距离dp表并回溯最优编辑操作序列；实现0-1背包的空间优化版本。📌作业关联：Assignment 2的核心题目通常是DP设计题，要求处理比课堂例题更复杂的约束条件。⚠️易错点：编辑距离的三种操作容易漏掉替换操作；背包空间优化时内循环遍历方向搞反（0-1背包必须逆序）。
Week 6图算法（一）：基础遍历与最短路
📖核心知识点：图的表示——邻接矩阵vs邻接表的时空权衡；BFS与DFS的性质与应用——连通分量、拓扑排序、环检测；最短路径算法——Dijkstra（非负权、贪心+优先队列O((V+E)logV)）、Bellman-Ford（可处理负权O(VE)）、负权环检测；DAG上的最短路径（拓扑排序+松弛）。⏰本周节奏：图算法种类多且细节密集，建议按「BFS/DFS→拓扑排序→Dijkstra→Bellman-Ford「的顺序逐一攻克，每个算法手动模拟至少2个示例图。🎯考试关联：Dijkstra手动模拟过程是期末常考计算题；Bellman-Ford的负权环检测原理是简答题考点。🧪Tutorial/Lab：在加权有向图上手动模拟Dijkstra和Bellman-Ford的松弛过程；实现拓扑排序并检测环。📌作业关联：Assignment 2可能涉及图上的最优路径设计，需要判断适用Dijkstra还是Bellman-Ford。⚠️易错点：Dijkstra不能处理负权边（反例要会构造）；拓扑排序只适用于DAG，有环图上会漏掉节点。
Week 7图算法（二）：网络流与匹配
📖核心知识点：最大流问题与Ford-Fulkerson方法——增广路径、残余图、流量守恒与容量约束；最大流最小割定理的陈述与证明思路；Edmonds-Karp算法（BFS找最短增广路O(VE²)）；最大流的应用——二部图最大匹配、最小顶点覆盖（König定理）、边不相交路径。⏰本周节奏：网络流是全课最抽象的主题，建议先理解Ford-Fulkerson的直觉，再看Edmonds-Karp的复杂度保证，最后练习建模（把实际问题转化为最大流）。🎯考试关联：网络流建模题是期末区分HD和D的关键——给定实际场景要求构造网络流模型并求解。🧪Tutorial/Lab：手动模拟Ford-Fulkerson在小型网络上的执行过程；将二部图匹配问题建模为网络流。📌作业关联：Assignment 2高概率包含网络流建模题，难点在于如何正确建图而非实现算法。⚠️易错点：残余图中反向边的容量更新搞错；建模时遗漏源点/汇点的边或容量设置不当。
Week 8字符串算法与数论基础
📖核心知识点：字符串匹配——朴素算法O(nm)、KMP算法的failure function构造与O(n+m)复杂度证明；Rabin-Karp算法的滚动哈希思想与期望复杂度；数论基础——GCD与扩展欧几里得算法、模运算性质、快速幂算法（O(logn)求a^n mod p）；RSA加密算法的数学基础（选修内容但有助理解）。⏰本周节奏：KMP的failure function是本周难点，建议手动构造3-5个模式串的failure function表格直到完全理解回退逻辑。🎯考试关联：KMP的failure function构造是期末计算题高频考点；快速幂和GCD可能出现在算法设计题中。🧪Tutorial/Lab：手动构造KMP failure function表并模拟匹配过程；实现扩展欧几里得算法求解模逆元。📌作业关联：Assignment可能涉及字符串处理或数论相关的算法设计题。⚠️易错点：KMP failure function的边界处理（j=0时的特殊情况）；Rabin-Karp的哈希冲突处理——需要二次验证。
Week 9NP完全性与计算复杂性
📖核心知识点：P类与NP类问题的形式化定义——确定性vs非确定性图灵机；多项式时间归约（Polynomial Reduction）的定义与方向性；NP完全问题的定义——既在NP中又是NP-hard；Cook-Levin定理（SAT是NP完全的）；经典NP完全问题——3-SAT、顶点覆盖、哈密顿回路、旅行商问题、子集和；归约链的构造方法。⏰本周节奏：NP理论是全课最抽象的内容，重点是理解「归约方向「——证明B是NPC需要从已知NPC问题A归约到B（A≤pB）。🎯考试关联：NP完全性证明是期末大题——给定新问题要求证明其NP完全性（先证NP再证NP-hard），分值15-20分。🧪Tutorial/Lab：练习经典归约——3-SAT→Independent Set→Vertex Cover→Clique；理解归约方向为何不能反过来。📌作业关联：Assignment 2可能要求对给定问题进行NP完全性证明或设计近似算法。⚠️易错点：归约方向搞反——要证B难需要从已知难题归约到B而非从B归约到已知难题；混淆NP与NP完全。
Week 10近似算法与全课总结
📖核心知识点：处理NP难问题的策略——近似算法、启发式算法、参数化算法；近似比的定义与分析；经典近似算法——顶点覆盖的2-近似（贪心取边）、旅行商问题的1.5-近似（Christofides算法思想）、集合覆盖的O(logn)-近似（贪心策略）；全课知识图谱回顾——分治→贪心→DP→图算法→NPC→近似的完整算法设计工具箱。⏰本周节奏：最后一周以整合复习为主，建议按「问题类型→适用算法→证明技术「绘制全课思维导图，重点回顾每类算法的适用条件与正确性证明方法。🎯考试关联：近似算法的近似比分析可能作为期末最后一题出现；全课综合题可能要求判断给定问题适合用哪种算法范式。🧪Tutorial/Lab：分析顶点覆盖2-近似算法的近似比证明；做全课综合模拟题覆盖所有主要算法范式。📌作业关联：所有Assignment截止前的最后检查——确保复杂度分析完整、证明严谨、伪代码清晰。⚠️易错点：近似比的方向搞错（是近似解/最优解还是最优解/近似解取决于最大化还是最小化问题）；复习时只刷题不回顾证明技术。
