Moderate -0.8 This is a straightforward application of standard algorithms (first-fit, quicksort, first-fit decreasing) with small datasets requiring minimal problem-solving. The procedures are mechanical and well-practiced in D1, making this easier than average A-level maths questions which typically involve more conceptual understanding or multi-step reasoning.
e.g. 6.8/2 = 3.4 so yes a minimum of 4 bins is needed
B1
(1)
Notes for Question 2:
- a1M1: First four items placed correctly and at least six values put in bins. (Condone cumulative totals here only.)
- a1A1: Bin 1 correct
- a2A1: CSO All correct
- b1M1: Quick sort – pivot, p. chosen (must be choosing middle left or right – choosing first/last item as the pivot M0) and first pass gives >p, p, <p. So after the first pass the list should read (values greater than the pivot), pivot, (values less than the pivot). If only choosing 1 pivot per iteration M1 only
- b1A1: First pass correct, next two pivots chosen consistently for second pass.
- b2A1ft: second and third pivots correct (if from their first pass and choice of pivots) – need not be choosing pivots for the fourth pass for this mark.
- b3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including 'sort complete' – this could be shown by the final list being re-written or 'sorted' statement or each item being used as a pivot.
- c1M1: Must be using 'sorted' list in descending order. First four items placed correctly and at least six values put in bins. (Condone cumulative totals here only.)
- c1A1: First seven items placed correctly (so Bin 1 and 2 correct, Bin 3 containing 0.9 and 0.7 and Bin 4 containing 0.6)
- c2A1: CSO
SC for part (c): If 'sorted' list is wrong from part (b) (i.e. one error e.g. a missing number, an extra number or one number incorrectly placed) then award M1 only in (c) for their first seven items correctly placed.
d1B1: A conclusion based on their answer to part (c) together with either a correct lower bound calculation or based on the total > 6 or full bins (three of the bins are full in part (c)).
| Bin 1: 0.6 0.2 0.4 0.5 0.1 | Bin 3: 1.6 | M1 A1 A1 (3) |
|Bin 2: 1.5 0.3|Bin 4: 0.7 0.9| | |
| | | 11 marks |
| $\begin{array}{|c|c|c|c|c|c|c|c|c|l|} \hline 0.6 & 1.5 & 1.6 & 0.2 & 0.4 & 0.5 & 0.7 & 0.1 & 0.9 & 0.3 \text{ pivot } 0.5 \\ 0.6 & 1.5 & \underline{1.6} & 0.7 & 0.9 & 0.5 & 0.2 & 0.4 & 0.1 & 0.3 \text{ pivots } 1.6 \text{ } 0.1 \\ 1.6 & 0.6 & 1.5 & \underline{0.7} & 0.9 & 0.5 & 0.2 & 0.4 & 0.3 & 0.1 \text{ pivots } 0.7 \text{ } 0.4 \\ \underline{1.6} & 1.5 & 0.9 & \underline{0.7} & 0.6 & 0.5 & 0.4 & 0.2 & 0.3 & 0.1 \text{ pivots } 0.9 \text{ } 0.3 \text{ } (0.6) \\ \underline{1.6} & 1.5 & 0.9 & \underline{0.7} & 0.6 & 0.5 & 0.4 & 0.3 & 0.2 & 0.1 \text{ sort complete } \\ \hline \end{array}$ | M1 A1 A1ft A1ft A1cso | (4) |
| Bin 1: $1.6$ 0.4 | Bin 2: $1.5$ 0.5 | Bin 3: $0.9$ 0.7 0.3 0.1 | Bin 4: 0.6 0.2 | M1 A1 A1 (3) |
| | | |
| e.g. 6.8/2 = 3.4 so yes a minimum of 4 bins is needed | B1 | (1) |
**Notes for Question 2:**
- a1M1: First four items placed correctly and at least six values put in bins. (Condone cumulative totals here only.)
- a1A1: Bin 1 correct
- a2A1: CSO All correct
- b1M1: Quick sort – pivot, p. chosen (must be choosing middle left or right – choosing first/last item as the pivot M0) and first pass gives >p, p, <p. So after the first pass the list should read (values greater than the pivot), pivot, (values less than the pivot). **If only choosing 1 pivot per iteration M1 only**
- b1A1: First pass correct, next two pivots chosen consistently for second pass.
- b2A1ft: second and third pivots correct (if from their first pass and choice of pivots) – need not be choosing pivots for the fourth pass for this mark.
- b3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including 'sort complete' – this could be shown by the final list being re-written or 'sorted' statement or each item being used as a pivot.
- c1M1: Must be using 'sorted' list in descending order. First four items placed correctly and at least six values put in bins. (Condone cumulative totals here only.)
- c1A1: First seven items placed correctly (so Bin 1 and 2 correct, Bin 3 containing 0.9 and 0.7 and Bin 4 containing 0.6)
- c2A1: CSO
**SC for part (c):** If 'sorted' list is wrong from part (b) (i.e. one error e.g. a missing number, an extra number or one number incorrectly placed) then award M1 only in (c) for their first seven items correctly placed.
**d1B1:** A conclusion based on their answer to part (c) together with either a correct lower bound calculation or based on the total > 6 or full bins (three of the bins are full in part (c)).
---
2.\\
0.6\\
0.2\\
0.4\\
0.5\\
0.7\\
0.1\\
0.9\\
0.3\\
1.5\\
1.6
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.\\
(3)
\item The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.
\item Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2 .
\item Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q2 [11]}}