Monge arrays
An m n array A of real numbers is a Monge array if for all i , j , k, and l such that 1 i < k m and 1 j < l n, we have
AOEi; j C AOEk; l AOEi; l C AOEk; j :
In other words, whenever we pick two rows and two columns of aMonge 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:
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 6
75 66 51 53 34
a. Prove that an array is Monge if and only if for all i D 1; 2; :::;m 1 and j D 1; 2; :::; n 1, we have
AOEi; j C AOEi C 1; j C 1 AOEi; j C 1 C AOEi C 1; j :
(Hint: For the "if" part, use induction separately on rows and columns.)
b. The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part (a).)
37 23 22 32
21 6 7 10
53 34 30 31
32 13 9 6
43 21 15 8
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 A0 of A consisting of the even-numbered rows of A.
Recursively determine the leftmost minimum for each row of A0. 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 C n/ time.
e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O.m C n log m/.