| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.3 This is a straightforward application of two standard bin-packing algorithms (first-fit and first-fit decreasing) with small numbers and clear instructions. The question requires only mechanical execution of learned procedures with no problem-solving insight, plus a simple practical observation. Significantly easier than average A-level maths questions. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| Mr Adams: | 10 | 4 | 2 | |||
| Mrs Adams: | 13 | 3 | 7 | 5 | 2 | 4 |
| Sarah Adams: | 5 | 8 | 2 | 5 | ||
| Tim Adams: | 10 | 5 | 3 | 5 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: First bundle: \(10, 4, 2\) and at least one more bag. Second bundle correct. All bundles correct. | M1, M1, A1 | A value missing from written out list may be treated as a misread and lose the A mark only. Sorting into decreasing order may be implied from first bundle starting with 13. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Decreasing order: \(10, 10, 8, 7, 5, 5, 5, 5, 4, 4, 3, 3, 3, 2, 2, 2\). Second and third bundles: \(13, 10, 2\) and \(10, 8, 7\) and \(5, 5, 5, 5\) and \(4, 4, 3, 3, 3, 2, 2\) respectively. | M1, M1, A1 | Sorting into decreasing order may be implied from first bundle starting with 13. If each row sorted, award M1 only. Second and third bundles correct. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Each person has roughly the same number of bags or the total weights are more evenly spread. | B1 | Saying that (i) gives a more even/equal allocation. Five bundles in either part: B0. |
**(i)**
Answer: First bundle: $10, 4, 2$ and at least one more bag. Second bundle correct. All bundles correct. | M1, M1, A1 | A value missing from written out list may be treated as a misread and lose the A mark only. Sorting into decreasing order may be implied from first bundle starting with 13.
**(ii)**
Answer: Decreasing order: $10, 10, 8, 7, 5, 5, 5, 5, 4, 4, 3, 3, 3, 2, 2, 2$. Second and third bundles: $13, 10, 2$ and $10, 8, 7$ and $5, 5, 5, 5$ and $4, 4, 3, 3, 3, 2, 2$ respectively. | M1, M1, A1 | Sorting into decreasing order may be implied from first bundle starting with 13. If each row sorted, award M1 only. Second and third bundles correct.
**(iii)**
Answer: Each person has roughly the same number of bags or the total weights are more evenly spread. | B1 | Saying that (i) gives a more even/equal allocation. Five bundles in either part: B0.
**Total: 7**
---1 An airline allows each passenger to carry a maximum of 25 kg in luggage. The four members of the Adams family have bags of the following weights (to the nearest kg ):
\begin{center}
\begin{tabular}{ l r l l l l l }
Mr Adams: & 10 & 4 & 2 & & & \\
Mrs Adams: & 13 & 3 & 7 & 5 & 2 & 4 \\
Sarah Adams: & 5 & 8 & 2 & 5 & & \\
Tim Adams: & 10 & 5 & 3 & 5 & 3 & \\
\end{tabular}
\end{center}
The bags need to be grouped into bundles of 25 kg maximum so that each member of the family can carry a bundle of bags.\\
(i) Use the first-fit method to group the bags into bundles of 25 kg maximum. Start with the bags belonging to Mr Adams, then those of Mrs Adams, followed by Sarah and finally Tim.\\
(ii) Use the first-fit decreasing method to group the same bags into bundles of 25 kg maximum.\\
(iii) Suggest a reason why the grouping of the bags in part (i) might be easier for the family to carry.
\hfill \mbox{\textit{OCR D1 2007 Q1 [7]}}