| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2021 |
| Session | November |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Comparing Sorting Algorithms |
| Difficulty | Moderate -0.8 This is a routine Further Maths question testing standard algorithms with straightforward application. Parts (a) and (b) require mechanical execution of bubble/shuttle sort with given data—pure recall and procedure following. Part (c) involves basic MST concepts but with clear structure: identifying which weight can be excluded requires simple reasoning about tree properties (n-1 edges for n vertices), and constructing extremal cases is methodical rather than requiring deep insight. The route inspection component is standard application of a known algorithm. While multi-part and requiring several techniques, each step is textbook-level with no novel problem-solving required. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (a) | (i) |
| Answer | Marks |
|---|---|
| After 2nd pass 0.9 1.5 2.9 3.5 4.2 2.3 4.7 (5.3) | M1 |
| A 1 | 1.1 |
| 1.1 | Substantially correct method, starting at left hand end of |
| Answer | Marks |
|---|---|
| If sorted into decreasing order: | SC1 only |
| Answer | Marks |
|---|---|
| (ii) | Original list 2.9 0.9 1.5 3.5 4.2 5.3 4.7 2.3 |
| Answer | Marks |
|---|---|
| After 2nd pass 0.9 1.5 2.9 (3.5) (4.2) (5.3) (4.7) (2.3) | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Substantially correct method, e.g. 0.9 jumps over 2.9 |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (b) | Bubble sort uses 7 + 6 + 14 = 27 comparisons |
| Answer | Marks |
|---|---|
| comparisons, so shuttle sort is more efficient | B1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 2.4 | 27 comparisons for bubble |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (c) | (i) |
| Must have 0.9 and 1.5 but then 2.3 may form a triangle | B1 |
| Answer | Marks |
|---|---|
| [2] | 3.1a |
| Answer | Marks |
|---|---|
| (ii) | e.g. e.g. |
| Weight of MST = 9.5 | M1 |
| Answer | Marks |
|---|---|
| [3] | 3.1a |
| Answer | Marks |
|---|---|
| 1.1 | Many possible solutions |
| Answer | Marks |
|---|---|
| (iii) | eg eg |
| Answer | Marks |
|---|---|
| 25.3 + 7.0 = 32.3 25.3 + 5.1 = 30.4 | M1 |
| Answer | Marks |
|---|---|
| [3] | 2.1 |
| Answer | Marks |
|---|---|
| 1.1 | Follow through their network from (c)(ii) |
Question 7:
7 | (a) | (i) | Original list 2.9 0.9 1.5 3.5 4.2 5.3 4.7 2.3
After 1st pass 0.9 1.5 2.9 3.5 4.2 4.7 2.3 5.3
After 2nd pass 0.9 1.5 2.9 3.5 4.2 2.3 4.7 (5.3) | M1
A 1 | 1.1
1.1 | Substantially correct method, starting at left hand end of
list, e.g. 1st pass correct
Both passes correct, need not show 5.3 in small font
If sorted into decreasing order: | SC1 only
Both passes correct, need not show 0.9 in small font
After 1st pass 2.9 1.5 3.5 4.2 5.3 4.7 2.3 0.9
After 2nd pass 2.9 3.5 4.2 5.3 4.7 2.3 1.5 (0.9)
[2]
(ii) | Original list 2.9 0.9 1.5 3.5 4.2 5.3 4.7 2.3
After 1st pass 0.9 2.9 (1.5) (3.5) (4.2) (5.3) (4.7) (2.3)
After 2nd pass 0.9 1.5 2.9 (3.5) (4.2) (5.3) (4.7) (2.3) | M1
A1
[2] | 1.1
1.1 | Substantially correct method, e.g. 0.9 jumps over 2.9
Both passes correct, need not show figures in small font
7 | (b) | Bubble sort uses 7 + 6 + 14 = 27 comparisons
Shuttle sort uses 1 + 2 + 11 = 14 comparisons
Number of swaps is the same for both sorts, shuttle sort uses fewer
comparisons, so shuttle sort is more efficient | B1
B1
B1ft
[3] | 1.1
1.1
2.4 | 27 comparisons for bubble
14 comparisons for shuttle
(bubble = 4+1+3 = 8 swaps, shuttle = 1+1+6 = 8 swaps)
Swaps same, shuttle more efficient (need both of these)
7 | (c) | (i) | 2.3
Must have 0.9 and 1.5 but then 2.3 may form a triangle | B1
B1
[2] | 3.1a
2.4
(ii) | e.g. e.g.
Weight of MST = 9.5 | M1
A1
B1
[3] | 3.1a
2.4
1.1 | Many possible solutions
0.9, 1.5 and 2.3 form a triangle
2.9, 3.5 and one lower weight arc form a triangle
0.9 + 1.5 + 2.9 + 4.2 = 9.5
(iii) | eg eg
2.3 + 4.7 = 7.0 0.9 + 4.2 = 5.1
2.9 + 5.3 = 8.2 2.9 + 5.3 = 8.2
(0.9+4.2) + (1.5+3.5) = 10.1 (0.9+2.9) + (0.9+5.3) = 10.0
Sum of weights = 25.3 Sum of weights = 25.3
25.3 + 7.0 = 32.3 25.3 + 5.1 = 30.4 | M1
B1
A1ft
[3] | 2.1
2.2a
1.1 | Follow through their network from (c)(ii)
Attempt to pair the four odd vertices
Sum of arc weights = 25.3 seen
Their seen 25.3 + their claimed least weight pairing
SC1 only
Both passes correct, need not show 0.9 in small font
PMT
OCR (Oxford Cambridge and RSA Examinations)
The Triangle Building
Shaftesbury Road
Cambridge
CB2 8EA
OCR Customer Contact Centre
Education and Learning
Telephone: 01223 553998
Facsimile: 01223 552627
Email: general.qualifications@ocr.org.uk
www.ocr.org.uk
For staff training purposes and as part of our quality assurance programme your call may be
recorded or monitored7 A network is formed by weighting the graph below using the listed arc weights.\\
\includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-8_168_190_310_258}\\
$\begin{array} { l l l l l l l l } 2.9 & 0.9 & 1.5 & 3.5 & 4.2 & 5.3 & 4.7 & 2.3 \end{array}$
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using bubble sort.
\item Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using shuttle sort.
In the remaining passes of bubble sort another 14 comparisons are made.\\
In the remaining passes of shuttle sort another 11 comparisons are made.\\
The total number of swaps needed is the same for both sorting methods.
\end{enumerate}\item Use the total number of comparisons and the total number of swaps to compare the efficiency of bubble sort and shuttle sort for sorting this list of weights.
The sorted list of arc weights for the network is as follows.\\
$\begin{array} { l l l l l l l l } 0.9 & 1.5 & 2.3 & 2.9 & 3.5 & 4.2 & 4.7 & 5.3 \end{array}$
These weights can be given to the arcs of the graph in several ways to form different networks.
\item \begin{enumerate}[label=(\roman*)]
\item What is the smallest weight that does not have to appear in a minimum spanning tree for any of these networks? You must explain your reasoning.
\item Show a way of weighting the arcs, using the weights in the list, that results in the largest possible total for a minimum spanning tree. You should state the total weight of your minimum spanning tree.
\item Determine the total weight of an optimal solution of the route inspection problem for the network found in part (c)(ii).
\section*{END OF QUESTION PAPER}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2021 Q7 [15]}}