\section*{6. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { MATHEMATICS \& COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
Distinct numbers are arranged in an $m \times n$ rectangular table with $m$ rows and $n$ columns so that in each row the numbers are in increasing order (left to right), and in each column the numbers are in increasing order (top to bottom). Such a table is called a sorted table and each location of the table containing a number is called a cell. Two examples of sorted tables with 3 rows and 4 columns (and thus $3 \times 4 = 12$ cells) are shown below.

\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
3 & 12 & 33 & 64 \\
\hline
15 & 26 & 37 & 78 \\
\hline
19 & 40 & 51 & 92 \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
5 & 22 & 53 & 68 \\
\hline
18 & 36 & 67 & 78 \\
\hline
19 & 45 & 81 & 92 \\
\hline
\end{tabular}
\end{center}

We index the cells of the table with a pair of integers $( i , j )$, with the top-left corner being $( 1,1 )$ and the bottom-right corner being $( m , n )$. Observe that the smallest entry in a sorted table can only occur in cell $( 1,1 )$; however, note that the second smallest entry can appear either in cell ( 1,2 ), as in the first example above, or in cell ( 2,1 ) as in the second example above.\\
(i) (a) Assuming that $m , n \geqslant 3$, where in an $m \times n$ sorted table can the third-smallest entry appear?\\
(b) For any $k \geqslant 4$ satisfying $m , n \geqslant k$, where in an $m \times n$ sorted table can the $k ^ { \text {th } }$ smallest entry appear? Justify your answer.\\
(ii) Given an $m \times n$ sorted table, consider the problem of determining whether a particular number $y$ appears in the table. Outline a procedure that inspects at most $m + n - 1$ cells in the table, and that correctly determines whether or not $y$ appears in the table. Briefly justify why your procedure terminates correctly in no more than $m + n - 1$ steps.\\[0pt]
[Hint: As the first step, consider inspecting the top-right cell.]\\
(iii) Consider an $m \times n$ table, say $A$, which might not be sorted; an example is shown below. Obtain table $B$ from $A$ by re-arranging the entries in each row so that they are in sorted order. Then obtain table $C$ from $B$ by re-arranging the entries in each column so that they are in sorted order. Fill in tables $B$ and $C$ here:

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{$A$ :}
\begin{tabular}{ | c | c | c | c | }
\hline
33 & 92 & 46 & 24 \\
\hline
25 & 26 & 37 & 8 \\
\hline
49 & 40 & 81 & 22 \\
\hline
\end{tabular}
\end{center}
\end{table}

$C$ :

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{$B$ :}
  \includegraphics[alt={},max width=\textwidth]{c3a5e72c-19e2-41de-8833-ff60948250a1-24_186_426_2238_788}
\end{center}
\end{figure}

\includegraphics[max width=\textwidth, alt={}, center]{c3a5e72c-19e2-41de-8833-ff60948250a1-24_186_428_2238_1238}\\
(iv) Show that for any $m \times n$ table $A$, performing the two operations from part (iii) results in a sorted table $C$.



This page has been intentionally left blank