CLRS Chapter 5

5.1-1:
  consider all the possible situations, if we can determine which candidate is best, then we can also compare the relation of all pairs of candidates.

5.1-2:
  a+random(0,1)*(b-a)

5.1-3:
  run the procedure BIASED-RANDOM twice, if the answer is 0 and 1, then return 0, if the answer is 1 and 0, then return 1; otherwise, continue this procedure.
 
5.2-1:
  hiring only once means that the first candidate is the best of all the candidates. so the probability is $\frac{1}{n}$. hiring n times means that the candidates' sequence is ordered, so the probability is $\frac{1}{n!}$

5.2-2:
  hiring twice means that we only hire the best candidate and the second best candidate. Besides, the second candidate must be in the first position, and the best candidate can appear at any of the other n-1 positions. so the probability is $\frac{1}[{n}$

5.2-3:
  for one dice, the expected value is $E[X]=\frac{1}{6}*(1+2+3+4+5+6)=\frac{7}{2}$, so for the sum of n dice, the expected value is $E[X_n]=nE[X]=\frac{7n}{2}$

5.2-4:
  we consider the rv. X, which represent that whether one person can get his own hat, for the rv. X, we have $P(X=1)=\frac{1}{n}$ and $P(X=0)=\frac{n-1}{n}$, so the expected value of X is $\frac{1}{n}$. Now if we assume that the number of customers who get their own hats is rv. Y, it comes to that:
                $$Y=X_1+X_2+...+X_n$$
so $E[Y]=E[X_1]+E[X_2]+...+E[X_n]=nE[X]=1$

5.2-5:
  we define such a rv. $X_{ij}(i<j)$, which refers to whether the ith element is larger than the jth element. we can easily get $E[X_{ij}]=\frac{1}{2}$. for the total number of inversions X, we have following formula:
$$E[X]=\sum_{i=1}^n\sum_{j=i+1}^nE[X_{ij}]=\frac{n(n-1)}{4}$$

5.3-1:
  n=length(A)
  A[1]=A[random(1,n)]
  for i=2 to n
    A[i]=A[random(i,n)]

5.3-2:
  no, can not get the original array

5.3-3:
 no, the result may not be an permutation.

5.3-4:
  we can image the array B as an circle, so for the element A[i], it has an probability $\frac{1}{n}$ to put it in any position of B. Besides, because we may put all elements of A to the same position of B, so the result array B is not uniform random.

5.3-5:
  we assume S(i) as the probability that the ith element is unique, so $S(i)=\frac{n^3-(i-1)}{n^3}=1-\frac{i-1}{n^3}$
so the target probability equals to $S(1)*S(2)*...*S(n)$. By utilizing the inequality
$$(1-a)(1-b)>1-a-b$$
we achieve the answer!

$\textbf{5.3-6}$

$\textbf{5.3-7:}$