D1 June 2013 Q2

EdexcelOld spec11 marksAlgorithms

0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3

(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2. (3)

(b) The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear. (4)

(c) Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2. (3)

(d) Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer. (1)

Mark scheme (a)

Scheme	Marks
Bin 1: 0.6 0.2 0.4 0.5 0.1 Bin 3: 1.6 Bin 2: 1.5 0.3 Bin 4: 0.7 0.9	M1 A1 A1
	(3)

Notes

a1M1 First four items placed correctly and at least six values put in bins. (Condone cumulative totals here only.)

a1A1 Bin 1 correct

a2A1 CSO All correct

Misreads

If they have misread a number at the start of part (a), so genuinely miscopied and got say 1.0 instead of 0.1 then mark the whole question as a misread – removing the last two A or B marks earned. This gives a maximum total of 9.
If they have used the correct numbers in part (a) and they then use incorrect numbers in part (b) (say 1.0 instead of 0.1) from the beginning of the sort or misread their own numbers during part (b) then count it as an error in part (b) but mark part (c) as a misread – giving a maximum of 8 or maybe 7 marks depending on how many marks they lose in (b).

Mark scheme (b)

Scheme	Marks
0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3 pivot 0.5	M1
0.6 1.5 1.6 0.7 0.9 0.5 0.2 0.4 0.1 0.3 pivots 1.6 0.1	A1
1.6 0.6 1.5 0.7 0.9 0.5 0.2 0.4 0.3 0.1 pivots 0.7 0.4
1.6 1.5 0.9 0.7 0.6 0.5 0.4 0.2 0.3 0.1 pivots 0.9 0.3 (0.6)	A1ft
1.6 1.5 0.9 0.7 0.6 0.5 0.4 0.3 0.2 0.1 sort complete	A1cso
	(4)

Notes

b1M1 Quick sort – pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0) and first pass gives >p, p, <p. So after the first pass the list should read (values greater than the pivot), pivot, (values less than the pivot). If only choosing 1 pivot per iteration M1 only

b1A1 First pass correct, next two pivots chosen consistently for second pass.

b2A1ft second and third passes correct (ft from their first pass and choice of pivots) – need not be choosing pivots for the fourth pass for this mark.

b3A1 CSO (correct solution only – all previous marks in this part must have been awarded) including ‘sort complete’ – this could be shown by the final list being re-written or ‘sorted’ statement or each item being used as a pivot.

Part (b) Using middle left as pivot

0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3 pivot 0.4	M1
0.6 1.5 1.6 0.5 0.7 0.9 0.4 0.2 0.1 0.3 pivots 1.6 0.1	A1
1.6 0.6 1.5 0.5 0.7 0.9 0.4 0.2 0.3 0.1 pivots 0.5 0.2
1.6 0.6 1.5 0.7 0.9 0.5 0.4 0.3 0.2 0.1 pivots 1.5 (0.3)	A1ft
1.6 1.5 0.6 0.7 0.9 0.5 0.4 0.3 0.2 0.1 pivot 0.7
1.6 1.5 0.9 0.7 0.6 0.5 0.4 0.3 0.2 0.1 sort complete	A1cso

Sorting list into ascending order in (b)

If the candidate sorts the list into ascending order and reverses the list in part (b) then they can score full marks.
If the list is not reversed in part (b) then mark as a misread (so remove the last two A marks if earned in part (b)). If the list is reversed at the start of part (c) but not in part (b) then still treat this as a misread. If the list is still in ascending order in part (c) award no marks for first fit increasing. If the candidate says that the list needs reversing in part (b) but doesn’t actually show the reversed list in part (b) then remove the final A mark.

Ascending (middle left)

0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3 (0.4)	M1
0.2 0.1 0.3 0.4 0.6 1.5 1.6 0.5 0.7 0.9 (0.1, 0.6)	A1
0.1 0.2 0.3 0.4 0.6 1.5 0.5 0.7 0.9 1.6 (0.2, 0.5)
0.1 0.2 0.3 0.4 0.5 0.6 1.5 0.7 0.9 1.6 ((0.3), 1.5)	A1ft
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.9 1.5 1.6 (0.7)
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.9 1.5 1.6	A1cso+complete

Ascending (middle right)

0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3 (0.5)	M1
0.2 0.4 0.1 0.3 0.5 0.6 1.5 1.6 0.7 0.9 (0.1, 1.6)	A1
0.1 0.2 0.4 0.3 0.5 0.6 1.5 0.7 0.9 1.6 (0.4, 0.7)
0.1 0.2 0.3 0.4 0.5 0.6 0.7 1.5 0.9 1.6 (0.3, (0.6), 0.9)	A1ft
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.9 1.5 1.6	A1cso+complete

Mark scheme (c)

Scheme	Marks
Bin 1: 1.6 0.4 Bin 2: 1.5 0.5 Bin 3: 0.9 0.7 0.3 0.1 Bin 4: 0.6 0.2	M1 A1 A1
	(3)

Notes

c1M1 Must be using ‘sorted’ list in descending order. First four items placed correctly and at least six values put in bins. (Condone cumulative totals here only.)

c1A1 First seven items placed correctly (so Bin 1 and 2 correct, Bin 3 containing 0.9 and 0.7 and Bin 4 containing 0.6)

c2A1 CSO

SC for part (c) If ‘sorted’ list is wrong from part (b) (i.e. one error e.g. a missing number, an extra number or one number incorrectly placed) then award M1 only in (c) for their first seven items correctly placed.

Mark scheme (d)

Scheme	Marks
e.g. 6.8/2 = 3.4 so yes a minimum of 4 bins is needed	B1
	(1)
	(11 marks)

Notes

d1B1 A conclusion based on their answer to part (c) together with either a correct lower bound calculation or based on the total > 6 or full bins (three of the bins are full in part (c)).