| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2022 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Algorithmic complexity calculations |
| Difficulty | Challenging +1.2 This is a Further Maths question on Dijkstra's algorithm complexity analysis. Parts (a)-(b) are routine application of the algorithm. Part (c) requires careful counting of comparisons in K₄, which is moderately challenging but follows a structured framework with clear guidance. The algorithmic complexity analysis is more sophisticated than standard A-level content, but the question provides substantial scaffolding and the counting exercise is methodical rather than requiring deep insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| A | B | C | D | E | F | G | |
| A | 64 | 60 | 111 | ||||
| B | 64 | 72 | 103 | ||||
| C | 60 | 66 | 58 | ||||
| D | 111 | 72 | 66 | 32 | 127 | ||
| E | 103 | 32 | 82 | ||||
| F | 58 | 127 | 75 | ||||
| G | 82 | 75 |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (a) | B1 |
| [1] | 3.3 | Correct network (arcs and weights) |
| 7 | (b) | Correct use of boxes at vertices |
| Answer | Marks |
|---|---|
| 64 60 111 143 118 193 | M1* |
| Answer | Marks |
|---|---|
| [3] | 3.1a |
| Answer | Marks |
|---|---|
| 1.1 | Evidence of using Dijkstra’s algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (c) | First pass: (0) + 2 |
| Answer | Marks |
|---|---|
| = 2(2 + 1) = 6 AG | M1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 1.1 | Correct comps for any (identified) pass correct or a type (column) |
| Answer | Marks | Guidance |
|---|---|---|
| B | C | D |
| 7 | (d) | 69 × 68 |
| Answer | Marks |
|---|---|
| = 4.7 seconds | M1 |
| A1 | 2.2a |
| 1.1 | Or implied from answer |
| Answer | Marks | Guidance |
|---|---|---|
| 102 0.03 | M1 | Working must be seen, not implied |
| = 3 | A0 |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (e) | (i) |
| Answer | Marks |
|---|---|
| Lower bound = 437 metres | M1 |
| Answer | Marks |
|---|---|
| [2] | 3.4 |
| 3.4 | Attempting MST with D deleted, soi from 339 or 437 |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (e) | (ii) |
| Answer | Marks | Guidance |
|---|---|---|
| Upper bound = 443 metres | B1 | |
| [1] | 3.4 | D – E – G – F – C – A – B – D and 443 |
| 7 | (e) | (iii) |
| Answer | Marks | Guidance |
|---|---|---|
| Hence 443 (metres) | B1 | |
| [1] | 3.1b | 443 with some valid reasoning about lower bound not being a tour |
Question 7:
7 | (a) | B1
[1] | 3.3 | Correct network (arcs and weights)
7 | (b) | Correct use of boxes at vertices
B C D E F G
64 60 111 143 118 193 | M1*
M1dep*
A1
[3] | 3.1a
1.1
1.1 | Evidence of using Dijkstra’s algorithm
(order of labelling and permanent labels at all 7 vertices)
Updating temporary label at E correctly
All correct (if not listed in table check on diagram)
7 | (c) | First pass: (0) + 2
Second pass: 2 + 1
Third pass: 1 + (0)
2 + (2 + 1) + 1 or 2 + 2 + 1 + 1
= 2(2 + 1) = 6 AG | M1
A1
[2] | 2.1
1.1 | Correct comps for any (identified) pass correct or a type (column)
but NOT 3 + 2 + 1
Verifying the given value 6 (from correct comps)
But not using the given result in stem to part (d)
[i.e. NOT (4 – 1)(4 – 2) = 3 2 = 6]
B | C | D | E | F | G
7 | (d) | 69 × 68
0.03
6 × 5
= 4.7 seconds | M1
A1 | 2.2a
1.1 | Or implied from answer
4.7 or better (4.69, 4.692)
Alternative answer
102 0.03 | M1 | Working must be seen, not implied
= 3 | A0
[2]
7 | (e) | (i) | MST with D deleted
= 58 + 60 + 64 + 75 + 82 = 339
339 + 32 + 66 = 437
Lower bound = 437 metres | M1
A1
[2] | 3.4
3.4 | Attempting MST with D deleted, soi from 339 or 437
437
7 | (e) | (ii) | D – E – G – F – C – A – B – D
= 32 + 82 + 75 + 58 + 60 + 64 + 72
Upper bound = 443 metres | B1
[1] | 3.4 | D – E – G – F – C – A – B – D and 443
7 | (e) | (iii) | 437 length 443
To make the lower bound into a tour we
need to use BD = 72 instead of CD = 66
Hence 443 (metres) | B1
[1] | 3.1b | 443 with some valid reasoning about lower bound not being a tour
PMT
Need to get in touch?
If you ever have any questions about OCR qualifications or services (including administration, logistics and teaching) please feel free to get in
touch with our customer support centre.
Call us on
01223 553998
Alternatively, you can email us on
support@ocr.org.uk
For more information visit
ocr.org.uk/qualifications/resource-finder
ocr.org.uk
Twitter/ocrexams
/ocrexams
/company/ocr
/ocrexams
OCR is part of Cambridge University Press & Assessment, a department of the University of Cambridge.
For staff training purposes and as part of our quality assurance programme your call may be recorded or monitored. © OCR
2022 Oxford Cambridge and RSA Examinations is a Company Limited by Guarantee. Registered in England. Registered office
The Triangle Building, Shaftesbury Road, Cambridge, CB2 8EA.
Registered company number 3484466. OCR is an exempt charity.
OCR operates academic and vocational qualifications regulated by Ofqual, Qualifications Wales and CCEA as listed in their
qualifications registers including A Levels, GCSEs, Cambridge Technicals and Cambridge Nationals.
OCR provides resources to help you deliver our qualifications. These resources do not represent any particular teaching method
we expect you to use. We update our resources regularly and aim to make sure content is accurate but please check the OCR
website so that you have the most up-to-date version. OCR cannot be held responsible for any errors or omissions in these
resources.
Though we make every effort to check our resources, there may be contradictions between published support and the
specification, so it is important that you always use information in the latest specification. We indicate any specification changes
within the document itself, change the version number and provide a summary of the changes. If you do notice a discrepancy
between the specification and a resource, please contact us.
Whether you already offer OCR qualifications, are new to OCR or are thinking about switching, you can request more
information using our Expression of Interest form.
Please get in touch if you want to discuss the accessibility of resources we offer to support you in delivering our qualifications.7 A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.\\
The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & & 64 & 60 & 111 & & & \\
\hline
B & 64 & & & 72 & 103 & & \\
\hline
C & 60 & & & 66 & & 58 & \\
\hline
D & 111 & 72 & 66 & & 32 & 127 & \\
\hline
E & & 103 & & 32 & & & 82 \\
\hline
F & & & 58 & 127 & & & 75 \\
\hline
G & & & & & 82 & 75 & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Model this information as a network.
\item Use an appropriate algorithm to calculate the minimum distance from A to each of the other vertices.
The run-time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with $n$ vertices, the worst case is when the algorithm is applied to a network based on the complete graph $\mathrm { K } _ { n }$.
In each pass
\begin{itemize}
\item A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.
\item The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are $k$ such vertices this involves $k - 1$ comparisons.
\item By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete graph $\mathrm { K } _ { 4 }$.
\end{itemize}
You are given that the total number of comparisons used when the algorithm is applied to a network based on $\mathrm { K } _ { n }$ is $( n - 1 ) ( n - 2 )$.
A computer takes 0.03 seconds to apply this algorithm on a network based on $\mathrm { K } _ { 7 }$.
\item Calculate, to $\mathbf { 1 }$ decimal place, how many seconds it will take the computer to apply the algorithm to a network based on $\mathrm { K } _ { 70 }$.
\section*{Question 7 continues on the next page}
The manager wants to construct a tour (a closed route) that passes each camera.
\item \begin{enumerate}[label=(\roman*)]
\item Find a lower bound for the length of this tour by initially deleting D .
\item Find an upper bound for the length of this tour by using the nearest neighbour algorithm starting from D.
\item Deduce the length of the shortest possible tour. Briefly explain your reasoning.
\section*{END OF QUESTION PAPER}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2022 Q7 [12]}}