[理工] [DS]103 台大資工 對答案+問題

[winnie48 (winnie)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.67.205
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422087695.A.ACA.html
推 JacobSyu: 這份真的爆難...
推 galapous: 1(a)應該是lognloglogn,展開應該是loglogn項
→ galapous: 1(b)我是用Substitution method猜O(n)去證
→ galapous: 2(b)我算degree最大=logn,發生在root
→ galapous: 4我戰友做法是先作topological sort之後再ＤＰ
→ galapous: 這份我想問2(a)跟5(c)要怎麼做
→ galapous: 3(c)把HP reduce成max degree=2的spanning tree問題
推 FRAXIS: 5(c) http://en.wikipedia.org/wiki/Point_in_polygon
→ FRAXIS: 4如果用DP作應該不是polynomial time  但是應該是答案
推 APE36: 爆難+1
→ winnie48: 謝謝大家提供的方法!晚點來研究!
推 galapous: 早上起來突然想到1（b）應該可以用遞洄樹去看
推 qoojordon: 1(b)應該可以只看n/2這項? 根號n n變大時衰減很快
→ galapous: 對阿，一開始我也是那樣想，不過今天想想好像用遞迴樹會
→ galapous: 更好。
推 galapous: Thx f大
推 abc12321: 4 用暴力法找出每條路O(n^2)就能解
推 joejoejoe: 1.B 洪毅在解時說約等於T(n/2)+n
推 jimmylin1024: 第一題
→ jimmylin1024: https://i.imgur.com/qk8BcKB.jpg
→ jimmylin1024: 1（a)也是可以假設n = 2^k 變數變換去做 也會得到O(
→ jimmylin1024: logn)