| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2020 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bin Capacity Constraints |
| Difficulty | Standard +0.3 This is a straightforward multi-part question on bin packing and bubble sort that requires careful reading and basic logical deduction rather than complex problem-solving. Part (a) involves simple arithmetic constraints from bin capacity, part (b) requires understanding one pass of bubble sort, and part (c) combines constraints to find a unique integer value. While it tests understanding of algorithms, the mathematical demands are minimal and the question guides students through each step clearly. |
| 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/Working | Mark | Guidance |
| If \(x\) has been placed in Bin 2 then \(10 < x \leq 31\); Bin 1 only contains 40, before \(x\) was placed in Bin 2 it only contained 19 | — | Context for reasoning |
| As 18 has been placed in Bin 3, this implies \(x > 50-(19+18)\), so \(x > 13\) | B1 | Correct reasoning of why \(x>13\); accept \(x > 50-(19+18)\) |
| As 10 has been placed in Bin 2 after \(x\), then \(x \leq 50-(19+10)\), so \(x \leq 21\) | B1 | Correct explanation of why \(x \leq 21\); accept \(x \leq 50-(19+10)\) |
| Numbers are all distinct, therefore \(13 < x < 21\) | B1 | Must mention numbers are distinct (oe) |
| Total | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(13 < x < 17\) | B1 | Use first complete pass to deduce \(x < 17\) |
| B1 | Correct lower bound \(x > 13\) | |
| Total | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| If \(x\) has been placed in Bin 3 then \(x \leq 15\) | M1 | Using first-fit decreasing to derive new upper bound for \(x\); accept stating both \(x\) could equal 14 or 15, \(x \leq 15\) or \(x < 15\) |
| \(x\) is either 14 or 15, but Bin 2 is full \(\Rightarrow x = 14\) | A1 | Must clearly state or imply that Bin 2 is full |
| Total | (2) |
# Question 5:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| If $x$ has been placed in Bin 2 then $10 < x \leq 31$; Bin 1 only contains 40, before $x$ was placed in Bin 2 it only contained 19 | — | Context for reasoning |
| As 18 has been placed in Bin 3, this implies $x > 50-(19+18)$, so $x > 13$ | B1 | Correct reasoning of why $x>13$; accept $x > 50-(19+18)$ |
| As 10 has been placed in Bin 2 after $x$, then $x \leq 50-(19+10)$, so $x \leq 21$ | B1 | Correct explanation of why $x \leq 21$; accept $x \leq 50-(19+10)$ |
| Numbers are all distinct, therefore $13 < x < 21$ | B1 | Must mention numbers are distinct (oe) |
| **Total** | **(3)** | |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $13 < x < 17$ | B1 | Use first complete pass to deduce $x < 17$ |
| | B1 | Correct lower bound $x > 13$ |
| **Total** | **(2)** | |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| If $x$ has been placed in Bin 3 then $x \leq 15$ | M1 | Using first-fit decreasing to derive new upper bound for $x$; accept stating both $x$ could equal 14 or 15, $x \leq 15$ or $x < 15$ |
| $x$ is either 14 or 15, but Bin 2 is full $\Rightarrow x = 14$ | A1 | Must clearly state or imply that Bin 2 is full |
| **Total** | **(2)** | |
---5. The nine distinct numbers in the following list are to be packed into bins of size 50
$$\begin{array} { l l l l l l l l l }
23 & 17 & 19 & x & 24 & 8 & 18 & 10 & 21
\end{array}$$
When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation.
Bin 1: 23178\\
Bin 2: $19 \quad x \quad 10$\\
Bin 3: 2418\\
Bin 4: 21
\begin{enumerate}[label=(\alph*)]
\item Explain why $13 < x < 21$
The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is
$$\begin{array} { l l l l l l l l l }
23 & 19 & 17 & 24 & x & 18 & 10 & 21 & 8
\end{array}$$
\item Using this information, write down the smallest interval that must contain $x$, giving your answer as an inequality.
When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation.
Bin 1: 2423\\
Bin 2: 211910\\
Bin 3: $1817 x$\\
Bin 4: 8\\
Given that only one of the bins is full and that $x$ is an integer,
\item calculate the value of $x$. You must give reasons for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2020 Q5 [7]}}