A2 June 2024 Q1
1.
| 17 | 8 | 16 | 12 | 24 | 19 | 23 | 11 | 20 | 13 | 4 |
The eleven numbers listed above 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 eleven numbers, the bins are packed as shown below.
| Bin 1: | 17 8 12 |
| Bin 2: | 16 24 |
| Bin 3: | 19 11 4 |
| Bin 4: | 23 13 |
| Bin 5: | 20 |
The original list of eleven numbers is to be sorted into descending order.
| Scheme | Marks | AO |
|---|---|---|
| The 16 was not placed in Bin 1 indicating that \(n \lt 41\) (= 17 + 8 + 16), or the 4 was not placed in Bin 1 indicating that \(n \lt 41\ (17 + 8 + 12 + 4)\) Bin 2 contains 40 (= 16 + 24) so therefore \(n = 40\) | B1 | 2.4 |
| (1) |
Notes
B1: CAO – clear indication that the 16 was not placed in Bin 1 accept sight of \(n \lt (17 + 8 + 16)\) or that the 4 was not placed in Bin 1 \(n \lt (17 + 8 + 12 + 4)\) and that Bin 2 contains a total of 40.
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
e.g. Middle Right
| M1 A1 A1ft A1 | 1.1b 1.1b 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
e.g. Middle Left
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (4) |
Notes
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 If they make a slip with one value (one slip, one missing or one extra) at the start they can score M1 A0 A1ft A0
A1: First two passes correct and pivots chosen for third pass
A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots – if an error oversimplifies so that after 3 passes all sublists are of length 1 A0)
A1: CSO (correct solution only – all previous marks in this part must have been awarded)
SC: If the list is sorted in ascending order, then award a maximum of M1A1A0A0 (so 2 marks) as in the scheme above even if the list is re-ordered after the sort is complete
Sort ascending for reference Middle Right
| 17 | 8 | 16 | 12 | 24 | 19 | 23 | 11 | 20 | 13 | 4 | 19 |
| 17 | 8 | 16 | 12 | 11 | 13 | 4 | \(\underline{\text{19}}\) | 24 | 23 | 20 | 12, 23 |
| 8 | 11 | 4 | \(\underline{\text{12}}\) | 17 | 16 | 13 | \(\underline{\text{19}}\) | 20 | \(\underline{\text{23}}\) | 24 | 11, 16 |
| 8 | 4 | \(\underline{\text{11}}\) | \(\underline{\text{12}}\) | 13 | \(\underline{\text{16}}\) | 17 | \(\underline{\text{19}}\) | 20 | \(\underline{\text{23}}\) | 24 | 4 |
| \(\underline{\text{4}}\) | 8 | \(\underline{\text{11}}\) | \(\underline{\text{12}}\) | 13 | \(\underline{\text{16}}\) | 17 | \(\underline{\text{19}}\) | 20 | \(\underline{\text{23}}\) | 24 |
Middle left
| 17 | 8 | 16 | 12 | 24 | 19 | 23 | 11 | 20 | 13 | 4 | 19 |
| 17 | 8 | 16 | 12 | 11 | 13 | 4 | \(\underline{\text{19}}\) | 24 | 23 | 20 | 12, 23 |
| 8 | 11 | 4 | \(\underline{\text{12}}\) | 17 | 16 | 13 | \(\underline{\text{19}}\) | 20 | \(\underline{\text{23}}\) | 24 | 11, 16 |
| 8 | 4 | \(\underline{\text{11}}\) | \(\underline{\text{12}}\) | 13 | \(\underline{\text{16}}\) | 17 | \(\underline{\text{19}}\) | 20 | \(\underline{\text{23}}\) | 24 | 8 |
| 4 | \(\underline{\text{8}}\) | \(\underline{\text{11}}\) | \(\underline{\text{12}}\) | 13 | \(\underline{\text{16}}\) | 17 | \(\underline{\text{19}}\) | 20 | \(\underline{\text{23}}\) | 24 |
| Scheme | Marks | AO |
|---|---|---|
| Bin 1: 24 16 Bin 2: 23 17 Bin 3: 20 19 Bin 4: 13 12 11 4 Bin 5: 8 | M1 A1 | 1.1b 1.1b |
| (2) | ||
| (7 marks) |
Notes
(c) NO MISREADS MARK EXACTLY TO THE SCHEME
M1: First 6 values placed correctly (the bold values) with at least 8 values placed in bins
A1: CSO so no additional/repeated values