Week 1算法分析基础 (Algorithm Analysis)
### 📊 核心知识点:渐近复杂性 探讨算法分析的基石。深入理解大O、大Ω、大Θ记号(Big-O, Big-Omega, Big-Theta notation)。 - **核心概念/公式**: Asymptotic Notation, Master Theorem, Recurrence Relations. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 利用主定理求解递推关系的复杂度。 🧪 **Tutorial/Lab**: 练习从伪代码推导时间复杂度。 📌 **作业关联**: 培养严格的算法证明习惯。 ⚠️ **易错点**: 混淆最坏情况(Worst-case)与大O记号的概念。 (数据来源:2026 Course Handbook)
Week 2分治策略 (Divide and Conquer)
### 🔀 核心知识点:分治与递归 学习如何将大问题拆解为子问题。重点分析归并排序(Merge Sort)、快速排序(Quick Sort)及其平均情况复杂度。 - **核心概念/公式**: Randomized Quicksort, Median of Medians, Closest Pair of Points. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 手写归并排序的合并过程与复杂度证明。 🧪 **Tutorial/Lab**: 实现求解数组中第 K 大元素的线性时间算法。 📌 **作业关联**: Project 1 的基础。 ⚠️ **易错点**: 递归基础情况(Base case)处理遗漏导致无限递归。 (数据来源:2026 Course Handbook)
Week 3动态规划 I (Dynamic Programming)
### 🧠 核心知识点:最优子结构与重叠子问题 引入动态规划(DP)思想。学习自底向上的打表法与自顶向下的备忘录法。 - **核心概念/公式**: Overlapping Subproblems, Optimal Substructure, Bellman Equation. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 15h 🎯 **考试关联**: 写出 DP 状态转移方程(Recurrence relation)。 🧪 **Tutorial/Lab**: 解决经典问题:最长公共子序列(LCS)和矩阵链乘法。 📌 **作业关联**: 复杂数据处理中的最优解问题。 ⚠️ **易错点**: 状态定义不清晰,导致状态转移方程无法涵盖所有情况。 (数据来源:2026 Course Handbook)
Week 4动态规划 II & 贪心算法 (DP & Greedy)
### 🎯 核心知识点:背包问题与贪心选择 对比 DP 与贪心算法。解析 0/1 背包问题(必须用 DP)与分数背包问题(可用贪心)。 - **核心概念/公式**: Greedy-choice Property, Knapsack Problem, Huffman Coding. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 14h 🎯 **考试关联**: 证明某特定问题可以使用贪心算法(交换论证法 Exchange Argument)。 🧪 **Tutorial/Lab**: 实现哈夫曼树进行数据压缩。 📌 **作业关联**: **Assignment 1 发布**,考察 DP 与图算法基础。 ⚠️ **易错点**: 错误地将贪心策略应用于不具备贪心选择性质的问题(如 0/1 背包)。 (数据来源:2026 Course Handbook)
Week 5图算法 I:遍历与拓扑排序 (Graph Algorithms)
### 🕸️ 核心知识点:BFS 与 DFS 系统学习图的表示方法(邻接矩阵与邻接表)。深入探索广度优先搜索(BFS)与深度优先搜索(DFS)的应用。 - **核心概念/公式**: Topological Sorting, Strongly Connected Components (SCC), Kosaraju's Algorithm. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 给出有向图,画出强连通分量。 🧪 **Tutorial/Lab**: 利用有向无环图(DAG)寻找任务的执行顺序。 📌 **作业关联**: 为处理复杂网络网络数据打底。 ⚠️ **易错点**: 混淆有向图中的树边、后向边、前向边与交叉边。 (数据来源:2026 Course Handbook)
Week 6图算法 II:最短路径 (Shortest Paths)
### 📍 核心知识点:Dijkstra 与 Bellman-Ford 解决单源最短路径(SSSP)与多源最短路径(APSP)问题。处理带负权边的图网络。 - **核心概念/公式**: Dijkstra's Algorithm, Bellman-Ford, Floyd-Warshall, Negative Cycles. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 15h 🎯 **考试关联**: 追踪 Dijkstra 算法中优先队列的状态变化。 🧪 **Tutorial/Lab**: 编写算法检测外汇交易中的套利机会(负权环)。 📌 **作业关联**: **Assignment 1 截止**。 🔥 ⚠️ **易错点**: 将 Dijkstra 算法用于包含负权边的图。 (数据来源:2026 Course Handbook)
Week 7图算法 III:最小生成树 (MST) & 网络流 (Network Flow)
### 💧 核心知识点:Kruskal, Prim 与最大流 学习贪心算法在 MST 中的经典应用。引入最大流/最小割定理(Max-flow Min-cut Theorem)。 - **核心概念/公式**: Kruskal's, Prim's, Disjoint-Set Data Structure (Union-Find), Ford-Fulkerson. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 15h 🎯 **考试关联**: 给定流量网络,寻找增广路径并计算最大流。 🧪 **Tutorial/Lab**: 使用并查集优化 Kruskal 算法。 📌 **作业关联**: 二分图匹配问题(Bipartite Matching)。 ⚠️ **易错点**: 混淆网络流中的反向边容量更新逻辑。 (数据来源:2026 Course Handbook)
Week 8字符串匹配算法 (String Matching)
### 🔤 核心知识点:KMP 算法与前缀函数 处理大规模文本搜索问题。学习朴素字符串匹配、Rabin-Karp 滚动哈希以及 KMP 算法。 - **核心概念/公式**: Knuth-Morris-Pratt (KMP) Algorithm, Prefix Function (Pi array), Rabin-Karp. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 计算给定模式串的 KMP 前缀数组。 🧪 **Tutorial/Lab**: 比较不同字符串算法在长文本中的执行时间。 📌 **作业关联**: **Assignment 2 发布**,重点考察图论高级应用与高级数据结构。 ⚠️ **易错点**: KMP 算法中状态回退(Fallback)的逻辑边界错误。 (数据来源:2026 Course Handbook)
Week 9计算复杂性理论 I (Complexity Theory)
### ⏱️ 核心知识点:P 与 NP 类问题 跨越算法设计,进入计算理论领域。探讨多项式时间可解问题(P)与多项式时间可验证问题(NP)。 - **核心概念/公式**: P vs NP, Deterministic vs Non-deterministic Turing Machines, Polynomial-time Verification. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 18h 🎯 **考试关联**: 简述 NP 类的严格数学定义。 🧪 **Tutorial/Lab**: 理论推演,无编程代码。 📌 **作业关联**: 理解某些问题的不可解性边界。 ⚠️ **易错点**: 误以为 NP 问题就是“Non-Polynomial(非多项式)”问题。 (数据来源:2026 Course Handbook)
Week 10计算复杂性理论 II:NP-Hardness
### 🧱 核心知识点:NP 完全性与归约 (Reductions) 学习多项式时间归约(Polynomial-time Reductions)。证明问题的 NP-Complete (NPC) 性质。 - **核心概念/公式**: NP-Complete, NP-Hard, SAT Problem, Clique, Vertex Cover. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 20h 🎯 **考试关联**: 证明问题 B 是 NP-Hard(通过将已知 NPC 问题 A 归约到 B)。 🧪 **Tutorial/Lab**: 练习经典的图论问题归约链条。 📌 **作业关联**: 证明某些算法任务不存在多项式精确解。 ⚠️ **易错点**: 归约方向搞反(必须从已知难问题归约到未知问题)。 (数据来源:2026 Course Handbook)
Week 11近似算法与随机化算法 (Approximation & Randomized Algorithms)
### 🎲 核心知识点:应对 NP 难问题 既然 NPC 问题无法在多项式时间内完美解决,我们学习如何寻找有性能保证的近似解(Approximation Ratio)及随机化策略。 - **核心概念/公式**: Approximation Ratio, Vertex Cover Approximation, Randomized Algorithms (Las Vegas vs Monte Carlo). ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 14h 🎯 **考试关联**: 证明某种贪心近似算法的近似比界限。 🧪 **Tutorial/Lab**: 实现 TSP(旅行商问题)的近似算法。 📌 **作业关联**: **Assignment 2 截止**。 🔥 ⚠️ **易错点**: 混淆 Las Vegas 算法(时间随机,结果一定正确)与 Monte Carlo 算法。 (数据来源:2026 Course Handbook)
Week 12期末复习与全课程串讲 (Review)
### 📝 复习周:算法思想大一统 串联分治、DP、贪心三大设计范式;总结图论与字符串匹配;回顾 P/NP 的理论天花板。 - **核心概念/公式**: Algorithm Design Paradigms, Reductions summary, Exam Strategy. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 20h+ 🎯 **考试关联**: 综合设计题:给定一个全新的问题,要求分析其复杂度并设计最优算法。 🧪 **Tutorial/Lab**: 历年 Final 真题冲刺解析。 📌 **作业关联**: 查漏补缺。 ⚠️ **易错点**: 考试时只写代码不写证明。COMP90038 极度强调算法正确性的数学证明。 (数据来源:2026 Course Handbook)