| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Algorithmic complexity calculations |
| Difficulty | Standard +0.3 This is a standard D1 question testing routine application of Dijkstra's algorithm, basic quadratic complexity calculations (simple proportion), and minimal spanning tree/route inspection concepts. All parts follow textbook procedures with no novel problem-solving required, making it slightly easier than average A-level maths. |
| Spec | 7.03g Order notation: O(n^k) for k = 0,1,2,3,47.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B = 8\), \(C = 11\) (temp or perm) and no others (no 18 at \(C\)) | B1 | |
| Temp label 23 at \(F\) (ignore any extras or omission of 22) | M1 | Condone 23 crossed out if consistent (e.g. with \(E\) or \(G\)); condone errors in other temp labels |
| All permanent labels correct (\(A\) may be blank, but others must be written as perm) | A1 | |
| Order of labelling correct for their permanent labels (use best temp if no perm shown), with \(A\) as 1 | B1 | Condone boxes swapped, provided consistent |
| \(A - B - F - G\) | B1 | \(A-B-F-G\) (cao) written or very easily seen on diagram; allow \(AB\), \(BF\), \(FG\) |
| [5] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(\left(\frac{1400}{7}\right)^2 \times 2.25 = 200^2 \times 2.25 = 90\,000\) seconds | M1 | A valid method for time in seconds (or minutes or hours), e.g. \(k(1400)^2\) with \(k = 2.25/49\) or equivalent (as a fraction) |
| \(= 1500\) minutes \(= 25\) hours | A1 | 25 (cao); \(25\ \text{www} \Rightarrow\) M1 A1 |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(11 + x + 15 \leq 31\) (\(x\) = new length of \(CE\)) or \(11 + 8 + 15 = 34\) | Method may be implied from answer 3 www, but watch out for answer 3 from wrong working | |
| \(\Rightarrow x \leq 5\); \(34 -\) 'their 31' (from i) | M1 | Allow \(x < 5\) or \(x = 5\), (\(CE\)) would become 5 (less than 5) |
| \(\Rightarrow\) (at least) 3 km shorter; \(34 - 31 = 3\) | A1 | 3 as answer (cao, www), condone '3 less' without 'at least'; units not reqd. ISW if answer 3 www is followed by 4 |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Odd nodes are \(A\), \(B\), \(C\) and \(F\) | B1 | \(A, B, C, F\) (may be implied from working) |
| \(AB = 8\), \(AC = 18\), \(AF = 22\), \(CF = 24\), \(BF = 14\), \(BC = 10\) | M1 | Any one correct pairing with weights or total |
| Totals: 32, 32, 32 | A1 | All three correct (with weights or totals); \(CF = 20\), \(AC = 11 \Rightarrow\) A0 |
| Total weight of arcs in network \(= 205\) | B1 | 205 or \(224 - 11 - 8\) or equivalent (seen in working) |
| The warden must travel \(205 + 32\) | M1 | 'Their 205' or (200 to 210) or \(224) +\) 'their 32' (min total weight of their claimed pairings), or implied from 237 www |
| \(= 237\) km | A1 | 237 (cao), condone no units |
| [6] |
# Question 5:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| $B = 8$, $C = 11$ (temp or perm) and no others (no 18 at $C$) | B1 | |
| Temp label 23 at $F$ (ignore any extras or omission of 22) | M1 | Condone 23 crossed out if consistent (e.g. with $E$ or $G$); condone errors in other temp labels |
| All permanent labels correct ($A$ may be blank, but others must be written as perm) | A1 | |
| Order of labelling correct for their permanent labels (use best temp if no perm shown), with $A$ as 1 | B1 | Condone boxes swapped, provided consistent |
| $A - B - F - G$ | B1 | $A-B-F-G$ (cao) written or very easily seen on diagram; allow $AB$, $BF$, $FG$ |
| **[5]** | | |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $\left(\frac{1400}{7}\right)^2 \times 2.25 = 200^2 \times 2.25 = 90\,000$ seconds | M1 | A valid method for time in seconds (or minutes or hours), e.g. $k(1400)^2$ with $k = 2.25/49$ or equivalent (as a fraction) |
| $= 1500$ minutes $= 25$ hours | A1 | 25 (cao); $25\ \text{www} \Rightarrow$ M1 A1 |
| **[2]** | | |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $11 + x + 15 \leq 31$ ($x$ = new length of $CE$) or $11 + 8 + 15 = 34$ | | Method may be implied from answer 3 www, but watch out for answer 3 from wrong working |
| $\Rightarrow x \leq 5$; $34 -$ 'their 31' (from i) | M1 | Allow $x < 5$ or $x = 5$, ($CE$) would become 5 (less than 5) |
| $\Rightarrow$ (at least) 3 km shorter; $34 - 31 = 3$ | A1 | 3 as answer (cao, www), condone '3 less' without 'at least'; units not reqd. ISW if answer 3 www is followed by 4 |
| **[2]** | | |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| Odd nodes are $A$, $B$, $C$ and $F$ | B1 | $A, B, C, F$ (may be implied from working) |
| $AB = 8$, $AC = 18$, $AF = 22$, $CF = 24$, $BF = 14$, $BC = 10$ | M1 | Any one correct pairing with weights or total |
| Totals: 32, 32, 32 | A1 | All three correct (with weights or totals); $CF = 20$, $AC = 11 \Rightarrow$ A0 |
| Total weight of arcs in network $= 205$ | B1 | 205 or $224 - 11 - 8$ or equivalent (seen in working) |
| The warden must travel $205 + 32$ | M1 | 'Their 205' or (200 to 210) or $224) +$ 'their 32' (min total weight of their claimed pairings), or implied from 237 www |
| $= 237$ km | A1 | 237 (cao), condone no units |
| **[6]** | | |
---5 This question uses the same network as question 4. The total weight of the arcs in the network is 224.\\
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}\\
(i) Apply Dijkstra's algorithm to the network, starting at $A$, to find the shortest route from $A$ to $G$.\\
(ii) Dijkstra's algorithm has quadratic order (order $n ^ { 2 }$ ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.\\
(iii) How much shorter would the path $C E$ need to be for it to become part of a shortest path from $A$ to $G$ ?
Following a landslip, the paths $A C$ and $C E$ become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.\\
(iv) Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex $C$. Show your working.
\hfill \mbox{\textit{OCR D1 2013 Q5 [15]}}