Question 3 - A-Level Maths

Edexcel D1 2021 January — Question 3 13 marks

Exam Board	Edexcel
Module	D1 (Decision Mathematics 1)
Year	2021
Session	January
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Sorting Algorithms
Type	Bubble Sort Execution
Difficulty	Easy -1.8 This is a purely procedural question requiring mechanical execution of standard algorithms (bubble sort, quick sort, bin packing) with no problem-solving, insight, or mathematical reasoning. Students simply follow learned procedures step-by-step with small numbers, making it significantly easier than average A-level maths questions which typically require some analytical thinking.
Spec	7.03j Sorting: bubble sort and shuttle sort 7.03k Sorting: quick sort 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin 7.03m Packing extensions: 2D/3D packing and knapsack problems

3. $\quad \begin{array} { l l l l l l l l l l } 2.6 & 0.8 & 2.1 & 1.2 & 0.9 & 1.7 & 2.3 & 0.3 & 1.8 & 2.7 \end{array}$

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 The list is to be sorted into descending order.
1. Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.
2. Write down, in the table in the answer book, the number of comparisons and the number of swaps performed during each of these two passes. After a third pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 2.6 & 2.1 & 1.7 & 2.3 & 1.2 & 1.8 & 2.7 & 0.9 & 0.8 & 0.3 \end{array}$$
Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 5

Show mark scheme Show mark scheme source

Question 3:

Part (a):

Answer	Marks	Guidance
Answer/Working	Marks	Guidance Notes
Bin 1: 2.6 0.8 1.2 0.3; Bin 2: 2.1 0.9 1.7; Bin 3: 2.3 1.8; Bin 4: 2.7	M1 $\underline{\text{A1}}$ A1	a1M1: First four items placed correctly and at least seven values placed in bins. Condone cumulative totals for M1 only (values in bold). a1A1: First seven items placed correctly (underlined and bold values) – any repeated/additional values then A0. a2A1: CSO (correct solution only – no additional/repeated values)

Total: 3 marks

Part (b)(i):

Answer	Marks	Guidance
Answer/Working	Marks	Guidance Notes
First pass: 2.6 2.1 1.2 0.9 1.7 2.3 0.8 1.8 2.7 0.3	B1	bi1B1: CAO (first pass) – some candidates may show each comparison/swap within the first pass so take the first pass to be the list when the 0.3 is in the correct position
Second pass: 2.6 2.1 1.2 1.7 2.3 0.9 1.8 2.7 0.8 0.3	B1	bi2B1: CAO (second pass) – take the second pass to be the list when the 0.8 and the 0.3 are in the correct positions. ISW if completing more than two passes

Total: 2 marks

Part (b)(ii):

Answer	Marks	Guidance
Answer/Working	Marks	Guidance Notes
First pass: Comparisons = 9, Swaps = 7	B1	bii1B1: Two correct values in the given table
Second pass: Comparisons = 8, Swaps = 4	B1	bii2B1: Fully correct table completed. Mark table on page 2 of the AB

Total: 2 marks

Part (c):

Answer	Marks	Guidance
Answer/Working	Marks	Guidance Notes
e.g. middle right pivot: 2.6 2.1 1.7 2.3 1.2 <u>1.8</u> 2.7 0.9 0.8 0.3 → Pivot: 1.8	M1	c1M1: Quick sort – pivot chosen (must be choosing middle left or middle right – choosing first/last item as a pivot is M0). After first pass list must read (values greater than pivot), pivot, (values less than pivot). If only choosing one pivot per iteration then M1 only. If sorting into ascending order then M0
2.6 2.1 <u>2.3</u> 2.7 1.8 1.7 1.2 <u>0.9</u> 0.8 0.3 → Pivots: 2.3, 0.9	A1	c1A1: First two passes correct (second pass pivot consistent with choice of pivot in first pass) – but need not be choosing pivots for the third pass
2.6 <u>2.7</u> 2.3 2.1 1.8 1.7 <u>1.2</u> 0.9 0.8 <u>0.3</u> → Pivots: 2.7, (2.1), 1.2, 0.3
2.7 2.6 2.3 2.1 1.8 1.7 1.2 0.9 0.8 0.3 → Sort complete	A1	c2A1: CSO – all previous marks must have been awarded including a 'sort complete' indication

Total: 3 marks

Middle left alternative also shown in mark scheme:

Answer	Marks	Guidance
Pivot 1.2 → 1.7, 0.8 → 2.3, (0.9), (0.3) → 2.6, 2.1 → Sort Complete		Two Special Cases: Case I – quick sort on original list scores M1 only. Case II – quick sort on 2.6 2.1 1.7 2.3 1.2 1.8 2.7 only (not including last three numbers) scores M1A1 only

Part (d):

Answer	Marks	Guidance
Answer/Working	Marks	Guidance Notes
Bin 1: 2.7 2.3; Bin 2: 2.6 2.1 0.3; Bin 3: <u>1.8</u> <u>1.7</u> <u>1.2</u>; Bin 4: 0.9 0.8	M1 $\underline{\text{A1}}$ A1	d1M1: First four items placed correctly and at least seven values placed in bins – condone cumulative totals for M1 only. d1A1: First seven items placed correctly (underlined and bold values) – any repeated/additional values is A0. d2A1: CSO (no additional/repeated values). No misreads in (d) – mark according to scheme in all cases

Total: 3 marks

# Question 3:

## Part (a):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| Bin 1: **2.6** **0.8** **1.2** 0.3; Bin 2: **2.1** 0.9 1.7; Bin 3: **2.3** 1.8; Bin 4: 2.7 | M1 $\underline{\text{A1}}$ A1 | **a1M1**: First four items placed correctly and at least seven values placed in bins. Condone cumulative totals for M1 only (values in bold). **a1A1**: First seven items placed correctly (underlined and bold values) – any repeated/additional values then A0. **a2A1**: CSO (correct solution only – no additional/repeated values) |

**Total: 3 marks**

## Part (b)(i):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| First pass: 2.6  2.1  1.2  0.9  1.7  2.3  0.8  1.8  2.7  0.3 | B1 | **bi1B1**: CAO (first pass) – some candidates may show each comparison/swap within the first pass so take the first pass to be the list when the 0.3 is in the correct position |
| Second pass: 2.6  2.1  1.2  1.7  2.3  0.9  1.8  2.7  0.8  0.3 | B1 | **bi2B1**: CAO (second pass) – take the second pass to be the list when the 0.8 and the 0.3 are in the correct positions. ISW if completing more than two passes |

**Total: 2 marks**

## Part (b)(ii):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| First pass: Comparisons = 9, Swaps = 7 | B1 | **bii1B1**: Two correct values in the given table |
| Second pass: Comparisons = 8, Swaps = 4 | B1 | **bii2B1**: Fully correct table completed. Mark table on page 2 of the AB |

**Total: 2 marks**

## Part (c):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| e.g. middle right pivot: 2.6  2.1  1.7  2.3  1.2  <u>1.8</u>  2.7  0.9  0.8  0.3 → Pivot: 1.8 | M1 | **c1M1**: Quick sort – pivot chosen (must be choosing middle left or middle right – choosing first/last item as a pivot is M0). After first pass list must read (values greater than pivot), pivot, (values less than pivot). **If only choosing one pivot per iteration then M1 only. If sorting into ascending order then M0** |
| 2.6  2.1  <u>2.3</u>  2.7  **1.8**  1.7  1.2  <u>0.9</u>  0.8  0.3 → Pivots: 2.3, 0.9 | A1 | **c1A1**: First two passes correct (second pass pivot consistent with choice of pivot in first pass) – but need not be choosing pivots for the third pass |
| 2.6  <u>2.7</u>  **2.3**  2.1  **1.8**  1.7  <u>1.2</u>  **0.9**  0.8  <u>0.3</u> → Pivots: 2.7, (2.1), 1.2, 0.3 | | |
| **2.7**  2.6  **2.3**  2.1  **1.8**  1.7  **1.2**  **0.9**  0.8  **0.3** → Sort complete | A1 | **c2A1**: CSO – all previous marks must have been awarded including a 'sort complete' indication |

**Total: 3 marks**

*Middle left alternative also shown in mark scheme:*

| Pivot 1.2 → 1.7, 0.8 → 2.3, (0.9), (0.3) → 2.6, 2.1 → Sort Complete |  | Two Special Cases: Case I – quick sort on original list scores M1 only. Case II – quick sort on 2.6  2.1  1.7  2.3  1.2  1.8  2.7 only (not including last three numbers) scores M1A1 only |

## Part (d):

| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| Bin 1: **2.7**  **2.3**; Bin 2: **2.6**  **2.1**  0.3; Bin 3: <u>1.8</u>  <u>1.7</u>  <u>1.2</u>; Bin 4: 0.9  0.8 | M1 $\underline{\text{A1}}$ A1 | **d1M1**: First four items placed correctly and at least seven values placed in bins – condone cumulative totals for M1 only. **d1A1**: First seven items placed correctly (underlined and bold values) – any repeated/additional values is A0. **d2A1**: CSO (no additional/repeated values). No misreads in (d) – mark according to scheme in all cases |

**Total: 3 marks**

---

Show LaTeX source

3. $\quad \begin{array} { l l l l l l l l l l } 2.6 & 0.8 & 2.1 & 1.2 & 0.9 & 1.7 & 2.3 & 0.3 & 1.8 & 2.7 \end{array}$
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5

The list is to be sorted into descending order.
\item \begin{enumerate}[label=(\roman*)]
\item Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.
\item Write down, in the table in the answer book, the number of comparisons and the number of swaps performed during each of these two passes.

After a third pass using this bubble sort, the updated list is

$$\begin{array} { l l l l l l l l l l } 
2.6 & 2.1 & 1.7 & 2.3 & 1.2 & 1.8 & 2.7 & 0.9 & 0.8 & 0.3
\end{array}$$
\end{enumerate}\item Use a quick sort on this updated list 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 5
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2021 Q3 [13]}}

This paper (7 questions)

View full paper

Q1 4 Q2 5 Q3 13 Q4 12 Q5 17 Q6 13 Q7 11