| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2022 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Lower Bound for Bins |
| Difficulty | Easy -1.2 This is a straightforward application of standard bin packing algorithms taught in D1/FD1. Part (a) requires simply summing the lengths and dividing by capacity (basic arithmetic), while part (b) is mechanical application of first-fit algorithm with no problem-solving required. Both parts are routine textbook exercises with clear procedures. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(\frac{4.3 + 6.1 + \ldots + 1.3}{10} = \frac{37.5}{10} = 3.75\) | M1 | Attempt to find lower bound \((37.5 \pm 6.1)/10\); a value of 3.75 seen with no working can imply this mark |
| Lower bound is 4 (balls of string) | A1 | cso – a lower bound of 4 with either a correct calculation seen or 3.75 or 'total is 37.5 and if each ball contains 10 this gives a lower bound of 4'. Answer of 4 with no working (or from part (b)) scores M0A0. Any incorrect working loses this mark. |
| (2 marks) | No MR in this question – mark according to the scheme |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bin 1: \(\boxed{4.3}\) \(\boxed{5.1}\) \(0.4\) | M1 | First four items placed correctly and at least eight items placed in bins (condone cumulative totals for M1 only – the boxed values) |
| Bin 2: \(\boxed{6.1}\) 2.5 \(1.3\) | A1 | First eight items placed correctly (boxed and bold values), and all eleven correct values only placed in bins |
| Bin 3: \(\boxed{4.7}\) 3.4 1.7 | A1 | cso (no additional/repeated values) |
| Bin 4: 5.9 \(2.1\) | Condone working in cm provided consistent | |
| (3 marks) |
## Question 1:
**Part (a):**
| Answer/Working | Marks | Guidance |
|---|---|---|
| $\frac{4.3 + 6.1 + \ldots + 1.3}{10} = \frac{37.5}{10} = 3.75$ | M1 | Attempt to find lower bound $(37.5 \pm 6.1)/10$; a value of 3.75 seen with no working can imply this mark |
| Lower bound is **4** (balls of string) | A1 | cso – a lower bound of 4 with either a correct calculation seen or 3.75 or 'total is 37.5 and if each ball contains 10 this gives a lower bound of 4'. Answer of 4 with no working (or from part (b)) scores M0A0. Any incorrect working loses this mark. |
| **(2 marks)** | | No MR in this question – mark according to the scheme |
**Part (b):**
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bin 1: $\boxed{4.3}$ $\boxed{5.1}$ $0.4$ | M1 | First four items placed correctly and at least eight items placed in bins (condone cumulative totals for M1 only – the boxed values) |
| Bin 2: $\boxed{6.1}$ **2.5** $1.3$ | A1 | First eight items placed correctly (boxed **and** bold values), and all eleven correct values only placed in bins |
| Bin 3: $\boxed{4.7}$ **3.4** **1.7** | A1 | cso (no additional/repeated values) |
| Bin 4: **5.9** $2.1$ | | Condone working in cm provided consistent |
| **(3 marks)** | | |\begin{enumerate}
\item A gardener needs the following lengths of string. All lengths are in metres.\\
0.4\\
1.7\\
1.3\\
2.5\\
2.1\\
3.4\\
4.3\\
4.7\\
5.1\\
5.9\\
6.1
\end{enumerate}
She cuts the lengths from balls of string. Each ball contains 10 m of string.\\
(a) Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.\\
(b) Use the first-fit bin packing algorithm to determine how the lengths could be cut from the balls of string.\\
\hfill \mbox{\textit{Edexcel FD1 2022 Q1 [5]}}