Question 1 - A-Level Maths

Edexcel D1 2012 June — Question 1 12 marks

Exam Board	Edexcel
Module	D1 (Decision Mathematics 1)
Year	2012
Session	June
Marks	12
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Sorting Algorithms
Type	Bubble Sort Execution
Difficulty	Easy -1.8 This is a routine D1 question requiring mechanical application of standard algorithms (bubble sort and bin packing) with no problem-solving or insight needed. The bubble sort execution is purely procedural—students simply follow the algorithm steps they've memorized. The bin packing parts are similarly algorithmic. This is significantly easier than average A-level maths questions which typically require some mathematical reasoning or technique selection.
Spec	7.03j Sorting: bubble sort and shuttle sort 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin

A carpet fitter needs the following lengths, in metres, of carpet.

$$\begin{array} { l l l l l l l l l } 20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25 \end{array}$$ He cuts them from rolls of length 50 m .

Calculate a lower bound for the number of rolls he needs. You must make your method clear.
Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.

Show mark scheme Show mark scheme source

Question 1:

Part (a)

Answer	Marks	Guidance
$\frac{219}{50} = 4.38$ so lower bound is 5 bins	M1 A1 (2)	a1M1: 219 (186–252) /50; a1A1: CAO correct calc seen or awrt $4.4 + 5$

Part (b)

Answer	Marks	Guidance
Bin 1: $\boxed{20}$ $\boxed{19}$; Bin 2: $\boxed{33}$; Bin 3: $\boxed{24}$ $\boxed{22}$; Bin 4: $\boxed{31}$ 18; Bin 5: $\boxed{27}$; Bin 6: 25	M1 1A1 2A1 (3)	b1M1: First four terms placed correctly in bins 1, 2 and 3 (condone cumulative totals here only); b1A1: First seven terms placed correctly; b2A1: CAO

Part (c)

Answer	Marks	Guidance
e.g. (left to right): $20\ 33\ 19\ 24\ 31\ 22\ 27\ 18\ 25$ → $33\ 20\ 24\ 31\ 22\ 27\ 19\ 25\ 18$ → $33\ 24\ 31\ 22\ 27\ 20\ 25\ 19\ 18$ → $33\ 31\ 24\ 27\ 22\ 25\ 20\ 19\ 18$ → $33\ 31\ 27\ 24\ 25\ 22\ 20\ 19\ 18$ → $33\ 31\ 27\ 25\ 24\ 22\ 20\ 19\ 18$; List in order	M1, 1A1, 2A1ft, 3A1 CSO (4)	c1M1: Bubble sort, consistent direction throughout, end number (greatest/least) in place; c1A1: First and second passes correct — end two numbers in place; c2A1ft: $3^{\text{rd}}$ and $4^{\text{th}}$ passes correct — end four numbers in place; c3A1: CSO, including 'sorted' or final list rewritten or 'final pass' stated — a clear statement in (c). If final list is reversed in (c), award full credit.

Part (d)

Answer	Marks	Guidance
Bin 1: $\boxed{33}$; Bin 2: $\boxed{31}$ 19; Bin 3: $\boxed{27}$ $\boxed{22}$; Bin 4: $\boxed{25}$ $\boxed{24}$; Bin 5: $\boxed{20}$ 18	M1 1A1 2A1 (3)	d1M1: Must be using 'sorted' list in decreasing order, first five terms correct; d1A1: First seven terms correct; d2A1: CAO. SC for 1(d): If 'sorted' list is wrong from (c) then award M1 only in (d) for their first seven terms correctly placed.

Total: 12

# Question 1:

## Part (a)

| $\frac{219}{50} = 4.38$ so lower bound is 5 bins | M1 A1 **(2)** | a1M1: 219 (186–252) /50; a1A1: CAO correct calc seen or awrt $4.4 + 5$ |

---

## Part (b)

| Bin 1: $\boxed{20}$ $\boxed{19}$; Bin 2: $\boxed{33}$; Bin 3: $\boxed{24}$ $\boxed{22}$; Bin 4: $\boxed{31}$ 18; Bin 5: $\boxed{27}$; Bin 6: 25 | M1 1A1 2A1 **(3)** | b1M1: First four terms placed correctly in bins 1, 2 and 3 (condone cumulative totals here only); b1A1: First seven terms placed correctly; b2A1: CAO |

---

## Part (c)

| e.g. (left to right): $20\ 33\ 19\ 24\ 31\ 22\ 27\ 18\ 25$ → $33\ 20\ 24\ 31\ 22\ 27\ 19\ 25\ 18$ → $33\ 24\ 31\ 22\ 27\ 20\ 25\ 19\ 18$ → $33\ 31\ 24\ 27\ 22\ 25\ 20\ 19\ 18$ → $33\ 31\ 27\ 24\ 25\ 22\ 20\ 19\ 18$ → $33\ 31\ 27\ 25\ 24\ 22\ 20\ 19\ 18$; List in order | M1, 1A1, 2A1ft, 3A1 CSO **(4)** | c1M1: Bubble sort, consistent direction throughout, end number (greatest/least) in place; c1A1: First and second passes correct — end two numbers in place; c2A1ft: $3^{\text{rd}}$ and $4^{\text{th}}$ passes correct — end four numbers in place; c3A1: CSO, including 'sorted' **or** final list rewritten **or** 'final pass' stated — a **clear statement** in (c). If final list is reversed in (c), award full credit. |

---

## Part (d)

| Bin 1: $\boxed{33}$; Bin 2: $\boxed{31}$ 19; Bin 3: $\boxed{27}$ $\boxed{22}$; Bin 4: $\boxed{25}$ $\boxed{24}$; Bin 5: $\boxed{20}$ 18 | M1 1A1 2A1 **(3)** | d1M1: **Must be using 'sorted' list** in decreasing order, first five terms correct; d1A1: First seven terms correct; d2A1: CAO. **SC for 1(d):** If 'sorted' list is wrong from (c) then award M1 only in (d) for their first seven terms correctly placed. |

**Total: 12**

Show LaTeX source

\begin{enumerate}
  \item A carpet fitter needs the following lengths, in metres, of carpet.
\end{enumerate}

$$\begin{array} { l l l l l l l l l } 
20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25
\end{array}$$

He cuts them from rolls of length 50 m .\\
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of rolls he needs.

You must make your method clear.
\item Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
\item Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
\item Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.\\
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2012 Q1 [12]}}

This paper (7 questions)

View full paper

Q1 12 Q2 7 Q3 7 Q4 12 Q5 10 Q6 14 Q7 13