Processing math: 100%

Problem 4-6

Monge arrays

An m×n array A of real numbers is a Monge array if for all i, j, k, and l such that 1i<km and 1j<ln, 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 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:

1017132823172216292324282234241113617745443237233633192167566515334

a. Prove that an array is Monge if and only if for all i=1,2,,m1 and j=1,2,,n1, we have

A[i,j]+A[i+1,j+1]A[i,j+1]+A[i+1,j].

(Hint: For the “if” part, use inductions separately on rows and columns.)

First of all, the “only if” part of this statement is already implied by the definition of a Monge array. For the “if” part we will use induction to show that

A[i,j]+A[i+1,j+1]A[i,j+1]+A[i+1,j]A[i,j]+A[k,j+1]A[i,j+1]+A[k,j]

where i<k. The base case of k=i+1 is given. Next by assuming that this holds for k=1+n we must prove that it also holds for k+1=i+n1. Combining these two gives us:

A[i,j]+A[k,j+1]+A[k,j]+A[k+1,j+1]A[i,j+1]+A[k,j]+A[k,j+1]+A[k+1,j]A[i,j]+A[k+1,j+1]A[i,j+1]+A[k+1,j]

which proves the inductive step. Employing this exact same approach on the rows which shows that this statement is indeed a restatement of the definition of Monge arrays.

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

37232232216710533430313213964321158

Let’s call this array B. Part a tells us that in order for B to be Monge, the following must be true:

B[i,j]+B[i+1,j+1]B[i,j+1]+B[i+1,j]i=1,2,3,4j=1,2,3

(Where the bounds for i and j come from the size of the array). Since B is not Monge, it must be true that this does not hold in all cases.

i=1,j=1:B[1,1]+B[2,2]B[1,2]+B[2,1]=37+623+21=4344i=1,j=2:B[1,2]+B[2,3]B[1,3]+B[2,2]=23+722+6=3028i=1,j=3:B[1,3]+B[2,4]B[1,4]+B[2,3]=22+1032+7=3239i=2,j=1:B[2,1]+B[3,2]B[2,2]+B[3,1]=21+346+53=5559i=2,j=2:B[2,2]+B[3,3]B[2,3]+B[3,2]=6+307+34=3641i=2,j=3:B[2,3]+B[3,4]B[2,4]+B[3,3]=7+3110+30=3840i=3,j=1:B[3,1]+B[4,2]B[3,2]+B[4,1]=53+1334+32=6666i=3,j=2:B[3,2]+B[4,3]B[3,3]+B[4,2]=34+930+13=4343i=3,j=3:B[3,3]+B[4,4]B[3,4]+B[4,3]=30+631+9=3640i=4,j=1:B[4,1]+B[5,2]B[4,2]+B[5,1]=32+2113+43=5356i=4,j=2:B[4,2]+B[5,3]B[4,3]+B[5,2]=13+159+21=2830i=4,j=3:B[4,3]+B[5,4]B[4,4]+B[5,3]=9+86+15=1731

The case that does not hold is where i=1 and j=2, therefore we must change one of these terms so that this case holds. Reducing B[1,2] by 2 will invalidate the case where i=1 and j=1 so we cannot use this value. Reducing B[2,3] by 2 will not invalidate any cases. Thus by setting B[2,3]=5 this array becomes Monge.

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.

Suppose f(i)>f(i+1). Based on the definition of Monge arrays, this would mean that in dealing with rows i and i+1 and columns f(i) and f(i+1) the following must be true:

A[i,f(i+1)]+A[i+1,f(i)]A[i,f(i)]+A[i+1,f(i+1)]

however this contradicts the definition of the function f which states that A[i,f(i+1)]>A[i,f(i)] and A[i+1,f(i)]A[i+1,f(i+1)].

d. Here is a description of a divide-and-conquer algorithm that computes the left-most 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.

Based on the conclusion of part c we can restrict the elements which we need to examine. For each odd row k we need only consult the elements between f(k1) and f(k+1) where f(0)=1 and f(m)=f(m+1)=n.

The matrix has m/2 odd-numbered rows, and so finding the leftmost minimum of each of them takes

m/2k=1(f(k+1)f(k1)+1)=m/2m/2k=1(f(k+1)f(k1)=O(m)+f(m/2)f(1)=O(m+n)

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

T(n)=T(m/2)+O(m+n)=T(m/2)+am+bn=am+bn+am2+bn+am4+bn+=logm1i=0(am2i+bn)(ami=012i)+bnlogm=am(1112)+bnlogm=2am+bnlogm=O(m+nlogm)