※ [本文转录自 neoneon 信箱] 作者: [email protected] ("爱宕有机奈米负离子猫") 标题: [心得] 陈健 演算法概论 时间: Sun Jul 10 12:42:39 2016 作者: smilecat13 (微笑的猫) 看板: NCTU-Teacher 标题: [心得] 陈健 演算法概论 时间: 2014/07/11 Fri 01:42:13 ⊕课名⊕ 演算法概论 (英文授课) ▲教授▲ 陈健 ★修课年度★（请加注开课单位 如:大三通识、XX系选修、XX所） 102学年度下学期 ￡教了什麽￡（课程大概内容。或是额外学会了什麽东西。） 选课系统上的课纲为: 1. Introduction to analysis of algorithms 2. Asymtotic notation 3. divide and conquer 4. Recurrences, summations 5. Randomized quicksort 6. Median, order statistics 7. Sorting in linear time 8. Hash 9. Red-Black tree 10. Dynamic Programming 11. Greedy algorithms 12. Minimum spanning tree 13. Graph algorithms: depth-first search, topological sorting, breadth-first search 14. Graph algorithms: Single-source shortest paths, Dijkstra's algorithm 15. Bellman-Ford algorithm, dag shortest paths 16. All-pairs shortest paths, Floyd-Warshall algorithm 17. Network flow 18. Introduction to NP-completeness 对应课本的章节为: 1、2、3、4、6、7、8、9、11、13、14、 15、16、17、22、23、24、25、26、34、35 ◆上课方式◆（投影片、团体讨论、老师教学风格） 老师都用他的平板接投影机， 直接在萤幕上写笔记和讲解，偶尔会用到黑板。 上到all-pairs shortest path algorithm、maximum-flow的时候， 有发讲义给我们练习算，他会带着我们练习。 讲解应该还算清楚吧，感觉得出来有认真备课， 但我觉得他的英文口语表达没有很好。 有不懂的地方，下课时去问老师， 老师会用中文重新讲解一遍给你听。 很喜欢问学生问题， 不过都是坐前面几排的固定几个人会理他， 其他人都在做自己的事 XD 有这些认真的同学在真好， 不然都没人理他真的会有点尴尬 XD ▼考试作业▼ 小考35% + 程式作业20% + 期中考20% + 期末考25% (1) 小考 35% 老师用一个很特殊的方式， 小考是考「当周」要教的东西， 也就是要你先回家预习。 老师会订一个schedule， 上面列了每周要我们读的章节和作业， 小考就是考那个范围。 我觉得小考题目不难， 回去有读书应该就会写。 有少数几次会出现比较困难的应用题， 那几题是以前放在期中考or期末考里的题目。 作业我觉得只是让我们练习用， 有些作业题目很难，但通常那种都不会出现在小考， (像是叫你设计一个演算法之类的那种) 但有些比较简单的题目就有可能会出现在小考。 老师都是两节课的那天考， 期中考前是第一节课的前10分钟考， 然後很准时收卷，有时候会写不完... 期中考後是第二节课的最後10~15分钟考， 可能是graph演算法要算比较久， 老师会给我们比较充裕的时间写。 (但graph演算法很重视熟练，你不熟一样写不完) 小考成绩占非常重，总共35%， 这学期考了13次，每次考两题、满分10分， 最後取最高的10次加总。 不过大家的小考都考的不是很好... 最後13次小考班级总平均约4分。 (2) 程式作业 20% 总共六次: a. find peak in 1D/2D array => 课外补充，老师上课会讲解，不会很难 b. 实作3种quicksort c. hash table d. dynamic programming e. greedy algorithm (Huffman encoding/decoding) f. all-pairs shortest path & maximum-flow的应用题 我觉得程式作业算简单， 大部分都是把课本的pseudo code改成C++就可以了。 (前提是你上学期的资料结构有学好) 善用C++伟大的STL，真的很好用， 如果不用STL，资结都自己写， 那我觉得会花满多苦工在这些程式作业上， 用STL一堆东西都可以轻松搞定。 这些程式作业都要先用程式检定系统(online judge system)去跑看结果对不对， 然後也要同时上传到E3， 助教会抓抄袭，如果被抓到就是0分。 听说现在是用一个判断程式码抄袭的程式， 看程式parse出来的结构、或是用一些text mining的技术， 所以不是变数名称改改、函式位置改一下就可以。 我觉得还是不要抱持着侥幸的心态， 这学期有不少人被抓到。 每次作业满分100分， 最後所有作业班级总平均62分。 (3) 期中考 20% 范围: ch1、2、3、4、6、7、8、9、11、13、14、15、17 题目有70%跟考古题类似， 剩下的部分有些会从小考出来。 考试前先看考古题， 大概就知道老师会怎麽考了。 通常会考一题设计演算法的题目， 这就要凭真本事了。 满分100分，班平均63分。 (4) 期末考 25% 范围: ch15、16、22、23、24、25、26、34、35 老师期末考前一周， 有给我们练习去年的考古题， 他会带着我们一起做。 而今年的题目我觉得比较难， 大概只有5成跟考古题类似。 (ch35的部分竟然考了15分...) 题目很多，我最後写不完... 我graph的题目花太多时间了 囧 然後很有趣的一点， 有一题跟期中考一模一样的题目考出来了，还占14分 XD 那题也出现在其中一次小考和程式作业里， 老师上课有一直强调这题很重要， 结果竟然考了三次 XD 满分100分，班平均51分。 (5) 学期成绩 我小考取最高的10次加总为81分， 程式成绩平均99分， 期中考92分，期末考78分。 原始成绩为86分，最後被调到99分!! 原始成绩，班上大概只有3成的人及格，平均约53分， 若每人都调13分左右，则最後只当约15%的人。 感觉老师给分满甜的说... 虽然老师上课时， 一直恐吓我们他不会调分，被当就是被当 XD 而且也听一些修过课的人说，他给分算不甜， 但我觉得调13分算调很大吧 @@ ￥其他￥（是否注重出席率or严禁迟到？需要的基础？） 出席率很惨， 每次大概只有20%的人会去上课。 我全勤，整学期没有点过名。(印象中...还是有点过一次我忘了) 需要的基础，我觉得就资料结构要学好吧， 程式能力也要有一定的基础。 老师是用自己做的投影片上课， 但内容有些好像是第二版的， 所以有一些跟第三版的不太一样。(像是ch22的DFS) 我虽然全勤， 但每堂课几乎都在做自己的事， 没在听老师上课... ￠最後想说的话￠ 每次的小考要好好把握， 因为期中、期末的范围非常大， 不可能考前两三天就读的完。 我每周约花8小时在读演算法， 每次小考都把他视为一次期中考般、 很认真的去准备。 虽然很累，但期中考、期末考前就很轻松。 我後来觉得这种每周小考的方式很棒， 可以督促自己读书， 才不会全部积在大考前才在准备。 演算法是资工核心科目之一， 也是研究所推甄必看的科目， 一定要很认真的去修这门课。 ＆谁适合修这门课＆ 不喜欢程式作业太难、喜欢自己读书的人 -- ※ Origin: 交大次世代(bs2.to) ◆ From: 182.235.242.149 作者从 182.235.242.149 修改文章於 2014/07/11 Fri 01:49:56 推 kougousei：改变数名字和函数名字对现在的抓抄袭程式效用=0 07/12 15:05 → ian031545：你说你没听老师上课，为什麽又说老师讲解很清楚 07/14 00:55 → ian031545：很多地方感觉要有听课才能写出的心得，对应後面的没听课 07/14 00:57 → ian031545：不知道可信度高不高 ＠＠ 07/14 00:58 我是没有很认真一直在听老师上课， 但偶尔有些章节会听一下， 所以才用「应该」、「吧」这种讲法， 没有直接肯定他讲解的「很清楚」。 像是他後来教到all-pairs最短路径与maximum-flow， 以及最後一堂课的考古题练习， 他都有带着我们练习，那部分我算是很认真在听。 这门课我全勤， 就算没从头到尾都很认真的在听老师讲课， 也都有去教室，偶尔会听听老师上课。 然後我觉得刚好跟你讲的相反， 这篇文章中需要听课才能写出的心得占的比例非常少。 如果你觉得哪边是没听课不可能写出来的心得、 或是有其他觉得不可信的地方， 可以再向我提出来，我会好好解释清楚，谢谢。 作者从 182.235.242.149 修改文章於 2014/07/14 Mon 13:35:19 → chia228：听说助教很帅 07/18 14:17 推 kevinqtt：推荐这篇文章 07/29 03:15 推 tingyagami：个人觉得图论的部分老师教得蛮好的, 虽然老师英文表达 07/29 10:10 → tingyagami：不是那麽的流畅, 但是下课去问问题他都会很认真的回答, 07/29 10:10 → tingyagami：我觉得他蛮照顾外系学生的, 不错的老师!!!!! 07/29 10:12 → evan09900966：我是外系的，想修修看资工演算法概论，不过感觉 12/21 13:26 → evan09900966：英文授课对我来讲会有困难，请问会影响很大吗 12/21 13:27

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: neoneon (106.105.175.48), 07/12/2016 04:04:06