先附上題目連結：
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大