A set of \(n\) cities is to be connected via communication links. The cost to
construct a link between cities \(i\) and \(j\) is \(C_{i j}, i \neq j .\) Enough
links should be constructed so that for each pair of cities there is a path of
links that connects them. As a result, only \(n-1\) links need be constructed. A
minimal cost algorithm for solving this problem (known as the minimal spanning
tree problem) first constructs the cheapest of all the
(in) links. Then, at each additional stage it chooses the cheapest link that
connects a city without any links to one with links. That is, if the first
link is between cities 1 and 2, then the second link will either be between 1
and one of the links \(3, \ldots, n\) or between 2 and one of the links \(3,
\ldots, n .\) Suppose that all of the \(\left(\begin{array}{c}n \\\
2\end{array}\right)\) costs \(C_{i j}\) are independent exponential random
variables with mean \(1 .\) Find the expected cost of the preceding algorithm if
(a) \(n=3\),
(b) \(n=4\).