A network is a set of servers and a set of wires. Throughout the exercise, we...

  

Transcribed Image Text:

A network is a set of servers and a set of wires. Throughout the exercise, we let S denote the number of servers and W the number of wires. Each server is identified by a unique integer in the range [0,S-1]. Each wire is a pair (x, y) of distinct servers and we say that x and y are wired. If x and y are wired then y and x are also wired. A link between two servers z and z, is a sequence of servers z,...,z, such that z; and 2+1 are wired for i = 1,...,j-1. For example the sets {0,1,2,3,4,5} and {(0, 1), (0,3), (0, 4), (1, 2), (2, 3), (2, 4), (3, 5), (4,5)} is a network with 6 servers and 8 wires. The sequence 2, 3,0 is a link between server 2 and server 0. 3.1 (2%) Describe how to model a network as a graph Solution: 3.4 (18%) The group of hackers now find a way to efficiently hack wires. If a wire (x, y) is hacked the wire disappears from the network, but the servers x and y at the endpoints are unaffected. We want to invest in protection for some of the wires such that even if the unprotected wires are hacked the network remains linked. We associate to each wire (x, y) a protection cost, denoted p(x, y), that indicates the cost of protecting the wire from hacking. A minimal wire set is a subset of wires X such that the network is linked and the sum of the protection cost of the wires in X is minimal. Give an algorithm that computes a minimal wire set given a network. Argue correctness of your algorithm. Analyze the running time of your algorithm in the relevant parameters of the problem. Solution: A network is a set of servers and a set of wires. Throughout the exercise, we let S denote the number of servers and W the number of wires. Each server is identified by a unique integer in the range [0,S-1]. Each wire is a pair (x, y) of distinct servers and we say that x and y are wired. If x and y are wired then y and x are also wired. A link between two servers z and z, is a sequence of servers z,...,z, such that z; and 2+1 are wired for i = 1,...,j-1. For example the sets {0,1,2,3,4,5} and {(0, 1), (0,3), (0, 4), (1, 2), (2, 3), (2, 4), (3, 5), (4,5)} is a network with 6 servers and 8 wires. The sequence 2, 3,0 is a link between server 2 and server 0. 3.1 (2%) Describe how to model a network as a graph Solution: 3.4 (18%) The group of hackers now find a way to efficiently hack wires. If a wire (x, y) is hacked the wire disappears from the network, but the servers x and y at the endpoints are unaffected. We want to invest in protection for some of the wires such that even if the unprotected wires are hacked the network remains linked. We associate to each wire (x, y) a protection cost, denoted p(x, y), that indicates the cost of protecting the wire from hacking. A minimal wire set is a subset of wires X such that the network is linked and the sum of the protection cost of the wires in X is minimal. Give an algorithm that computes a minimal wire set given a network. Argue correctness of your algorithm. Analyze the running time of your algorithm in the relevant parameters of the problem. Solution: