算法（下）
这门课学什么
后半部分讲图算法和字符串算法。内容包括深度优先与广度优先搜索、最小生成树、最短路径、最大流、字典树、子串查找和数据压缩。同样用 Java 实现，配编程作业。
内容摘要
这门课是普林斯顿 COS 226 的后半部分，讲图算法、字符串算法和问题求解模型。它沿用上半部分的方法：先定义 API，再写 Java 实现，最后分析性能。课程默认学生已掌握上半部分的排序、优先队列和符号表。
课程分 3 个阶段。第 1 阶段讲图：无向图和有向图的搜索、拓扑排序、强连通分量，然后讲最小生成树、最短路径和最大流。第 2 阶段讲字符串：基数排序、字典树（trie）、子串查找、正则表达式和数据压缩。第 3 阶段讲问题求解模型：用归约把新问题转成已知问题，选学线性规划，最后讲 P 与 NP 和难解性。
课程有 5 个编程作业，全部自动评分：WordNet 语义网络、接缝裁剪（seam carving）、棒球淘汰判定、Boggle 拼字游戏求解和 Burrows-Wheeler 压缩。每个作业都把课上的算法用到一个真实问题上，例如用最短路径缩放图片，用最大流判断球队是否已被淘汰。多数模块还配不计分的面试题。
学完以后，学生能为图和字符串问题选出合适的算法并独立实现，能判断一个问题能否归约到最短路径、最大流或线性规划，并能识别 NP 完全问题，避免在它们上面找精确的高效解法。
讲课方式和上半部分一致：幻灯片动画逐步演示算法执行过程，讲完实现再讲性能和应用背景。图和字符串部分的工作量最大，归约和难解性部分偏概念。
为什么值得学
上下两部分覆盖了技术面试和系统开发最常用的算法。讲师就是标准教材《算法》的作者。
课程信息
- 学校
- 普林斯顿（Princeton）
- 课程号
- COS 226
- 讲师
- 罗伯特·塞奇威克（Robert Sedgewick）、凯文·韦恩（Kevin Wayne）
- 学期
- self-paced
- 平台
- Coursera
- 费用
- 免费
- 难度
- 中级
- 学时
- 约 6 周 × 每周 10 小时
- 先修
- 需要先学完 Algorithms, Part I。
- 材料
- 视频、幻灯片、作业、代码、教材
- 许可证
- 未注明
课程大纲 · 共 14 节
大纲依据：Coursera 模块列表（14 个模块，约 70 段视频；结构取自 api.coursera.org onDemandCourseMaterials.v2 与课程页）（查看原始页面 ↗）
- 1课程导论Introduction
介绍下半部分的主题和学习方式。
- 2无向图Undirected Graphs
讲图 API 和邻接表表示，实现深度优先搜索、广度优先搜索和连通分量，并讨论几类图问题的难易。
- 3有向图Directed Graphs
讲有向图搜索、拓扑排序和强连通分量。作业 WordNet 用有向图计算词语之间的语义距离。
- 4最小生成树Minimum Spanning Trees
从通用贪心算法出发，实现 Kruskal 算法和 Prim 算法，并介绍这个问题的研究背景。
- 5最短路径Shortest Paths
讲最短路径的性质、Dijkstra 算法、无环加权有向图上的解法和负权边的处理。作业是用最短路径做图片的接缝裁剪。
- 6最大流与最小割Maximum Flow and Minimum Cut
讲 Ford-Fulkerson 算法、最大流最小割定理、运行时间分析和 Java 实现。作业是用最大流判断棒球队是否已被淘汰。
- 7基数排序Radix Sorts
讲键索引计数、LSD 和 MSD 基数排序、三向字符串快速排序，最后讲后缀数组。
- 8字典树Tries
讲 R 向字典树和三向搜索字典树，以及前缀匹配这类按字符的操作。作业是写 Boggle 拼字游戏求解器。
- 9子串查找Substring Search
从暴力法讲起，依次讲 KMP、Boyer-Moore 和 Rabin-Karp 算法。
- 10正则表达式Regular Expressions
讲正则表达式和非确定有限自动机（NFA）的对应关系，构造并模拟 NFA，实现 grep 的核心算法。
- 11数据压缩Data Compression
讲游程编码、霍夫曼编码和 LZW 压缩。作业是实现基于 Burrows-Wheeler 变换的压缩程序。
- 12归约Reductions
讲如何把新问题归约到已解决的问题来设计算法，以及如何用归约证明下界和给问题分类。
- 13线性规划（选学）Linear Programming (optional)
以酿酒商问题引入线性规划，讲单纯形法及其实现，以及如何把其他问题归约成线性规划。
- 14难解性Intractability
讲搜索问题、P 与 NP、NP 完全性，以及面对难解问题时的应对办法。
普林斯顿的其他经典课
- 算法（上） · Algorithms, Part I
- 计算机科学：有目的的编程 · Computer Science: Programming with a Purpose
- 计算机科学：算法、理论与机器 · Computer Science: Algorithms, Theory, and Machines
- 解析组合学 · Analytic Combinatorics
- 算法分析 · Analysis of Algorithms
- 比特币与加密货币技术 · Bitcoin and Cryptocurrency Technologies