Dynamic programming question.

4. (20 pts) You and your friend Bryan decide to split the task of implementing mergesort on a given array A[1, ..., n). Big mistake! Unfortunately, Bryan hasn't taken CS 381, and so implements the merge part to be horribly inefficient. Bryan has already submitted his code, so you have no choice but to use his merge function to compute the sorted array. His implemented algorithm takes in 4 parameters: Merge(A, i, j, k): merges (sorted) subarrays (A;...Aj-1] and [Aj...Ak). Using some of the cool techniques learned in class, you analyze his algorithm and find the run time to be: Tmerge (A, i, j, k) = time( A, i, j - 1) + time(A, j, k), where time(A, p, q) = (sum of elements Ap...Ag) (number of elements Ap...Ag) (max element of Ap...Ag) (a) Describe and analyze a preprocessing algorithm which takes input array A, and precomputes values so that Tmerge(A, i, j, k) can be calculated in constant time for any i, j, k. (b) Using your preprocessing from part (a), describe and analyze an efficient DP algorithm which re- turns the minimum cost of merge-sorting the array A[1..n) using Bryan's merge function. Explicitly argue optimal substructure, define subproblems, state recurrences and analyze extra space and run- time. Hint: Input arrays to the merge algorithm must be sorted themselves, and the output is a sorted array. (c) Describe and analyze an algorithm to return the pairs of subarrays that were merged in (b). You must return all the triples (i, j, k), indicating subarrays (Ai... Aj-1] and [Aj...Ak] were merged. 4. (20 pts) You and your friend Bryan decide to split the task of implementing mergesort on a given array A[1, ..., n). Big mistake! Unfortunately, Bryan hasn't taken CS 381, and so implements the merge part to be horribly inefficient. Bryan has already submitted his code, so you have no choice but to use his merge function to compute the sorted array. His implemented algorithm takes in 4 parameters: Merge(A, i, j, k): merges (sorted) subarrays (A;...Aj-1] and [Aj...Ak). Using some of the cool techniques learned in class, you analyze his algorithm and find the run time to be: Tmerge (A, i, j, k) = time( A, i, j - 1) + time(A, j, k), where time(A, p, q) = (sum of elements Ap...Ag) (number of elements Ap...Ag) (max element of Ap...Ag) (a) Describe and analyze a preprocessing algorithm which takes input array A, and precomputes values so that Tmerge(A, i, j, k) can be calculated in constant time for any i, j, k. (b) Using your preprocessing from part (a), describe and analyze an efficient DP algorithm which re- turns the minimum cost of merge-sorting the array A[1..n) using Bryan's merge function. Explicitly argue optimal substructure, define subproblems, state recurrences and analyze extra space and run- time. Hint: Input arrays to the merge algorithm must be sorted themselves, and the output is a sorted array. (c) Describe and analyze an algorithm to return the pairs of subarrays that were merged in (b). You must return all the triples (i, j, k), indicating subarrays (Ai... Aj-1] and [Aj...Ak] were merged