16
27
31
Initially bubble sort is used.
- Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
After the fourth pass the list is:
23
15
16
27
31
14
12
9
4
The sorting is then continued using shuttle sort on this list. - Record the list at the end of each of the first, second and third passes of shuttle sort. You do not need to show the individual swaps in each pass.
- How many passes through shuttle sort are needed to complete the sort? Explain your reasoning.
- A digraph is represented by the adjacency matrix below.
$$\begin{gathered}
\text { from }
\end{gathered} \begin{gathered}
\mathrm { A }
\mathrm {~B}
\mathrm { C }
\end{gathered} \quad \quad \left( \begin{array} { c c c }
1 & \mathrm {~B} & \mathrm { C }
1 & 1 & 0
0 & 0 & 0
0 & 1 & 0
\end{array} \right)$$
(a) For each vertex, write down
- the indegree,
- the outdegree.
(b) Explain how the indegrees and outdegrees show that the digraph is semi-Eulerian. - A graph is represented by the adjacency matrix below.
$$\left. \begin{array} { c }
\mathrm { D }
\mathrm { E }
\mathrm {~F}
\end{array} \quad \begin{array} { c c c }
\mathrm { D } & \mathrm { E } & \mathrm {~F}
2 & 1 & 0
1 & 0 & 2
0 & 2 & 0
\end{array} \right)$$
(a) Explain how the numerical entries in the matrix show that this can be drawn as an undirected graph.
(b) Explain how the adjacency matrix shows that this graph is semi-Eulerian. - By referring to the vertex degrees, explain why the loop from A to itself is shown as a 1 in the adjacency matrix in part (i) but the loop from \(D\) to itself is shown as 2 in the adjacency matrix in part (ii).
- List the 15 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } \}\).
Amy, Bao, Cal and Dana want to travel by taxi from a meeting to the railway station. They book taxis but only two taxis turn up. Each taxi must have a minimum of one passenger and can carry a maximum of four passengers. Dana jumps into one of the taxis.
- Find the number of ways that Amy, Bao and Cal can be split between the two taxis.
Amy does not want to travel in the same taxi as Bao.
- Determine the number of ways that Amy, Bao and Cal can be split between taxis with this additional restriction.
Six people want to travel by taxi from a hotel to the railway station using taxis. There must be a minimum of one passenger and a maximum of four passengers in each taxi. The taxis may be regarded as being indistinguishable.
- Calculate how many ways there are of splitting the six people between taxis.
\section*{END OF QUESTION PAPER}
\section*{OCR}
Oxford Cambridge and RSA