# CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

## Homework #2 open thread

Ask yr HW2 questions here…

### 7 responses to “Homework #2 open thread”

1. Avrim Blum January 30, 2011 at 7:53 pm

In problem 1, it should have said “after every element has been compared to the pivot, place the pivot itself at random into one of the two buckets”. (The assignment on the webpage has been updated to reflect this change).

2. cmurandomized February 2, 2011 at 7:52 pm

For exercise 4(a), 1-n^2 doesn’t make sense since n is an integer. It should be 1-1/n^2. Thanks, Jamie!

3. Afshin Nikzad February 4, 2011 at 2:27 pm

In one of the problems, I need to prove a non-trivial inequality. We used the inequality in one of the lectures in class (without mentioning the proof). Do I need to prove the inequality in my homework?

4. cmurandomized February 4, 2011 at 6:18 pm

> For problem 1 in homework2, we have to prove that the algorithm yields a random
> permutation. I don’t really know the exact meaning of this. Do you want us to prove that
> the algorithm generates one of the n! possible permutations with equal probability 1/n! OR
> that the algorithm can produce any permutation of the n! possible (not necessarily each
> with equal probability)?

one of the n! possible permutations with equal probability 1/n!

5. cmurandomized February 4, 2011 at 6:19 pm

non-trivial inequality: if you can prove it, might as well prove it. ðŸ™‚

6. Tudor February 6, 2011 at 3:13 pm

Is problem 2a supposed to read “(1-1/k) fraction of the points?”

7. Tudor February 6, 2011 at 3:18 pm

nevermind about my last question