想問大家 資演都有寫算式嗎
最後一題根本沒有讀怎麼寫
（approximation那題）ans=2
直接把背的答案寫上去了～
不過整份考卷我都沒看到說要explain有點怕怕的，所以每一題除了那題我都有寫XD
作者:
can18 (18號)
2018-02-05 12:06:00雖然他沒要求但我每題都證明
作者:
can18 (18號)
2018-02-05 12:07:002|C*| < 2|A| = |C|
我覺得要 去年我都沒怎麼寫算式 出來不如預期 QQ
作者: MaoJ 2018-02-05 12:07:00
第一題ce嗎
作者:
can18 (18號)
2018-02-05 12:08:002|C*| > 2|A| = |C| 才對
作者:
gR7P4zXH (tpn7gpdx)
2018-02-05 12:08:00第一題是A?
作者:
gR7P4zXH (tpn7gpdx)
2018-02-05 12:09:00Multipop那題有人有頭緒嗎QQ
作者: MaoJ 2018-02-05 12:09:00
帥喔
作者: havewind 2018-02-05 12:10:00
CE+1
作者: MaoJ 2018-02-05 12:10:00
n^2 + n 我賽一個
作者:
moneylon (bencool)
2018-02-05 12:11:00排序的lower bound 是多少
作者:
can18 (18號)
2018-02-05 12:11:00ce+1
可是他說開頭空結尾也空 所以pop=push (包含mutilpop)所以我猜不會那麼多
作者:
gR7P4zXH (tpn7gpdx)
2018-02-05 12:13:00恭喜大家QQ
作者:
can18 (18號)
2018-02-05 12:14:00stack O(n) 我用accounting method 證
作者:
can18 (18號)
2018-02-05 12:15:00排序 nlogn 用 decision tree證
作者:
wade8204 (路過的小鄉民)
2018-02-05 12:20:00如果只寫答案會有分嗎QQ 像排序那題
作者:
leoone (里歐一代)
2018-02-05 12:20:00Stack 那題在考amortize cost O(n)
作者: MaoJ 2018-02-05 12:21:00
排序那題會不會是純比較和交換而已呢
Stack那題他說總共n次operation我想很久 最後我是算push最多n-1次 pop：2/n次 mpop：2/n次 然後把lower upper bound都寫給它
Multi 我寫theta(n)因為我upper和lower bound都算n...
排序我是比較 交換 合在一起算的複雜度都寫了 因為不知道要不要分開寫
作者:
sarsman (DeNT15T♠)
2018-02-05 12:35:00感覺得出來在考分攤，但我只有寫次數，沒轉成複雜度符號qq
potential function用裡面item數量應該ok 吧？
作者:
can18 (18號)
2018-02-05 12:37:00比較後交換也是o(1) 沒差吧
作者: MaoJ 2018-02-05 12:39:00
水管 23嗎
作者:
s06i06 (三條魚)
2018-02-05 12:40:0023
作者:
moneylon (bencool)
2018-02-05 12:42:0019+4
作者:
can18 (18號)
2018-02-05 12:44:00vertex cover = 2 那題課本有
作者:
leoone (里歐一代)
2018-02-05 12:45:00Vertex cover 那題是2 近似演算法的經典題水管我寫19忘記+4QQ
作者: MaoJ 2018-02-05 12:47:00
是哪題呀 最後嗎
那個考古的singer value 既然出現了 還有Jordan...
作者:
s06i06 (三條魚)
2018-02-05 15:24:00數學爆炸的舉手 幹
作者:
p5341500 (godklike)
2018-02-05 15:24:00幹
作者:
s06i06 (三條魚)
2018-02-05 15:25:00是吧
作者:
Ofianse (大便人)
2018-02-05 15:28:00無解
作者:
can18 (18號)
2018-02-05 15:29:00無解+1
作者:
can18 (18號)
2018-02-05 15:30:00機率第二題2/5？
作者:
can18 (18號)
2018-02-05 15:31:00第一題我算 83/200多
作者:
MOUOREO (毛毛)
2018-02-05 15:32:00不是45/83嗎 還有x1,x2都等於2的情況？
作者:
can18 (18號)
2018-02-05 15:32:0045/83是哪一題呢
作者:
can18 (18號)
2018-02-05 15:33:00... GG兩題都錯
作者:
Ofianse (大便人)
2018-02-05 15:33:0045/83辣
作者:
moneylon (bencool)
2018-02-05 15:33:00我算45/83下一題紅球的3/8
是要算SVD還是只要singular value啊請問?!!
作者:
s1020824 (HowardW)
2018-02-05 15:37:00C(10,8)/[2*C(10,8)-C(7,6)] 吧
作者:
can18 (18號)
2018-02-05 15:39:00誤會題目意思 QQ
作者:
can18 (18號)
2018-02-05 16:07:00請問紅球怎麼算
作者:
Ofianse (大便人)
2018-02-05 16:09:00八個紅球只有三個來自第二桶啊
作者:
can18 (18號)
2018-02-05 16:16:00我算 第二桶拿到紅球 /(第一桶拿到紅球+第二桶拿到紅球)請問這樣的算法的錯誤在哪
作者:
can18 (18號)
2018-02-05 16:19:00好的 感謝
（1/2*1/3）/（1/2*5/9 +1/2*1/3）
作者: nvwy9632 (熾熾) 2018-02-05 16:51:00
難道只有我覺得是第二題1/6嗎...
作者:
nO25948 (chenyuyan)
2018-02-05 17:06:00我也寫1/6
作者:
q1qip123 (wtlee)
2018-02-05 17:20:00題目有說第二顆要拿紅球喔？！想說2個箱子 直接寫1／2…
作者:
leoone (里歐一代)
2018-02-05 17:54:00樓上 畫出BST 記得c選項有出現 911 2xx 912 這樣會出現分支 就是錯的 去年台大也考過
作者: nvwy9632 (熾熾) 2018-02-05 17:58:00
往下找的數一定會夾在兩個轉向的數中間
作者: jd06 2018-02-05 20:16:00
資演第一題有e? 我檢查了兩次沒發現欸@@
作者:
MOUOREO (毛毛)
2018-02-05 20:24:00有哦
作者:
can18 (18號)
2018-02-05 20:06:00雖然他沒要求但我每題都證明
作者:
can18 (18號)
2018-02-05 20:07:002|C*| < 2|A| = |C|
我覺得要 去年我都沒怎麼寫算式 出來不如預期 QQ
作者: MaoJ 2018-02-05 20:07:00
第一題ce嗎
作者:
can18 (18號)
2018-02-05 20:08:002|C*| > 2|A| = |C| 才對
作者:
gR7P4zXH (tpn7gpdx)
2018-02-05 20:08:00第一題是A?
作者:
gR7P4zXH (tpn7gpdx)
2018-02-05 20:09:00Multipop那題有人有頭緒嗎QQ
作者: MaoJ 2018-02-05 20:09:00
帥喔
作者: havewind 2018-02-05 20:10:00
CE+1
作者: MaoJ 2018-02-05 20:10:00
n^2 + n 我賽一個
作者:
moneylon (bencool)
2018-02-05 20:11:00排序的lower bound 是多少
作者:
can18 (18號)
2018-02-05 20:11:00ce+1
可是他說開頭空結尾也空 所以pop=push (包含mutilpop)所以我猜不會那麼多
作者:
gR7P4zXH (tpn7gpdx)
2018-02-05 20:13:00恭喜大家QQ
作者:
can18 (18號)
2018-02-05 20:14:00stack O(n) 我用accounting method 證
作者:
can18 (18號)
2018-02-05 20:15:00排序 nlogn 用 decision tree證
作者:
wade8204 (路過的小鄉民)
2018-02-05 20:20:00如果只寫答案會有分嗎QQ 像排序那題
作者:
leoone (里歐一代)
2018-02-05 20:20:00Stack 那題在考amortize cost O(n)
作者: MaoJ 2018-02-05 20:21:00
排序那題會不會是純比較和交換而已呢
Stack那題他說總共n次operation我想很久 最後我是算push最多n-1次 pop：2/n次 mpop：2/n次 然後把lower upper bound都寫給它
Multi 我寫theta(n)因為我upper和lower bound都算n...
排序我是比較 交換 合在一起算的複雜度都寫了 因為不知道要不要分開寫
作者:
sarsman (DeNT15T♠)
2018-02-05 20:35:00感覺得出來在考分攤，但我只有寫次數，沒轉成複雜度符號qq
potential function用裡面item數量應該ok 吧？
作者:
can18 (18號)
2018-02-05 20:37:00比較後交換也是o(1) 沒差吧
作者: MaoJ 2018-02-05 20:39:00
水管 23嗎
作者:
s06i06 (三條魚)
2018-02-05 20:40:0023
作者:
moneylon (bencool)
2018-02-05 20:42:0019+4
作者:
can18 (18號)
2018-02-05 20:44:00vertex cover = 2 那題課本有
作者:
leoone (里歐一代)
2018-02-05 20:45:00Vertex cover 那題是2 近似演算法的經典題水管我寫19忘記+4QQ
作者: MaoJ 2018-02-05 20:47:00
是哪題呀 最後嗎
那個考古的singer value 既然出現了 還有Jordan...
作者:
s06i06 (三條魚)
2018-02-05 23:24:00數學爆炸的舉手 幹
作者:
p5341500 (godklike)
2018-02-05 23:24:00幹
作者:
s06i06 (三條魚)
2018-02-05 23:25:00是吧
作者:
Ofianse (大便人)
2018-02-05 23:28:00無解
作者:
can18 (18號)
2018-02-05 23:29:00無解+1
作者:
can18 (18號)
2018-02-05 23:30:00機率第二題2/5？
作者:
can18 (18號)
2018-02-05 23:31:00第一題我算 83/200多
作者:
MOUOREO (毛毛)
2018-02-05 23:32:00不是45/83嗎 還有x1,x2都等於2的情況？
作者:
can18 (18號)
2018-02-05 23:32:0045/83是哪一題呢
作者:
can18 (18號)
2018-02-05 23:33:00... GG兩題都錯
作者:
Ofianse (大便人)
2018-02-05 23:33:0045/83辣
作者:
moneylon (bencool)
2018-02-05 23:33:00我算45/83下一題紅球的3/8
是要算SVD還是只要singular value啊請問?!!
作者:
s1020824 (HowardW)
2018-02-05 23:37:00C(10,8)/[2*C(10,8)-C(7,6)] 吧
作者:
can18 (18號)
2018-02-05 23:39:00誤會題目意思 QQ
作者:
can18 (18號)
2018-02-06 00:07:00請問紅球怎麼算
作者:
Ofianse (大便人)
2018-02-06 00:09:00八個紅球只有三個來自第二桶啊
作者:
can18 (18號)
2018-02-06 00:16:00我算 第二桶拿到紅球 /(第一桶拿到紅球+第二桶拿到紅球)請問這樣的算法的錯誤在哪
作者:
can18 (18號)
2018-02-06 00:19:00好的 感謝
（1/2*1/3）/（1/2*5/9 +1/2*1/3）
作者: nvwy9632 (熾熾) 2018-02-06 00:51:00
難道只有我覺得是第二題1/6嗎...
作者:
nO25948 (chenyuyan)
2018-02-06 01:06:00我也寫1/6
作者:
q1qip123 (wtlee)
2018-02-06 01:20:00題目有說第二顆要拿紅球喔？！想說2個箱子 直接寫1／2…
作者:
leoone (里歐一代)
2018-02-06 01:54:00樓上 畫出BST 記得c選項有出現 911 2xx 912 這樣會出現分支 就是錯的 去年台大也考過
作者: nvwy9632 (熾熾) 2018-02-06 01:58:00
往下找的數一定會夾在兩個轉向的數中間
作者: jd06 2018-02-06 04:16:00
資演第一題有e? 我檢查了兩次沒發現欸@@
作者:
MOUOREO (毛毛)
2018-02-06 04:24:00有哦
作者:
arhtur945 (AnthonyBennet)
2018-03-01 20:14:00程設100神人朝聖推