D1 June 2012 Q1

EdexcelOld spec12 marksAlgorithms

1. A carpet fitter needs the following lengths, in metres, of carpet.

20 33 19 24 31 22 27 18 25

He cuts them from rolls of length 50 m.

(a) Calculate a lower bound for the number of rolls he needs.
You must make your method clear. (2)

(b) Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m. (3)

(c) Carry out a bubble sort to produce a list of the lengths needed in descending order.
You need only give the state of the list after each pass. (4)

(d) Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls. (3)

Scheme	Marks
\(\dfrac{219}{50} = 4.38\) so lower bound is 5 bins	M1 A1
	(2)

Mark scheme (b)

Scheme	Marks
Bin 1: 20 19 Bin 2: 33 Bin 3: 24 22 Bin 4: 31 18	M1 1A1 2A1
Bin 5: 27 Bin 6: 25
	(3)

Notes

b1M1 First four terms placed correctly in bins 1, 2 and 3. (Condone cumulative totals here only.)

b1A1 First seven terms placed correctly.

b2A1 CAO

Mark scheme (c)

Scheme	Marks
e.g. (left to right)
20 33 19 24 31 22 27 18 25
33 20 24 31 22 27 19 25 18	M1
33 24 31 22 27 20 25 19 18	1A1
33 31 24 27 22 25 20 19 18
33 31 27 24 25 22 20 19 18	2A1ft
33 31 27 25 24 22 20 19 18
List in order	3A1 CSO
	(4)

Notes

c1M1 Bubble sort. Consistent direction throughout sort, end number (greatest/least) in place.

c1A1 first and second passes correct – so end two numbers in place

c2A1ft 3rd and 4th passes correct – so end four numbers in place.

c3A1 CSO; including ‘sorted’ or final list rewritten in (c) or ‘final pass’ o.e. A clear statement in (c).

Alt for (c) right to left

20 33 19 24 31 22 27 18 25
33 20 31 19 24 27 22 25 18	M1
33 31 20 27 19 24 25 22 18	1A1
33 31 27 20 25 19 24 22 18
33 31 27 25 20 24 19 22 18	2A1ft
33 31 27 25 24 20 22 19 18
33 31 27 25 24 22 20 19 18
List in order	3A1 CSO

Question 1 (c) Misread

Usual rule, remove the last 2 A marks awarded in (c) if list not reversed.

Note: if final list is reversed in (c), award full credit

20 33 19 24 31 22 27 18 25	M1
20 19 24 31 22 27 18 25 33
19 20 24 22 27 18 25 31 33	A1
19 20 22 24 18 25 27 31 33
19 20 22 18 24 25 27 31 33	A1ft
19 20 18 22 24 25 27 31 33
19 18 20 22 24 25 27 31 33
18 19 20 22 24 25 27 31 33
List in order	A1 CSO

20 33 19 24 31 22 27 18 25	M1
18 20 33 19 24 31 22 27 25
18 19 20 33 22 24 31 25 27	A1
18 19 20 22 33 24 25 31 27
18 19 20 22 24 33 25 27 31	A1ft
18 19 20 22 24 25 33 27 31
18 19 20 22 24 25 27 33 31
18 19 20 22 24 25 27 31 33
List in order	A1 CSO

Mark scheme (d)

Scheme	Marks
Bin 1: 33 Bin 2: 31 19 Bin 3: 27 22 Bin 4: 25 24 Bin 5: 20 18	M1 1A1 2A1
	(3)
	(12 marks)

Notes

d1M1 Must be using ‘sorted’ list in decreasing order. First five terms correct.

d1A1 First seven terms correct.

d2A1 CAO

SC for 1(d) If ‘sorted’ list is wrong from (c) then award M1 only in (d) for their first seven terms correctly placed.