| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.8 This is a straightforward application of standard bin-packing algorithms with no problem-solving required. Part (i) and (ii) involve mechanical execution of first-fit methods on a small dataset, and part (iii) is a simple quadratic scaling calculation (doubling n means 4× time). All steps are routine recall and basic arithmetic, making this significantly easier than average A-level questions. |
| Spec | 7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Box 1: 2, 4, 2; Box 2: 3, 3; Box 3: 5; Box 4: 4 | M1, A1 [2] | For packing these seven weights into boxes with no more than 8 kg total in each box; For this packing |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Order: 5 4 4 3 3 2 2 | B1 | For putting the weights into decreasing order (may be implied from packing) |
| Box 1: 5, 3; Box 2: 4, 4; Box 3: 3, 2, 2 | M1, A1 [3] | For packing the seven weights into three boxes with no more than 8 kg total in each box; For this packing |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(15 \times 2^2 = \mathbf{60}\) seconds | M1, A1 [2] | For a correct calculation; For 60 or 60 seconds or 1 minute |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Box 1: **2, 4, 2**; Box 2: **3, 3**; Box 3: **5**; Box 4: **4** | M1, A1 [2] | For packing these seven weights into boxes with no more than 8 kg total in each box; For this packing |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Order: 5 4 4 3 3 2 2 | B1 | For putting the weights into decreasing order (may be implied from packing) |
| Box 1: **5, 3**; Box 2: **4, 4**; Box 3: **3, 2, 2** | M1, A1 [3] | For packing the seven weights into three boxes with no more than 8 kg total in each box; For this packing |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $15 \times 2^2 = \mathbf{60}$ seconds | M1, A1 [2] | For a correct calculation; For 60 or 60 seconds or 1 minute |
---1 (i) Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each.
$$\begin{array} { l l l l l l l }
2 & 4 & 3 & 3 & 2 & 5 & 4
\end{array}$$
Show clearly which weights are packed into which boxes.\\
(ii) Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.\\
(iii) First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?
\hfill \mbox{\textit{OCR D1 2006 Q1 [7]}}