I need help Please help.

1. The input to this problem consists of a collection of software packages X1,....Xn. The solution partitions this set into two parts (U.V) indicating the subset U S {X1,...,x} of packages you choose to buy vs those in V not buy. Your goal is to choose (UV) in the way that minimizes your total cost. Pre-Condition: The input specifies all of the costs. Cost of Buying X : For each software package Xi, the input specifies the cost bi > 0 that you incur if you buy X, i.e. include it in U. Cost of Not Buying X;: Everything costs something. The input also specifies the cost a; > 0 that you incur if you do not buy Xy, i.e. include it in V. Cost of Buying X, and Not X;: Some of these packages rely on each other. For every pair (X,X;) of packages, the input specifies the cost w > 0 that you incur if you buy X, but not X, Note ww) and wg.) could be different non-zero values. Post-Condition: The total cost that you want to minimize is the following: Cost of (U,V): cost (UV) = Dicubi + Djeva; + Diev jev Algorithm: The algorithm for solving this problem is as follows. Given an instance for the software problem, the first step is to form a "similar" instance for the network flow problem (by adding nodes s and t). The algorithm then solves the network flow instance by finding its max flow and the min cut (UV). It is not a coincidence that I used the letter U in two roles. This min cut (UV) (after removing s and t) becomes our solution for the software problem, i.e. U is the set of software packages that should be bought. Example: Instead of describing an algorithm for this problem, your task will be to step though the algorithm on the following example. There will be four software packages, X1,..., X4- The non-zero costs will be as follows: bj = 10 and b2 = 3 to buy Xi and X2. a3 = 9 and a 4 = 5 to not buy X3 and X. The additional costs w(is) for buying Xbut not X, are: W(1,2) = 5, (3,1) = 4, w(3,2) = 4, W (4,1)= 7, W(4.2) = 3. and w(4,3) = 2. Input to Network Flow: The nodes in the graphetwork will be consists of special nodes s and t and the four nodes X1.....X1. Your task is to add directed edges to this graph and to provide each of these edges with a capacity Capacity of Cut (UV): Recall that a cut is a partition of the nodes of your network into two parts U and V, such that s is in U and t is in V. (Because U will become the set that you buy, you might want to think of s as something that you definitely buy and t as something that you definitely do not buy.) Hint: Try drawing various possible cuts on your network and recall the definition of the capacity of these cuts. Now add capacities to this network so that the capacity of the cut is always equal to the cost of buying software packages U and not buying V. a) Question - Cost of Buying X, and Not X;: For every pair (X, X;) of packages, explain how to add a directed edge with capacity ww) to your network so that the cut capacity cost of buying" X, but not X, is W(13) b) Question - Cost of Buying X : For each X, explain how to add a directed edge with ca- pacity b; to your network so that the cut capacity cost of "buying" X is bi. c) Question - Cost of Not Buying X;: Similarly explain how to add a; so that the cut ca- pacity cost of not "buying" X, is aj. d) Question - Cost of Buying U: Explain why the capacity of a cut in your constructed net- work will be cost(UV) = Lier bi+jev aj + Lieujer WMJ). e) Proof of Correctness: You are now asked to prove that our algorithm's (U-3, V-t) 50- lution for this software problem instance is optimal if and only if the minimal cut solution (UV) for this similar" network flow instance is optimal Hint: I am not sure if you will feel that this is too confusing to prove or too obvious to prove. My proof says biection and then proves the contra-positive, i.e. not A iff exits this iff exits that iff not B Note: To prove this software buying algorithm works, it is sufficient to prove this above statement (assuming of course that we already trust the max flow min cut algorithm to give us optimal solutions). Complete the Algorithm: Solve the problem for our example. f) Max Flow: Draw the max flow for this network and give its rate of flow. Give a one or two sentence explanation how you obtained this. g) Augmentation Graph: Draw the augmentation graph for this max flow, Give a one or two sentence explanation how you obtained this, h) Min Cut: Draw the min cut for this network (on top of the input network). Compute its capacity. How you know that this is optimal MINIMUM cut. Give a one or two sentence explanation for each of these three things i) Solution to Software Problem: Which software packages should you buy? Give a one or two sentence explanation how you obtained this. i) Cost of Buying Software: What things cost you and what is the total cost? Give a one or two sentence explanation how you obtained this. 2 1. The input to this problem consists of a collection of software packages X1,....Xn. The solution partitions this set into two parts (U.V) indicating the subset U S {X1,...,x} of packages you choose to buy vs those in V not buy. Your goal is to choose (UV) in the way that minimizes your total cost. Pre-Condition: The input specifies all of the costs. Cost of Buying X : For each software package Xi, the input specifies the cost bi > 0 that you incur if you buy X, i.e. include it in U. Cost of Not Buying X;: Everything costs something. The input also specifies the cost a; > 0 that you incur if you do not buy Xy, i.e. include it in V. Cost of Buying X, and Not X;: Some of these packages rely on each other. For every pair (X,X;) of packages, the input specifies the cost w > 0 that you incur if you buy X, but not X, Note ww) and wg.) could be different non-zero values. Post-Condition: The total cost that you want to minimize is the following: Cost of (U,V): cost (UV) = Dicubi + Djeva; + Diev jev Algorithm: The algorithm for solving this problem is as follows. Given an instance for the software problem, the first step is to form a "similar" instance for the network flow problem (by adding nodes s and t). The algorithm then solves the network flow instance by finding its max flow and the min cut (UV). It is not a coincidence that I used the letter U in two roles. This min cut (UV) (after removing s and t) becomes our solution for the software problem, i.e. U is the set of software packages that should be bought. Example: Instead of describing an algorithm for this problem, your task will be to step though the algorithm on the following example. There will be four software packages, X1,..., X4- The non-zero costs will be as follows: bj = 10 and b2 = 3 to buy Xi and X2. a3 = 9 and a 4 = 5 to not buy X3 and X. The additional costs w(is) for buying Xbut not X, are: W(1,2) = 5, (3,1) = 4, w(3,2) = 4, W (4,1)= 7, W(4.2) = 3. and w(4,3) = 2. Input to Network Flow: The nodes in the graphetwork will be consists of special nodes s and t and the four nodes X1.....X1. Your task is to add directed edges to this graph and to provide each of these edges with a capacity Capacity of Cut (UV): Recall that a cut is a partition of the nodes of your network into two parts U and V, such that s is in U and t is in V. (Because U will become the set that you buy, you might want to think of s as something that you definitely buy and t as something that you definitely do not buy.) Hint: Try drawing various possible cuts on your network and recall the definition of the capacity of these cuts. Now add capacities to this network so that the capacity of the cut is always equal to the cost of buying software packages U and not buying V. a) Question - Cost of Buying X, and Not X;: For every pair (X, X;) of packages, explain how to add a directed edge with capacity ww) to your network so that the cut capacity cost of buying" X, but not X, is W(13) b) Question - Cost of Buying X : For each X, explain how to add a directed edge with ca- pacity b; to your network so that the cut capacity cost of "buying" X is bi. c) Question - Cost of Not Buying X;: Similarly explain how to add a; so that the cut ca- pacity cost of not "buying" X, is aj. d) Question - Cost of Buying U: Explain why the capacity of a cut in your constructed net- work will be cost(UV) = Lier bi+jev aj + Lieujer WMJ). e) Proof of Correctness: You are now asked to prove that our algorithm's (U-3, V-t) 50- lution for this software problem instance is optimal if and only if the minimal cut solution (UV) for this similar" network flow instance is optimal Hint: I am not sure if you will feel that this is too confusing to prove or too obvious to prove. My proof says biection and then proves the contra-positive, i.e. not A iff exits this iff exits that iff not B Note: To prove this software buying algorithm works, it is sufficient to prove this above statement (assuming of course that we already trust the max flow min cut algorithm to give us optimal solutions). Complete the Algorithm: Solve the problem for our example. f) Max Flow: Draw the max flow for this network and give its rate of flow. Give a one or two sentence explanation how you obtained this. g) Augmentation Graph: Draw the augmentation graph for this max flow, Give a one or two sentence explanation how you obtained this, h) Min Cut: Draw the min cut for this network (on top of the input network). Compute its capacity. How you know that this is optimal MINIMUM cut. Give a one or two sentence explanation for each of these three things i) Solution to Software Problem: Which software packages should you buy? Give a one or two sentence explanation how you obtained this. i) Cost of Buying Software: What things cost you and what is the total cost? Give a one or two sentence explanation how you obtained this. 2