| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2023 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bin Capacity Constraints |
| Difficulty | Standard +0.3 This is a multi-part bin packing question requiring systematic application of standard algorithms (first-fit, first-fit decreasing) and basic reasoning about capacity constraints. While it has multiple parts and requires careful bookkeeping, each step follows routine procedures taught in FD1 with no novel problem-solving insight needed. The constraint reasoning in parts (a), (b), and (e) involves straightforward arithmetic inequalities rather than creative mathematical thinking. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(132 + x > 120\) for all positive values of \(x\), therefore 3 bins is not possible | B1 | Correct reasoning why 3 bins not possible or at least 4 bins required. Accept: lower bound \(= \frac{156}{40} = 3.9\) so 3 not possible; if \(x > 23\) then \(132 + x \geq 156\) and \(\frac{156}{40} = 3.9\); 4 values are at least half capacity (20, 22, 23 and \(x\)) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(23 < x \leqslant 28\) | B1 | One correct inequality (\(x > 23\), \(x \geq 24\), \(x \leqslant 28\) or \(x < 29\)) |
| B1 | CAO: \(23 < x \leqslant 28\) or \(24 \leqslant x \leqslant 28\) or 29 with strict inequality |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Bin 1: 15, <u>22</u>, 3 | M1 | First five values placed correctly (underlined) and \(x\) not in Bin 1 or 2; at least eight values placed |
| Bin 2: 9, <u>23</u>, [5] | A1 | First eight values placed correctly (underlined and boxed) with no repeated values |
| Bin 3: \(x\), [4] | A1 | CSO — no additional/repeated values |
| Bin 4: 18, 20 | NO MISREADS — mark exactly to scheme; if \(x\) given a value then M1 only | |
| Bin 5: 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Pass 1: \(\underline{x}\), 15, 22, 3, 9, 23, 5, 4, 18, 20, 13 | M1 | Quick sort; pivot chosen must be middle left or right — choosing first/last item as pivot is M0. After first pass list must read (values \(>\) pivot), pivot, (values \(<\) pivot) |
| Pass 2: \(\underline{x}\), <u>23</u>, 15, 22, 9, 18, 20, 13, <u>5</u>, 3, 4 | A1 | First two passes correct (pivots for third pass need not be chosen) |
| Pass 3: \(\underline{x}\), <u>23</u>, 22, 20, <u>18</u>, 15, 9, 13, <u>5</u>, <u>4</u>, 3 | A1ft | Third and fourth passes correct (follow through from second pass); after second pass list must contain 10, 11 or 12 numbers |
| Pass 4: \(\underline{x}\), <u>23</u>, 22, <u>20</u>, <u>18</u>, 15, 13, <u>9</u>, <u>5</u>, <u>4</u>, 3 | ||
| Pass 5: \(\underline{x}\), <u>23</u>, <u>22</u>, <u>20</u>, <u>18</u>, <u>15</u>, <u>13</u>, <u>9</u>, <u>5</u>, <u>4</u>, <u>3</u> | A1 | CSO — all previous marks must have been awarded; both middle-left and middle-right require six passes. SC: if sorted ascending, award max M1A1A0A0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Attempt at first-fit decreasing (correct order): Bin 1: \(x\); Bin 2: 23, 15; Bin 3: 22, 18; Bin 4: 20, 13. If 15 cannot go in Bin 1 then \(x > 25\); if 13 cannot go in Bin 1 then \(x > 27\) | B1 | Any clear indication that 15 does not fit in Bin 1 so \(x + 15 > 40\) (condone just stating \(x > 25\)), or 13 does not fit in Bin 1 so \(x + 13 > 40\) (condone just stating \(x > 27\)) |
| Therefore \(x\) must be 28 | dB1 | Correct answer \(x = 28\); dependent on previous B mark and correct upper bound of 28 in (b). Accept \(x + 13 > 40 \Rightarrow x > 27\) so \(x = 28\) |
# Question 4:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $132 + x > 120$ for all positive values of $x$, therefore 3 bins is not possible | B1 | Correct reasoning why 3 bins not possible or at least 4 bins required. Accept: lower bound $= \frac{156}{40} = 3.9$ so 3 not possible; if $x > 23$ then $132 + x \geq 156$ and $\frac{156}{40} = 3.9$; 4 values are at least half capacity (20, 22, 23 and $x$) |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| $23 < x \leqslant 28$ | B1 | One correct inequality ($x > 23$, $x \geq 24$, $x \leqslant 28$ or $x < 29$) |
| | B1 | CAO: $23 < x \leqslant 28$ or $24 \leqslant x \leqslant 28$ or 29 with strict inequality |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Bin 1: 15, <u>22</u>, 3 | M1 | First five values placed correctly (underlined) and $x$ not in Bin 1 or 2; at least eight values placed |
| Bin 2: 9, <u>23</u>, [5] | A1 | First eight values placed correctly (underlined and boxed) with no repeated values |
| Bin 3: $x$, [4] | A1 | CSO — no additional/repeated values |
| Bin 4: 18, 20 | | **NO MISREADS — mark exactly to scheme; if $x$ given a value then M1 only** |
| Bin 5: 13 | | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Pass 1: $\underline{x}$, 15, 22, 3, 9, 23, **5**, 4, 18, 20, 13 | M1 | Quick sort; pivot chosen must be middle left or right — choosing first/last item as pivot is M0. After first pass list must read (values $>$ pivot), pivot, (values $<$ pivot) |
| Pass 2: $\underline{x}$, <u>23</u>, 15, 22, 9, **18**, 20, 13, <u>5</u>, 3, **4** | A1 | First two passes correct (pivots for third pass need not be chosen) |
| Pass 3: $\underline{x}$, <u>23</u>, 22, **20**, <u>18</u>, 15, **9**, 13, <u>5</u>, <u>4</u>, 3 | A1ft | Third and fourth passes correct (follow through from second pass); after second pass list must contain 10, 11 or 12 numbers |
| Pass 4: $\underline{x}$, <u>23</u>, 22, <u>20</u>, <u>18</u>, 15, **13**, <u>9</u>, <u>5</u>, <u>4</u>, 3 | | |
| Pass 5: $\underline{x}$, <u>23</u>, <u>22</u>, <u>20</u>, <u>18</u>, <u>15</u>, <u>13</u>, <u>9</u>, <u>5</u>, <u>4</u>, <u>3</u> | A1 | CSO — all previous marks must have been awarded; both middle-left and middle-right require six passes. **SC: if sorted ascending, award max M1A1A0A0** |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Attempt at first-fit decreasing (correct order): Bin 1: $x$; Bin 2: 23, 15; Bin 3: 22, 18; Bin 4: 20, 13. If 15 cannot go in Bin 1 then $x > 25$; if 13 cannot go in Bin 1 then $x > 27$ | B1 | Any clear indication that 15 does not fit in Bin 1 so $x + 15 > 40$ (condone just stating $x > 25$), **or** 13 does not fit in Bin 1 so $x + 13 > 40$ (condone just stating $x > 27$) |
| Therefore $x$ must be 28 | dB1 | Correct answer $x = 28$; dependent on previous B mark **and** correct upper bound of 28 in (b). Accept $x + 13 > 40 \Rightarrow x > 27$ so $x = 28$ |
---4. The eleven distinct numbers listed below are to be packed into bins of size 40
$$\begin{array} { l l l l l l l l l l l }
15 & 22 & 3 & 9 & 23 & x & 5 & 4 & 18 & 20 & 13
\end{array}$$
It is known that $x$
\begin{itemize}
\item is an integer less than 40
\item is the largest number in the list
\begin{enumerate}[label=(\alph*)]
\item Explain why it is not possible to pack the numbers into 3 bins of size 40
\end{itemize}
Given that it is possible to pack the numbers into 4 bins of size 40
\item determine the range of values for $x$
\item Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40
\item Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin.
\item Determine the value of $x$. You must give reasons for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2023 Q4 [12]}}