a. Suppose that each leaf of TA is labeled with the probability that it is reached given a random input. Prove that exactly n! Leaves are labeled 1/n! And that the rest are labeled 0.
b. Let D(T) denote the external path length of a decision tree T ; that is, D(T) is the sum of the depths of all the leaves of T. Let T be a decision tree with k > 1 leaves, and let LT and RT be the left and right sub trees of T. Show that D(T) = D(LT) + D(RT) + k.
f. Show that for any randomized comparison sort B, there exists a deterministic comparison sort A that makes no more comparisons on the average than B does.