CS自学指南-数据结构与算法
CS61B: Data Structures and Algorithms
课程简介
- 所属大学:UC Berkeley
- 先修要求:CS61A
- 编程语言:Java
伯克利 CS61 系列的第二门课程,注重数据结构与算法的设计,同时让学生有机会接触上千行的工程代码,通过 Java 初步领会软件工程的思想。
我上的是 2018 年春季学期的版本,该课的开课老师 Josh Hug 教授慷慨地将 autograder 开源了,大家可以通过网站公开的邀请码在 gradescope 免费加入课程,从而方便地测评自己的代码。
这门课所有的编程作业都是使用 Java 完成的。没有 Java 基础的同学也不用担心,课程会有保姆级的教程,从 IDEA(一款主流的 Java 编程环境)的配置讲起,把 Java 的核心语法与特性事无巨细地讲授,大家完全不用担心跟不上的问题。
这门课的作业质量也是绝绝子。14 个 lab 会让你自己实现课上所讲的绝大部分数据结构,10 个 Homework 会让你运用数据结构和算法解决实际问题, 另外还有 3 个 Project 更是让你有机会接触上千行的工程代码,在实战中磨练自己的 Java 能力。
课程资源
- 课程网站:https://sp18.datastructur.es/
- 课程视频:https://sp18.datastructur.es/,每节课的链接详见课程网站
- 课程教材:无
- 课程作业:每年略有不同,18 年春季学期有 14 个 Lab,10 个 Homework以及 3 个 Project,具体要求详见课程网站。
资源汇总
@PKUFlyingPig 在学习这门课中用到的所有资源和作业实现都汇总在 PKUFlyingPig/CS61B - GitHub 中。
Coursera: Algorithms I & II
课程简介
- 所属大学:Princeton
- 先修要求:CS61A
- 编程语言:Java
这是 Coursera 上评分最高的算法课程。Robert Sedgewick 教授有一种魔力,可以将无论多么复杂的算法讲得极为生动浅显。实不相瞒,困扰我多年的 KMP 以及网络流算法都是在这门课上让我茅塞顿开的,时隔两年我甚至还能写出这两个算法的推导与证明。
你是否觉得算法学了就忘呢?我觉得让你完全掌握一个算法的核心在于理解三点:
- 为什么这么做?(正确性推导,抑或是整个算法的核心本质)
- 如何实现它?(光学不用假把式)
- 用它解决实际问题(学以致用才是真本事)
这门课的构成就非常好地契合了上述三个步骤。观看课程视频并且阅读教授的开源课本有助于你理解算法的本质,让你也可以用非常 生动浅显的话语向别人讲述为什么这个算法得长这个样子。
在理解算法之后,你可以阅读教授对于课程中讲授的所有数据结构与算法的代码实现。 注意,这些实现可不是 demo 性质的,而是工业级的高效实现,从注释到变量命名都非常严谨,模块化也做得相当好,是质量很高的代码。我从这些代码中收获良多。
最后,就是这门课最激动人心的部分了,10 个高质量的 Project,并且全都有实际问题的背景描述,丰富的测试样例,自动的评分系统(代码风格也是评分的一环)。让你在实际生活中 领略算法的魅力。
课程资源
- 课程网站:Algorithm I, Algorithm II
- 课程视频:详见课程网站
- 课程教材:https://algs4.cs.princeton.edu/home/
- 课程作业:10个Project,具体要求详见课程网站
资源汇总
@PKUFlyingPig 在学习这门课中用到的所有资源和作业实现都汇总在 PKUFlyingPig/Princeton-Algorithm - GitHub 中。
MIT 6.006: Introduction to Algorithms
课程简介
- 所属大学:MIT
- 先修要求:计算机导论(CS50/CS61A or equivalent)
- 编程语言:Python
MIT-EECS 系的瑰宝。授课老师之一是算法届的奇才 Erik Demaine. 相比较于斯坦福的 CS106B/X(基于 C++ 的数据结构与算法课程),该课程更侧重于算法方面的详细讲解。课程也覆盖了一些经典的数据结构,如 AVL 树等。个人感觉在讲解方面比 CS106B 更加详细,也弥补了 CS106B 在算法方面讲解的不足。适合在 CS106B 入门之后巩固算法知识。
不过该课程也是出了名的难,大家需要做好一定的心理准备。
课程资源
MIT 6.046: Design and Analysis of Algorithms
课程简介
- 所属大学:MIT
- 先修要求:算法入门(6.006/CS61B/CS106B/CS106X or equivalent)
- 编程语言:Python
6.006的后续课程。授课老师依旧是 Erik Demaine 和 Srini Devadas,此外还有一位新老师 Nancy Lynch.
相比较于“现学现用”的6.006,6.046更加侧重于如何运用课上所学到的内容举一反三,设计出一套完备的算法并能够证明该算法能解决相应的问题。虽然该课程在板书以及作业中的编程语言为 Python,但基本上没有编程作业;绝大部分的作业都是提出要求,然后需要学生进行算法设计以及合理性证明。所以该课程的难度又提高了一大截:)
在该门课程后还有一门 6.854 高级算法,但对于绝大多数考试以及应聘来说,学完该课程基本上已经能覆盖99%的题目了。
课程资源
- 课程网站:Spring 2015
- 课程视频:Spring 2015
- 课程教材:Introduction to Algorithms (CLRS)
- 课程作业:Spring 2015
CS170: Efficient Algorithms and Intractable Problems
课程简介
- 所属大学:UC Berkeley
- 先修要求:CS61B, CS70
- 编程语言:LaTeX
伯克利的算法设计课,更注重算法的理论基础与复杂度分析。课程内容涵盖了分治、图算法、最短路、生成树、贪心、动规、并查集、线性规划、网络流、NP 问题、随机算法、哈希算法等等。
这门课的教材写的很好,证明浅显易懂,非常适合作为工具书查阅。另外,这门课只有书面作业,并且推荐用 LaTeX 编写,大家可以借此机会锻炼自己的 LaTeX 技巧。
课程资源
- 课程网站:https://cs170.org/
- 课程视频:https://www.bilibili.com/video/BV1BU4y1b7RK
- 课程教材:详见课程网站 notes
- 课程作业:13 次书面作业,用 LaTeX 编写
资源汇总
@PKUFlyingPig 在学习这门课中用到的所有资源和作业实现都汇总在 PKUFlyingPig/UCB-CS170 - GitHub 中。