CSCI3160 阅读导航

本轮更新（2026-10-13）将 22 份主课与 13 份辅导、共 666 页的教学内容补入 42 份分段笔记。按下面的顺序读正文即可学习：定义、公式、原例输入、算法步骤、证明和图表中的关键数据都在对应页码段内，不需要同时打开课件对照。原页码用于定位出处；标题与分节页简要标注，重复动画整理成逐步状态表。

这里按课程原先的知识依赖安排阅读，不替代各讲逐页正文。每一讲和全部分 Part 的入口都在课程全览，也可使用维护脚本生成的文件目录。

第一段：先会分析算法，再设计算法

从 L00A 认识 RAM 的原子操作、字长与随机代价，随后读 L00B，始终区分“固定输入上的随机平均”和“所有同规模输入里的最坏”。T01 补渐近记号，尤其注意大 O 自身不代表最坏情况。

L01 Part 1 讲如何相信规模更小的调用；Part 2 将失败后重试变成常数期望成本；Part 3 把这些逐层成本加成线性。T02 中的拒绝采样要分别证明均匀性与时间，别用取模代替。

L02 接着把单支递归拓展到多子问题：排序、逆序对、支配与矩阵乘法各一份。读完逆序对与支配再做 T03，看“让子问题返回更多信息”怎样减少合并开销。

第二段：局部选择为什么不会后悔

L03 用交换论证开始贪心：先说明替换一个选择后仍可行，再说明目标不变坏。L04 把这一思路变成图上的安全加边；T04 负责高效实现，T05 则从森林而非单棵树扩张。

L05 再看“先交换到最轻兄弟，再收缩”的证明。算法执行、最优性证明和运行时间是三件事，都要能独立说明。

第三段：写出状态，也兑现依赖

L06 抓住重复子问题；L07 在最优值之外保存选择；L08 检查每个状态是否在依赖算好后才计算。

L09 用两个前缀做状态，L10 用连续区间做状态。T06 区分值、方案与滚动空间，T07 把“枚举最后一次合并位置”练完整。遇到一份不完整递推，先查基本情形，不直接填一个猜测值。

第四段：图上的方向、时间与距离

L11 先看清白、灰、黑与发现/完成事件；L12 再利用完成次序和反图分离 SCC；T08 解释这些操作怎样保持线性。

L13 的前提是非负权；L14 允许负权并用轮数传播；L15 借势函数将两种算法连起来。T09 是全点对问题的另一种 DP。T10 区分“检测存在”和“输出一条环”，配套证明 单独阅读。2026-09-17 留存的官网说明及 T10 p.33 对后者有非考试说明，不能扩展到所有最短路内容。

L16 是2026-09-17 留存的官网说明标注不要求考试的额外主讲。读时始终把原始容量、当前净流和残量三个量分开，反向残量表示可撤销的选择。

第五段：无法高效精确求解时，还能保证多少

L17 比较最小化的上界与最大化的期望下界。T11 补归约方向、构造规模及双向证明；该辅导重点是归约证明，而非新的贪心算法。

L18 用 MST 下界加三角不等式；L19 用平均收益与剩余量下降；L20 用最优簇和三角不等式。T12 练建模时参数如何变化：宇宙、集合个数、最大集合大小与最大出现频率不能混用。

读到什么程度再向后走？ 可以用下面三个小检查定位依赖，而不是把所有讲义连续看完再发现前提没掌握。

• 进入 DP 前，拿 [2,2,1] 解释为何有两个逆序对，并说明合并时相等不能算逆序；若只能背递推，回看 T03 Part 1。
• 进入最短路前，在三点链 a→b→c 上分别说出发现顺序、完成顺序和从 c 可达的集合；把搜索访问与距离确定混为一谈时，回看 L11。
• 进入近似算法前，写清“可行解的成本”与“OPT 下界”哪个更大；若把 MST 当成 TSP 巡回，先做 Sp12 Q3。

使用历史试卷时

先读附录完整题面，明确图方向、扫描顺序、输出要求及输入编码。题目文件中的数学排版以渲染页为准，尤其是根号覆盖范围。当前课程讲义与历史卷不完全同版：历史卷的特殊 gadget、计算模型史和单独的边遍历问题，不凭当前课件补成老师讲过的内容。缺项与本次识别到的边界记录在内容核对（本地资料）。