Problem 6.3

Young tableaus

An $m \times n$ Young tableau is an $m \times n$ matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be $\infty$, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold $r \le mn$ finite numbers.

Draw $4 \times 4$ tableau containing the elements $\{9, 16, 3, 2, 4, 8, 5, 14, 12\}$

Argue that an $m \times n$ Young tableau $Y$ is empty if $Y[1, 1] = \infty$. Argue that $Y$ is full (contains $mn$ elements) if $Y[m, n] < \infty$.

Give an algorithm to implement EXTRACT-MIN on a nonempty $m \times n$ Young tableau that runs in $\O(m + n)$ time. Your algorithm should use a recursive subroutine that solves an $m \times n$ problem by recursively solving either an $(m - 1) \times n$ or an $m \times (n - 1)$ subproblem. (Hint: Think about MAX-HEAPIFY.) Define $T(p)$ where $p = m + n$, to be the maximum running time of EXTRACT-MIN on any $m \times n$ Young tableau. Give and solve a recurrence relation for $T(p)$ that yields the $\O(m + n)$ time bound.

Show how to insert a new element into a nonfull $m \times n$ Young tableau in $\O(m + n)$ time

Using no other sorting method as a subroutine, show how to use an $n \times n$ Young tableau to sort $n^2$ numbers in $\O(n^3)$ time.

Give an $\O(m + n)$-time algorithm to determine whether a given number is stored in a given $m \times n$ Young tableau.

Draw a tableau

$$ \begin{matrix} 2 & 3 & 12 & 14 \\ 4 & 8 & 16 & \infty \\ 5 & 9 & \infty & \infty \\ \infty & \infty & \infty & \infty \\ \end{matrix} $$

Empty and full

If the top left element is $\infty$, then all the elements on the first row need to be $\infty$. But if this is the case, all other elements need to be $\infty$ because they are larger than the first element on their column.

If the bottom right element is smaller than $\infty$, all the elements on the bottom row need to be smaller than $\infty$. But so are the other elements in the tableau, because each is smaller than the bottom element of its column.

Extracting a minimum element

The $A[1, 1]$ is the smallest elemnt. We store it, so we can return it later and then replace is with $\infty$. This breaks the Young tableau property and we need to perform a procedure, similar to MAX-HEAPIFY to restore it.

We compare $A[i, j]$ with each of its neighbours and exchange it with the smallest. This restores the property for $A[i, j]$ but reduces the problem to either $A[i, j+1]$ or $A[i+1, j]$. We terminate when $A[i,j]$ is smaller than its neighbours.

The relation in question is:

$$ T(p) = T(p - 1) + \O(1) = T(p-2) + \O(1) + \O(1) = \ldots = \O(p) $$

Inserting a new element

The algorithm is very similar to the previous, except that we start with the bottom right element of the tableau and move it upwards and leftwards to the correct position. The asymptotic analysis is the same.

Sorting

We can sort by starting with an empty tableau and inserting all the $n^2$ elements in it. Each insertion is $\O(n + n) = \O(n)$. The complexity is $n^2\O(n) = \O(n^3)$. Afterwards we can take them one by one and put them back in the original array which has the same complexity. In total, its $\O(n^3)$.

We can also do it in place if we allow for "partial" tableaus where only a portion of the top rows (and a portion of the last of them) is in the tableau. Then we can build the tableau in place and then start putting each minimal element to the end. This would be asymptotically equal, but use constant memory. It would also sort the array in reverse.

Finding

We from the lower-left corner. We check the current element $current$ with the one we're looking for $key$ and move up if $current > key$ and right if $current < key$. We declare success if $current = key$ and otherwise terminate if we walk off the tableau.

C code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

typedef struct {
    int i;
    int j;
} cell;

typedef struct {
    int *elements;
    int m;
    int n;
} tableau_t;

cell up(cell c) {
    cell result = {c.i - 1, c.j};
    return result;
}

cell down(cell c) {
    cell result = {c.i + 1, c.j};
    return result;
}

cell left(cell c) {
    cell result = {c.i, c.j - 1};
    return result;
}

cell right(cell c) {
    cell result = {c.i, c.j + 1};
    return result;
}

cell make_cell(int i, int j) {
    cell result = {i, j};
    return result;
}

bool within(tableau_t *tableau, cell c) {
    return (c.i >= 0 && c.j >= 0 && c.i < tableau->m && c.j < tableau->n);
}

int get(tableau_t *tableau, cell c) {
    int index = c.i * tableau->n + c.j;
    return tableau->elements[index];
}

void set(tableau_t *tableau, cell c, int value) {
    int index = c.i * tableau->n + c.j;
    tableau->elements[index] = value;
}

void init_empty_tableau(tableau_t *tableau) {
    for (int i = 0; i < tableau->m * tableau-> n; i++) {
        tableau->elements[i] = INT_MAX;
    }
}

int extract_min(tableau_t *tableau) {
    int min, new;
    cell current = {0, 0},
         next;

    new = INT_MAX;
    min = get(tableau, current);

    set(tableau, current, INT_MAX);

    while (true) {
        int smallest;
        cell d = down(current);
        cell r = right(current);

        if (within(tableau, d) && get(tableau, d) < new) {
            next = d;
            smallest = get(tableau, next);
        } else {
            smallest = new;
        }

        if (within(tableau, r) && get(tableau, r) < smallest) {
            next = r;
            smallest = get(tableau, next);
        }

        if (new == smallest) {
            set(tableau, current, new);
            break;
        }

        set(tableau, current, smallest);
        current = next;
    }

    return min;
}

void insert(tableau_t *tableau, int key) {
    cell current = make_cell(tableau->m - 1, tableau->n - 1),
         next;

    if (get(tableau, current) != INT_MAX) {
        fprintf(stderr, "tableau is full\n");
        exit(0);
    }

    while (true) {
        int largest;
        cell u = up(current);
        cell l = left(current);

        if (within(tableau, u) && get(tableau, u) > key) {
            next = u;
            largest = get(tableau, next);
        } else {
            largest = key;
        }

        if (within(tableau, l) && get(tableau, l) > largest) {
            next = l;
            largest = get(tableau, next);
        }

        if (key == largest) {
            set(tableau, current, key);
            break;
        }

        set(tableau, current, largest);
        current = next;
    }
}

void sort(int *array, int size_sqrt) {
    int elements[size_sqrt * size_sqrt];
    tableau_t tableau = {elements, size_sqrt, size_sqrt};

    init_empty_tableau(&tableau);

    for (int i = 0; i < size_sqrt * size_sqrt; i++) {
        insert(&tableau, array[i]);
    }

    for (int i = 0; i < size_sqrt * size_sqrt; i++) {
        int next = extract_min(&tableau);
        array[i] = next;
    }
}

bool find(tableau_t *tableau, int key) {
    cell c = {tableau->m - 1, 0};

    while (within(tableau, c)) {
        int value = get(tableau, c);

        if (value == key) {
            return true;
        } else if (value > key) {
            c = up(c);
        } else {
            c = right(c);
        }
    }

    return false;
}