We model Northeastern's network routers using an undirected graph G = (V, E) where the vertices...

Transcribed Image Text:

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: 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:

Answer rating: 100% (QA)

With a small tweak you may apply Kruskals algorithm to identify the network that Alice wants which r... View the full answer