| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.3 This is a standard D1 question testing routine application of nearest neighbour algorithm, Prim's algorithm, and MST-based lower bound calculation. All parts follow textbook procedures with no novel problem-solving required, though the multi-part nature and table reading add minor complexity. Slightly easier than average A-level maths due to being purely algorithmic. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Pam | Alan | Bob | Caz | Dan | Ella | Fred | Gita | |
| Pam | - | 10 | 4 | 8 | 18 | 12 | 12 | 9 |
| Alan | 10 | - | 6 | 10 | 18 | 12 | 11 | 9 |
| Bob | 4 | 6 | - | 9 | 17 | 10 | 11 | 10 |
| Caz | 8 | 10 | 9 | - | 15 | 13 | 10 | 7 |
| Dan | 18 | 18 | 17 | 15 | - | 16 | 19 | 20 |
| Ella | 12 | 12 | 10 | 13 | 16 | - | 13 | 14 |
| Fred | 12 | 11 | 11 | 10 | 19 | 13 | - | 18 |
| Gita | 9 | 9 | 10 | 7 | 20 | 14 | 18 | - |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | 6 | – |
I'm unable to process this content as the input appears to be incomplete or corrupted. The data you've provided:
```
Question 4:
4 | 6 | – | 9 | 17 | 10 | 11
```
contains only numerical values separated by pipes and doesn't include any marking annotations (M1, A1, B1, etc.), marking criteria, or guidance notes that would constitute a mark scheme.
Could you please provide the full mark scheme content for Question 4 that includes:
- The question text or marking criteria
- Marking points with annotations (M1, A1, B1, DM1, etc.)
- Any guidance or notes for markers
Once you provide the complete content, I'll be happy to clean it up and convert unicode symbols to LaTeX notation as requested.4 Pam has seven employees. When it snows they all need to be contacted by telephone.\\
The table shows the expected time, in minutes, that it will take Pam and her employees to contact each other.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& Pam & Alan & Bob & Caz & Dan & Ella & Fred & Gita \\
\hline
Pam & - & 10 & 4 & 8 & 18 & 12 & 12 & 9 \\
\hline
Alan & 10 & - & 6 & 10 & 18 & 12 & 11 & 9 \\
\hline
Bob & 4 & 6 & - & 9 & 17 & 10 & 11 & 10 \\
\hline
Caz & 8 & 10 & 9 & - & 15 & 13 & 10 & 7 \\
\hline
Dan & 18 & 18 & 17 & 15 & - & 16 & 19 & 20 \\
\hline
Ella & 12 & 12 & 10 & 13 & 16 & - & 13 & 14 \\
\hline
Fred & 12 & 11 & 11 & 10 & 19 & 13 & - & 18 \\
\hline
Gita & 9 & 9 & 10 & 7 & 20 & 14 & 18 & - \\
\hline
\end{tabular}
\end{center}
(i) Use the nearest neighbour method, starting from Pam, to find a cycle through all the employees and Pam. If there is a choice of names choose the one that occurs first alphabetically. Calculate the total weight of this cycle.\\
(ii) Apply Prim's algorithm to the copy of the table in the answer book, starting by crossing out the row for Pam and looking down the column for Pam. List the arcs in the order in which they were chosen. Draw the resulting minimum spanning tree and calculate its total weight.\\
(iii) Find a lower bound for the minimum weight cycle through Pam and her seven employees by initially removing Gita from the minimum spanning tree.
Pam realises that it takes less time if she splits the employees into teams.\\
(iv) Use the minimum spanning tree to suggest how to split the employees into two teams, so that Pam contacts the two team leaders and they each contact the members of their team. Using this solution, find the minimum elapsed time by which all the employees can be contacted.
\hfill \mbox{\textit{OCR D1 2013 Q4 [17]}}