We model Northeastern's network routers using an undirected graph G = (V, E) where the vertices are the routers and the edges are the potential connections to be installed between the routers. Some potential connections are underground while some potential connections are above ground. We would like to connect the routers so that data can be sent from any router to any other router using as few connections as possible. However, there are disagreements in the team. Alice would like to build the network using as few underground connections as possible whereas Bob would like to use as many underground connections as possible. (a) Give an algorithm to find the network Alice wants. For full credit, your algorithm should run in 0(m +n) time or O((m +n)logn) time. Solution: (b) Give an algorithm to find the network Bob wants. For full credit, you can either give an algorithm with O(m + n) or O((m+n)log n) time, or describe how to use the algorithm in part (a) to solve this part. Solution: (c) Suppose that Alice's solution T has a underground connections while Bob's solution T has b underground connections. To mediate the team, Charlie picks a number x in between (a x b) and would like to get a solution with exactly x underground connections. Give an algorithm to find the network Charlie wants starting from Alice's and Bob's solutions and its running time. Hint: start from T and try to increase the number of underground connections by swapping in underground connections in T\T for appropriate connections in T T (just a reminder, the set A\ B consists of all elements in A but not in B) Solution: