### **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.)

Course Home Page

cole@cs.nyu.edu (Richard Cole)

Last modified: Feb 18, 1997