A2 October 2021 Q5
5.
| 30 | 12 | 5 | 2 | 23 | 18 | 36 | 10 | 15 | 24 |
The ten numbers are to be packed into bins of size \(n\), where \(n\) is a positive integer.
When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained.
| Bin 1: | 30 12 2 |
| Bin 2: | 5 23 10 |
| Bin 3: | 18 15 |
| Bin 4: | 36 |
| Bin 5: | 24 |
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
e.g., middle right pivot(s)
| M1 A1 A1ft A1 | 1.1b 1.1b 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||
| (4) |
Notes
(a) M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). If only choosing one pivot per iteration then max of M1 only – Bubble sort is not a MR and scores M0
A1: First pass correct and next pivots chosen correctly for the second pass (but the second pass does not need to be correct)
A1ft: Second and third passes correct (follow through from their first pass and choice of pivots). They do not need to be choosing a pivot for the fourth pass for this mark
A1: cso (correct solution only – all previous marks in this part must have been awarded) including ‘sort complete’ statement
If list sorted into ascending order then mark as a MR
Middle left pivot(s)
| 30 | 12 | 5 | 2 | 23 | 18 | 36 | 10 | 15 | 24 |
| 30 | 36 | 24 | \(\underline{23}\) | 12 | 5 | 2 | 18 | 10 | 15 |
| \(\underline{36}\) | 30 | 24 | \(\underline{23}\) | 12 | 5 | 18 | 10 | 15 | \(\underline{2}\) |
| \(\underline{36}\) | \(\underline{30}\) | 24 | \(\underline{23}\) | \(\underline{18}\) | 12 | 5 | 10 | 15 | \(\underline{2}\) |
| \(\underline{36}\) | \(\underline{30}\) | 24 | \(\underline{23}\) | \(\underline{18}\) | 12 | 10 | 15 | \(\underline{5}\) | \(\underline{2}\) |
| \(\underline{36}\) | \(\underline{30}\) | 24 | \(\underline{23}\) | \(\underline{18}\) | 12 | 15 | \(\underline{10}\) | \(\underline{5}\) | \(\underline{2}\) |
| \(\underline{36}\) | \(\underline{30}\) | 24 | \(\underline{23}\) | \(\underline{18}\) | 15 | \(\underline{12}\) | \(\underline{10}\) | \(\underline{5}\) | \(\underline{2}\) |
Therefore, the sort is complete
| Scheme | Marks | AO |
|---|---|---|
| The 5 has been put in Bin 2 rather than Bin 1 which indicates that the size of the bins is less than 30 + 12 + 5 = 47 and so therefore \((42 \leqslant n) \leqslant 46\) | B1 | 3.1a |
| The fact that there is still room for the 2 in Bin 1 indicates that \(n \geqslant 44\) | B1 | 2.4 |
| The 18 cannot fit in Bin 2 and so therefore \(n \lt 5 + 23 + 18 = 46\) which implies that \(n\) is either 44 or 45 | B1 | 2.2a |
| (3) |
Notes
(b) B1: Correct reasoning why \(n \leqslant 46\) or \(n \lt 47\) or \(n \leqslant 45\) or \(n \lt 46\) - condone an argument which is mathematical in nature only e.g., \(n \lt 30 + 12 + 5\) or \(n \lt 5 + 23 + 18\)
B1: Correct reasoning why \(n \geqslant 44\) - condone ‘largest bin filled is 44 so \(n \geqslant 44\)’ or other similar mathematical argument. This mark can be awarded for an argument which is mathematical in nature only e.g., \(n \geqslant 30 + 12 + 2\)
B1: Completely correct reasoning for why n is either 44 or 45 only – this mark is dependent on the two previous B marks and must give sufficient detail (so an argument that contains no clear explanation of why certain inequalities hold cannot score this mark)
| Scheme | Marks | AO | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| M1 A1 A1 | 1.1b 1.1b 1.1b | ||||||||
| (3) | ||||||||||
| (10 marks) |
Notes
No MR or follow through in this part
(c) M1: First five values placed correctly - with at least eight values placed (the squared values)
A1: First eight values places correctly with no additional/repeated values (the squared and underlined values)
A1: cso - no additional/repeated values