课程名称︰随机算法
课程性质︰选修
课程教师︰吕学一
开课学院：电机资讯学院
开课系所︰资讯工程学研究所/生医电子与资讯学研究所
考试日期（年月日）︰2014/03/31
考试时限（分钟）：180(14:30-17:30)
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
台大资工随机算法第一次期中考
2014年3月31日下午2:20起三个小时
总共五题，每题二十分，可按任何顺序答题。每题难度不同，请审慎判断恰当的解题顺序
第一题 Show that the randomized quicksort algorithm RandQS on a set of n
distinct numbers runs in expected O(nlogn) time.
第二题 Prove the following key observation used in analyzing both algorithms
for finding minimum cuts via edge contractions:
Pr[e(i)不属于C* | e(1)不属于C* ^ e(2)不属于C* ^ ... ^ e(i-1)不属于C*]
≧ (n-i-1) / (n-i+1)
where C* is an arbitrary minimum cut of the input n-node graph G and e(i) is
the i-th contracted edge for each i = 1,2,...,n-2.
第三题
(1) State Loomis' Theorem.
(2) State Yao's Lemma.
(3) Prove Yao's Lemma using Loomis' Theorem.
(4) Use Yao's Lemma to show that any correct depth-first evaluaion algorithm
for NOR-circuits runs in expected Ω( n^0.694 ) time, where n is the number of
input pins.
第四题 In our analysis of median selection algorithm via random sampling,
there are two events:
Event 1 : |L| ≦ 0.5n ＜ |L|+|M| and
Event 2 : |M| ≦ 4 * n^0.75.
Prove that Pr[~Event 1 ] = O( n^(-0.25) )
Pr[~Event 2 | Event 1 ] = O( n^(-0.25) ).
第五题 Let S ba a finite set. Let g be a bijection from S^2 to S^2. Let a and
b be two elements chosen from S uniformly at random, where a and b are not
necessarily distinct. Let (c,d) = g(a,b). Prove or disprove that c and d are
independent.