課程名稱︰隨機演算法
課程性質︰選修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所︰資訊工程學研究所/生醫電子與資訊學研究所
考試日期（年月日）︰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.