課程名稱︰隨機演算法
課程性質︰選修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所︰資訊工程學研究所/生醫電子與資訊學研究所
考試日期（年月日）︰2014/05/05
考試時限（分鐘）：180(14:30-17:30)
是否需發放獎勵金：是
試題 :
總共五題，每題二十分，可按任何順序答題。
每題難度不同，請審慎判斷恰當的解題順序。
第一題
Let X = X_1 + X_2 + ... + X_n, where X_1, ..., X_n are n independent
Poisson trials with 0 < Pr[X_i = 1] < 1 for each i = 1, 2, ..., n.
Prove that if 1 + δ > 2e, then
Pr[X > (1 + δ)μ] < 1 / 2^[(1 + δ)μ]
第二題
Give and justify a deterministic polynomial-time approximation algorithm
with approximation ratio 1 - 1 / e for the NP-complete MAXSAT problem.
第三題
In the deterministic polynomial-time Ο(sqrt(n ln n))-approximation algorithm
for the balanced coloring problem for n balls and n sets, we have to
compute the following function of the sum of n conditional probabilities
for Ο(n) nodes u in the coloring tree:
q(u) = Σ{i = 1 to n} Pr[|A_i x| > 4 sqrt(n ln n) | c(u)]
Explain how to compute q(u) for each node u in time polynomial in n.
第四題
In the second scenario for the proof of the hitting-time formula
H(u, v) + H(v, u) = 2 m R(u, v)
in an m-edge graph G, we insert 2m units of current into node u
and deg(x) units of current out of each node x (including u) of G.
You are asked to prove that, for any node x of G, the potential difference
V(u, x) between nodes u and x equals the expected hitting time H(x, u)
from node x to node u.
(You are NOT asked to prove the above hitting-time formula.)
第五題
Prove or disprove that the expected hitting time H_G(u, v) from node u
to node v in graph G is greater than or equal to the expected hitting time
H_G'(u, v) from u to v in a graph G' that is obtained from G by adding
a number of edges.