D1 January 2011 Q2

EdexcelOld spec12 marksAlgorithms

23 29 11 34 10 14 35 17

The numbers represent the sizes, in megabytes (MB), of eight files.

The files are to be stored on 50 MB discs.

(a) Calculate a lower bound for the number of discs needed to store all eight files. (2)

(b) Use the first-fit bin packing algorithm to fit the files onto the discs. (3)

(c) Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass. (4)

(d) Use the first-fit decreasing bin packing algorithm to fit the files onto the discs. (3)

Scheme	Marks
Lower bound = \(\dfrac{173}{50} = 3.46\) so 4 bins	B1 B1
	(2)

Mark scheme (b)

Scheme	Marks
Bin 1: 23 + 11 + 10 Bin 4: 35 Bin 2: 29 + 14 Bin 5: 17 Bin 3: 34	M1 A1 A1
	(3)

1M1: First four items placed correctly and at least 6 values put in bins

1A1: Bin 1 correct (condone cumulative totals)

2A1: All correct (condone cumulative totals)

Mark scheme (c)

Scheme

Marks

e.g.

List sorted - no more changes

M1
A1
A1ft
A1cso

(4)

1M1: Bubble sort, one pass complete end term 35 or 10, consistent direction.

1A1: First two passes correct

2A1ft: Next two passes correct

3A1: cso + ‘final’ or re-listing etc.

Sorting into ascending order
If list reversed into descending order at end, allow full marks

(i) Left to right

(ii) right to left

If list not reversed remove last 2A if earned

Numbers changing during the course of the sort

If the number change does not alter the sort (e.g. 23 becomes 25) remove final A only. If persists in (d) but does not affect answer similarly remove final A only in (d).
If the number alters the sort (e.g 23 becomes 32) mark as a misread in (c) and if persists in (d) mark (c) and (d) together as a misread – so just take 2 marks off in total for these two sections.

Mark scheme (d)

1M1: Bin 3 correct and at least 6 values put in bins

1A1: two bins correct (condone cumulative totals)

2A1: cso (condone cumulative totals)