The linear partition problem (LP1) is defined as follows: Given a sequence Sof n positive integers (s1, s2, . . . , sn) and an integer k, partition S into k ranges so as to minimize the maximum sum over all ranges. Note that "minimizing the maximum sum" is one way to quantify fairness. It minimizes the most work that anyone has to do. Another way to quantify fairness given the same input instead maximizes the minimum sum over all ranges. Call this version of the problem LP2. For an input sequence (1 2 4) with k= 2, an optimal solution to LP2 would place a divider between 2 and 4 giving a fairness index of min(1+2,4) = 3. This is superior to placing the divider between 1 and 2 resulting in a fairness index of min(1,2+4) = 1. a. Prove that the two definitions are equivalent when k= 2; i. e., given (s1, s2, . . . , sn), show that an optimal solution to both LP1 and LP2 will partition the sequence in exactly the same location.

b. Using a small example, show that, in general, the two problems are not equivalent; i. e., a partition corresponding to an optimal solution under one definition is not an optimal partition under the other definition.

c. What is the size of the solution space of the linear partition problem? This should be a formula in terms of n and k that counts the number of distinct ways to partition S into k ranges.

d. Provide the recurrence relation (including base cases) for LP2.

e. Implement a recursive algorithm for LP2 in code based on your recurrence relation above. Suggested languages include Python or C++.

f. Implement a dynamic programming algorithm in code (that uses a table to avoid recomputation) to compute the optimal fairness index for LP2.

g. Implement a traceback step in code that identifies the locations of the dividers in an optimal solution to LP2.

h. Demonstrate that your code works correctly by showing its results on the following instance. S= (10 6 7 3 8 5 7 9 11 7 15 10 12 6 19 7 3 12 14 6); k= 4.