| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.2 This is a multi-part question testing routine algorithmic procedures (first-fit bin packing, quick sort, Kruskal's algorithm) that require careful execution but minimal problem-solving insight. Each part follows standard textbook methods with straightforward data sets, making it easier than average despite the length. |
| Spec | 7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bin 1: 4.2 1.8 1.3; Bin 2: 3.1 4.0; Bin 3: 4.1 3.7; Bin 4: 2.3 2.7 | M1 A1 | (2) First four (underlined) items placed correctly |
| \(\frac{27.2}{7.8} \approx 3.487\) so yes 4 bins is optimal | M1 A1 | (2) CSO – correct calculation seen or awrt 3.49 or 3.48 and a conclusion |
| Quick sort, pivot, p, chosen (must be choosing middle left or right). After first pass the list must read (values less than pivot), pivot, (values greater than pivot). If only choosing one pivot per iteration then M1 only. Passes: Pivot 4.0, Pivot 3.7 or 4.1, Pivot 1.3 (4.2), Pivot 2.3, Pivot (1.8) 2.7, Sort complete | M1 (quick) A1 (2 passes + choice of pivot for 3rd) A1ft (3rd and 4th passes correct) | (6) |
| Kruskal: AC, AD, CE, reject DE, reject CD, AB, reject BE, EF | A1 (CSO) M1 A1 | (4) (2) |
| e.g. Prim cannot be used since with Prim the tree 'grows' in a connected fashion. e.g. AB and DE have no vertex in common and since Prim adds arcs which introduce new vertices to the tree, they will never be connected | B1 | (1) |
| 11 marks |
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bin 1: 4.2 1.8 1.3; Bin 2: 3.1 4.0; Bin 3: 4.1 3.7; Bin 4: 2.3 2.7 | M1 A1 | (2) First four (underlined) items placed correctly |
| $\frac{27.2}{7.8} \approx 3.487$ so yes 4 bins is optimal | M1 A1 | (2) CSO – correct calculation seen or awrt 3.49 or 3.48 and a conclusion |
| Quick sort, pivot, p, chosen (must be choosing middle left or right). After first pass the list must read (values less than pivot), pivot, (values greater than pivot). If only choosing one pivot per iteration then M1 only. Passes: Pivot 4.0, Pivot 3.7 or 4.1, Pivot 1.3 (4.2), Pivot 2.3, Pivot (1.8) 2.7, Sort complete | M1 (quick) A1 (2 passes + choice of pivot for 3rd) A1ft (3rd and 4th passes correct) | (6) |
| Kruskal: AC, AD, CE, reject DE, reject CD, AB, reject BE, EF | A1 (CSO) M1 A1 | (4) (2) |
| e.g. Prim cannot be used since with Prim the tree 'grows' in a connected fashion. e.g. AB and DE have no vertex in common and since Prim adds arcs which introduce new vertices to the tree, they will never be connected | B1 | (1) |
| | | **11 marks** |
**Notes for Question 1:**
- a1M1: First four (underlined) items placed correctly
- a1A1: CSO – all correct
- b1M1: Attempt to find lower bound $(27.2 \pm 4.2) / 7.8$ (awrt 3.49 or 3.48 with no working can imply this mark)
- b1A1: CSO – correct calculation seen or awrt 3.49 or 3.48 **and** a conclusion – accept 'yes' as a minimum conclusion – however, '4 is the optimal number of bins' (or equivalent) with no reference to the solution in (a) is A0
- c1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as pivot is M0). After the first pass the list must read (values less than the pivot), pivot, (values greater than the pivot). **If only choosing one pivot per iteration then M1 only** – Bubble sort is not a MR and scores M1 only for 1.8 3.1 1.3 4.0 4.1 3.7 2.3 2.7 4.2 (for left to right) or 1.3 4.2 1.8 3.1 2.3 4.0 4.1 3.7 2.7 (for right to left)
- c2A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots). They do not need to be choosing a pivot for the fifth pass for this mark
- c3A1: CSO – including a fifth pass (the 27) **and** a 'sort complete' statement if middle right **or** a fifth pass (the 23) if middle left
- d1M1: Kruskal: first three arcs correctly chosen (AC(1.3), AD(1.8), CE(2.3)) and arc DE(2.7) rejected at the correct time – no follow through from an incorrect list – condone the use of the arc weights for this mark
- d1A1: CSO – all selections and rejections correct (in the correct order at the correct time) – arcs not weights
- e1B1: CAO (an indication that AB and DE are not connected is sufficient for this mark)
---1.
$$\begin{array} { l l l l l l l l l }
4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 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 7.8
\item Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
\item The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\item Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree.
A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
\item Explain why Prim's algorithm could not be used to complete the tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q1 [11]}}