AQA D2 2013 January — Question 3 9 marks

Exam BoardAQA
ModuleD2 (Decision Mathematics 2)
Year2013
SessionJanuary
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMatchings and Allocation
TypeHungarian algorithm for minimisation
DifficultyModerate -0.5 This is a standard Hungarian algorithm application question from D2, requiring systematic application of a well-defined procedure (row/column reduction, covering zeros, adjustments) to find optimal allocation. While it involves multiple steps, it's a routine algorithmic process with no conceptual insight or problem-solving required beyond following the taught method.
Spec7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort

3 Four pupils, Wendy, Xiong, Yasmin and Zaira, are each to be allocated a different memory coach from five available coaches: Asif, Bill, Connie, Deidre and Eric. Each pupil has an initial training session with each coach, and a test which scores their improvement in memory-recall produces the following results.

Question 3:
Part (a)
AnswerMarks Guidance
AnswerMarks Guidance
Subtract each value from 43 to give:
AsifBill Connie
Wendy8 5
Xiong5 6
Yasmin11 10
Zaira9 5
\(B1\)Correct modified table
Part (b)
AnswerMarks Guidance
AnswerMarks Guidance
Reduce rows: subtract row minimum from each row\(M1\) Row reduction shown
AsifBill Connie
Wendy8 5
Xiong0 1
Yasmin1 0
Zaira4 0
Reduce columns\(M1\) Column reduction shown
AsifBill Connie
Wendy8 5
Xiong0 1
Yasmin1 0
Zaira4 0
Cover zeros with minimum lines; augment\(M1\) Correct augmentation
Optimal assignment: Wendy–Connie, Xiong–Asif, Yasmin–Deidre (or Eric), Zaira–Bill\(A1\) Correct assignment
Total improvement \(= 43 + 38 + 31 + 38 = 150\)\(A1\) Correct total
# Question 3:

## Part (a)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Subtract each value from 43 to give: | | |
| | **Asif** | **Bill** | **Connie** | **Deidre** | **Eric** |
| **Wendy** | 8 | 5 | 0 | 9 | 6 |
| **Xiong** | 5 | 6 | 5 | 9 | 7 |
| **Yasmin** | 11 | 10 | 12 | 12 | 11 |
| **Zaira** | 9 | 5 | 8 | 12 | 9 |

$B1$ | Correct modified table

## Part (b)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Reduce rows: subtract row minimum from each row | $M1$ | Row reduction shown |
| | **Asif** | **Bill** | **Connie** | **Deidre** | **Eric** |
| **Wendy** | 8 | 5 | 0 | 9 | 6 |
| **Xiong** | 0 | 1 | 0 | 4 | 2 |
| **Yasmin** | 1 | 0 | 2 | 2 | 1 |
| **Zaira** | 4 | 0 | 3 | 7 | 4 |

| Reduce columns | $M1$ | Column reduction shown |
| | **Asif** | **Bill** | **Connie** | **Deidre** | **Eric** |
| **Wendy** | 8 | 5 | 0 | 7 | 5 |
| **Xiong** | 0 | 1 | 0 | 2 | 1 |
| **Yasmin** | 1 | 0 | 2 | 0 | 0 |
| **Zaira** | 4 | 0 | 3 | 5 | 3 |

| Cover zeros with minimum lines; augment | $M1$ | Correct augmentation |
| Optimal assignment: Wendy–Connie, Xiong–Asif, Yasmin–Deidre (or Eric), Zaira–Bill | $A1$ | Correct assignment |
| Total improvement $= 43 + 38 + 31 + 38 = 150$ | $A1$ | Correct total |

---
3 Four pupils, Wendy, Xiong, Yasmin and Zaira, are each to be allocated a different memory coach from five available coaches: Asif, Bill, Connie, Deidre and Eric. Each pupil has an initial training session with each coach, and a test which scores their improvement in memory-recall produces the following results.

\hfill \mbox{\textit{AQA D2 2013 Q3 [9]}}