2. Balancing Weights. (25) You have n> 1 positive integer weights, W1,..., Wn. The goal is to find a subset of indices A C{1,...,n} so that the difference Lica Wi Liga w;is minimized and to return this difference. (Treat an empty sum as 0.) For example, if n = 4 and (W1, W2, W3, w4) = (1,3,2,4), then A = {1,4} minimizes the aforementioned difference and 0 should be returned. (a) The nave algorithm is given by: "try all possible subsets for A: for each such set, compute the sums, compute the difference, and update the best choice of A if need be". Express the complexity of the nave algorithm with big- notation. (b) Provide a bottom-up solution to this problem using dynamic programming. Aim for a total running time of O(nW), where W = {1-1 W; is the sum of the weights. Hint: This problem is similar to the 0-1 knapsack problem. (c) Modify your algorithm from the previous part to return a set of indices A that minimizes the difference. Your algorithm should continue to run in time O(nW). (d) In what case would you expect the nave algorithm to run faster than the DP algorithm from the previous part? List at least 1 case in which this could happen, assuming that you run both algorithms on the same machine. 2. Balancing Weights. (25) You have n> 1 positive integer weights, W1,..., Wn. The goal is to find a subset of indices A C{1,...,n} so that the difference Lica Wi Liga w;is minimized and to return this difference. (Treat an empty sum as 0.) For example, if n = 4 and (W1, W2, W3, w4) = (1,3,2,4), then A = {1,4} minimizes the aforementioned difference and 0 should be returned. (a) The nave algorithm is given by: "try all possible subsets for A: for each such set, compute the sums, compute the difference, and update the best choice of A if need be". Express the complexity of the nave algorithm with big- notation. (b) Provide a bottom-up solution to this problem using dynamic programming. Aim for a total running time of O(nW), where W = {1-1 W; is the sum of the weights. Hint: This problem is similar to the 0-1 knapsack problem. (c) Modify your algorithm from the previous part to return a set of indices A that minimizes the difference. Your algorithm should continue to run in time O(nW). (d) In what case would you expect the nave algorithm to run faster than the DP algorithm from the previous part? List at least 1 case in which this could happen, assuming that you run both algorithms on the same machine