New answers tagged randomized-algorithms
3
You already proved in First part that using random assignments to the values it solves $\frac{m}{2}$ equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability $\frac{1}{2}$ on every random assignment. So we can use the following algorithm to solve this problem:
E = Unsolved equations (...
4
Yes. Your algorithm can return all permutations.
You can prove it by fixing any arbitrary permutation $\pi$ of the input string str and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of str can match the last $i$ characters of $\pi$.
For $i=0$ this is trivial.
For $i>0$: Let $n$ be the lenght of str, $...
1
It is $2/N$ : the probability of picking the smallest or the biggest as pivot.
If you choose one of them, they will be compared.
If you choose any other, then the smallest and the biggest elements will be put in different partitions, and thus will not be compared.
Top 50 recent answers are included
