CLRS Solutions | Problem 6-3

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 \leq mn$ finite numbers.

Draw a $4 \times 4$ Young 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 $\textsc{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 $m \times (n-1)$ subproblem. (Hint: Think about $\textsc{Max-Heapify}$.) Deﬁne $T(p)$, where $p = m + n$, to be the maximum running time of $\textsc{Extract-Min}$ on any $m \times n$ Young tableau. Give and solve a recurrence 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.

A

We need to arrange the elements {9, 16, 3, 2, 4, 8, 5, 14, 12} in a $4 \times 4$ matrix such that rows increase left to right and columns increase top to bottom.

Starting with the smallest element, 2, we place it in the top-left corner. Then we insert the remaining elements one by one. A valid $4 \times 4$ Young tableau is:

\[\begin{array}{|c|c|c|c|} \hline 2 & 3 & 4 & 5 \\ \hline 8 & 9 & 12 & 14 \\ \hline 16 & \infty & \infty & \infty \\ \hline \infty & \infty & \infty & \infty \\ \hline \end{array}\]

We can verify this is valid: each row increases from left to right (2 < 3 < 4 < 5, etc.), and each column increases from top to bottom (2 < 8 < 16 < $\infty$, etc.).

B

Think about what the ordering properties tell us. If $Y[1,1] = \infty$, then since every element in the first row must be at least as large as $Y[1,1]$ (rows increase left to right), we have $Y[1,j] = \infty$ for all $j$. Similarly, since every element in the first column must be at least as large as $Y[1,1]$ (columns increase top to bottom), we have $Y[i,1] = \infty$ for all $i$.

But now consider any element $Y[i,j]$ with $i, j > 1$. We have $Y[i,j] \geq Y[i,1] = \infty$ (since columns increase), so $Y[i,j] = \infty$. By induction, all elements in the tableau are $\infty$, meaning the tableau is empty.

For the second part, if $Y[m,n] < \infty$, then $Y[m,n]$ is a finite number. Since rows increase left to right, every element in row $m$ is finite: $Y[m,j] \leq Y[m,n] < \infty$ for all $j \leq n$. Similarly, since columns increase top to bottom, every element in column $n$ is finite: $Y[i,n] \leq Y[m,n] < \infty$ for all $i \leq m$.

Now consider any element $Y[i,j]$. We have $Y[i,j] \leq Y[i,n] < \infty$ (row increases) and $Y[i,j] \leq Y[m,j] < \infty$ (column increases). Therefore, every element in the tableau is finite, meaning the tableau contains exactly $mn$ elements and is full.

C

The minimum element in a Young tableau is always at position $[1,1]$ because it’s smaller than everything in its row and column, which in turn are smaller than everything else in the tableau.

After extracting $Y[1,1]$, we need to fill the hole. We replace $Y[1,1]$ with $\infty$ and then “sink” this $\infty$ down to its proper position, similar to $\textsc{Max-Heapify}$ but adapted to the two-dimensional structure.

$$\textsc{Young-Extract-Min}(Y)$$$$\begin{aligned} 1& \quad min\,=\,Y[1, \,\, \,1] \\ 2& \quad Y[1, \,\, \,1]\,=\,\infty \\ 3& \quad \textsc{Young-Heapify}(Y, \, 1, \, 1) \\ 4& \quad \textbf{return }\,min \\ \end{aligned}$$

$$\textsc{Young-Heapify}(Y, i, j)$$$$\begin{aligned} 1& \quad \textbf{/\!/} \text{ Find}\,\text{ the}\,\text{ minimum}\,\text{ among}\,\text{ current}\,\text{ position,}\,\text{ right}\,\text{ neighbor,}\,\text{ and}\,\text{ bottom}\,\text{ neighbor}\, \\ 2& \quad min_{i}\,=\,i \\ 3& \quad min_{j}\,=\,j \\ 4& \quad \\ 5& \quad \textbf{/\!/} \text{ Check}\,\text{ right}\,\text{ neighbor}\, \\ 6& \quad \textbf{if }\,j\,<\,n\textbf{ and }\,Y[i, \,\, \,j + 1]\,<\,Y[min_i, \,\, \,min_j] \\ 7& \quad \qquad min_{i}\,=\,i \\ 8& \quad \qquad min_{j}\,=\,j\,+\,1 \\ 9& \quad \\ 10& \quad \textbf{/\!/} \text{ Check}\,\text{ bottom}\,\text{ neighbor}\, \\ 11& \quad \textbf{if }\,i\,<\,m\textbf{ and }\,Y[i + 1, \,\, \,j]\,<\,Y[min_i, \,\, \,min_j] \\ 12& \quad \qquad min_{i}\,=\,i\,+\,1 \\ 13& \quad \qquad min_{j}\,=\,j \\ 14& \quad \\ 15& \quad \textbf{/\!/} \text{ If}\,\text{ we}\,\text{ found}\,\text{ a}\,\text{ smaller}\,\text{ neighbor,}\,\text{ swap}\,\text{ and}\,\text{ recurse}\, \\ 16& \quad \textbf{if }\,min_{i}\,\ne\,i\textbf{ or }\,min_{j}\,\ne\,j \\ 17& \quad \qquad \text{exchange}\,Y[i, \,\, \,j]\,\text{with}\,Y[min_i, \,\, \,min_j] \\ 18& \quad \qquad \textsc{Young-Heapify}(Y, \, i, \, j)\,(Y, \, min_i, \, min_j ) \\ \end{aligned}$$

At each step, we compare at most 3 elements (current position and two neighbors) and swap with one of them, moving either right or down. Let $T(p)$ be the maximum running time for a tableau where $p = m + n$.

After one step, we recurse on either an $(m-1) \times n$ tableau (if we moved down) or an $m \times (n-1)$ tableau (if we moved right). In both cases, the new parameter is $(m-1) + n$ or $m + (n-1) = p - 1$.

This gives us the recurrence:

\[T(p) = T(p-1) + O(1)\]

Solving this recurrence:

\[\begin{align*} T(p) &= T(p-1) + O(1) \\ &= T(p-2) + O(1) + O(1) \\ &= \cdots \\ &= T(1) + O(p) \\ &= O(p) \\ &= O(m + n) \end{align*}\]

Therefore, $\textsc{Extract-Min}$ runs in $O(m + n)$ time.

D

To insert a new element, we use the opposite strategy from extraction. We place the new element at position $[m,n]$ (replacing the $\infty$ there in a nonfull tableau) and then “bubble” it up and left to its proper position.

$$\textsc{Young-Insert}(Y, key)$$$$\begin{aligned} 1& \quad \textbf{if }\,Y[m, \,\, \,n]\,<\,\infty \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft tableau is full\textquotedblright} \\ 3& \quad Y[m, \,\, \,n]\,=\,key \\ 4& \quad \textsc{Young-Bubble-Up}(Y, \, m, \, n) \\ \end{aligned}$$

$$\textsc{Young-Bubble-Up}(Y, i, j)$$$$\begin{aligned} 1& \quad \textbf{/\!/} \text{ Find}\,\text{ the}\,\text{ maximum}\,\text{ among}\,\text{ current}\,\text{ position,}\,\text{ left}\,\text{ neighbor,}\,\text{ and}\,\text{ top}\,\text{ neighbor}\, \\ 2& \quad max_{i}\,=\,i \\ 3& \quad max_{j}\,=\,j \\ 4& \quad \\ 5& \quad \textbf{/\!/} \text{ Check}\,\text{ left}\,\text{ neighbor}\, \\ 6& \quad \textbf{if }\,j\,>\,1\textbf{ and }\,Y[i, \,\, \,j - 1]\,>\,Y[max_i, \,\, \,max_j] \\ 7& \quad \qquad max_{i}\,=\,i \\ 8& \quad \qquad max_{j}\,=\,j\,-\,1 \\ 9& \quad \\ 10& \quad \textbf{/\!/} \text{ Check}\,\text{ top}\,\text{ neighbor}\, \\ 11& \quad \textbf{if }\,i\,>\,1\textbf{ and }\,Y[i - 1, \,\, \,j]\,>\,Y[max_i, \,\, \,max_j] \\ 12& \quad \qquad max_{i}\,=\,i\,-\,1 \\ 13& \quad \qquad max_{j}\,=\,j \\ 14& \quad \\ 15& \quad \textbf{/\!/} \text{ If}\,\text{ we}\,\text{ found}\,\text{ a}\,\text{ larger}\,\text{ neighbor,}\,\text{ swap}\,\text{ and}\,\text{ recurse}\, \\ 16& \quad \textbf{if }\,max_{i}\,\ne\,i\textbf{ or }\,max_{j}\,\ne\,j \\ 17& \quad \qquad \text{exchange}\,Y[i, \,\, \,j]\,\text{with}\,Y[max_i, \,\, \,max_j] \\ 18& \quad \qquad \textsc{Young-Bubble-Up}(Y, \, i, \, j)\,(Y, \, max_i, \, max_j ) \\ \end{aligned}$$

The analysis is symmetric to $\textsc{Extract-Min}$. At each step, we move either up or left, reducing either $i$ or $j$ by 1. Starting from position $[m,n]$ and moving to position $[1,1]$ requires at most $m-1 + n-1 = m + n - 2$ moves.

Therefore, $\textsc{Young-Insert}$ runs in $O(m + n)$ time.

E

To sort $n^2$ numbers using an $n \times n$ Young tableau, we first insert all $n^2$ numbers into an initially empty tableau, then extract them one by one in sorted order.

The algorithm is:

Initialize an $n \times n$ Young tableau with all entries set to $\infty$.
For each of the $n^2$ numbers, call $\textsc{Young-Insert}$ to insert it into the tableau.
For $i = 1$ to $n^2$, call $\textsc{Young-Extract-Min}$ and store the result in position $i$ of the output array.

Each insertion takes $O(n + n) = O(n)$ time, and we perform $n^2$ insertions, giving $O(n^3)$ time for step 2. Each extraction takes $O(n)$ time, and we perform $n^2$ extractions, giving $O(n^3)$ time for step 3.

Therefore, the total running time is $O(n^3) + O(n^3) = O(n^3)$.

F

To search for a value $x$ in a Young tableau, we can exploit the ordering properties. Starting from the top-right corner at position $[1,n]$, we can eliminate either an entire row or an entire column at each step.

The key observation is that at position $[i,j]$:

All elements to the left in row $i$ are smaller than $Y[i,j]$
All elements below in column $j$ are larger than $Y[i,j]$

So if $x < Y[i,j]$, we know $x$ cannot be anywhere in column $j$ (since all elements in that column below $[i,j]$ are even larger). If $x > Y[i,j]$, we know $x$ cannot be anywhere in row $i$ to the left of position $j$.

$$\textsc{Young-Search}(Y, x)$$$$\begin{aligned} 1& \quad i\,=\,1 \\ 2& \quad j\,=\,n \\ 3& \quad \textbf{while }\,i\,\leq\,m\textbf{ and }\,j\,\geq\,1 \\ 4& \quad \qquad \textbf{if }\,Y[i, \,\, \,j]\,=\,x \\ 5& \quad \qquad \qquad \textbf{return }\,(i, \, j) \\ 6& \quad \qquad \textbf{else }\textbf{ if }\,Y[i, \,\, \,j]\,>\,x \\ 7& \quad \qquad \qquad j\,=\,j\,-\,1\quad \textbf{/\!/} \text{ eliminate}\,\text{ column}\,\text{ j}\, \\ 8& \quad \qquad \textbf{else } \\ 9& \quad \qquad \qquad i\,=\,i\,+\,1\quad \textbf{/\!/} \text{ eliminate}\,\text{ row}\,\text{ i}\, \\ 10& \quad \textbf{return }\,\textsc{NIL} \\ \end{aligned}$$

We start at position $[1,n]$ and move either down (incrementing $i$) or left (decrementing $j$) at each step. We can move down at most $m-1$ times and left at most $n-1$ times, so the total number of steps is at most $(m-1) + (n-1) = m + n - 2$.

Therefore, the algorithm runs in $O(m + n)$ time.