CSCI3160 学习入口
2026-10-13 完成本轮自足学习更新：22 份主讲与 13 份辅导，共 666 页，42 份分段学习笔记。原件的定义、公式、例题输入、代码与伪代码、图表数据和证明已融入按页序展开的正文，可直接按 Part 学习；原页码保留作出处定位。必要推导放在主线，历史试题仍单列附录。
2026-09-17 从教师课程页重新下载全部 35 份对应材料，字节均与本地原件一致。该次版本核验针对 2026-09-17 当时可取得的官网文件，没有把旧 PDF 的原始学期改写成 2026。L04 以后及 T02 以后多数链接在该次核验时处于官网隐藏行中，保留为预习材料；这与文件可以访问是两回事。
先从下表按讲次阅读；遇到“见附录”可在同一文件跳转并返回。附录演练有题源和过程，A 级表示这份历史卷确实考过，B 级是官方范围或方式的明确说明，C 级是通识判断。扫描题标出视觉读取；缺题干的解答卷不用于反推题目。
- 阅读导航：基础、贪心、动态规划、图、近似算法的承接顺序。
- 课程索引索引（本地资料）：只收入主讲有出处的知识，辅导新概念保留在正文。
- 来源核验（本地资料）：35 份材料的页数、网址与 SHA-256 记录。
- 内容核对（本地资料）：原件边界、笔误及历史卷缺项。
- 更新记录（本地资料）：本次覆盖范围与恢复位置。
先选学习任务，再选入口。 初学一讲按下表原页序进入；已经理解算法但手算容易出错，可到 习题总览 选 Special 的状态表；证明卡在“为什么这一步合法”，优先看对应 Regular 与辅导。准备 Warm Up 至 Greedy 2 的指定复习范围时，使用 Quiz 复习笔记，不要把本页列出的后续讲义都当成本次考纲。
一次阅读最好留下可复现的结果：随机算法写一次成功概率，分治写本层合并开销，DP 写一个完整状态及依赖，图算法写当前集合与下一步变化，近似算法写可行解和 OPT 的不等式。若结果对不上，先回查输入假设（互异、非负权、闭区间或度量），再查计算；这些假设往往正是不同算法能够使用的边界。
期中复习：Warm Up 1 至 DP 4
本次范围为 L00A、L00B、L01–L09，截止最长公共子序列。期中复习只保留以下三份。两份知识点稿均独立讲解概念，不含例题或自测；真题稿保留原题、必要数据与完整解析。
| 文档 | 用法 |
|---|---|
| 详细知识点稿 | 按 Lec 分章，讲清问题定义、原理、完整算法、正确性与复杂度 |
| 简略知识点稿 | 对应相同范围和知识点，用定义、公式、条件与关键理由速查 |
| 期中真题详解 | 10 道大题、7 个判断小问的完整题干、图解、推理与答题写法 |
此前概念增补前版本已归档（本地资料），原六份期中文档的早期版本见旧稿归档（本地资料）。原有 Quiz 复习范围另见上文；期中不包含 L10 的 DP 5 或 T07 矩阵链。
全部材料与伴读
| 单元 | 原件 | 伴读 |
|---|---|---|
| L00A | L00A-Warmup-01-RAM-Model-未核.pdf（本地课件） | RAM模型与随机运行时间（p.1–16） |
| L00B | L00B-Warmup-02-Worst-Case-Analysis-未核.pdf（本地课件） | 最坏输入与最坏期望（p.1–11） |
| L01 | L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件） | 递归（p.1–9） · 重试直到成功（p.10–15） · 几何级数与选择（p.16–20） |
| L02 | L02-Divide-and-Conquer-未核.pdf（本地课件） | 归并排序（p.1–6） · 逆序对计数（p.7–12） · 二维支配（p.13–22） · Strassen矩阵乘法（p.23–28） |
| L03 | L03-Greedy-01-Activity-Selection-未核.pdf（本地课件） | 活动选择与交换论证（p.1–11） |
| L04 | L04-Greedy-02-Minimum-Spanning-Trees-未核-隐藏.pdf（本地课件） | 最小生成树与Prim算法（p.1–22） |
| L05 | L05-Greedy-03-Huffman-Codes-未核-隐藏.pdf（本地课件） | Huffman编码与贪心证明（p.1–23） |
| L06 | L06-DP-01-Pitfall-of-Recursion-未核-隐藏.pdf（本地课件） | 递归陷阱与动态规划（p.1–9） |
| L07 | L07-DP-02-Rod-Cutting-未核-隐藏.pdf（本地课件） | 钢条切割与最优方案恢复（p.1–8） |
| L08 | L08-DP-03-Dependency-未核-隐藏.pdf（本地课件） | 动态规划依赖与填表顺序（p.1–9） |
| L09 | L09-DP-04-Longest-Common-Subsequence-未核-隐藏.pdf（本地课件） | 最长公共子序列与回溯（p.1–11） |
| L10 | L10-DP-05-Optimal-BST-未核-隐藏.pdf（本地课件） | 最优二叉搜索树（p.1–14） |
| L11 | L11-Graph-01-DFS-White-Path-Theorem-未核-隐藏.pdf（本地课件） | 深度优先搜索与白路径定理（p.1–18） |
| L12 | L12-Graph-02-Strongly-Connected-Compon-未核-隐藏.pdf（本地课件） | 强连通分量与两遍DFS（p.1–18） |
| L13 | L13-Graph-03-Dijkstra-未核-隐藏.pdf（本地课件） | Dijkstra最短路径与松弛（p.1–21） |
| L14 | L14-Graph-04-Bellman-Ford-未核-隐藏.pdf（本地课件） | Bellman-Ford与负权最短路径（p.1–28） |
| L15 | L15-Graph-05-Johnson-APSP-未核-隐藏.pdf（本地课件） | Johnson全点对最短路径（p.1–14） |
| L16 | L16-Graph-06-Max-Flow-未核-隐藏.pdf（本地课件） | 最大流、残量网络与最小割（p.1–25） |
| L17 | L17-Approximation-01-Vertex-Cover-Max-未核-隐藏.pdf（本地课件） | 顶点覆盖与随机MAX-3SAT近似（p.1–18） |
| L18 | L18-Approximation-02-Traveling-Salesma-未核-隐藏.pdf（本地课件） | 旅行商问题的树遍历近似（p.1–12） |
| L19 | L19-Approximation-03-Set-Cover-Hitting-未核-隐藏.pdf（本地课件） | 集合覆盖、击中集与对数近似（p.1–20） |
| L20 | L20-Approximation-04-k-Center-未核-隐藏.pdf（本地课件） | k-center最远点贪心与二倍保证（p.1–15） |
| T01 | T01-函数增长-未核.pdf（本地课件） | 渐近增长与复杂度（p.1–20） |
| T02 | T02-三种基本技巧-未核-隐藏.pdf（本地课件） | 递归与拒绝采样练习（p.1–18） |
| T03 | T03-分治-未核-隐藏.pdf（本地课件） | 归并数逆序对（p.1–24） · 归并数二维支配（p.25–45） |
| T04 | T04-Prim实现-未核-隐藏.pdf（本地课件） | Prim实现（p.1–38） |
| T05 | T05-Kruskal算法-未核-隐藏.pdf（本地课件） | Kruskal执行（p.1–13） · Kruskal正确性（p.14–20） |
| T06 | T06-动态规划技巧-未核-隐藏.pdf（本地课件） | DP方案恢复与空间（p.1–18） |
| T07 | T07-矩阵链乘法-未核-隐藏.pdf（本地课件） | 矩阵链乘法（p.1–11） |
| T08 | T08-强连通分量-未核-隐藏.pdf（本地课件） | SCC线性实现与汇分量（p.1–34） |
| T09 | T09-Floyd-Warshall-未核-隐藏.pdf（本地课件） | Floyd-Warshall全点对路径（p.1–19） |
| T10 | T10-负环检测-未核-隐藏.pdf（本地课件） | 负环检测与恢复（p.1–34） |
| T10-proof | T10-proof-负环检测-未核-隐藏.pdf（本地课件） | 负环恢复证明（p.1–2） |
| T11 | T11-NP难归约-未核-隐藏.pdf（本地课件） | NP难归约与团问题（p.1–16） |
| T12 | T12-集合覆盖与击中集-未核-隐藏.pdf（本地课件） | 集合覆盖与击中集应用（p.1–20） |