算法专项课程
这门课学什么
4 门课依次讲分治与随机算法、图搜索与最短路径与数据结构、贪心与动态规划、NP 完全问题及应对方法。每门课有编程作业和测验。
内容摘要
这个专项课程由 4 门课组成，每门 4 周，内容来自 Tim Roughgarden 在斯坦福讲的算法课。主线是几种算法设计范式：分治、随机化、图搜索、数据结构、贪心和动态规划，最后讲怎样应对 NP 难问题。Roughgarden 讲课重视算法为什么正确，每个算法都配正确性证明和运行时间分析。
第 1 门课讲分治和随机化：渐近记号、归并排序、主定理、快速排序、线性时间选择和最小割。第 2 门课讲图搜索和数据结构：BFS、DFS、强连通分量、Dijkstra 算法、堆、平衡搜索树、哈希表和布隆过滤器。
第 3 门课讲贪心和动态规划：调度、Prim 和 Kruskal 最小生成树、并查集、聚类、哈夫曼编码、背包问题、序列比对和最优二叉搜索树。第 4 门课先讲 Bellman-Ford、Floyd-Warshall 和 Johnson 最短路径算法，再讲 NP 完全性。最后讲应对 NP 难问题的 3 种方法：更快的精确算法、近似算法和局部搜索。
每周有 1 次习题测验和 1 次编程作业。编程作业给出一个数据文件，你用任何语言实现算法，再提交计算结果。每门课最后有期末考试，另有选做的理论题。标为 Advanced 或 Optional 的视频可以跳过。学完后，你能分析算法的运行时间，能为常见问题选对设计范式。
为什么值得学
Roughgarden 重点讲算法为什么正确，而不只是怎样写。课程后来整理成 Algorithms Illuminated 系列书。
课程信息
- 学校
- 斯坦福（Stanford）
- 讲师
- Tim Roughgarden
- 学期
- self-paced
- 平台
- Coursera
- 费用
- 免费旁听
- 难度
- 中级
- 学时
- 4 门课，每门约 13–15 小时
- 先修
- 需要会一门编程语言，了解基础离散数学和证明。
- 材料
- 视频、作业、考试、教材
- 许可证
- 未注明
课程大纲 · 共 16 节
大纲依据：Coursera 专项课程 4 门子课程的周模块列表（子课程 → 周）（查看原始页面 ↗）
- 1.1第 1 门第 1 周：导论与渐近分析Course 1, Week 1: Introduction; Asymptotic Analysis
用整数乘法和 Karatsuba 算法引出算法设计。讲归并排序及其分析，再讲大 O、大 Ω 和大 Θ 记号。
- 1.2第 1 门第 2 周：分治算法与主定理Course 1, Week 2: Divide and Conquer; The Master Method
讲逆序对计数、Strassen 矩阵乘法和最近点对。讲主定理（master method）的陈述、例子和证明。
- 1.3第 1 门第 3 周：快速排序Course 1, Week 3: QuickSort
讲围绕主元的分区和主元的选择。用随机化分析证明期望运行时间，并复习概率。
- 1.4第 1 门第 4 周：线性时间选择与最小割Course 1, Week 4: Linear-Time Selection; Graphs and Minimum Cuts
讲随机化选择、确定性选择和比较排序的下界。讲图的表示，以及用随机收缩算法求最小割。
- 2.1第 2 门第 1 周：图搜索与连通性Course 2, Week 1: Graph Search and Connectivity
讲 BFS、DFS 和拓扑排序。讲计算强连通分量的算法和网页图的结构。
- 2.2第 2 门第 2 周：Dijkstra 最短路径算法Course 2, Week 2: Dijkstra's Shortest-Path Algorithm
讲算法步骤和例子。证明正确性，并讲基于堆的实现。
- 2.3第 2 门第 3 周：堆与平衡搜索树Course 2, Week 3: Heaps and Balanced Search Trees
讲堆的操作和应用。讲二叉搜索树和红黑树，包括旋转和插入。
- 2.4第 2 门第 4 周：哈希表与布隆过滤器Course 2, Week 4: Hash Tables and Bloom Filters
讲哈希表的实现、病态数据集和全域哈希（universal hashing）。讲布隆过滤器及其误报率分析。
- 3.1第 3 门第 1 周：贪心调度与 Prim 最小生成树Course 3, Week 1: Greedy Scheduling and Prim's MST
介绍贪心算法，并证明一个调度算法的正确性。讲 Prim 算法、割性质和基于堆的快速实现。
- 3.2第 3 门第 2 周：Kruskal 最小生成树、聚类与并查集Course 3, Week 2: Kruskal's MST, Clustering and Union-Find
讲 Kruskal 算法、并查集实现和单链接聚类。选学部分讲按秩合并、路径压缩和 Ackermann 函数。
- 3.3第 3 门第 3 周：哈夫曼编码与动态规划入门Course 3, Week 3: Huffman Codes; Introduction to Dynamic Programming
讲哈夫曼编码的贪心算法和正确性证明。用路径图上的最大权独立集引入动态规划。
- 3.4第 3 门第 4 周：动态规划进阶Course 3, Week 4: Advanced Dynamic Programming
用动态规划解背包问题、序列比对和最优二叉搜索树。每个问题都先找最优子结构，再写算法。
- 4.1第 4 门第 1 周：Bellman-Ford 与全源最短路径Course 4, Week 1: Bellman-Ford and All-Pairs Shortest Paths
讲 Bellman-Ford 算法、负环检测和互联网路由。讲 Floyd-Warshall 算法和 Johnson 算法。
- 4.2第 4 门第 2 周：NP 完全性与精确算法Course 4, Week 2: NP-Completeness and Exact Algorithms
讲归约、NP 完全性和 P 与 NP 问题。用顶点覆盖和旅行商问题讲比暴力搜索更快的精确算法。
- 4.3第 4 门第 3 周：近似算法Course 4, Week 3: Approximation Algorithms
讲背包问题的贪心启发式和动态规划启发式。分析它们的近似保证。
- 4.4第 4 门第 4 周：局部搜索与更广的算法世界Course 4, Week 4: Local Search; The Wider World of Algorithms
讲最大割问题、局部搜索原则和解 2-SAT 的 Papadimitriou 随机游走算法。选学部分介绍稳定匹配、网络流和线性规划。