problem 6-3

6-3 Young tableaus An m x n Young tableau is an m x 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 1, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r  mn finite numbers.

c)Give an algorithm to implement EXTRACT-MIN on a nonempty mxn Young tableau that runs in O(m + n) time. Your algorithm should use a recursive subroutine that solves an m x n problem by recursively solving either an m-1 x n or an m x n-1 subproblem. (Hint: Think about MAXHEAPIFY.) Define T(p), where p = O(m + n), to be the maximum running time of EXTRACT-MIN on any mxn Young tableau. Give and solve a recurrence for T(p) that yields the O(m + n) time bound.
1,1 will have smallest element in the matrix. Lets replace this with $\infty$ (since empty should have infinity in tableau). Now the array is not a tableau. But i+1..m,j..n and i..m,j+1..m are two tableau(sub tableaus). we need to recursive
EXTRACT-MIN(A,m,n)
int min = A[1,1]
A[1,1] = $ \infty $
YOUNGIFY(A,m,n,1,1)
return min.
YOUNGIFY(A,m,n,i,j)
$minimum_i$ = i
$minimum_j$ = j
if i+1 <= m and A[i][j] < A[i+1][j]
$minimum_i$ = i+1
if j+1 <=n and A[$minimum_i$][j] $minimum_j$ = j+1
if $minimum_i$ != i and $minimum_j != j$
swap A[i][j] and A[$minimum_i$][$minimum_j$]
YOUNGIFY(A,m,n,$minimum_i$,$minimum_j$)
The YOUNGIFY is recursively called for i+j times(take a small 2 x 2 or 3 x 3 matrix infinity will reach from 1,1 to 3,3 finally). i and j cannot exceed m and n hence the running time $O(m+n)$ and we are solving the mxn problem recursively m-1 x n or m x n-1.

d. INSERT(A,m,n,key)
IF A[m] [n] < key
error ("Error")
A[m][n] = key;
BUILD-YOUNGIFY(A,m,n)


Below is BUILD-YOUNGIFY BUILD-YOUNGIFY(A,m,n)
$maximum_i$ = m
$maximum_j$ = n
if m-1 > 0 and A[$maximum_i$][$maximum_j$] < A[m-1][n] Then
$maximum_i$ = m-1
if n-1 > 0 and A[$maximum_i$][$maximum_j$] < A[m][n-1] Then
$maximum_j$ = n-1
If $maximum_i$ != m or $maximum_j != n$ Then
swap A[$maximum_i$][$maximum_j$] and A[m][n]
BUILD-YOUNGIFY(A,$maximum_i$,$maximum_j$)
even if we have an empty array and we are inserting new element the elements will traverse only (i+j) the maximum values for i and j are m and n so the running time is $O(m+n)$
e. SORT(A)
for i = 1 to m
INSERT(Y,n,n,A[i])
for i = 1 to m
A[i] = EXTRACT-MIN(Y)
The above procedure from line 1 to 2 is inserting $n^2$ in to tableau which takes $O(n+n)$ and lines 3 to 4 also extract $n^2$ and EXTRACT-MIN runs $O(n+n)$ this gives the running time of $O(n^3)$
In general, given n numbers to sort, let $a = \sqrt n$. We can create an empty a x a Young tableau and perform the above algorithm (with m = n). Each operation on the Young tableau will take O(a + a) = $O(\sqrt n)$ time. Therefore, the running time of the algorithm will be $O(n \sqrt n)$ = $O(n^{1.5})$.
f.
If we start from 1,1 or m,m we have to scan m x n elements. It will in efficient compared to m+n. The only possible way is to 1,n and move left until we the value if we dont we have to search the below row. if A[$i_0$][$j_0$] $\geq$ key we dont have to search i < $i_0$ and j < $j_0$.Because of the above logic we will always skip n elements and search only m+n in worst case hence the running time is $O(m+n)$
SEARCH-KEY (A,key,m,n)
i = 1
j = n
while j <= 1 and A[i][j] >= key
if A[i][j] == key
return "found"
j = j -1
m = m - 1
if i <= m
SEARCH-KEY(A,key,m,n)