D1 June 2016 Q3
3.
59 45 18 55 47 11 63 17 15 42
The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.
| Scheme | Marks |
|---|---|
| e.g. using middle right | M1 (quick) |
| \(59\quad 45\quad 18\quad 55\quad 47\quad \boxed{11}\quad 63\quad 17\quad 15\quad 42\) pivot 11 | |
| \(59\quad 45\quad 18\quad 55\quad \boxed{47}\quad 63\quad 17\quad 15\quad 42\quad \boxed{11}\) pivot 47 | A1 (2 passes + choice of pivot for the 3rd) |
| \(59\quad \boxed{55}\quad 63\quad \boxed{47}\quad 45\quad 18\quad \boxed{17}\quad 15\quad 42\quad \boxed{11}\) pivot 55 17 | |
| \(59\quad \boxed{63}\quad \boxed{55}\quad \boxed{47}\quad 45\quad \boxed{18}\quad 42\quad \boxed{17}\quad 15\quad \boxed{11}\) pivot 63 18 (15) | A1ft (3rd and 4th passes correct) |
| \(\boxed{63}\quad 59\quad \boxed{55}\quad \boxed{47}\quad 45\quad \boxed{42}\quad \boxed{18}\quad \boxed{17}\quad 15\quad \boxed{11}\) pivot (59) 42 | |
| \(\boxed{63}\quad 59\quad \boxed{55}\quad \boxed{47}\quad 45\quad \boxed{42}\quad \boxed{18}\quad \boxed{17}\quad 15\quad \boxed{11}\) (sort complete) | A1 (CSO) |
| (4) |
Notes
a1M1: 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 greater than the pivot), pivot, (values less than the pivot). If only choosing one pivot per iteration then M1 only – Bubble sort is not a MR and scores M1 only for 59 45 55 47 18 63 17 15 42 11 (for left to right) or 63 59 45 18 55 47 11 42 17 15 (for right to left)
a1A1: First two passes correct and next pivots chosen correctly for third pass (but third pass does not need to be correct) – so they must be choosing (if middle right) pivot values of 55 and 17 for the third pass or (if middle left) pivot values of 59 and 17
a2A1ft: 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
a3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including a fifth pass in which the 42 (if middle right) or 45 (if middle left) is used as a pivot (not just stated as a pivot)
Misreads
- If the candidate has misread a number at the start of (a), so genuinely miscopy a number then mark the whole question as a misread – removing the last two A marks earned. This gives a maximum of total of 7 marks
- If the candidate starts the sort with the correct numbers in (a) but they misread their own numbers (so they have a copying error) during the sort then count this as an error in (a) but mark (b) and (c) as a misread. If they restart in (b) and (c) with the correct list of numbers then this is fine for full marks
Sorting list into ascending order in (a)
- If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (a)
- If the list is not reversed in (a) then mark as a misread (so remove the last two A marks earned in (a)). If the list is reversed at the start of (b) but not in (a) then still treat this as a misread. If the list is in ascending order in (b) award no marks for first-fit increasing. If the candidate says that the list needs reversing in (a) but does not actually show the reversed list in (a) then remove the final A mark
For part (a) using middle left as pivot
| \(59\quad 45\quad 18\quad 55\quad \boxed{47}\quad 11\quad 63\quad 17\quad 15\quad 42\) pivot 47 | |
| \(59\quad \boxed{55}\quad 63\quad \boxed{47}\quad 45\quad 18\quad \boxed{11}\quad 17\quad 15\quad 42\) pivot 55 11 | |
| \(\boxed{59}\quad 63\quad \boxed{55}\quad \boxed{47}\quad 45\quad 18\quad \boxed{17}\quad 15\quad 42\quad \boxed{11}\) pivot 59 17 | |
| \(63\quad \boxed{59}\quad \boxed{55}\quad \boxed{47}\quad 45\quad \boxed{18}\quad 42\quad \boxed{17}\quad 15\quad \boxed{11}\) pivot (63) 18 (15) | |
| \(63\quad \boxed{59}\quad \boxed{55}\quad \boxed{47}\quad \boxed{45}\quad 42\quad \boxed{18}\quad \boxed{17}\quad 15\quad \boxed{11}\) pivot 45 | |
| \(63\quad \boxed{59}\quad \boxed{55}\quad \boxed{47}\quad \boxed{45}\quad 42\quad \boxed{18}\quad \boxed{17}\quad 15\quad \boxed{11}\) (sort complete) |
Ascending (middle right)
| \(59\quad 45\quad 18\quad 55\quad 47\quad \boxed{11}\quad 63\quad 17\quad 15\quad 42\) (11) | M1 |
| \(\boxed{11}\quad 59\quad 45\quad 18\quad 55\quad \boxed{47}\quad 63\quad 17\quad 15\quad 42\) (47) | |
| \(\boxed{11}\quad 45\quad 18\quad \boxed{17}\quad 15\quad 42\quad \boxed{47}\quad 59\quad \boxed{55}\quad 63\) (17, 55) | A1 |
| \(\boxed{11}\quad 15\quad \boxed{17}\quad 45\quad \boxed{18}\quad 42\quad \boxed{47}\quad \boxed{55}\quad 59\quad \boxed{63}\) ((15), 18, 63) | |
| \(\boxed{11}\quad 15\quad \boxed{17}\quad \boxed{18}\quad 45\quad \boxed{42}\quad \boxed{47}\quad \boxed{55}\quad 59\quad \boxed{63}\) (42, (59)) | A1ft |
| \(\boxed{11}\quad 15\quad \boxed{17}\quad \boxed{18}\quad \boxed{42}\quad 45\quad \boxed{47}\quad \boxed{55}\quad 59\quad \boxed{63}\) | A1 CSO + ‘sort complete’ statement |
Ascending (middle left)
| \(59\quad 45\quad 18\quad 55\quad \boxed{47}\quad 11\quad 63\quad 17\quad 15\quad 42\) (47) | M1 |
| \(45\quad 18\quad \boxed{11}\quad 17\quad 15\quad 42\quad \boxed{47}\quad 59\quad \boxed{55}\quad 63\) (11, 55) | |
| \(\boxed{11}\quad 45\quad 18\quad \boxed{17}\quad 15\quad 42\quad \boxed{47}\quad \boxed{55}\quad \boxed{59}\quad 63\) (17, 59) | A1 |
| \(\boxed{11}\quad 15\quad \boxed{17}\quad 45\quad \boxed{18}\quad 42\quad \boxed{47}\quad \boxed{55}\quad \boxed{59}\quad 63\) ((15), 18, (63)) | |
| \(\boxed{11}\quad 15\quad \boxed{17}\quad \boxed{18}\quad \boxed{45}\quad 42\quad \boxed{47}\quad \boxed{55}\quad \boxed{59}\quad 63\) (45) | A1ft |
| \(\boxed{11}\quad 15\quad \boxed{17}\quad \boxed{18}\quad 42\quad \boxed{45}\quad \boxed{47}\quad \boxed{55}\quad \boxed{59}\quad 63\) | A1 CSO + ‘sort complete’ statement |
| Scheme | Marks |
|---|---|
| Bin 1: \(\underline{63}\ \ \boxed{18}\ \ \boxed{17}\) | M1 A1 A1 |
| Bin 2: \(\underline{59}\ \ 15\ \ 11\) | |
| Bin 3: \(\underline{55}\ \ \underline{45}\) | |
| Bin 4: \(\underline{47}\ \ \boxed{42}\) | |
| (3) |
Notes
b1M1: Must be using ‘sorted’ list in descending order. First five items placed correctly and at least eight values placed in bins – condone cumulative totals for M1 only (the underlined values)
b1A1: First eight items placed correctly (the underlined and boxed values)
b2A1: CSO
SC for part (b) – if ‘sorted’ list is incorrect from part (a) and M0 would be awarded in (b) then award M1 only in (b) for their first eight items correctly placed – by ‘incorrect’ they can have only one error, e.g. one missing number, one extra number, or one number incorrectly placed| Scheme | Marks |
|---|---|
| \(\frac{372}{100} = 3.72\) so yes the solution in (b) is optimal | M1 A1 |
| (2) | |
| (9 marks) |
Notes
c1M1: Attempt to find lower bound \((372 \pm 63)/100\) (a value of 3.72 seen with no working can imply this mark) or any argument based on the four largest values
c1A1: CSO – correct calculation seen or 3.72 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 (b) is A0. For those using the four largest values argument they must clearly explain why two of these values cannot be placed in a bin e.g. the sum of any two of 63, 59, 55, 47 is greater than 100 so no two can be placed in a bin