Problem 4.6
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 \le i < k \le m$ and $1 \le j < l \le n$, we have
$$ A[i, j] + a[k, l] \le 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:
$$ \begin{matrix} 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 \end{matrix} $$
Prove that an array is Monge if and only i for all $i = 1,2,\ldots, m-1$, and $j = 1,2,\ldots,n-1$ we have $$ A[i,j] + A[i+1,j+1] \le A[i,j+1] + A[i+1,j] $$ (Hint: For the "if" part, use induction seperately on rows and columns)
The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part (a).) $$ \begin{matrix} 37 & 23 & 22 & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \\ \end{matrix} $$
Let $f(i)$ be the index of the column containing the leftmost minimum element of the row $i$. Prove that $f(1) \le f(2) \le \dots f(m)$ for any $m \times n$ Monge array.
Here is a description of a divide-and-conquer algorithm that computes the leftmost 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 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.
- Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is $O(m + n\log{m})$.
Part one
The "only if" part is trivial -- it follows form the definition of Monge array.
As for the "if" part, let's first prove that:
$$ A[i,j] + A[i+1, j+1] \le A[i,j+1] + A[i+1, j] \\ \Downarrow \\ A[i,j] + A[k, j+1] \le A[i, j+1] + A[k,j] $$
Where $i < k$.
Let's prove it by induction. The base case of $k = i + 1$ is given. As for the inductive step, we assume it holds for $k = i + n$ and we want to prove it for $k + 1= i + n + 1$. If we add the given to the assumption, we get:
$$ A[i, j] + A[k, j+1] \le A[i, j+1] + A[k, j] \quad (assumption) \\ A[k, j] + A[k+1, j+1] \le A[k, j+1] + A[k+1, j] \quad (given) \\ \Downarrow \\ A[i, j] + A[k, j+1] + A[k, j] + A[k+1, j+1] \le A[i, j+1] + A[k, j] + A[k, j+1] + A[k+1, j] \\ \Downarrow \\ A[i, j] + A[k+1, j+1] \le A[i, j+1] + A[k+1, j] $$
Part two
$$ \begin{matrix} 37 & 23 & \mathbf{24} & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \\ \end{matrix} $$
Part three
Let $a_i$ and $b_j$ be the leftmost minimal elements on rows $a$ and $b$ and let's assume that $i > j$. Then we have:
$$ A[j, a] + A[i, b] \le A[i, a] + A[j, b] $$
But:
$$ \begin{aligned} & A[j, a] \ge A[i, a] & (a_i \text{ is minimal}) \\ & A[i, b] \ge A[j, b] & (b_j \text{ is minimal}) \\ \end{aligned} $$
Which implies that:
$$ A[j, a] + A[i, b] \ge A[i, a] + A[j, b] \\ \Downarrow \\ A[j, a] + A[i, b] = A[i, a] + A[j, b] $$
Which in turn implies that either:
$$ \begin{aligned} &A[j, b] < A[i, b] \Rightarrow A[i, a] > A[j, a] && \Rightarrow a_i \text{ is not minimal} \\ &A[j, b] = A[i, b] && \Rightarrow b_j \text{ is not the leftmost minimal} \end{aligned} $$
Part four
If $\mu_i$ is the index of the $i$-th row's leftmost minimum, then we have:
$$ \mu_{i-1} \le \mu_i \le \mu_{i+1} $$
For $i = 2k + 1$, $k \ge 0$, finding $\mu_i$ takes $\mu_{i+1}-\mu_{i-1} + 1$ steps at most, since we only need to compare with those numbers. Thus:
$$ \begin{aligned} T(m, n) &= \sum_{i=0}^{m/2-1}\Big(\mu_{2i + 2} - \mu_{2i} + 1\Big) \\ &= \sum_{i=0}^{m/2-1}\mu_{2i+2} - \sum_{i=0}^{m/2-1}\mu_{2i} + m/2 \\ &= \sum_{i=1}^{m/2}\mu{2i} - \sum_{i=0}^{m/2-1}\mu{2i} + m/2 \\ &= \mu_m - \mu_0 + m/2 \\ &= n + m/2 \\ &= O(m + n) \end{aligned} $$
Part five
The divide time is $O(1)$, the conquer part is $T(m/2)$ and the merge part is $O(m+n)$. Thus:
$$ \begin{aligned} T(m) &= T(m/2) + cn + dm \\ &= cn + dm + cn + dm/2 + cn + dm/4 + \ldots \\ &= \sum_{i=0}^{\lg{m}-1}cn + \sum_{i=0}^{\lg{m}-1}\frac{dm}{2^i} \\ &= cn\lg{m} + dm\sum_{i=0}^{\lg{m} - 1} \\ &< cn\lg{m} + 2dm \\ &= O(n\lg{m} + m) \end{aligned} $$
C code
typedef struct array { int m; int n; int step; int *data; } array; int get(array A, int i, int j) { return A.data[((i + 1) * A.step - 1) * A.n + j]; } array half(array a) { array result = { a.m, a.n, a.step * 2, a.data }; return result; } int height(array array) { return array.m / array.step; } int min_index(array A, int row, int left, int right) { int min = left; for (int i = left; i < right; i++) { if (get(A, row, i) < get(A, row, min)) { min = i; } } return min; } void find_minimums(array A, int *mins) { if (height(A) == 1) { mins[0] = min_index(A, 0, 0, A.n); } else { array evens = half(A); int even_minimums[height(evens)]; find_minimums(evens, even_minimums); int leftmost = 0; for (int i = 0; i < height(evens); i++) { leftmost = min_index(A, 2 * i, leftmost, even_minimums[i] + 1); mins[2 * i] = leftmost; mins[2 * i + 1] = even_minimums[i]; } if (height(A) % 2) { mins[height(A) - 1] = min_index(A, height(A) - 1, leftmost, A.n); } } }