課程名稱︰隨機演算法
課程性質︰選修
課程教師︰呂學一
開課學院：電資學院
開課系所︰資工所
考試日期（年月日）︰2004.06.09
考試時限（分鐘）：180
試題 :
Randomized Algorithms
close-book final exam
June 9, 2004
Instruction
Please write down your name and ID on each piece of your answer sheets.
Cheating will be most seriously punished. Any dishonest attempt in this exam
implies an 'F' as your final grade.
You may use anything of our lectures as a subroutine to your answers, unless
you are explicitly asked to explain something we explained in class.
Problem 1 (20 points)
˙(5 points) State Loomis' Theorem.
˙(5 points) State Yao's Minimax Principle.
˙(10 points) Explain why Loomis' Theorem implies Yao's Minimax Principle.
Problem 2 (20 points)
˙(5 points) State Adleman's Theorem on derandomizing randomized circuits.
˙(15 points) Prove the above theorem.
Problem 3 (20 points)
Give and justify an expected O(n)-time algorithm by random sampling for
selecting the (n^(1/8))-th smallest number out of n distinct numbers. (Giving
the well known deterministic O(n)-time algorithm for selecting a number is not
a feasible solution to this problem. An ideal solution to this problem would
be an algorithm modified from the randomized median-selection algorithm
explained in class.)
Problem 4 (20 points)
Let C_x be the cycle (x_1, x_2, ... , x_n, x_1). Let C_y be the cycle
(y_1, y_2, ... , y_n, y_1). Let graph G consist of C_x and C_y with x_1 and y_1
identified. That is, G has (2n - 1) nodes forming two simple length-n cycles
C_x and C_y joined at x_1 = y_1.
˙(10 points) What is the hitting time H(x_i, x_j) in G?
˙(10 points) What is the hitting time H(x_i, y_j) in G?
Problem 5 (25 points)
We proved in class that the node with rank k has expected depth
H_k + H_(n-k+1) - 1 in a random TREAP of n nodes. We used Mulmuley's Games A
and B. Recall that A(n) = H_n and B(n, m) = H_m + H_n - H_(m+n). Yi-Wei showed
us a very elegant proof for the first equality.
˙(15 points) Prove that the node with rank k also has expected subtree size
H_k + H_(n-k+1) - 1.
Hint: you may resort to Mulmuley's games. Alternatively (or equivalently)
you might want to prove and use an observation that the node with
rank i is an ancestor of the node with rank j with probability
exactly 1/(|i-j| + 1).
˙(10 points) Let us introduce another game, called game C. It has n regular
cards and m stop cards. The counting is just like game A, but as soon as a
stop card appears the counting is over. You are asked to prove that
C(n, m) = H_(m+n) - H_m. (For example, it should be pretty easy to prove
the equality for m = 0 or m = 1.)
Problem 6 (15 points)
Let G be an n-node m edge graph. In the very last lecture, we get stuck at a
step for proving
︿ n
Pr[e ∈ Ｔ] ≦ ──
r
︿
where e is a randomly chosen edge in the input graph G, and Ｔ is the minimum
spanning tree of the union of {e}, a fixed spanning tree T_0 of G, and a size-r
random sample R of G's edges. The above inequality can, as a matter of fact,
be proved very easily. You are asked to give it a try possibly with the
following hint:
Instead of considering adding e to R, try to think of e as a randomly chosen
︿
edge in Ｒ = R ∪ {e}.
(This is exactly what Timothy Chan meant by "Backward Analysis".)