A challenge that arises in databases is how to summarize data in easy-to-display formats, such as a histogram. A problem in this context is the minimal imbalance problem. The input consists of an array A containing n positive numbers and an integer k. Consider k indices j1,j2,...,jk that partition the array into k+1 subarrays A[1,j1], A[j1 +1,j2], ..., A[jk + 1, n]. The weight w(i) of the ith subarray is the sum of its entries. The imbalance of the partition is .

That is, the imbalance is the maximum deviation of any partition from the average size.

a) Give an algorithm for determining the partition with minimal imbalance given A, n and k. (This basically corresponds to finding a histogram with k + 1 bars as close to equal as possible.)

b) Explain how your algorithm would change if the imbalance was redefined to be

max w(i)--4 k +1 max w(i)--4 k +1