D1 January 2013 Q2

EdexcelOld spec6 marksAlgorithms

(a) Starting with a list of all the letters of the alphabet in alphabetical order, demonstrate how a binary search is used to locate the letter P. In each iteration, you must make clear your pivot and the part of the list you are retaining. (4)

(b) Find the maximum number of iterations needed to locate any particular letter of the alphabet. Justify your answer. (2)

Mark scheme (a)

Scheme	Marks
Pivot 1 = \(\left\lceil \frac{1+26}{2}\right\rceil = \lceil 13.5\rceil = 14\) letter N reject A – N	M1 A1
Pivot 2 = \(\left\lceil \frac{15+26}{2}\right\rceil = \lceil 20.5\rceil = 21\) letter U reject U – Z
Pivot 3 = \(\left\lceil \frac{15+20}{2}\right\rceil = \lceil 17.5\rceil = 18\) letter R reject R – T	A1
Pivot 4 = \(\left\lceil \frac{15+17}{2}\right\rceil = 16\) letter P – located	A1
	(4)

Notes

a1M1 Choosing middle right pivot (choosing middle left is M0) + discarding/retaining half the list. M1 only for an ‘incorrect’ list - allow 1 error (e.g. two letters interchanged) or one omission or 1 extra letter.

a1A1 First pass correct i.e. N found as pivot for a correct list and either using O to Z in 2nd pass or discarding A to N (so therefore no ‘sticky’ pivots – sticky is when the letter being considered is retained in the next pass)

a2A1 Second and third passes correct i.e. U and R (no sticky pivots).

Special case: Allow recovery for this mark if a sticky pivot is used in first pass but sticky pivots are not used in the 2nd and 3rd passes. So after retaining N incorrectly the 2nd pass would give T and the 3rd pass would give Q leaving a list with N O P.

a3A1 CSO (correct solution only – all three previous marks must have been awarded to score this mark) search complete + ‘found’ (accept ‘found’, ‘located’, ‘stop’, etc. but not just the letter; must be convinced that P has been located).

If no alphabetical list seen then withhold the final A mark in part (a). If the alphabetical list is not given then bod that candidate is using the correct ordered list (which is implied by the correct passes). Listing the alphabet and then numbering the alphabet and referring to the corresponding numbers is fine for full marks. Candidates may renumber their list for each pass to calculate pivots. However, use of numbers and comparing to 16 without any reference to the alphabet is M0.

Mark scheme (b)

Scheme	Marks
E.g. The maximum number of letters at the start of each iteration is 26, 13, 6, 3, 1	M1
So a maximum of 5 iterations is necessary	A1
	(2)
	(6 marks)

Notes

b1M1 Numerical argument; listing size of list, using logs, etc.

b1A1 Correct complete argument.