582691 Randomized Algorithms I (Spring 2013)
Course examination, Tuesday 26 February, 16:00–19:00, Exactum A111 Examiner: Jyrki Kivinen
Important: Solve three(3) of the following four problems. You can choose whichever three problems you prefer. They all give the same amount of points, maximum of 16 points per problem, for a maximum of 48 points for the whole exam.
Please mark clearly in your answer sheet which three problems you have chosen. If you don’t, the grader will use his own discretion to choose what to grade, not necessarily to your advantage.
In Problems 1, 3 and 4 you may use any results from the course. Some results that may be useful are listed at the end of this sheet.I Answer all parts of the problem. In Problem 2, your answer should be on a similar level of detail as the one presented in the textbook and lecture notes.
You may answer in English, Finnish or Swedish.
Problem 1 We assume that there is a function f from {1, . . . , n} to N, where n is very large.
We are given an efficient procedure that receives x ∈ {1, . . . , n} as input and returns f(x), but otherwise we know nothing about f. (That is, we consider the procedure forf as a “black box.”) We also assume we have an efficient procedure for choosing random elements uniformly from {1, . . . , n}.
We define, for the purposes of this problem, the median of f as any natural numberM such that at least half the elements x∈ {1, . . . , n}satisfyf(x)≥M, and at least half the elements x ∈ {1, . . . , n} satisfy f(x) ≤ M. (This value is not in general unique, but that is not a problem here.)
(a) Suppose that we know the median valueM, and our task is to find elements a and b from {1, . . . , n} such that f(a) ≤ M and f(b) ≥ M. The result b =a with f(a) =M is also acceptable. Give for the problem a Las Vegas type random algorithm (i.e., one that never gives incorrect answers) and analyze its performance. In particular, estimate the expected number of values f(x) that need to be evaluated.
(b) Suppose now that we do not know the median but still wish to find a and b such that f(a) ≤ M and f(b) ≥ M. Give a randomized algorithm that for any given δ outputs with probability at least 1−δ values a and b that satisfy the conditions. With probabilityδ, your algorithm may produce an incorrect answer.
More on the reverse side!
Problem 2 Assume that X1, . . . , Xn are independent 0-1 valued random variables with Pr(Xi = 1) =pi and Pr(Xi = 0) = 1−pi. Let X =Pn
i=1Xi andµ=E[X].
Prove the following Chernoff bound: for 0< δ <1 we have
Pr(X ≤(1−δ)µ)≤
e−δ (1−δ)1−δ
µ
.
Problem 3 Consider an instance of the Boolean satisfiability problem (SAT) where there are m clauses and each of them has exactly k literals.
(a) Give a Las Vegas algorithm that finds an assignment satisfying at least m(1−2−k)clauses. Show that the expected running time of your algorithm is finite; no closer analysis is needed.
(b) Derandomize your algorithm from part (a) using the method of conditional expectations.
Problem 4 We have n clients and n servers. Each client needs the services of one server, and each server can serve two clients at the same time.
We try to assign servers to clients using the following protocol: Each client sends a request to a random server. A server that receives at most two service requests, accepts those requests. A server that receives more than two service requests, accepts two requests and discards the rest. Let X be the number of clients that have their request accepted when this protocol is run once.
(a) What is the expected value ofX? Give an exact value and the limit when n→ ∞.
(b) Model the situation using the balls and bins model. Calculate the expected value ofXusing the Poisson approximation. Compare this result to part (a).
(c) Still considering the Poisson approximation, show that there is a constant c > 0 such that for large n, with high probability we have X ≥ E[X]− c√
nlogn. Can you transfer this result to the exact model?
Hint: You may find it useful to consider, for i = 1, . . . , n, the events “server i receives no requests,” “serverireceives exactly one request,” and “serverireceives two or more requests.”
Possibly useful mathematical facts:
Markov’s inequality: if X takes only non-negative values, for all a > 0 we have Pr(X ≥a)≤E[X]/a.
Chernoff bounds: using the notation of Problem 2, we have Pr(X ≥ (1 +δ)µ) ≤ e−µδ2/3 and Pr(X ≤(1−δ)µ)≤e−µδ2/2.
Poisson distribution: ifX ∼Poisson(µ), thenE[X] =µandPr(X =j) = e−µµj/j!.
2
