4-7 Monge arrays¶
An $m\times n$ array $A$ of real numbers is a Monge array if for all $i,j,k$, and $l$ such that $1\leq i <k \leq m$ and $i \leq j < l \leq n$, we have
$A[i,j]+A[k,l]\leq 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:
$$ \begin{array}{} 10 & 17 & 13 & 28 & 23\cr 17 & 22 & 16 & 29 & 23\cr 24 & 28 & 22 & 34 & 24\cr 11 & 13 & 6 & 17 & 7\cr 45 & 44 & 32 & 37 & 23\cr 36 & 33 & 19 & 21 & 6\cr 75 & 66 & 51 & 53 & 34\cr \end{array} $$
a. Prove that an array is Monge if and only if for all $i=1,2,\dots,m-1$ and $j=1,2,\dots,n-1$, we have
$$ A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+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).)
$$ \begin{array}{} 37 & 23 & 22 & 32\cr 21 & 6 & 7 & 10\cr 53 & 34 & 30 & 31\cr 32 & 13 & 9 & 6\cr 43 & 21 & 15 & 8\cr \end{array} $$
c. Let $f(i)$ be the index of the column containing the leftmost minimum elementof row $i$. Prove that $f(1)\leq f(2)\leq \cdots \leq f(m)$ for any $m\times n$ Monge array.
d. Here is a description of a divide-and-conquer algorithm that computes the left most minimum element in each row of an $m\times 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 for the running time of the algorithm in part (d). Show that its solution is $O(m+n\log m)$.
a¶
$$ \begin{aligned} \text{assume }A[i,j]+A[i+k,j+l]\leq A[i,j+l]+A[i+k,j]\cr A[i+k,j]+A[(i+1)+k,j+l] \leq A[i+k,j+l]+A[i+k+1,j]\cr \implies A[i,j]+A[i+k+1,j+l]\leq A[i,j+l]+A[i+k+1,j]\cr A[i,j+l]+A[i+k,j+l+1]\leq A[i,j+l+1]+A[i+k,j+1]\cr \implies A[i,j]+A[i+k,(j+1)+l]\leq A[i,j+l+1]+A[i+k,j]\cr \end{aligned} $$
b¶
$$ \begin{array}{} 37 & 23 & 22 & 32\cr 21 & 6 & (5) & 10\cr 53 & 34 & 30 & 31\cr 32 & 13 & 9 & 6\cr 43 & 21 & 15 & 8\cr \end{array} $$
c¶
$$ \begin{aligned} i \lt k\cr \text{since } A[i,f(i)] = \min(A[i,x]),A[k,f(k)] = \min(A[k,x])\cr A[i,f(i)] + A[k,f(k)] \leq A[i,f(k)] + A[k,f(i)]\cr \text{assume }f(i) \gt f(k)\cr \implies A[i,f(k)] + A[k,f(i)] \leq A[i,f(i)] + A[k,f(k)]\cr \implies A[i,f(k)] + A[k,f(i)] = A[i,f(i)] + A[k,f(k)]\cr A[i,f(i)] \leq A[i,f(k)]\cr A[k,f(k)] \leq A[k,(f(i))]\cr \implies A[i,f(i)] = A[i,f(k)]\cr \implies A[k,f(k)]= A[k,(f(i))]\cr \implies f(i)\leq f(k)\cr \text{Contradictory to assumption}\cr \implies f(i)\leq f(k)\cr \end{aligned} $$
d¶
since $f(2k) \leq f(2k+1)\leq f(2k+2)$
in each odd row, we only need to compare $f(2k+2)-f(2k)+1$ elements. totally need to deal with $O(m)+O(n)=O(m+n)$ over all odd rows.
e¶
$$ \begin{aligned} T(m,n) & = T(m/2,n)+O(m+n)\cr T(m,n) & = \sum_{i=0}^{\lg m}O(m/2^i+n)\cr & = O(n\lg m)+\sum_{i=1}^{\lg m}O(m/2^i)\cr & = O(n\lg m)+O(m)\cr & = O(m+n\lg m)\cr \end{aligned} $$