课程名称︰随机算法
课程性质︰选修
课程教师︰吕学一
开课学院：电机资讯学院
开课系所︰资讯工程学研究所/生医电子与资讯学研究所
考试日期（年月日）︰2014/06/16
考试时限（分钟）：180(14:35-17:35)
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
第一题
(5 points) Define PCP(r(n), q(n)).
(5 points) Prove PCP(0, 0) = P.
(5 points) Prove NP is a subset of PCP(0, poly(n)).
(10 points) Find an n-variable 3-CNF ψ(x) for some positive number n
and some truth assignment A that does not satisfy ψ such that P(a) = 0
holds for the birany vector a in Z^n_2 corresponding to A, where
P(x) is the polynomial over Z_2 that arithmetizes ψ(x).
(For instance, if the 3-CNF ψ(x) is (x_1 v !x_2 v !x_3) ^ (x_1 v x_2),
then P(x) = (1 - x_1) x_2 x_3 + (1 - x_1)(1 - x_2).)
第二题
(10 points) Define the class IP.
(15 points) Prove #3SAT in IP. For brevity of your proof, you may assume
that the input n-variable 3-CNF has Ο(1) clauses.
(Feel free to use a well-known result due to Shamir stating that IP equals
a certain deterministic class.)
第三题
(25 points) Prove the sampling lemma below which can be used to analyze
the expected linear-time algorithm of Karger, Klein, and Tarjan for
minimum spanning tree:
Let T_0 be a spanning tree of an n-node m-edge undirected connected graph G
with distinct edge weights. Let R be a uniformly random sample of the edge
set of G. If the minimum spanning tree of the connected graph R ∪ T_0 is T,
the expected number of edges in G \ T that are not T-heavy in G is at most
(m n) / |R|.
第四题
(25 points) Given the n * n all-pairs distance matrix D for an n-node
connected unweighted graph G, you are asked to give and justify an algorithm
to obtain all except expected Ο(n) entries of the n * n successor matrix S
of G whose running time is Ο(log^2 n) times the time MM(n) needed for
multiplying two n * n matrices. You may directly use the following
sampling lemma:
There are exactly m white balls in a urn containing n > m balls. If we sample
r balls without replacement for the urn, where n / 2 ≦ r m ≦ n, then
the probability that exactly one of these m white balls is sampled is
at least 1 / (2e).
第五题
(10 points) Prove that the value A(n) of Mulmuley's first game is H_n.
(Recall that A(n) is the expected value of the number X of cards,
in a randomly shuffled deck of cards {1, 2, ..., n},
that are larger than all previous cards.)
(15 points) You are asked to prove that the expected depth of any node
in an n-node treap is Ο(H_n).