算法导论
这门课学什么
这是标准的算法入门课。内容包括复杂度分析、排序、哈希、二叉搜索树、堆、图搜索、最短路径和动态规划。每讲有讲义，另有作业和考试及答案。
内容摘要
这是 MIT 计算机系的第一门算法课。2020 年春季版由德迈纳（Erik Demaine）、Jason Ku 和所罗门（Justin Solomon）轮流讲授。课程围绕一个问题展开：怎样用数据结构和算法高效地回答查询。每个主题都同时讲正确性证明和运行时间分析。
课程按 3 次测验分成 3 个单元。第 1 单元（第 1–8 讲）讲计算模型、渐近分析、动态数组、排序、哈希、线性时间排序、二叉树、AVL 树和二叉堆。第 2 单元（第 9–14 讲）讲图算法：广度优先搜索、深度优先搜索、拓扑排序，以及 Bellman-Ford、Dijkstra 和 Johnson 最短路径算法。第 3 单元（第 15–19 讲）用 4 讲讲动态规划，再用 1 讲介绍 P、NP 和计算复杂度。最后 2 讲是总复习和后续课程介绍。
课程有 1 份先修测试（Problem Set 0）和 8 份习题集。习题以算法设计和证明为主，部分题目要求用 Python 写代码。另有 3 次测验和 1 次期末考试。播放列表还收录了习题课（Problem Session）录像，演示怎样一步步解题。
学完以后，你能为常见问题选择合适的数据结构，能证明算法正确并分析复杂度，能把新问题归约成图问题或动态规划问题。这门课也是 6.046J 的先修课。
讲课以板书为主，节奏紧凑。2020 版把动态规划的设计步骤总结成 SRTBOT 框架：子问题、关系、拓扑序、基础情况、原问题、时间。这个框架让动态规划题有固定的解题套路。
为什么值得学
很多面试备考计划以这门课为主线。Demaine 擅长把难的算法思想讲得简单。
课程信息
- 学校
- 麻省理工（MIT）
- 课程号
- 6.006
- 讲师
- 埃里克·德迈纳（Erik Demaine）、Jason Ku、贾斯汀·所罗门（Justin Solomon）
- 学期
- Spring 2020
- 平台
- MIT OpenCourseWare
- 费用
- 免费
- 难度
- 入门
- 学时
- 32 段视频
- 先修
- 会 Python，学过离散数学（6.042J 或同等）。
- 材料
- 视频、讲义、作业、考试
- 许可证
- CC BY-NC-SA 4.0
课程大纲 · 共 21 节
大纲依据：Spring 2020 OCW 课程日历与讲座视频（21 讲）（查看原始页面 ↗）
- 1算法与计算Algorithms and Computation
定义问题、算法和正确性，介绍字 RAM 计算模型和渐近记号。
- 2数据结构与动态数组Data Structures and Dynamic Arrays
区分接口和实现，用链表和动态数组实现序列，引出均摊分析。
- 3集合与排序Sets and Sorting
用有序数组实现集合接口，讲选择排序、插入排序和归并排序。
- 4哈希Hashing
给出基于比较的搜索下界，再用哈希表实现期望常数时间的查找。
- 5线性时间排序Linear Sorting
讲直接访问数组、计数排序和基数排序，绕开比较排序的下界。
- 6二叉树（上）Binary Trees, Part 1
介绍二叉树的遍历顺序，以及在树上插入和删除节点的操作。
- 7二叉树（下）：AVL 树Binary Trees, Part 2: AVL
用旋转维持树的平衡，保证树高为 O(log n)，并用子树信息增强树的功能。
- 8二叉堆Binary Heaps
用二叉堆实现优先队列，讲原地建堆和堆排序。
- 9广度优先搜索Breadth-First Search
介绍图的表示方法，用 BFS 求无权图的单源最短路径。
- 10深度优先搜索Depth-First Search
用 DFS 求连通分量、检测环并做拓扑排序。
- 11带权最短路径Weighted Shortest Paths
定义带权图的最短路径和负权环，在有向无环图上用松弛操作求最短路径。
- 12Bellman-Ford 算法Bellman-Ford
在可能含负权边的图上求单源最短路径，并检测负权环。
- 13Dijkstra 算法Dijkstra's Algorithm
在非负权图上用优先队列求单源最短路径，并比较不同堆实现的运行时间。
- 14全源最短路径与 Johnson 算法APSP and Johnson's Algorithm
用重新赋权把负权边变成非负权，再多次运行 Dijkstra 求所有点对的最短路径。
- 15动态规划（1）：SRTBOT、斐波那契、DAG 与保龄球Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling
介绍 SRTBOT 设计框架和记忆化，用斐波那契数和保龄球问题做例子。
- 16动态规划（2）：最长公共子序列、最长递增子序列与取硬币Dynamic Programming, Part 2: LCS, LIS, Coins
用前缀和后缀作子问题，解 LCS、LIS 和交替取硬币游戏。
- 17动态规划（3）：全源最短路径、括号化与钢琴指法Dynamic Programming, Part 3: APSP, Parens, Piano
讲给子问题加约束、扩展状态的技巧，用 3 个例子演示。
- 18动态规划（4）：切钢条、子集和与伪多项式时间Dynamic Programming, Part 4: Rods, Subset Sum, Pseudopolynomial
讲伪多项式时间算法，说明它和真正的多项式时间有什么区别。
- 19计算复杂度Complexity
介绍 P、NP、EXP 和 NP 完全，用归约证明问题的难度。
- 20课程总复习Course Review
回顾全课的数据结构、图算法和动态规划，梳理它们之间的联系。
- 21算法：下一步学什么Algorithms—Next Steps
介绍 MIT 的后续算法课程和算法研究方向。