Stanford CS161: Design and Analysis of Algorithms
课程简介
- 先修要求：数据结构，概率论的基础知识
- 参考材料：
- 斯坦福大学的算法设计与分析课程 CS161
- Introduction to Algorithm，作者: Thmos.H.Cormen, Charles E. Leiserson, etc.
- 主要内容：
- 基本算法分析方法：大 O 记号、主方法、摊还分析
- 基本算法设计方法：分治、动态规划、贪心
- 基本算法：排序、顺序统计量；最长公共子序列、背包问题、赫夫曼编码；BFS、DFS、拓扑排序、强连通分量、最小生成树、最短路径、网络最大流、稳定匹配
个人心得
严格来说，学习数据结构的同时，应该已经接触到了一些算法（例如排序、DFS、BFS 等），但是那时并没有学习这些算法背后的设计思路和方法，即使涉及到了，也只是一点基础，没有作深入学习。因此，在学习完数据结构后，我紧接着学习了算法。
同数据结构中相同，我仍然推荐在学习完一个算法后从0开始实现该算法。另外，这门课程的 slides 配图十分详实，很有助于理解算法的运行过程（相同的效果也可以在 Hello 算法中获得）；在 slides 中，几乎每一个算法都给出了实际的问题情景，让我意识到算法和生活其实是息息相关的。
CS161 的配套教材是《算法导论》，一本有名的算法圣经，其数学推导非常严谨（但是有些章节又略显繁琐），尽管对数学基础欠佳的同学不太友好，但仍然非常值得一读。此外，在随机化算法和其后续的一些复杂度分析中会使用一些基础的概率论知识，可以通过阅读《概率导论》的前三章来补齐。
相关链接
- 课程网站：https://stanford-cs161.github.io/winter2024/
- 课程视频：B 站搜索
- Hello 算法：Github 上的 62k+star 项目，包含了基本的数据结构和算法教程，提供了不少的代码的可视化，可以帮助理解背后的逻辑；另外还提供了多种语言的算法实现。
- OI-wiki：一个 OI 竞赛向网站，里面囊括了几乎所有竞赛常见算法的教程，可作为课外扩展内容。
- 洛谷：一个偏 OI 向的算法题网站。
- 力扣：一个偏 offer 向的算法题网站。