| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | June |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply both algorithms and compare |
| Difficulty | Easy -1.2 This is a straightforward algorithmic application question from D1. Part (a) requires recall of two standard algorithms with no problem-solving. Parts (b)(i) and (b)(ii) involve mechanical execution of Prim's and Kruskal's algorithms on a given network—routine procedural work with no conceptual challenges or novel insights required. This is easier than average A-level maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
\begin{enumerate}[label=(\alph*)]
\item Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network.
\end{enumerate}
\includegraphics{figure_2}
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
\begin{enumerate}[label=(\roman*)]
\item Prim's algorithm,
\item Kruskal's algorithm.
\end{enumerate}
[4]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q3 [4]}}