| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Standard +0.3 This is a straightforward application of the Hungarian algorithm with a standard modification for unequal sets (adding a dummy row). The algorithm itself is mechanical and well-practiced in D2, requiring only careful arithmetic and following the standard procedure. The context is clear and the table is small (5×4), making it easier than average A-level questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Phil | Quin | Ros | Sue | Tim | |
| Topic A | 18 | 15 | 19 | 20 | 17 |
| Topic B | 23 | 24 | 22 | 25 | 23 |
| Topic C | 20 | 16 | 18 | 22 | 19 |
| Topic D | 21 | 17 | 18 | 23 | 20 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Add extra row with all values equal (usually \(+25\) and below rest) | B1 | Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Reduce columns first | M1 | Do not award if full row of zeros added |
| Correct column-reduced matrix | A1 | |
| Reduce rows next | M1 | These 2 marks available for those who reduce row first |
| Correct fully reduced matrix (one error only) | \(\text{A1}\sqrt{}\) | |
| Covering zeros requires 3 lines; adjust with least entry remaining being 1 | M1 | SC if full row of zeros: award M1 for further stage, A1 for final correct matrix |
| Correct adjusted matrix (ft one error only) | \(\text{A1}\sqrt{}\) | |
| Match: A–Tim; B–Phil; C–Quin; D–Ros | B1 | |
| \(\text{Min time} = 17+23+16+18 = 74\) secs | B1 | Total: 8 |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Add extra row with all values equal (usually $+25$ and below rest) | B1 | Total: 1 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Reduce columns first | M1 | Do not award if full row of zeros added |
| Correct column-reduced matrix | A1 | |
| Reduce rows next | M1 | These 2 marks available for those who reduce row first |
| Correct fully reduced matrix (one error only) | $\text{A1}\sqrt{}$ | |
| Covering zeros requires 3 lines; adjust with least entry remaining being 1 | M1 | SC if full row of zeros: award M1 for further stage, A1 for final correct matrix |
| Correct adjusted matrix (ft one error only) | $\text{A1}\sqrt{}$ | |
| Match: A–Tim; B–Phil; C–Quin; D–Ros | B1 | |
| $\text{Min time} = 17+23+16+18 = 74$ secs | B1 | Total: 8 |
---2 Four of the five students Phil, Quin, Ros, Sue and Tim are to be chosen to make up a team for a mathematical relay race. The team will be asked four questions, one each on the topics A, B, C and D. A different member of the team will answer each question. Each member has to give the correct answer to the question before the next question is asked. The team with the least overall time wins.\\
The average times, in seconds, for each student in some practice questions are given below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Phil & Quin & Ros & Sue & Tim \\
\hline
Topic A & 18 & 15 & 19 & 20 & 17 \\
\hline
Topic B & 23 & 24 & 22 & 25 & 23 \\
\hline
Topic C & 20 & 16 & 18 & 22 & 19 \\
\hline
Topic D & 21 & 17 & 18 & 23 & 20 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
\item Use the Hungarian algorithm, reducing columns first, then rows, to decide which four students should be chosen for the team. State which student should be allocated to each topic and state the total time for the four students on the practice questions using this matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q2 [9]}}