# CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

## Homework #2 open thread

January 26, 2011

Posted by on Ask yr HW2 questions here…

Advertisements

Randomized Algorithms, Carnegie Mellon: Spring 2011

January 26, 2011

Posted by on Ask yr HW2 questions here…

Advertisements

%d bloggers like this:

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

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!

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?

> 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!

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

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

nevermind about my last question