作者qaswed101 (一一)
看板Grad-ProbAsk
標題[理工] 成大107 資訊聯招
時間Mon Feb 5 12:05:41 2018
想問大家 資演都有寫算式嗎
最後一題根本沒有讀怎麼寫
（approximation那題）ans=2
直接把背的答案寫上去了～
不過整份考卷我都沒看到說要explain有點怕怕的，所以每一題除了那題我都有寫XD
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.8.247.71
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1517803544.A.8CA.html
1F：推 can18: 雖然他沒要求但我每題都證明02/05 12:06
2F：推 kssdpp222: 202/05 12:06
3F：→ kssdpp222: 都沒寫 哈哈 寫一面02/05 12:06
4F：→ can18: 2|C*| < 2|A| = |C|02/05 12:07
5F：推 lion83395: 我覺得要 去年我都沒怎麼寫算式 出來不如預期 QQ02/05 12:07
6F：→ MaoJ: 第一題ce嗎02/05 12:07
7F：→ can18: 2|C*| > 2|A| = |C| 才對02/05 12:08
8F：推 gR7P4zXH: 第一題是A?02/05 12:08
9F：→ lion83395: Ce02/05 12:08
10F：→ kssdpp222: ce+102/05 12:08
11F：→ gR7P4zXH: Multipop那題有人有頭緒嗎QQ02/05 12:09
12F：推 MaoJ: 帥喔02/05 12:09
13F：推 havewind: CE+102/05 12:10
14F：→ MaoJ: n^2 + n 我賽一個02/05 12:10
15F：推 moneylon: 排序的lower bound 是多少02/05 12:11
16F：推 can18: ce+102/05 12:11
17F：推 kssdpp222: 可是他說開頭空結尾也空 所以pop=push (包含mutilpop)02/05 12:12
18F：→ kssdpp222: 所以我猜不會那麼多02/05 12:12
19F：→ qaswed101: 我寫 O(n)02/05 12:13
20F：推 gR7P4zXH: 恭喜大家QQ02/05 12:13
21F：推 can18: stack O(n) 我用accounting method 證02/05 12:14
22F：推 kssdpp222: Mutilpop O(n)+1 02/05 12:14
23F：→ can18: 排序 nlogn 用 decision tree證02/05 12:15
24F：推 wade8204: 如果只寫答案會有分嗎QQ 像排序那題02/05 12:20
25F：推 leoone: Stack 那題在考amortize cost O(n)02/05 12:20
26F：→ MaoJ: 排序那題會不會是純比較和交換而已呢02/05 12:21
27F：推 jch660tw: Stack那題他說總共n次operation我想很久 最後我是算push02/05 12:33
28F：→ jch660tw: 最多n-1次 pop：2/n次 mpop：2/n次 然後把lower upper b02/05 12:33
29F：→ jch660tw: ound都寫給它02/05 12:33
30F：推 ahahahahah: Multi 我寫theta(n)02/05 12:34
31F：→ ahahahahah: 因為我upper和lower bound都算n...02/05 12:34
32F：→ jch660tw: 排序我是比較 交換 合在一起算的複雜度都寫了 因為不知02/05 12:35
33F：→ jch660tw: 道要不要分開寫02/05 12:35
34F：推 sarsman: 感覺得出來在考分攤，但我只有寫次數，沒轉成複雜度符號q02/05 12:35
35F：→ sarsman: q02/05 12:35
36F：推 gary70812: potential function用裡面item數量應該ok 吧？02/05 12:37
37F：推 can18: 比較後交換也是o(1) 沒差吧02/05 12:37
38F：→ MaoJ: 水管 23嗎02/05 12:39
39F：推 s06i06: 2302/05 12:40
40F：推 jch660tw: 23 我忘記幾加幾了02/05 12:40
41F：推 moneylon: 19+402/05 12:42
42F：推 OctRhythm: vertex cover大家算多少呢？02/05 12:44
43F：推 can18: vertex cover = 2 那題課本有02/05 12:44
44F：推 leoone: Vertex cover 那題是2 近似演算法的經典題 02/05 12:45
45F：→ leoone: 水管我寫19忘記+4QQ02/05 12:46
46F：→ MaoJ: 是哪題呀 最後嗎02/05 12:47
47F：推 kssdpp222: 那個考古的singer value 既然出現了 還有Jordan...02/05 15:22
48F：推 s06i06: 數學爆炸的舉手 幹02/05 15:24
49F：推 p5341500: 幹02/05 15:24
50F：推 kssdpp222: 最後無解嗎02/05 15:25
51F：→ s06i06: 是吧02/05 15:25
52F：推 lion83395: SVD看到直接跳了02/05 15:25
53F：推 gary70812: 無解＋102/05 15:26
54F：推 ahahahahah: 無解02/05 15:27
55F：推 jch660tw: 無解02/05 15:27
56F：推 Ofianse: 無解02/05 15:28
57F：推 can18: 無解+102/05 15:29
58F：推 ahahahahah: 離散第一題是38/83嗎02/05 15:29
59F：推 gary70812: 紅球那題是條件機率嗎02/05 15:30
60F：→ can18: 機率第二題2/5？02/05 15:30
61F：→ gary70812: 我寫45/83死定了02/05 15:30
62F：→ can18: 第一題我算 83/200多02/05 15:31
63F：推 lion83395: 45/83 +102/05 15:31
64F：→ can18: 好像是83 /28602/05 15:31
65F：→ lion83395: 第二題我算3/802/05 15:32
66F：推 MOUOREO: 不是45/83嗎 還有x1,x2都等於2的情況？ 02/05 15:32
67F：→ can18: 45/83是哪一題呢02/05 15:32
68F：推 ahahahahah: 啊幹我最後一步錯了02/05 15:32
69F：→ gary70812: 紅球算3/802/05 15:32
70F：→ MOUOREO: 第二題我也3/802/05 15:32
71F：→ ahahahahah: 這樣還會有分嗎QQ02/05 15:32
72F：→ lion83395: 整數解那題02/05 15:32
73F：→ can18: ... GG兩題都錯02/05 15:33
74F：推 Ofianse: 45/83辣02/05 15:33
75F：→ can18: 求算式02/05 15:33
76F：→ moneylon: 我算45/83下一題紅球的3/802/05 15:33
77F：推 king8313: 是要算SVD還是只要singular value啊請問?!!02/05 15:34
78F：→ lion83395: 高中的記憶都還在 神奇XD02/05 15:34
79F：推 s1020824: C(10,8)/[2*C(10,8)-C(7,6)] 吧02/05 15:37
80F：→ can18: 誤會題目意思 QQ02/05 15:39
81F：→ qaswed101: 我也是45/83 跟 3/802/05 16:03
82F：→ can18: 請問紅球怎麼算02/05 16:07
83F：推 Ofianse: 八個紅球只有三個來自第二桶啊02/05 16:09
84F：→ qaswed101: 紅球8顆 第二箱有3顆 故得 3/802/05 16:10
85F：推 can18: 我算 第二桶拿到紅球 /(第一桶拿到紅球+第二桶拿到紅球)02/05 16:16
86F：→ can18: 請問這樣的算法的錯誤在哪02/05 16:17
87F：推 lion83395: 你這樣算也會得3/8 我也是這樣算的02/05 16:18
88F：推 can18: 好的 感謝 02/05 16:19
89F：推 gary70812: (1/6) /(8/18)吧 好像02/05 16:20
90F：推 lion83395: （1/2*1/3）/（1/2*5/9 +1/2*1/3）02/05 16:21
※ 編輯: qaswed101 (180.204.178.227), 02/05/2018 16:40:06
91F：推 nvwy9632: 難道只有我覺得是第二題1/6嗎... 02/05 16:51
92F：推 kssdpp222: 3/8 02/05 17:04
93F：推 nO25948: 我也寫1/6 02/05 17:06
94F：推 shownlin: 3/8 林緯題庫班有一題一模一樣的 02/05 17:07
95F：推 kssdpp222: 45/83 02/05 17:07
96F：推 q1qip123: 題目有說第二顆要拿紅球喔？！想說2個箱子 直接寫1／2… 02/05 17:20
97F：推 haohaoger: 請問資演第一題搜尋363怎麼找出錯誤選項啊？ 02/05 17:48
98F：推 leoone: 樓上 畫出BST 記得c選項有出現 911 2xx 912 這樣會出現分 02/05 17:54
99F：→ leoone: 支 就是錯的 去年台大也考過 02/05 17:54
100F：推 nvwy9632: 往下找的數一定會夾在兩個轉向的數中間 02/05 17:58
101F：推 haohaoger: 嗯嗯好的謝謝兩位解答~ 02/05 18:31
102F：推 jd06: 資演第一題有e? 我檢查了兩次沒發現欸@@ 02/05 20:16
103F：推 MOUOREO: 有哦 02/05 20:24
104F：推 arhtur945: 程設100神人朝聖推 03/01 20:14