算法（上）
这门课学什么
这是普林斯顿数据结构与算法课的前半部分。内容包括并查集、栈与队列、归并排序、快速排序、二叉搜索树和散列表。所有算法用 Java 实现，编程作业自动评分。
内容摘要
这门课是普林斯顿 COS 226 的前半部分，讲程序员必须掌握的基础数据结构和算法。每个主题都按同一条主线展开：先定义问题和 API，再写出 Java 实现，最后用实验和数学模型分析性能。内容和教材《算法（第 4 版）》一一对应。
课程分 3 个阶段。第 1 阶段讲方法：用并查集（union-find）展示一个算法从慢到快的改进过程，再讲怎样用科学方法估算运行时间和内存。第 2 阶段讲排序：先讲栈和队列，再依次讲初级排序、归并排序、快速排序和优先队列。第 3 阶段讲查找：从符号表和二叉搜索树讲到红黑树、kd 树和散列表，最后讲符号表的实际用例。
课程有 5 个编程作业，全部自动评分：渗透模型（Percolation）、双端队列与随机队列、共线点检测、8 数码问题求解和 kd 树。评分程序检查正确性、运行时间、内存用量和代码风格。多数模块还配 1 组不计分的面试题，练习把课上的算法用到新问题上。
学完以后，学生能独立实现常用的排序和查找结构，能为具体问题选出合适的结构，并能估算程序在大数据量下的运行时间。下半部分 Algorithms, Part II 接着讲图算法和字符串算法。
讲课用大量幻灯片动画，逐步演示算法每一步怎样改变数据。讲完实现后，讲师会给出实测数据和数学分析，并说明这个算法在真实系统里的用法。每个模块约 1–2 小时视频，作业的工作量明显大于视频。
为什么值得学
这是公认最好的算法 MOOC 之一，Coursera 上 12000 多条评价打出 4.9 分。讲师 Sedgewick 是快速排序分析的权威，也是经典教材《算法》的作者。
课程信息
- 学校
- 普林斯顿（Princeton）
- 课程号
- COS 226
- 讲师
- 凯文·韦恩（Kevin Wayne）、罗伯特·塞奇威克（Robert Sedgewick）
- 学期
- self-paced
- 平台
- Coursera
- 费用
- 免费
- 难度
- 中级
- 学时
- 约 5 周 × 每周 10 小时
- 先修
- 需要会用 Java 或另一种语言编程。
- 材料
- 视频、幻灯片、作业、代码、教材
- 许可证
- 未注明
课程大纲 · 共 13 节
大纲依据：Coursera 模块列表（13 个模块，约 60 段视频；结构取自 api.coursera.org onDemandCourseMaterials.v2 与课程页）（查看原始页面 ↗）
- 1课程导论Course Introduction
介绍课程范围、学习算法的理由，以及配套教材和书站。
- 2并查集Union−Find
以动态连通性问题为例，从 quick-find、quick-union 逐步改进到加权和路径压缩的实现。作业是用并查集估算渗透阈值。
- 3算法分析Analysis of Algorithms
先用实验测量运行时间，再用数学模型和增长阶分类解释结果。最后讲大 O 一类记号和 Java 对象的内存估算。
- 4栈与队列Stacks and Queues
用链表和可变长数组实现栈和队列，并讲 Java 泛型和迭代器。作业是实现双端队列和随机队列。
- 5初级排序Elementary Sorts
讲选择排序、插入排序、希尔排序和随机洗牌，并用排序求平面点集的凸包。
- 6归并排序Mergesort
讲自顶向下和自底向上的归并排序，证明基于比较的排序下界，并讲比较器和稳定性。作业是找出平面上的共线点。
- 7快速排序Quicksort
讲随机化快速排序、快速选择和处理重复键的三向切分，并分析 Java 系统排序的设计取舍。
- 8优先队列Priority Queues
用二叉堆实现优先队列，由此得到堆排序，选学部分讲事件驱动模拟。作业是用 A* 搜索求解 8 数码问题。
- 9初级符号表Elementary Symbol Tables
定义符号表 API，比较无序链表和有序数组两种实现，再讲二叉搜索树的查找、有序操作和删除。
- 10平衡搜索树Balanced Search Trees
讲 2-3 树和红黑树，保证查找和插入在最坏情况下也是对数时间。选学部分讲 B 树。
- 11二叉搜索树的几何应用Geometric Applications of BSTs
讲一维和二维范围查找、线段相交、kd 树、区间搜索树和矩形相交。作业是实现 kd 树并做最近邻查询。
- 12散列表Hash Tables
讲散列函数的设计、拉链法和线性探测，并比较散列表和平衡树各自适合的场景。
- 13符号表应用（选学）Symbol Table Applications
用集合、字典、索引和稀疏向量 4 类例子，展示符号表在实际程序里的用法。
普林斯顿的其他经典课
- 算法（下） · Algorithms, Part II
- 计算机科学：有目的的编程 · Computer Science: Programming with a Purpose
- 计算机科学：算法、理论与机器 · Computer Science: Algorithms, Theory, and Machines
- 解析组合学 · Analytic Combinatorics
- 算法分析 · Analysis of Algorithms
- 比特币与加密货币技术 · Bitcoin and Cryptocurrency Technologies