An m × n array A of real numbers is a Monge array if for all i, j, k, l such tha

Question

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

A[i, j] + A[k, l] A[i, l] + A[k, j].

That is, the four elements at the intersections of any two given rows and two given columns of a Monge array satisfies the following property: 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.

1, Property of Monge Array

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

f(1) f(2) · · · f(m).

2. Divide-and-Conquer Method

Below is a divide-and-conquer algorithm that computes the left-most minimum element in each row of an m × n Monge array A:

S1. Construct a sub-matrix A0 of A consisting of the even-numbered rows of A.

S2. Recursively determine the leftmost minimum for each row of A0 .

S3. Compute the leftmost minimum in the odd-numbered rows of A.

Explain how Step S3 to compute the leftmost minimum in the odd-numbered rows of A can be done in O(m + n) time, given that the leftmost minimum element of the even numbered rows is known.

Explanation / Answer

ANS 1 (Proof BY Contradiction)Let us assume that for some m × n Monge array, there exists some row i such that f(i) is not less than f(i+ 1). Let j = f(i+ 1), and k = f(i). Since f(i) is the index of the minimum value of row i, and f(i+ 1) is the index of the minimum value of row i + 1, there can be no pair of values in rows i, i + 1 whose sum is less than or equal to Ai+1,j +Ai,k. But due to the definition of Monge, we know Ai,j +Ai+1,k+1 Ai+1,j +Ai,k. Therefore there cannot be a Monge array such that f(i) > f(i + 1).

ANS 2 We know from ANS1(above) that the leftmost minimum of row i is less than or equal to the leftmost minimum of i + 1. We also know the leftmost minimum of the even rows. Given f(2), we find f(1) as follows: begin with column f(2), and scan leftwards in row 1 until we find its minimum. Similarly, for row 3, we scan leftwards until we reach index f(1). We must scan all n columns, and at worst we must scan all m rows. Thus this algorithm takes O(n + m) time.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.