| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2024 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bin Capacity Constraints |
| Difficulty | Moderate -0.8 This is a straightforward application of standard algorithms with minimal problem-solving required. Part (a) is simple deduction from given information, part (b) is routine execution of quick sort (a memorized algorithm), and part (c) is direct application of first-fit decreasing. All parts involve mechanical application of learned procedures rather than insight or novel reasoning. |
| 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 | Marks | Guidance |
| The 16 was not placed in Bin 1 indicating that \(n < 41\) (= \(17 + 8 + 16\)), or the 4 was not placed in Bin 1 indicating that \(n < 41\) (\(17 + 8 + 12 + 4\)). Bin 2 contains \(40\) (= \(16 + 24\)) so therefore \(n = 40\) | B1 | AO 2.4 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Correct first pass sorting attempt (e.g. Middle Right or Middle Left method applied) | M1 | AO 1.1b |
| Correct second sort pass | A1 | AO 1.1b |
| Correct follow-through third pass | A1ft | AO 1.1b |
| Fully correct final sorted list: \(4, 8, 11, 12, 13, 16, 17, 19, 20, 23, 24\) | A1 | AO 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Correct bin-packing method applied: Bin 1: 24 16, Bin 2: 23 17, Bin 3: 20 19, Bin 4: 13 12 11 4, Bin 5: 8 | M1 | AO 1.1b |
| All bins fully and correctly assigned | A1 | AO 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| 16 was not placed in Bin 1; \(n < (17 + 8 + 16)\) or 4 was not placed in Bin 1 \(n < (17 + 8 + 12 + 4)\); Bin 2 contains total of 40 | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Quick sort with pivot chosen as middle left or right; after first pass list reads (values greater than pivot), pivot, (values less than pivot) | M1 | Choosing first/last item as pivot scores M0; only one pivot per iteration |
| First two passes correct and pivots chosen for third pass | A1 | |
| Third and fourth passes correct, follow through from second pass and pivot choices | A1ft | If error oversimplifies so after 3 passes all sublists length 1: A0 |
| Fully sorted correct solution | A1 | CSO — all previous marks must have been awarded |
| Answer | Marks | Guidance |
|---|---|---|
| First 6 values (bold values) placed correctly with at least 8 values placed in bins | M1 | No misreads |
| CSO — no additional/repeated values | A1 |
# Question 1:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| The 16 was not placed in Bin 1 indicating that $n < 41$ (= $17 + 8 + 16$), or the 4 was not placed in Bin 1 indicating that $n < 41$ ($17 + 8 + 12 + 4$). Bin 2 contains $40$ (= $16 + 24$) so therefore $n = 40$ | B1 | AO 2.4 |
**(1 mark)**
---
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct first pass sorting attempt (e.g. Middle Right or Middle Left method applied) | M1 | AO 1.1b |
| Correct second sort pass | A1 | AO 1.1b |
| Correct follow-through third pass | A1ft | AO 1.1b |
| Fully correct final sorted list: $4, 8, 11, 12, 13, 16, 17, 19, 20, 23, 24$ | A1 | AO 1.1b |
**(4 marks)**
---
## Part (c)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct bin-packing method applied: Bin 1: **24** 16, Bin 2: **23** 17, Bin 3: **20** 19, Bin 4: 13 12 11 4, Bin 5: 8 | M1 | AO 1.1b |
| All bins fully and correctly assigned | A1 | AO 1.1b |
**(2 marks)**
**(7 marks total)**
# Question 1:
## Part (a)
| 16 was not placed in Bin 1; $n < (17 + 8 + 16)$ or 4 was not placed in Bin 1 $n < (17 + 8 + 12 + 4)$; Bin 2 contains total of 40 | B1 | CAO |
## Part (b)
| Quick sort with pivot chosen as middle left or right; after first pass list reads (values greater than pivot), pivot, (values less than pivot) | M1 | Choosing first/last item as pivot scores M0; only one pivot per iteration |
| First two passes correct and pivots chosen for third pass | A1 | |
| Third and fourth passes correct, follow through from second pass and pivot choices | A1ft | If error oversimplifies so after 3 passes all sublists length 1: A0 |
| Fully sorted correct solution | A1 | CSO — all previous marks must have been awarded |
**Special Case:** If sorted in ascending order, award maximum M1A1A0A0 (2 marks)
## Part (c)
| First 6 values (bold values) placed correctly with at least 8 values placed in bins | M1 | No misreads |
| CSO — no additional/repeated values | A1 | |
---1.
$$\begin{array} { l l l l l l l l l l l }
17 & 8 & 16 & 12 & 24 & 19 & 23 & 11 & 20 & 13 & 4
\end{array}$$
The eleven numbers listed above are to be packed into bins of size $n$ where $n$ is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below.
Bin 1: 17812\\
Bin 2: 1624\\
Bin 3: 19114\\
Bin 4: 2313\\
Bin 5: 20
\begin{enumerate}[label=(\alph*)]
\item Explain why this packing means that the value of $n$ must be 40
The original list of eleven numbers is to be sorted into descending order.
\item Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
\item Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2024 Q1 [7]}}