### Homework 5, Randomized Algorithms

Due date: March 25.

All references are to the course text.

Page 99, Exercise 4.8.
Hint. Let q(n) be the number of repetitions of the algorithm. For x not in L, what is the probability that the algorithm obtains at least q(n)/2 "yes" responses on q(n) independent trials of the algorithm on input x? Similarly, for x in L, what is the probability of fewer than q(n)/2 "yes" responses?

Page 99, problem 4.14.
Hint. Consider the recursion tree. Call a node v good if its children each have at most 3/4 of the items at node v (i.e. the partitioning at v is in the ratio 1/4 to 3/4 or better). What is the probability that a node is good? Next, consider an arbitrary root to leaf path in the recursion tree. Choose a constant c so that the probability that the path has length more than c log n is at most 1/n^{k+1}, where k is a given constant. Conclude that the algorithm performs at most c n log n comparisons with probability 1 - 1/n^k.

Page 100, problem 4.15.

Page 99, problem 4.11.
Hint: Show that for the ith row of A, ai, |ai(p-q)| > max{sqrt(4 ln n |ai.p|), {sqrt(4 ln n |ai.(1-p))}, where 1 in 1-p denotes the all ones vector, with small probability (at most 2/n^2). (ai denotes a vector.)

cole@cs.nyu.edu (Richard Cole)