5.3-6

5.3-6 Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.

PERMUTE-BY-SORTING(A)
1 n = A.length
2 let P[1..n] be a new array
3 for i = 1 to n
4 P[i] = RANDOM(1, $n^3$)+ i
5 sortA, using P as sort keys
I made simple change. I am adding i in step 4.I changed the original algorithm form P[i] = RANDOM(1, $n^3$) to P[i] = RANDOM(1, $n^3$)+i. Lets say we get all equal priorities. But i is distinct it would make each of priorities distinct.

Ex:
n = 3
i =1
Let RANDOM(1, 3^3) = 1
P[1] = RANDOM(1, $n^3$)+ 1
P[1] = 2;


i = 2
Let RANDOM(1, 3^3) = 1
P[1] = RANDOM(1, $n^3$)+ 2
P[1] = 3;


i = 3
Let RANDOM(1, 3^3) = 1
P[1] = RANDOM(1, $n^3$)+ 3
P[1] = 4;
It's a small change but it would create distinct priorities. This doesn't feel right. please check again.Still we can get same priorities when i = 1 and random returns 2 and i = 2 random returns 1.Rework is needed.

5.3-5

Prove that in the array P in procedure PERMUTE-BY-SORTING, the probability that all elements are unique is at least 1 - 1/n.

The algorithm is as below
PERMUTE-BY-SORTING(A)
1 n = A.length
2 letP(1...n) be a new array
3 for i = 1 to n
4 P [i] = $RANDOM(1, n^3)$
5 sortA, using P as sort keys
For P[] to unique lets go through one element at a time. For the first since no element is there in the Array P the probability is 1 bcoz it is the first element.The probability of picking the first element $1/n^3$ since every element has a fair chance in a set of $n^3$
For the second element we have to make sure we don't pick the first element again.
for example consider the tossing of a coin the probability of not getting a tail is 1 -(1/2)(probability of getting a head).
Similarly the probability of not getting the first element when we pick the first element is $1 - (1/n^3)$ (we might tempted in doing 1/n^3-1 but this is wrong since we are not selecting element from a smaller set of $1..n^3$ all elements will be there)
Similarly the probability of not getting the first and second element when we pick the third element is $1 - (1/n^3+1/n^3)$
Let us Indicator random variables $E_i$ be the event in which we pick unique prioroty for element i and E the indicator random variable for all elements of array p $$ P\{E\}=P\{E_1 \cap E_2 \cap .. \cap E_n\} = P\{E_2|E_1\} P\{E_1\} P\{E_3|E_2 \cap E_1\} P\{E_2 \cap E_1\} .... P\{E_n|E_n-1 \cap E_n-2... \cap E_1\} p\{E_n \cap E_n-1.... \cap E_1\}$$ $$ P\{E\} = 1 . 1 - (1/n^3) . 1 - (1/n^3+1/n^3) ... 1 - (n-1/n^3) $$
the last term has to be n - 1 because we would want substract the probability of not getting n-1 terms while picking the last element.
$$ P\{E\} = 1 . (n^3 - 1)/n^3 . (n^3 - 2)/n^3 ... (n^3 - n+1)/n^3 $$ $$ > 1 . (n^3 - n)/n^3 . (n^3 - n)/n^3 ... (n^3 - n)/n^3 $$ $$ > (1 - 1/n^2) . (1 - 1/n^2) . (1 - 1/n^2) ... (1 - 1/n^2) $$ even $1 > (1 - 1/n^2)$ $$ > (1 - 1/n^2)^n $$ The above equation look in the form of $(1+x)^n$ the binomial theorem has an expansion see Wikipedia or any other source. $$(1+x)^n ={n \choose 0} x^0 + {n \choose 1} x^1+{n \choose 2} x^2+....+{n \choose n} x^n$$ $$ (1 - 1/n^2)^n = 1 - 1/n+(n-1/2n^2)-(n-1/6n^2)+...$$ $$ > 1-1/n$$ even for odd and even powers of n

5.3-3

Suppose that instead of swapping element A[i] with a random element from the subarray A[i....n] , we swapped it with a random element from anywhere in the array:


PERMUTE-WITH-ALL(A)
1 n = A:length
2 for i = 1 to n
3 swap A[i] with A[1...n]
Does this code produce a uniform random permutation? Why or why not?


The above code will not produce uniform random permutation. The above for loop increments i but the call to random take 1 to n as arguments. So the probability for each no from 1 .. n is fair. This is just like tossing a coin twice where the probability is fair for H an T. The probability is 1/4 for each tossing since you can get (HT,TH,HH,TT) with 1/4 probability which $1/2^2$.
Ex: consider n = 3 A[0] = 1 ,A[2] = 2,A[3] = 3 then the possible no of permutations 3^3 from Random(1,2)(since it is called from PERMUTE-WITH-ALL(A) thrice).
permutations:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Similarly probability of picking a random number from n numbers n times is $1/n^n$. But for a uniform probability distribution according lemma 5.4 it should be $1/n!$ if PERMUTE-WITH-ALL did produce a uniform random permutation, then each permutation would occur 1/6 of the time. That would mean that each permutation would have to occur an integer number m times(bcoz 1/27 is not equal 1/6 so there might be an integer m), where m/27 = 1/6. No integer m satisfies this condition.

5.2–3

5.2–3 Use indicator random variables to compute the expected value of the sum of n dice. Let $X1,X2,X3,X4,X5,X6$ be the indicator variable that capture the no of 1,2,3,4,5,6 on a dice. Let X the indicator variable that denotes the sum when we throw the dice n times or throw n dice. Expected value is the Mean of the random variable so $$E[X] = 1 E[X1]+ 2 E[X2]+3E[X3]+4E[X4]+5 E[X5]+6 E[X6]$$ the above equation can be written as $$E[X] = \sum_{i = 1}^6 i E[Xi] $$ the no of 1 side in n dice throws $E[X1] = \sum_{i = 1}^n 1/6 $ $$E[X1] = 1/6(1+1+1....1) $$ sum of n 1's is n $$E[X1] = n/6 $$ $$E[X] = \sum_{i = 1}^6 i E[Xi] $$ $$E[X] = \sum_{i = 1}^6 i n/6 $$ $$E[X] = n/6 \sum_{i = 1}^6 i $$ $$E[X] = n/6 (1+2+3+4+5+6) $$ $$E[X] = 21n/6 $$

4.3-6

4.3-6 Show that the solution to T(n) = 2T(\lfloor (n/2) \rfloor + 17)+ n is O(n lg n). let $T(n) \leq c(n-34) lgn - n $ $$ T(n) = 2c(n/2 -34+17) lg(n/2+17) - 2n + n $$ $$ T(n) = c(n -34) lg(n/2+17) - n $$ $$ T(n) = c(n -34) lg(n/2+17) - n < c(n-34)lg n -n $$ the above eq is less than $ c(n-34)lg n -n $ becoz n/2+17 < n.

4.3-5

Show that $\theta(n lg n)$ is the solution to the “exact” recurrence (4.3) for merge sort.
equation 4.3 $$ T(n) = T(\lfloor (n/2) \rfloor)+ T(\lceil (n/2) \rceil)+ \theta(n) $$ Let $ T(n) \leq c n lg n $ $$ T(n) = c n/2 lg (n/2) + c n/2 lg(n/2) + n $$ $$ T(n) = c n lg (n/2) + n $$ $$ T(n) = c n lg (n/2) + n $$ $$ T(n) = c n lg n - c n + n $$ $$ T(n) = c n lg n -( c n - n )$$ the residual should be greater than zero $$cn - n \geq 0 $$ $$c \geq 1 $$ if we want prove the base case we can do T(2) and T(3) else we can add $c_2 n $ at the end of our assumption and prove for T(1)

4.3-4

Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T(n) for recurrence (4.19) without adjusting the boundary conditions for the inductive proof. $$ T(n) = 2 T( \lfloor n/2 \rfloor) + n $$ let $ T(n)\leq c_1 n lgn +c_2 n $ $$ T(n) \leq 2 c_1 n/2 lg(n/2) + 2 c_2 n/2 $$ $$ T(n) \leq c_1 n lg(n/2) + c_2 n $$ $$ T(n) \leq c_1 n lg n - c_1 n + c_2 n $$ $$ T(n) \leq c_1 n lg n - ( c_1 n - c_2 n ) $$ $$ c_1 n - c_2 n \geq 0 $$ $$ c_1 \geq c_2 $$ for base case $ T(1)\leq c_1 1 lg1 +c_2 1 $ $ T(1)\leq c_2 1 $ if $c_2$ is sufficiently large the above case is proved for base case as well.