CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

HW #4 Open Thread

Please ask your HW#4 questions here. Here’s one:

For Exercise 2, Part A, the algorithm says to “Choose 2m+1 elements S uniformly at random…”. Does this mean with replacement, or without replacement? In other words, are we choosing 2m+1 elements one at a time, each with equal probability of picking any of the elements from A, such that S might be a multiset? Or, are we choosing a set of 2m+1 elements from A, where each set has probability 1 / binom(n, 2m+1) of being picked?

It does not matter; you can do it either way. Though the analysis for the process where you choose independently with replacement is slightly simpler.

Update: the phrasing for problem #2(b) was ambiguous, and has been fixed. (Thanks Kevin!)

Update #2: the indices in the algorithm in problem #2 were off by 1 and have been fixed. (Thanks Favonia!)

4 responses to “HW #4 Open Thread

  1. L March 9, 2011 at 7:05 pm

    Can we assume that epsilon in problem 2 (a) is <=1/4, not only that epsilon <=1/2?

  2. cmurandomized March 9, 2011 at 8:18 pm

    Sure. And showing that $O(1/epsilon^2 log 1/delta)$ instead of just $1/epsilon^2 log 1/delta$ is fine too.

  3. L March 14, 2011 at 1:03 pm

    For exercise 2 (b), we have to give an algorithm for finding an element K with rank in k+-epsilon*n. Do we also have to prove that Prob[rank(K) is in k+-epsilon*n]>=1-delta? Or do we just give the algorithm and say that the calculations to prove Prob[rank(K) is in k+-epsilon*n]>=1-delta are very similar to point (a)?

  4. cmurandomized March 14, 2011 at 6:39 pm

    You could do the latter, and just indicate where the analysis differs from that for (a). Or, you could even give a black-box reduction from the problem in (b) to that in (a).

%d bloggers like this: