课程名称︰随机算法
课程性质︰选修
课程教师︰吕学一
开课学院：电机资讯学院
开课系所︰资讯工程学研究所/生医电子与资讯学研究所
考试日期（年月日）︰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.