An m ? n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ? i

In other words, whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersections of the rows and the columns, the sum of the upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right elements. For example, the following array is Monge:

a. Prove that an array is Monge if and only if for all i = 1, 2, ?., m - 1 and j = 1, 2, ?, n - 1, we have

b. The following array is not Monge. Change one element in order to make it Monge. Use part (a).

?

c. Let f (i) be the index of the column containing the leftmost minimum element of row i. Prove that f (1) ? f (2) ? ? ? f (m) for any m ? n Monge array.

d. Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum element in each row of an m ? n Monge array A:?

Construct a submatrix A? of A consisting of the even-numbered rows of A. Recursively determine the leftmost minimum for each row of A?. Then compute the leftmost minimum in the odd-numbered rows of A.?

Explain how to compute the leftmost minimum in the odd-numbered rows of A. given that the leftmost minimum of the even-numbered rows is known) in O(m + n) time.

e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O(m + n log m).

Transcribed Image Text:

10 17 13 28 23 17 22 16 29 23 24 28 22 34 24 11 13 6 17 7 45 44 32 37 23 36 33 19 21 75 66 51 53 34