A2 October 2020 Q5
5. The nine distinct numbers in the following list are to be packed into bins of size 50
| 23 | 17 | 19 | \(x\) | 24 | 8 | 18 | 10 | 21 |
When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation.
| Bin 1: | 23 17 8 |
| Bin 2: | 19 \(x\) 10 |
| Bin 3: | 24 18 |
| Bin 4: | 21 |
The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is
| 23 | 19 | 17 | 24 | \(x\) | 18 | 10 | 21 | 8 |
When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation.
| Bin 1: | 24 23 |
| Bin 2: | 21 19 10 |
| Bin 3: | 18 17 \(x\) |
| Bin 4: | 8 |
Given that only one of the bins is full and that \(x\) is an integer,
| Scheme | Marks | AO |
|---|---|---|
| If \(x\) has been placed in Bin 2 then \(10 \lt x \leqslant 31\) - this is because Bin 1 at this stage only contains 40 and before \(x\) had been placed in Bin 2 it only contained 19 | ||
| As the 18 has been placed in Bin 3 this implies that \(x \gt 50 - (19 + 18)\) so \(x \gt 13\) | B1 | 3.1a |
| As the 10 has been placed in Bin 2 after the \(x\) then \(x \leqslant 50 - (19 + 10)\) so \(x \leqslant 21\) | B1 | 2.4 |
| However, the number are all distinct and therefore \(13 \lt x \lt 21\) | B1 | 2.2a |
| (3) |
Notes
(a) B1: Correct reasoning of why \(x \gt 13\) accept \(x \gt 50 - (19 + 18)\)
B1: Correct explanation of why \(x \leqslant 21\) accept \(x \leqslant 50 - (19 + 10)\)
B1: Correct deduction that \(13 \lt x \lt 21\) must mention that the numbers are distinct (oe)
| Scheme | Marks | AO |
|---|---|---|
| \(13 \lt x \lt 17\) | B1 B1 | 2.2a 2.2a |
| (2) |
Notes
(b) B1: Use first complete pass to deduce that \(x \lt 17\)
B1: Correct lower bound of \(x \gt 13\)
| Scheme | Marks | AO |
|---|---|---|
| If \(x\) has been placed in Bin 3 then this implies that \(x \leqslant 15\) | M1 | 2.4 |
| So \(x\) is either 14 or 15 – but as Bin 2 is full \(\Rightarrow x = 14\) | A1 | 2.2a |
| (2) | ||
| (7 marks) |
Notes
(c) M1: Using first-fit decreasing in an attempt to derive new upper bound for \(x\) (so either for stating both \(x\) could equal 14 or 15, \(x \leqslant 15\) or \(x \lt 15\))
A1: Correct deduction that \(x = 14\) (must clearly state or imply that Bin 2 is full)