| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2001 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a straightforward application of Prim's algorithm with a small 6-node network and clearly presented distance table. Students simply follow the algorithmic procedure (select nearest unconnected vertex repeatedly) with no problem-solving insight required. The calculation in part (b) is trivial addition. This is easier than average A-level maths content, being purely procedural recall from a Decision Maths module. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Office | Room A | Room B | Room C | Room D | Room E | |
| Office | -- | 8 | 16 | 12 | 10 | 14 |
| Room A | 8 | -- | 14 | 13 | 11 | 9 |
| Room B | 16 | 14 | -- | 12 | 15 | 11 |
| Room C | 12 | 13 | 12 | -- | 11 | 8 |
| Room D | 10 | 11 | 15 | 11 | -- | 10 |
| Room E | 14 | 9 | 11 | 8 | 10 | -- |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | M1 A1 | HUSSAIN occurs before JONES. So first list is 1. ALLEN, 2. BALL, 3. COOPER, 4. EVANS, 5. HUSSAIN |
| M1 A1 | Middle is now \(\lfloor\frac{1(1+5)}{2}\rfloor = 3\) is COOPER | |
| M1 A1 | Comparison 2: HUSSAIN occurs after COOPER. So list 3 is 4. EVANS, 5. HUSSAIN. Middle is now \(\lfloor\frac{1(4+5)}{2}\rfloor = 5\) | |
| A1 (6) | Comparison 3: HUSSAIN has been found at position 5 | |
| (b) | B1 cae(1) | Maximum number of comparisons with a list of 11 names is 4 |
(a) | M1 A1 | HUSSAIN occurs before JONES. So first list is 1. ALLEN, 2. BALL, 3. COOPER, 4. EVANS, 5. HUSSAIN |
| M1 A1 | Middle is now $\lfloor\frac{1(1+5)}{2}\rfloor = 3$ is COOPER |
| M1 A1 | Comparison 2: HUSSAIN occurs after COOPER. So list 3 is 4. EVANS, 5. HUSSAIN. Middle is now $\lfloor\frac{1(4+5)}{2}\rfloor = 5$ |
| A1 (6) | Comparison 3: HUSSAIN has been found at position 5 |
(b) | B1 cae(1) | Maximum number of comparisons with a list of 11 names is 4 |
---This question should be answered on the sheet provided in the answer booklet.
A school wishes to link 6 computers. One is in the school office and one in each of rooms $A$, $B$, $C$, $D$ and $E$. Cables need to be laid to connect the computers. The school wishes to use a minimum total length of cable.
The table shows the shortest distances, in metres, between the various sites.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
& Office & Room A & Room B & Room C & Room D & Room E \\
\hline
Office & -- & 8 & 16 & 12 & 10 & 14 \\
\hline
Room A & 8 & -- & 14 & 13 & 11 & 9 \\
\hline
Room B & 16 & 14 & -- & 12 & 15 & 11 \\
\hline
Room C & 12 & 13 & 12 & -- & 11 & 8 \\
\hline
Room D & 10 & 11 & 15 & 11 & -- & 10 \\
\hline
Room E & 14 & 9 & 11 & 8 & 10 & -- \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Starting at the school office, use Prim's algorithm to find a minimum spanning tree. Indicate the order in which you select the edges and draw your final tree. [5 marks]
\item Using your answer to part (a), calculate the minimum total length of cable required. [1 mark]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2001 Q1 [6]}}