Randomized Algorithms, Carnegie Mellon: Spring 2011
Ask yr HW2 questions here…
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