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} $$

  1. 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)

  2. 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} $$

  3. 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.

  4. 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.

  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})$.

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);
        }
    }
}