| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2003 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm with clear tabular data and standard steps. Part (a) requires mechanical execution of a well-defined algorithm (row reduction, column reduction, covering zeros, finding allocation), while part (b) tests basic understanding that maximisation requires converting to minimisation by subtracting from the maximum value. No novel insight or complex problem-solving is needed—just careful arithmetic and following the algorithm procedure taught in D2. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | Talk I | Talk II | Talk III | Talk IV |
| Clive | 12 | 34 | 28 | 16 |
| Julie | 13 | 32 | 36 | 12 |
| Nicky | 15 | 32 | 32 | 14 |
| Steve | 11 | 33 | 36 | 10 |
| Answer | Marks | Guidance |
|---|---|---|
| (a)(i) | Either rows then columns or columns then rows. Rows then columns: 3 lines only needed. Columns then rows: 3 lines only needed (or least element 1 so least uncovered 1) | M1, A1, A1 |
| Alternative approach (columns then rows): 3 lines only needed and either row 1 or column 3 | M1, A1 | - |
| If row 1: least uncovered 2 → if column 3: least uncovered 1 → then least uncovered 1 | M1 A1 M1 A1 | 6 |
| (ii) | C – III, J – I or IV, N – II, S – IV or I. 83 minutes ∴ 11.23 a.m. | M1 A1 M1 A1 |
| (b) | Subtracting all entries from some \(n \geq 36\) (stated). e.g. subtractions from 36 | M1 A2, 1, 0 |
(a)(i) | Either rows then columns or columns then rows. Rows then columns: 3 lines only needed. Columns then rows: 3 lines only needed (or least element 1 so least uncovered 1) | M1, A1, A1 | 3 |
Alternative approach (columns then rows): 3 lines only needed and either row 1 or column 3 | M1, A1 | - |
If row 1: least uncovered 2 → if column 3: least uncovered 1 → then least uncovered 1 | M1 A1 M1 A1 | 6 |
(ii) | C – III, J – I or IV, N – II, S – IV or I. 83 minutes ∴ 11.23 a.m. | M1 A1 M1 A1 | 4 |
(b) | Subtracting all entries from some $n \geq 36$ (stated). e.g. subtractions from 36 | M1 A2, 1, 0 | 3 |3. Talkalot College holds an induction meeting for new students. The meeting consists of four talks: I (Welcome), II (Options and Facilities), III (Study Tips) and IV (Planning for Success). The four department heads, Clive, Julie, Nicky and Steve, deliver one of these talks each. The talks are delivered consecutively and there are no breaks between talks. The meeting starts at 10 a.m. and ends when all four talks have been delivered. The time, in minutes, each department head takes to deliver each talk is given in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & Talk I & Talk II & Talk III & Talk IV \\
\hline
Clive & 12 & 34 & 28 & 16 \\
\hline
Julie & 13 & 32 & 36 & 12 \\
\hline
Nicky & 15 & 32 & 32 & 14 \\
\hline
Steve & 11 & 33 & 36 & 10 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the Hungarian algorithm to find the earliest time that the meeting could end. You must make your method clear and show
\begin{enumerate}[label=(\roman*)]
\item the state of the table after each stage in the algorithm,
\item the final allocation.
\end{enumerate}\item Modify the table so it could be used to find the latest time that the meeting could end.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2003 Q3 [13]}}