PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] [DS]103 台大资工 对答案+问题
楼主:
winnie48
(winnie)
2015-01-24 16:21:33
先附上题目连结:
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103424.pdf
就快要考试了,却还是都找不到这份的相关讨论,所以就po上自己写的和大家讨论!不过
这年的感觉有点难,有些不会的题目希望大家能给点提示~有错误的欢迎指正!
不会写的题目有:
1(b) 这感觉蛮基本...、3(c)、4
谢谢!大家加油!
http://i.imgur.com/gPRLRxT.jpg
http://i.imgur.com/VfrkNFE.jpg
http://i.imgur.com/d56ynn5.jpg
作者:
JacobSyu
(JacobSyu)
2015-01-24 17:59:00
这份真的爆难...
作者:
galapous
(墨)
2015-01-24 19:10:00
1(a)应该是lognloglogn,展开应该是loglogn项1(b)我是用Substitution method猜O(n)去证2(b)我算degree最大=logn,发生在root4我战友做法是先作topological sort之后再DP这份我想问2(a)跟5(c)要怎么做3(c)把HP reduce成max degree=2的spanning tree问题
作者:
FRAXIS
(喔喔)
2015-01-24 23:02:00
5(c)
http://en.wikipedia.org/wiki/Point_in_polygon
4如果用DP作应该不是polynomial time 但是应该是答案
作者:
APE36
(PT乡民)
2015-01-24 23:33:00
爆难+1
楼主:
winnie48
(winnie)
2015-01-25 08:23:00
谢谢大家提供的方法!晚点来研究!
作者:
galapous
(墨)
2015-01-25 09:49:00
早上起来突然想到1(b)应该可以用递洄树去看
作者:
qoojordon
(颖川琦)
2015-01-25 09:55:00
1(b)应该可以只看n/2这项? 根号n n变大时衰减很快
作者:
galapous
(墨)
2015-01-25 10:15:00
对阿,一开始我也是那样想,不过今天想想好像用递回树会更好。Thx f大
继续阅读
[理工] [自控] 补偿器极零点
siate
[理工] 线代是非
Mathew2010
Re: [理工] [线代、离散]函数可逆、同构
doom8199
Re: [理工] 102 台大电机丙 资结 对答案
galapous
[理工] [线代、离散]函数可逆、同构
yulinya
[资工] 交大100-97 DS&Algo数题
qoojordon
[资工] Ker 与 Nullity 观念问题
ra226683
[理工] 材料力学
eric820715
[理工] 线代
Mathew2010
[理工] binomial heap vs fibonacci heap
waterman815
Links
booklink
Contact Us: admin [ a t ] ucptt.com