Question 4 - A-Level Maths

Edexcel D1 2010 January — Question 4 11 marks

Exam Board	Edexcel
Module	D1 (Decision Mathematics 1)
Year	2010
Session	January
Marks	11
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Sorting Algorithms
Type	Quick Sort Execution
Difficulty	Easy -1.2 This is a straightforward procedural question requiring mechanical application of the quick sort algorithm and first-fit decreasing bin-packing. Part (a) is pure algorithm execution with no problem-solving, part (b) is simple arithmetic packing, and part (c) requires only basic verification—all standard D1 textbook exercises with no novel insight required.
Spec	7.03k Sorting: quick sort 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin

4. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are $$0.6,4.0,2.5,3.2,0.5,2.6,0.4,0.3,4.0 \text { and } 1.0$$ Guttering is sold in 4 m lengths.

Carry out a quick sort to produce a list of the lengths needed in descending order. You should show the result of each pass and identify your pivots clearly.
Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the total number of 4 m lengths needed.
Does the answer to part (b) use the minimum number of 4 m lengths? You must justify your answer.

Show mark scheme Show mark scheme source

Question 4(a):

Answer	Marks	Guidance
Answer	Mark	Guidance
Row 1: 0.6, 4.0, 2.5, 3.2, 0.5, 2.6, 0.4, 0.3, 4.0, 1.0 → 2.6	M1	Pivot chosen; list sorted $>p$, $p$, $p$. If only choosing 1 pivot per iteration M1 only
Row 2: 4.0, 3.2, 4.0, $\underline{2.6}$, 0.6, 2.5, 0.5, 0.4, 0.3, 1.0 → 3.2 0.4	A1	$1^{st}$ pass correct and chosen next two pivots correctly for sublists $>1$
Row 3: 4.0, 4.0, $\underline{3.2}$, $\underline{2.6}$, 0.6, 2.5, 0.5, 1.0, $\underline{0.4}$, 0.3 → 4.0 0.5	A1ft	$2^{nd}$ pass correct and chosen next two pivots correctly for sublists $>1$
Row 4: 4.0, $\underline{4.0}$, $\underline{3.2}$, $\underline{2.6}$, 0.6, 2.5, 1.0, $\underline{0.5}$, $\underline{0.4}$, $\underline{0.3}$ → 2.5	A1ft	$3^{rd}$ pass correct and next pivot for sublist $>1$ chosen correctly
Row 5: $\underline{4.0}$, $\underline{4.0}$, $\underline{3.2}$, $\underline{2.6}$, 2.5, 1.0, $\underline{0.6}$, $\underline{0.5}$, $\underline{0.4}$, $\underline{0.3}$	A1 cso

(5 marks)

Question 4(b):

Answer	Marks	Guidance
Answer	Mark	Guidance
Length 1: 4	M1	left column & 1.0 in place
Length 2: 4	A1
Length 3: 3.2, 0.6	A1	$0.6\ \&\ 0.5$
Length 4: 2.6, 1.0, 0.4	A1	0.4; All correct (c.s.o)
Length 5: 2.5, 0.5, 0.3

(4 marks)

Question 4(c):

Answer	Marks	Guidance
Answer	Mark	Guidance
$19.1 \div 4 = 4.775$ so 5 lengths needed; accept total is 19.1m, or refer to 0.9 'spare'	B1
Yes, the answer to (b) does use the minimum number of bins	DB1	Dependent on B1

(2 marks) [11 total]

# Question 4(a):

| Answer | Mark | Guidance |
|--------|------|----------|
| Row 1: 0.6, 4.0, 2.5, 3.2, 0.5, **2.6**, 0.4, 0.3, 4.0, 1.0 → **2.6** | M1 | Pivot chosen; list sorted $>p$, $p$, $<p$ or $<p$, $p$, $>p$. If only choosing 1 pivot per iteration M1 only |
| Row 2: 4.0, **3.2**, 4.0, $\underline{2.6}$, 0.6, 2.5, 0.5, **0.4**, 0.3, 1.0 → **3.2 0.4** | A1 | $1^{st}$ pass correct and chosen next **two** pivots correctly for sublists $>1$ |
| Row 3: 4.0, **4.0**, $\underline{3.2}$, $\underline{2.6}$, 0.6, 2.5, **0.5**, 1.0, $\underline{0.4}$, **0.3** → **4.0 0.5** | A1ft | $2^{nd}$ pass correct and chosen next **two** pivots correctly for sublists $>1$ |
| Row 4: **4.0**, $\underline{4.0}$, $\underline{3.2}$, $\underline{2.6}$, 0.6, **2.5**, 1.0, $\underline{0.5}$, $\underline{0.4}$, $\underline{0.3}$ → **2.5** | A1ft | $3^{rd}$ pass correct and next pivot for sublist $>1$ chosen correctly |
| Row 5: $\underline{4.0}$, $\underline{4.0}$, $\underline{3.2}$, $\underline{2.6}$, **2.5**, **1.0**, $\underline{0.6}$, $\underline{0.5}$, $\underline{0.4}$, $\underline{0.3}$ | A1 cso | |

**(5 marks)**

---

# Question 4(b):

| Answer | Mark | Guidance |
|--------|------|----------|
| Length 1: 4 | M1 | left column & 1.0 in place |
| Length 2: 4 | A1 | |
| Length 3: 3.2, 0.6 | A1 | $0.6\ \&\ 0.5$ |
| Length 4: 2.6, 1.0, 0.4 | A1 | 0.4; All correct (c.s.o) |
| Length 5: 2.5, 0.5, 0.3 | | |

**(4 marks)**

---

# Question 4(c):

| Answer | Mark | Guidance |
|--------|------|----------|
| $19.1 \div 4 = 4.775$ so 5 lengths needed; accept total is 19.1m, or refer to 0.9 'spare' | B1 | |
| Yes, the answer to (b) does use the minimum number of bins | DB1 | Dependent on B1 |

**(2 marks) [11 total]**

---

Show LaTeX source

4. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are

$$0.6,4.0,2.5,3.2,0.5,2.6,0.4,0.3,4.0 \text { and } 1.0$$

Guttering is sold in 4 m lengths.
\begin{enumerate}[label=(\alph*)]
\item Carry out a quick sort to produce a list of the lengths needed in descending order. You should show the result of each pass and identify your pivots clearly.
\item Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the total number of 4 m lengths needed.
\item Does the answer to part (b) use the minimum number of 4 m lengths? You must justify your answer.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2010 Q4 [11]}}

This paper (7 questions)

View full paper

Q1 6 Q2 9 Q3 10 Q4 11 Q5 7 Q6 15 Q7 17