作者candog (怕热的肥宅)
看板NTHU_Course
标题Fw: [心得] 资工系 资料结构 韩永楷
时间Wed Feb 15 12:15:12 2017
※ [本文转录自 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