# A set of n cities is to be connected via communication links. The cost to construct a link…

A set of n cities is to be connected via communication links. The cost to construct a link between cities i and j is Cij , i ?= 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 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, . . . , n or between 2 and one of the links 3, . . . , n. Suppose that all of the costs Cij are independent exponential random variables with mean 1. Find the expected cost of the preceding algorithm if

(a) n = 3,

(b) n = 4.