D1 June 2019 Q4

EdexcelOld spec15 marksAlgorithms

The numbers in the list represent the weights, in kilograms, of eleven suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 50 kg.

(a) Calculate a lower bound for the number of containers needed. You must make your method clear. (2)

(b) Use the first-fit bin packing algorithm to allocate the suitcases to the containers. (2)

(c) Carry out a quick sort to produce a list of the weights in descending order. You should show the result of each pass and identify your pivots clearly. (4)

(d) Use the first-fit decreasing bin packing algorithm to allocate the suitcases to the containers. (3)

The two heaviest suitcases are replaced with two suitcases both of which weigh \(x\) kg. It is given that the lower bound for the number of containers needed is now one less than the number found in (a).

(e) Determine the range of values for \(x\). You should make your working clear. (4)

Mark scheme (a)

Scheme	Marks
\(\dfrac{204}{50} = 4.08\) so lower bound is 5 containers	M1 A1
	(2)

Notes

PLEASE NOTE NO MISREADS IN THIS QUESTION – MARK ACCORDING TO THE SCHEME AND THE SPECIAL CASES IN PARTS (c) AND (d)

a1M1: Attempt to find the lower bound \((204 \pm 40) / 50\) (a value of 4.08 seen with no working can imply this mark)

a1A1: CSO - correct calculation seen or 4.08 followed by 5 (containers) – accept 4.1 followed by 5 if correct calculation seen. An answer of 5 with no working scores M0A0

Mark scheme (b)

Scheme	Marks
Container 1: 25 9 16 Container 2: 32 17 Container 3: 23 18 4 Container 4: 12 8 Container 5: 40	M1 A1
	(2)

Notes

b1M1: First five items placed correctly and at least eight values placed in containers. Condone cumulative totals for M1 only (the values in bold)

b1A1: CSO (correct solution only – so no additional/repeated values)

Mark scheme (c)

Scheme

Marks

middle right

25	9	32	16	17	23	18	12	4	8	40
25	32	40	23	9	16	17	18	12	4	8
40	32	25	23	18	9	16	17	12	4	8
40	32	25	23	18	16	17	12	9	4	8
40	32	25	23	18	17	16	12	9	8	4
40	32	25	23	18	17	16	12	9	8	4

M1
A1
A1ft
A1

middle left

25	9	32	16	17	23	18	12	4	8	40
25	32	40	23	9	16	17	18	12	4	8
40	32	25	23	18	9	16	17	12	4	8
40	32	25	23	18	17	9	16	12	4	8
40	32	25	23	18	17	16	12	9	4	8
40	32	25	23	18	17	16	12	9	8	4
40	32	25	23	18	17	16	12	9	8	4

(4)

Notes

c1M1: Quick sort – pivot, \(p\), chosen (must be choosing middle left or middle 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 that the pivot). If only choosing one pivot per iteration then M1 only – bubble sort is not a MR and scores M1 only for 25 32 16 17 23 18 12 9 8 40 4

c1A1: 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 value of 12 or (if middle left) pivot value of 17

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 (correct solution only – all previous marks in this part must have been awarded) - if middle right then a fifth pass in which the 8 is used as a pivot must be included or if middle left then a fifth pass in which the 4 is used as a pivot and a sixth pass in which the 9 is used as a pivot must be included

SC for (c): If using an incorrect list from the start of (c) with only one error (an error is either one missing number, one extra number, one incorrect number or one number incorrectly placed) then the most they can score is M1A0A1ftA0

Sorting list into ascending order in (c)

If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (c)
If the list is not reversed in (c) then remove the last two A marks earned in (c). If the list is reversed at the start of (d) but not in (c) then still remove the last two A marks earned in (c). If the list is in ascending order in (c) award no marks for first-fit increasing in (d). If the candidate says that the list needs reversing in (c) but does not actually show the reversed list in (c) then remove the last A mark earned

Mark scheme (d)

Scheme	Marks
Container 1: 40 9 Container 2: 32 18 Container 3: 25 23 Container 4: 17 16 12 4 Container 5: 8	M1 A1 A1
	(3)

Notes

d1M1: Must be using the correct 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 bold values)

d1A1: First seven items placed correctly (the underlined and bold values)

d2A1: CSO (so no additional/repeated values)

SC for (d) – if ‘sorted’ list is incorrect from part (c) and M0 would be awarded in (d) then award M1 only in (d) for their first eight items correctly placed – by ‘incorrect’ they can have only one ‘error’- an ‘error’ is one missing number, one extra number, one incorrect number or one number incorrectly placed. Allow full marks in (d) if a correct list is used in (d) even if the list is incorrect at the end of (c). Please note that if ‘sorted’ list is incorrect in (c) and it is clear that this has been used from their working in (d) then please award at most M1 in (d)

Mark scheme (e)

Scheme	Marks
Total weight of suitcases: \(132 + 2x\)	B1
\(3 \lt \dfrac{132 + 2x}{50} \leqslant 4\)	M1
\(9 \lt x \leqslant 34\)	A1 A1
	(4)
	15 marks

Notes

e1B1: \(132 + 2x\) (oe)

e1M1: \(((132 \pm 15) + 2x) / 50\) ‘equated’ to their 3 or their 4 (that is 1 or 2 less than the lower bound stated in (a))

e1A1: Either 9 or 34 correctly found

e2A1: \(9 \lt x \leqslant 34\) as a final answer (do not isw incorrect ‘simplification’)