※ [本文转录自 candog 信箱] 作者: [email protected] ("FireBolt") 标题: [心得] 资工系 资料结构 韩永楷 时间: Wed Feb 15 01:32:32 2017 作者: flere (小羊) 站内: nthu.course 标题: [心得] 资工系 资料结构 韩永楷 时间: 2011/06/29 Wed 23:59:26 课名： 资料结构 (Data Structure) 科号： 09920CS 235101 老师： 韩永楷 课本： 1. Introduction to Algorithms, 3rd edition, MIT Press. By T. Cormen, C. E. Leiserson, and R. L. Rivest (演算法我没买) 2. Fundamentals of Data Structures in C++, 2nd edition, Silicon Press. By E. Horowitz, S. Sahni, and D. Mehta (基础资料结构,我也没买XD) 课别： 资工系必修,电资院学士班核心选修 学分： 3 凉度： ★★★★★★....(反正不点名嘛~ 甜度： ★★★★★★....(因为我觉得我第一次考试63期末总分还94.... 建议先修课程： 基本上是没有啦~ 不过作业coding部分最好是有修过普通程式设计会比较好一点优~ 课程内容\简介： 课程内容 1. Growth of Functions 这边主要就是讲资工系对时间复杂度的看法,虽然他会讲很多个,可是 其实重要的只有big-O而已啦我觉得!! 2. Heaps && sorting 老师一开始会教很多sorting的方式 比如说有~ bubble,insertion,selection,merge,quick,heaps(不知道有没有少列 我觉得老师似乎很注重merge (他讲好久Zzz~) 可是我本身从来不写merge的QQ 然後他也非常喜欢heaps.... 好啦我承认他喜欢的我都没用过啦XDD 我觉得真正要学并且实作的的嘛.... 大概就是最好写的bubble(因为太简单了他一下就带过了XD 不然就是C内建的quick sort了(可是老师着墨很少 以上两个都很实用,只是在DS的课程里没什麽好讨论的 所以老师才对heaps跟merge讲很久吧 3. Lists, Stacks, and Queues 老师会先介绍pointer,可是有修过程式设计的应该都会,所以这边他不会拖很久 然後介绍最简单的linked list,这也没说很久 进入重头戏吧~ 老师会仔细介绍stack && queue的不同 stack-->就像一个箱子,你先进去的被放在最底部,越後面的在越上面 queue-->就像排队,你先排的可以先出去,後排的就要等比较久 这边老师还会介绍运算式的前序後序中序的写法 比如说 2+3-->中序 +23-->前序 23+-->後序 这边会出一个作业要同学写程式 这一阶段的作业分成2次(1.2为同一次,3为另外一次) 1.其中一题是要用学到的东西做出大数加减乘法 比如说9999999999999*9999999999999=? 2.还有他给你一串後序表示法的式子,要你算出他的答案是多少 比如说 2 3 + 答案是多少? 3.还有一题是给你中序要你转後序 比如说 2 3 +转成中序为2+3 4. Trees and Graphs 这边会介绍最基本的树跟图形 然後会教DFS跟BFS 还有preorder,inorder,postorder 前序 中序 後序 也就是说!! 你把算是做成运算式树後, 做前序-->得到前序表示 做中序-->得到中序表示 做後序-->得到後序表示 阿不过这边我觉得最重要的DFS他却没有讲很久> < 该不会我觉得重要的点都很不重要吧QQ 然後很奇怪的是 他也没有介绍euler circuit (由拉回路 也没有介绍dijkstra algo (P2P最短路径 (另一班有讲 没有好好介绍这两个让我有点小失望 =============================================================== 基础的说完之後就要进入本学期最精华了喔!!! 他要介绍BST跟AVL了!! BST-->binary serch tree 他就是你在放资料的时候(建立这棵树的过程 比较小的放左边,比较大的放右边 如此一来,你要搜寻跟排序都会变得很方便!! 不过有个缺点就是如果你的数字是1 2 3 4 5 插入的话 那他会变得极度不平衡(因为数字都一直变大结果都插在右边-->变成普通List 为了解决这个问题!! 於是就产生了AVL tree了!!! 这边版面有限说不了太多XD 简单来说AVL就是会旋转的BST而已~所以会变平衡(高度会变矮 然後这边会有一次作业要你写出AVL 只要做insert跟search就可以拿到100了 不过如果你可以做出delete功能的话可以再加20%喔~ =============================================================== 之後会讲B-tree (就是有很多个child的tree啦~ 5. Hashing hashing则是会教你要怎麽把资料存好,才会比较好找 举一个简单的例子 假设a,b,c,d,e分别为3,5,7,11,13 当你存入ace时你就把他放在3+7+13=23那一格 bc就放在5+7=12那一格 所以假设你要找abc存不存在,你就去3+5+7=15那里面看看有没有abc就好罗~ 我觉得是类似把你的资料编码的一种技巧啦~ 作业内容 作业占45%喔~共6次~ 然後coding跟纸本刚好一半一半~ 不过我觉得她作业难度分布很不平均> < 你会觉得打了好久也是7.5% 纸本不用多久就写完也是7.5%QQ 最夸张的就是final project只占10%啦QQ 要打粉久馁> < 简单介绍一下纸本作业跟fianl project吧(coding在上面讲过了优~ 1.纸本作业 纸本作业基本上都可以在1.5个小时内完成吧 上课有仔细听这不会是什麽大障碍,很快就可以完成的~ 2.coding 阿你不是说上面讲过了XD 没有啦我想说一下大概难度跟完成的时间 基本上难度因人而异,有人很快打完,有人根本打不出来 打出来的也纷很多种阿~ 有的打很快,有的打得很精简也是百百种XD 3.final project 我们这次是做通讯录,不过似乎每年不太一样就是了XD 考试内容 考试内容吗~其实我看一看他只会考以下几种 1.考演算法,不过一定可以用上课教的东西做出来 2.考一些计算跟画图(你纸本作业都会写就一定没问题 3.要你手写code(不过都是不会很难的部分,只会叫你写出一小段而已 上课方式： 老师上课都是用英语上喔!!! 不过老师的英语不会很艰深,基本上应该都可以听得懂顺利上课才对~ 老师上课前会先用中文讲一些益智游戏 所以如果你迟到了发现老师还在用中文说话, 那就表示你没有delay到任何进度啦XD 老师上课还满有趣的,大部分的时间都很有趣 不过还是会有少部分让人无聊的时间就是了~ 然後上课老师有时候会说n minutes break要给同学讨论 或是问助教问题 可是其实很多人都是用来补眠或是聊天啦XD 然後老师教完一点就会问大家听得懂吗? 听得懂的请举手 如果太少人举老师就会再讲一次 所以一定会教到你会的啦~ 给分： 应该算很甜吧~ 然後也算几分耕耘几分收获啦~ 你没做当然没分罗~ 附上我的作业成绩状态 Title Grade Percentage Assignment 1 100.00 7.50 % Midterm 1 63.00 15.00 % Assignment 2-1 100.00 3.75 % (大数...明显配分不当阿 Assignment 2-2 100.00 3.75 % Assignment 3 98.00 7.50 % Midterm 2 85.00 15.00 % Assignment 4 110.00 7.50 % Assignment 6 100.00 7.50 % Midterm 3 100.00 15.00 % Assignment 5 120.00 7.50 % Project (Function) 100.00 10.00 % Project (Document) 0.95 0.00 % Total 94.00 100.00 % 老师的喜好、个性： 老师跟同学互动良好 而且老师幽默风趣 我朋友表示老师长的好可爱喔 好像海贼王的大熊 我个人是觉得比较像摩莉亚啦XDD 反正老师人很好上起课来很开心~ 阿附注一下 老师在课程大纲上面放的东西~ Remark 1: Last year, approximately 70% of the students passed the course. The average score is 75. Remark 2: We normally will not make any score adjustment unless we have made serious mistakes that affect the assessment. Good news: It is possible that all students get A. Bad news: It is possible that we are failing all students. 给加签吗? 给阿~都说老师人超好的了XDD 总成绩/班上排名： 94(班排应该很後面吧~还没出来之後补上~ 百分比 (人数) A+ 90~100 21.3% (23人) A 85~89 20.4% (22人) A- 80~84 14.8% (16人) B+ 77~79 11.1% (12人) B 73~76 7.4% (8人) B- 70~72 6.5% (7人) C+ 67~69 3.7% (4人) C 63~66 2.8% (3人) C- 60~62 1.9% (2人) D 50~59 F 1~49 9.3% (10人) X 0 0.9% (1人) 总人数108人 PS:值得一修的好课!! -- ※ Origin: 枫桥驿站<bbs.cs.nthu.edu.tw> ◆ From: flere @ s9962303.YI.ab.nthu.edu.tw △ onlelonely：推~老师教的很好，分数给的真的很高 06/30 00:29Lqgs △ snake2：老师是个长得超级可爱的香港人！ 06/30 00:55oluG △ easteast：助教人都超 nice 的 ^ ^ 06/30 01:00olTj △ bgbgbg0087：推小羊^^ 06/30 07:07olTk △ tony810430：这学期似乎颇甜 9成以上都过了 而且A+颇多 06/30 13:49wNuv △ crazyplum：老师超可爱的XD!! 06/30 15:52oltj △ doctorpi：楼楼上总成绩100分神人...外加高程A+ 06/30 15:59mxsz △ jefflyc2002：推老师超有趣!助教人也都超nice! 06/30 16:22olua △ Only：总成绩94还很後面吗?@@ 06/30 22:46olub 那不就一半以上A+ XDD △ easteast：这次有20%的人 A+...非常的甜… 06/30 23:34gxmz △ easteast：也算是我少数能在第一上课时间，直接理解70%以上的06/30 23:35gxmz 好课，老师长得很像哆啦A梦，很有喜感，而且，上课 英文字正腔圆，非常有精神！！每周都很期待资料结 构的课！！ ^ ^ △ otwoeean：好老师必推 07/01 07:35lcyu △ tyson81833：推小羊~!! 07/02 01:32lkgU ─ proguest：去年当不少欸 平均我觉得只有6出头吧 07/04 23:34lyWT △ allencheng07：推楼上室友 07/05 13:58olis △ SLMT：推室友10与在下导师~~ 07/05 14:09mlbr △ qoo392：这次很甜，老师用心，助教用心，DS大推 07/05 20:42olUc ─ elioteliot42：去年第一届的白老鼠QAQ 07/06 18:07srAv △ OhBye：推，韩老师不点吗？ XD　 07/06 22:35olig ─ OhBye：去年的其实也不错，我还蛮喜欢去年期末专题的模式 07/06 22:36olig flere 於 2011/07/07 Thu 00:26:37 从 s9960105.CHENG.ab.nthu.edu.tw 修改 ─ creier：\简介： 12/29 10:12lzho

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: candog (140.114.32.68), 02/15/2017 12:15:12