Hilltop University (HU) is building a new campus on one of the highest hills in its hometown.

The following table shows details about 6 key buildings under construction at the new site.

No. Name Coords x y Altitude 1 Administration 100 100 300 2 Library 52 55 210 3 Student Union 151 125 204 4 Engineering 50 208 150 5 Management 147 25 142 6 Residence Hall 210 202 100 HU wants to construct a minimum total length system of sidewalks that contains a path from every building to every other, taking into account both the distance between their sites and the steepness caused by changes in altitude. Specifically a link joining buildings i and j should be viewed as having weighted length.
dij !1Euclidean distance from i to j2 *
11 + Absolute difference of altitudes for i and j2

(a) Compute lengths dij defined above for all pairs of buildings i and j.

(b) Explain why an optimal sidewalk network for the new HU campus will be a minimum total weight spanning tree of the complete graph with nodes at the 6 buildings and edges of weight computed in part (a).

(c) Apply Greedy Algorithm 10F to compute such a minimum weight spanning tree, commenting on how subtrees are formed and merged as the algorithm proceeds, and on why some attractive edges were skipped.