先附上题目连结：
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

这份真的爆难...

1(a)应该是lognloglogn,展开应该是loglogn项1(b)我是用Substitution method猜O(n)去证2(b)我算degree最大=logn,发生在root4我战友做法是先作topological sort之后再ＤＰ这份我想问2(a)跟5(c)要怎么做3(c)把HP reduce成max degree=2的spanning tree问题

5(c) http://en.wikipedia.org/wiki/Point_in_polygon4如果用DP作应该不是polynomial time 但是应该是答案

爆难+1

谢谢大家提供的方法!晚点来研究!

早上起来突然想到1（b）应该可以用递洄树去看

1(b)应该可以只看n/2这项? 根号n n变大时衰减很快

对阿，一开始我也是那样想，不过今天想想好像用递回树会更好。Thx f大