Easy -1.2 This is a standard D1 algorithm application question requiring mechanical execution of first-fit bin packing, quicksort, and binary search with no problem-solving or insight needed. The algorithms are applied exactly as taught, with straightforward arithmetic (adding decimals to check bin capacity) and the optimality explanation in part (d) is a textbook result about lower bounds.
Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14
The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14
Explain why the number of bins used in part (c) is optimal.
Use the binary search algorithm to try to locate 3.0 in the list of numbers.
Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.
Bin 1: 5.2 4.7 3.1; Bin 2: 6.5 4.5 1.8 1.2; Bin 3: 5.1 2.9 3.4; Bin 4: 3.8
M1 A1 A1(3)
1(b)
Pivots: 5.1, 2.9, 6.5 (middle right) or 5.1, 1.8, 2.9, 3.4, 3.8, 1.2 (middle left) with items sorted correctly
M1, A1, A1 (with ft), A1 (4)
1(c)
Bin 1: 6.5 5.2 1.8; Bin 2: 5.1 4.7 3.8; Bin 3: 4.5 3.4 3.1 2.9; Bin 4: 1.2
M1 A1 (ft), A1(3)
1(d)
\(\frac{1.2+1.8+\cdots+6.5}{14} = \frac{42.2}{14} = 3.01\ldots\) so a minimum of 4 bins is required and (c) is optimal
B1 (1)
1(e)
\(\left\lfloor\frac{1+11}{2}\right\rfloor = 6\) 3.8 > 3.0 so reject 3.8 to 6.5 (or reject 6th to 11th items); \(\left\lfloor\frac{1+5}{2}\right\rfloor = 3\) 2.9 < 3.0 so reject 1.2 to 2.9 (or reject 1st to 3rd item); \(\left\lfloor\frac{4+5}{2}\right\rfloor = 5\) 3.4 > 3.0 so reject 3.4 (or reject 5th item); [4] = 4 3.1 is not 3.0 so 3.0 not found
M1, A1 (ft), A1 (3)
| Part | Answer/Working | Marks | Guidance |
|------|---|---|---|
| 1(a) | Bin 1: 5.2 4.7 3.1; Bin 2: 6.5 4.5 1.8 1.2; Bin 3: 5.1 2.9 3.4; Bin 4: 3.8 | M1 A1 A1(3) | The correct first five items placed correctly (the bold values) and at least eight values placed in bins (allow repeated values). Condone cumulative totals for M1 only |
| 1(b) | Pivots: 5.1, 2.9, 6.5 (middle right) or 5.1, 1.8, 2.9, 3.4, 3.8, 1.2 (middle left) with items sorted correctly | M1, A1, A1 (with ft), A1 (4) | Quick sort using all 11 numbers (condone one slip), 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 less than the pivot), pivot, (values greater than the pivot). If only choosing one pivot per iteration then M1 only. Bubble sort is M0. First and second passes correct and pivots correctly chosen for third pass |
| 1(c) | Bin 1: 6.5 5.2 1.8; Bin 2: 5.1 4.7 3.8; Bin 3: 4.5 3.4 3.1 2.9; Bin 4: 1.2 | M1 A1 (ft), A1(3) | Their six largest items placed correctly and at least eight values placed in bins (if correct this will be the bold items but must check their packing if any of their six largest values are incorrect). Condone cumulative totals for M1 only. First-fit increasing scores no marks in this part. If no sort seen in (b) then mark (c) assuming the correct ordered list is being used |
| 1(d) | $\frac{1.2+1.8+\cdots+6.5}{14} = \frac{42.2}{14} = 3.01\ldots$ so a minimum of 4 bins is required and (c) is optimal | B1 (1) | CAO using either a correct lower bound calculation (accept awrt 3.01 without seeing the full calculation) or spare capacity in the first 3 bins (e.g. total spare in first three bins is $0.5 + 0.4 + 0.1 = 1$, so cannot fit into 3 bins); note that the conclusion of optimal or states using the minimum number of bins (dependent on scoring at least M1 in (c)) |
| 1(e) | $\left\lfloor\frac{1+11}{2}\right\rfloor = 6$ 3.8 > 3.0 so reject 3.8 to 6.5 (or reject 6th to 11th items); $\left\lfloor\frac{1+5}{2}\right\rfloor = 3$ 2.9 < 3.0 so reject 1.2 to 2.9 (or reject 1st to 3rd item); $\left\lfloor\frac{4+5}{2}\right\rfloor = 5$ 3.4 > 3.0 so reject 3.4 (or reject 5th item); [4] = 4 3.1 is not 3.0 so 3.0 not found | M1, A1 (ft), A1 (3) | Must be using their sorted list. Choosing their middle pivot (3.8) and an attempt at discarding/retaining half the list (condone if retaining the wrong half of the list) (If pivot is retained at any stage M1 only). The actual rejections may be shown as values from the list or the positions in the list. First and second passes correct for their list i.e. selecting the 6th item in the first pass and using 1st to 5th items in the second pass (must not be using the 6th item for the second pass) and then correctly selecting the 3rd item (the 2.9) in the second pass and rejecting the 1st to 3rd items. Candidates may either compare 3.0 with the actual values or the positions of items in a correctly sorted list. Comparisons may be implied by the choice of the correct item and corresponding rejection. If a candidate renumbers the list after a pass check the position numbers and values carefully. CSO—must be the correct values with the search completed correctly (so rejecting the 3.4 in the third pass) together with "not found". |
---
1.
\begin{center}
\begin{tabular}{ l l l l l l l l l l l }
5.2 & 4.7 & 6.5 & 4.5 & 3.1 & 5.1 & 1.8 & 2.9 & 3.4 & 3.8 & 1.2 \\
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14
\item The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
\item Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14
\item Explain why the number of bins used in part (c) is optimal.
\item Use the binary search algorithm to try to locate 3.0 in the list of numbers.
Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2024 Q1 [14]}}