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