想问大家 资演都有写算式吗
最后一题根本没有读怎么写
（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神人朝圣推