Chapter 8, Problem 1P

(a)

Program Plan Intro

To prove that exactly $n!$ leaves are labeled $1/n!$ and that the rest are labeled 0.

Explanation of Solution

The input array has distinct elements and each element is equally likely so the distribution is uniformly supported on the array.

As the array has n elements then the probability of each element occurs as $1/n!$ and the corresponding to different leaf as the program needs to be distinguishes between all the elements.

Since, there are distinct n elements so thepermutation of the leaf nodes is exactly $n!$ .

(b)

Program Plan Intro

To shows $D(T)=D(LT)+D(RT)+k$ where $D(T)$ is the external path length of tree T .

Explanation of Solution

Suppose the tree T then the depth of particular elements of LT is one less than the depth of the tree so the $D(T)$ of the tree is defined as follows:

  $\begin{array}{c}D(T)={\displaystyle \sum _{l\in L(T)}DT(l)}.\\ \\ {\displaystyle \sum _{l\in L(T)}DT(l)}={\displaystyle \sum _{l\in L(T)}DT(l)}+{\displaystyle \sum _{l\in R(T)}DT(l).}\\ \\ D(T)={\displaystyle \sum _{l\in L(LT)}(DTL(l)+1)}+{\displaystyle \sum _{l\in L(RT)}(DTR(l)+1)}.\\ \\ D(T)={\displaystyle \sum _{l\in L(LT)}DTL(l)}+{\displaystyle \sum _{l\in L(RT)}DRT(l)+k.}\\ \\ D(T)=D(LT)+D(RT)+k.\end{array}$

Since the minimum length of the left leaf and the minimum length of the right leaf are equals to the length of the tree there is another variable k which defines the constant increasing in the path defined in the minimum path of the length.

Therefore, $D(T)=D(LT)+D(RT)+k.$

(c)

Program Plan Intro

To show that $d(k)=\min \{d(i)+d(k-i)+k\}$ where $d(k)$ is the minimum value of $D(T)$ overall decision tree T.

Explanation of Solution

Suppose a tree T having leaves node k, LT and RT be minimum length path of left and right leaves then the equation of the tree is defined as follows:

  $D(T)=d(k).$

Suppose the minimum path length equation of the tree as follows:

  $D(T)=D(LT)+D(RT)+k.$

Now, suppose the LT have $i0$ number of leaves then combining the both above equations it get the following:

  $d(k)=d(i)+d(k-i)+k.$

For the minimum external path length the value of the equation is consider as minimum value of the i value of the $d(k)$ so the equation will as follows:

  $d(k)=\min \{d(i)+d(k-i)+k\}.$

(d)

Program Plan Intro

To show that the function $i\lg i+(k-i)\lg (k-i)$ is minimum at $i=k/2$ for a given value of $k>1$ and $1\le i\le k-1$ .

Explanation of Solution

Suppose i is a continuous variable and it finds the critical points using derivatives of the tree equation $d(k)=\min \{d(i)+d(k-i)+k\}$ now the taking the general term of the tree the equation will be $d(k)=d(i)+d(k-i)+k$ .

Suppose it picks the two sub-trees of approx. equal sizes then the depth of the tree is equals to $\lg k$ contributing each level k therefore the total external path length is at least $k\lg k$ .

Suppose the tree equation $d(k)=d(i)+d(k-i)+k$ .

Taking the log on both sides with derivate of the equation.

  $\frac{1}{\ln (2)}+\lg (i)+\frac{1}{\ln (2)}-\lg (k-1)=\frac{2}{\ln (2)}+\lg \frac{i}{(k-i)}.$

Putting the value $\frac{i}{k-i}=0$ .

  $\frac{i}{k-i}=2^{-\frac{2}{\ln (2)}}=2e^{-\lg (e^2)}=e^{-2}.$

As $(1+e^{-2})i=k$ .

  $\therefore i=\frac{k}{1+e^{-2}}$ .

Therefore, the equation $i\lg i+(k-i)\lg (k-i)$ is minimum if $k=k/2$ .

(e)

Program Plan Intro

To show that $D(TA)=\Omega (n!\lg (n!))$ and computes the average-case time to sort n -elements is $\Omega (n\lg n)$ .

Explanation of Solution

Suppose that a tree with k leaves needs to have external length $k\lg k$ and that a sorting tree needs at least $n!$ tree, a sorting tree must have external tree of length at least $n!\lg (n!)$ .

The average-case is the situation in which the algorithm computes the execution and given the result in moderate time and moderate conditions.

Since the average-case run time is the depth of a leaf weighted by the probability of that leaf being the one that occurs.

Therefore, the running time is $n!\lg (n!)/n!=\lg (n!)\in \Omega (n\lg n)$ .

(f)

Program Plan Intro

To show that for any randomized comparison sort B , there is a deterministic comparison sort A whose expected number of comparisons is no more than those made by B .

Explanation of Solution

The expected running time is the average over all possible results from the random bits. The equation of the tree is defined as follows: $n!\lg (n!)/n!=\lg (n!)$ .

The comparisons sort of B has the randomness that has higher value than the deterministic comparisons of A. The random sorting algorithm uses the partition of the array and uses the random sorting values for the dividing the array.

The possible fixing of the randomness resulted in a higher runtime, the average would have to be higher than the other so comparisons sort of B has higher value.