算法导论重点# JobHunting - 待字闺中
w*g
1 楼
【 以下文字转载自 Programming 讨论区 】
发信人: wdong (cybra), 信区: Programming
标 题: 算法导论重点
发信站: BBS 未名空间站 (Mon Oct 15 17:15:36 2012, 美东)
上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和上面三类方法结合。书中没有。可以
自己动手编一下算fibonacci数和解Tower of Hanoi问题的算法，体会一下回溯算法的
基本结构。看眼下面的页面
http://en.wikipedia.org/wiki/Memoization
知道基本算法复杂度和程序设计方法的一般性对应关系：
O(logN), O(NlogN): 分治法
O(N^3): 动态规划
O(2^N)： 穷举法，无脑的回溯实现（一般还伴随堆栈溢出）
C. 数据结构
线性表 10.1-10.4 pp. 200-220
树 本书貌似没有一般性介绍，自己看下面两个链接
http://en.wikipedia.org/wiki/Tree_%28data_structure%29
http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Traversa
需要知道树的三种遍历方法，需要能写程序读入两种遍历方法的输出并转换成
另一种遍历方法的输出。
图 22.1-22.4 pp.525-549
D. 重要问题
* 排序 2.1
6.1-6.5 pp.127-145
7.1-7.3 pp.145-155
8.1 记住结论就行：排序问题的复杂度是O(nlogn)
* 检索
二分查找 12.1-12.3 pp.253-265
B-tree 18.1-18.2 pp.434-449 B-tree的删除操作没有人能搞的清，不看也罢。
散列 11.1-11.4 pp.221-245
倒排表 书中没有，看链接http://en.wikipedia.org/wiki/Inverted_index
* 找最短路径， 结合动态规划看。
24.1-24.3 pp.580-601
发信人: wdong (cybra), 信区: Programming
标 题: 算法导论重点
发信站: BBS 未名空间站 (Mon Oct 15 17:15:36 2012, 美东)
上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和上面三类方法结合。书中没有。可以
自己动手编一下算fibonacci数和解Tower of Hanoi问题的算法，体会一下回溯算法的
基本结构。看眼下面的页面
http://en.wikipedia.org/wiki/Memoization
知道基本算法复杂度和程序设计方法的一般性对应关系：
O(logN), O(NlogN): 分治法
O(N^3): 动态规划
O(2^N)： 穷举法，无脑的回溯实现（一般还伴随堆栈溢出）
C. 数据结构
线性表 10.1-10.4 pp. 200-220
树 本书貌似没有一般性介绍，自己看下面两个链接
http://en.wikipedia.org/wiki/Tree_%28data_structure%29
http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Traversa
需要知道树的三种遍历方法，需要能写程序读入两种遍历方法的输出并转换成
另一种遍历方法的输出。
图 22.1-22.4 pp.525-549
D. 重要问题
* 排序 2.1
6.1-6.5 pp.127-145
7.1-7.3 pp.145-155
8.1 记住结论就行：排序问题的复杂度是O(nlogn)
* 检索
二分查找 12.1-12.3 pp.253-265
B-tree 18.1-18.2 pp.434-449 B-tree的删除操作没有人能搞的清，不看也罢。
散列 11.1-11.4 pp.221-245
倒排表 书中没有，看链接http://en.wikipedia.org/wiki/Inverted_index
* 找最短路径， 结合动态规划看。
24.1-24.3 pp.580-601
