Question

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

>A[i,j]+a[k,l]≤A[i,l]+A[k,j]>

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 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>24>11>45>36>7517222813443366131622632195128293417372153232324723634>>

Prove that an array is Monge if and only

An m x n array A of real numbers is a Monge array if for all i, j, k, and I such that lsi 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 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 13 6 17 7> 45 44 32 37 23 36 33 19 21 6 75 66 51 53 34> 1. Prove that an array is Monge if and only i for all i-1,2,....m- 1, and - 1,2, , n - 1 we have (Hint: For the "if" part, use induction seperately on rows and columns) 1. 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 710 53 34 30 31 32 13 96 43 21 15 8 1. Let f(i) be the index of the column containing the leftmost minimum element of the row i. Prove that f(l) 3f(2) ...f(m) for any m xn Monge array 2. Here is a description of a divide-and conquer algorithm that computes the leftmost minimum element in each row of an m X 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 in 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. 1. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O(m + n log m).

Answer 1

AnsweGiven Nonge anay 0713 a8 3 69 3 31 | 2.3 36 | 33 | 13, 7S1 66SS3 * ps" ove that an anty vろMonge iff for all assume that array Ais monge se siniply sel ve have as desired Now we psove that, it' potǐ-ete niat, wsume that e want to ppove that the asag is nonge first we do inducrion on the nows, that i will prove that for any 0 For the base Case cguahon

Fes the fnductive Caie, ak utu e that equationの s true for sonne We rua vel Asimilas unient Cin du ction on the Colem Therefore indeed, Monge iven aray $3 3 303) 213 96 ange one eleueufto ruake t monge S3 3y 303/ 3 2 126 43

Change 13 to la in cider make frasmenge ヴ1 Proof : A unit by Ctnti adiction that tfu JA, tint ' u e. Than let t be the nnallest Valua ·fen Then Fek and ala ured by he nmonge n Contradiction of the iongepy F'U, FlCi):F(i) , [m]ユ1] nla7. in which Then FC-FTia7

to be Ts Column inde For the unning tinie, note that tre Outer loop 、ㅅ executed O (n) tinu Cone toi eacP Odd i,and a fotal of at most an auay Over the entive Sun of the alooithns k Let T Conn) be the uniugfinme ot the aig For some Cons fant C0 and n and an addition al tern 0