| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Challenging +1.2 This is a standard D1 question testing Prim's algorithm in matrix form (routine application), Dijkstra's algorithm (also routine), and basic algorithmic complexity analysis. Part (i) is textbook procedure, parts (ii)-(iii) require applying two standard algorithms sequentially, and part (iv) asks for complexity which is straightforward counting (6 applications of Dijkstra, each O(n²)). While multi-part with several marks, each component is standard recall and application with no novel problem-solving required, making it slightly above average difficulty only due to length and the complexity analysis component. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | - | 10 | 7 | - | 9 | 5 |
| B | 10 | - | - | 1 | - | 4 |
| C | 7 | - | - | - | 3 | - |
| D | - | 1 | - | - | 2 | - |
| E | 9 | - | 3 | 2 | - | - |
| F | 5 | 4 | - | - | - | - |
| Answer | Marks | Guidance |
|---|---|---|
| Order of inclusion table with arcs AF, FB, BD, DE, EC and Length: 15 | M1 A1 A1 A1 B1 B1 | select; delete; order |
| Answer | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied to network showing working values, order of labelling, and labels. Arcs: AF, FB, BD, AC, AE; Length: 26 | M1 A1 A1 A1 M1 A1 | Dijkstra; working values; order of labelling; labels |
| Answer | Marks | Guidance |
|---|---|---|
| Cubic | B1 | n applications of Dijkstra, which is quadratic |
| B1 |
**(i)**
| Order of inclusion table with arcs AF, FB, BD, DE, EC and Length: 15 | M1 A1 A1 A1 B1 B1 | select; delete; order |
**(ii) & (iii)**
| Dijkstra's algorithm applied to network showing working values, order of labelling, and labels. Arcs: AF, FB, BD, AC, AE; Length: 26 | M1 A1 A1 A1 M1 A1 | Dijkstra; working values; order of labelling; labels |
**(iv)**
| Cubic | B1 | n applications of Dijkstra, which is quadratic |
| | B1 | |6 The matrix gives the lengths of the arcs of a network.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 10 & 7 & - & 9 & 5 \\
\hline
B & 10 & - & - & 1 & - & 4 \\
\hline
C & 7 & - & - & - & 3 & - \\
\hline
D & - & 1 & - & - & 2 & - \\
\hline
E & 9 & - & 3 & 2 & - & - \\
\hline
F & 5 & 4 & - & - & - & - \\
\hline
\end{tabular}
\end{center}
(i) Using the copy of the matrix in your answer book, apply the tabular form of Prim's algorithm to find a minimum connector for the network. Start by choosing vertex A and show the order in which you include vertices.\\
List the arcs in your connector and give its total length.
Serena takes a different approach to find a minimum connector. She first uses Dijkstra's algorithm to find shortest paths from A to each of the other vertices. She then uses the arcs in those paths to construct a connector.\\
(ii) Draw the network using the vertices printed in your answer book.\\
(iii) Apply Serena's method to produce a connector.
List the arcs in the connector and give its total length.
Serena adapts her method by starting from each vertex in turn, producing six connectors, from which she chooses the best.\\
(iv) Serena's approach will not find the minimum connector in all networks, but it is an algorithm. What is its algorithmic complexity? Justify your answer.
\hfill \mbox{\textit{OCR MEI D1 2008 Q6 [16]}}