\section*{7. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
A character in a video game is collecting the magic coins that are attached to a cliff face. The character starts at the bottom left corner $S$ and must reach the top right corner $E$. One point is scored for each coin $C$ that is collected on the way, and the aim is to reach the top right corner with the highest possible score. At each step the character may move either one cell to the right or one cell up, but never down or to the left.\\
\includegraphics[max width=\textwidth, alt={}, center]{df72dfe2-9f61-49a0-a6b9-a4ad637d3c86-20_848_860_902_539}\\
(i) Let $c ( i , j ) = 1$ if there is a coin at position $( i , j )$, and $c ( i , j ) = 0$ otherwise. Describe how the maximum score $m ( i , j )$ achievable on reaching position $( i , j )$, where $i \geqslant 2$ and $j \geqslant 2$, can be determined in terms of the maximum scores $m ( i , j - 1 )$ and $m ( i - 1 , j )$ achievable at the positions immediate below and to the left. Briefly justify your answer.\\
(ii) Use the result from part (i) to fill in each cell in the diagram above to show the maximum score achievable on reaching that cell. What is the maximum score achievable in the game? A spare copy of the diagram appears at the end of the question.\\
(iii) Given the array of scores $m ( i , j )$, describe a method for tracing backwards from $E$ to $S$ a path that, if followed in a forward direction by the character, would achieve the maximum score. Draw one such path across the cliff.\\
(iv) With the pattern of coins shown, how many different paths from $S$ to $E$ achieve the maximum score? Describe a method for computing the number of such paths.\\
\includegraphics[max width=\textwidth, alt={}, center]{df72dfe2-9f61-49a0-a6b9-a4ad637d3c86-21_847_853_1580_541}

End of last question

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank

This page has been intentionally left blank\\
\includegraphics[max width=\textwidth, alt={}, center]{df72dfe2-9f61-49a0-a6b9-a4ad637d3c86-28_573_558_718_754}