AS October 2020 Q1
1.
| 3.7 | 2.5 | 5.4 | 1.9 | 2.7 | 3.2 | 3.1 | 2.7 | 4.2 | 2.0 |
The first-fit bin packing algorithm is to be used to pack \(n\) numbers into bins. The number of comparisons is used to measure the order of the first-fit bin packing algorithm.
| Scheme | Marks | AO |
|---|---|---|
| Bin 1: \(\boxed{3.7}\) \(\boxed{2.5}\) \(\boxed{1.9}\) Bin 2: \(\boxed{5.4}\) \(\underline{2.7}\) Bin 3: \(\underline{3.2}\) \(\underline{3.1}\) 2.0 Bin 4: \(\underline{2.7}\) 4.2 | M1 A1 A1 | 1.1b 1.1b 1.1b |
| (3) |
Notes
M1: First four items placed correctly (the values in boxes) with at least eight values placed – allow cumulative totals for M1 only
A1: First eight items placed correctly (the values in boxes and underlined) – no repeated values
A1: CSO (so no repeated values)
| Scheme | Marks | AO |
|---|---|---|
| In the worst case the second number must be compared with the first number so 1 comparison, then the third number must be compared with the first and second numbers so 2 comparisons… so, in total there are 1 + 2 + 3 + … + (\(n\) – 1) comparisons in total | M1 | 2.1 |
| \(1 + 2 + \ldots + (n - 1) = \dfrac{1}{2}(n - 1)n\) | A1 | 2.2a |
| \(\dfrac{1}{2}(n - 1)n\) so quadratic order | B1 | 1.1b |
| (3) | ||
| (6 marks) |
Notes
M1: Considers the correct worst case and attempts to sum the total number of comparisons in the first (\(n\) – 1) comparisons – this mark can be implied by the correct summation
A1: Correct sum evaluation seen or implied from a correct simplified formula together with the correct method for determining the total number of comparisons in the worst case
For those candidates who simply state that the total number of comparisons is \(\dfrac{1}{2}n(n - 1)\) then M1A0
As a minimum for M1A1 accept (total comparisons =) \(\displaystyle\sum_{r=1}^{n-1} r = \frac{1}{2}n(n - 1)\) (or considers 1 + 2 + … + (\(n\) – 1) together with the correct expression for this sum)
B1: Or equivalent e.g. order \(n^2\), O(\(n^2\)), etc. (this mark is independent of the previous M and A mark)