\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
A data operator is receiving tokens one by one through an input channel. The data operator will receive a total of $n$ tokens, where $n \geqslant 6$, and these are numbered as $1,2 , \ldots , n$. The data operator is required to pass these tokens to the output channel; however they must do so using a valid sequence. A valid sequence is one where all the odd tokens appear first, followed by the even tokens, or the other way round; furthermore all the odd tokens must appear in either increasing or decreasing order, and likewise all the even tokens must appear in increasing or decreasing order. All valid sequences for $n = 6$ are listed below.

\begin{center}
\begin{tabular}{ | l l l l | }
\hline
135246 & 135642 & 531246 & 531642 \\
246135 & 246531 & 642135 & 642531 \\
\hline
\end{tabular}
\end{center}

The data operator has a storage unit that can hold a sequence, and can perform the following operations as they receive the tokens one by one.

\begin{itemize}
  \item pass: Input token goes straight to the output channel.
  \item pop : Instead of using a token from the input, the token from the right end of the storage unit is removed (provided one exists) and sent to the output channel.
  \item pushL : Input token is pushed in at the left end of the storage unit.
  \item pushR : Input token is pushed in at the right end of the storage unit.
\end{itemize}

As an illustrative example, when $n = 6$, the storage and output channel are shown for the following sequence of operations, which results in the valid output sequence 13 5642.

\begin{center}
\begin{tabular}{ c c c c }
\hline
Input Token & Operation & Storage & Output \\
\hline
1 & pass & [ ] & 1 \\
2 & pushR & $[ 2 ]$ & 1 \\
3 & pass & $[ 2 ]$ & 13 \\
4 & pushR & $[ 24 ]$ & 13 \\
5 & pass & $[ 24 ]$ & 135 \\
6 & pass & $[ 24 ]$ & 1356 \\
 & pop & $[ 2 ]$ & 13564 \\
 & pop & [ ] & 135642 \\
\end{tabular}
\end{center}

(i) For $n = 6$, which valid sequences can the data operator achieve?\\
(ii) For $n \geqslant 6$ and even, how many valid sequences are there? Justify your answer.\\
(iii) For $n \geqslant 6$ and even, how many valid sequences can be achieved by the data operator? Briefly justify your answer.\\
(iv) In the remainder of the question, $n \geqslant 9$ is a multiple of 3 . A 3 -valid output sequence is one where among the tokens $1,2 , \ldots , n$, all tokens of the form $3 k$ appear together in increasing or decreasing order, likewise all tokens of the form $3 k + 1$ appear together in increasing or decreasing order, and the same is the case for all tokens of the form $3 k + 2$. As examples, the two sequences on the left below are 3 -valid, whereas the two on the right are not - the first because it mixes groups and the second because although the groups are separate, the tokens of the form $3 k + 2$ are in neither increasing nor decreasing order.

\begin{center}
\begin{tabular}{ | c c | }
\hline
3 -valid & not 3 -valid \\
\hline
147963852 & 135642789 \\
258147369 & 285963147 \\
\hline
\end{tabular}
\end{center}

For $n \geqslant 9$ and multiple of 3 , how many 3 -valid sequences of length $n$ are there? Justify your answer.\\
(v) For $n \geqslant 9$ and multiple of 3, given the input sequence of tokens $1,2 , \ldots , n$, how many 3 -valid sequences can be achieved by the operator using a single storage unit and the operations pass, pop, pushL and pushR? Justify your answer.

This page has been intentionally left blank

This page has been intentionally left blank\\
\includegraphics[max width=\textwidth, alt={}, center]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-32_573_558_718_754}