You are given an array of integers named arr. Split arr into two subsets that produce...

Transcribed Image Text:

You are given an array of integers named arr. Split arr into two subsets that produce the minimum absolute value of the difference between the total sum between the subsets. Hint: instead solve the following problem: does some subset of the elements of arr sum to sum(arr). Then, use the resulting table to solve the original problem. Example: Input: arr = [10, 7, 2, 7, 1] Output: 1 because subsets [7, 7] and [10, 2, 1] produce the minimum absolute difference: (7 +7)-(10+2 + 1) = 1 a.) (6 points) Define the entries of your table in words. E.g. T(i) or T(i, j) is ... b.) (12 Points) State the recurrence for entries of your table in terms of smaller subproblems. Briefly explain in words why it is correct. Don't forget the base cases here. c.) (6 points) Use your recurrence relationship to write pseudocode for your algorithm. d.) (10 Points) Determine the running time of your algorithm. Briefly provide justification. You are given an array of integers named arr. Split arr into two subsets that produce the minimum absolute value of the difference between the total sum between the subsets. Hint: instead solve the following problem: does some subset of the elements of arr sum to sum(arr). Then, use the resulting table to solve the original problem. Example: Input: arr = [10, 7, 2, 7, 1] Output: 1 because subsets [7, 7] and [10, 2, 1] produce the minimum absolute difference: (7 +7)-(10+2 + 1) = 1 a.) (6 points) Define the entries of your table in words. E.g. T(i) or T(i, j) is ... b.) (12 Points) State the recurrence for entries of your table in terms of smaller subproblems. Briefly explain in words why it is correct. Don't forget the base cases here. c.) (6 points) Use your recurrence relationship to write pseudocode for your algorithm. d.) (10 Points) Determine the running time of your algorithm. Briefly provide justification.

Answer rating: 100% (QA)

Answer Basically this is a standard problem of dynamic programming It can be sol... View the full answer