| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2001 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Binary Search Execution |
| Difficulty | Easy -1.3 This is a straightforward application of the binary search algorithm with no problem-solving required. Part (a) asks students to mechanically apply a standard algorithm they've learned, showing each step on a small list where HUSSAIN is found quickly. Part (b) requires only recall of the formula for maximum comparisons (⌈log₂(n)⌉ or counting tree depth). Both parts are routine bookwork with no conceptual challenges beyond basic algorithm execution. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt |
| Answer | Marks | Guidance |
|---|---|---|
| B1 cae | Odd vertices are A, D, E and F | |
| M1 A1 | Possible pairings shortest route total: (A,F) and (D,E): AF + DE = 150, (60) + (90) = 150 | |
| M1 A1 | (A,E) and (D,F): AFGE + DGF = 240, (190) + (70) = 240 | |
| M1 A1 | (A,D) and (E,F): ACD + EGF = 230, (120) + (110) = 230 | |
| A1(5) | So repeat AF and DE | |
| A1(5) | Possible route: AFEDEGDCBACGEBA | |
| (b) | M1 | Total length of route = Total weight of edges + 150 |
| A1(2) | = 690 + 150 = 840 m |
| B1 cae | Odd vertices are A, D, E and F |
| M1 A1 | Possible pairings shortest route total: (A,F) and (D,E): AF + DE = 150, (60) + (90) = 150 |
| M1 A1 | (A,E) and (D,F): AFGE + DGF = 240, (190) + (70) = 240 |
| M1 A1 | (A,D) and (E,F): ACD + EGF = 230, (120) + (110) = 230 |
| A1(5) | So repeat AF and DE |
| A1(5) | Possible route: AFEDEGDCBACGEBA |
(b) | M1 | Total length of route = Total weight of edges + 150 |
| A1(2) | = 690 + 150 = 840 m |
---\begin{enumerate}[label=(\alph*)]
\item Use the binary search algorithm to locate the name HUSSAIN in the following alphabetical list. Explain each step of the algorithm.
1. ALLEN
2. BALL
3. COOPER
4. EVANS
5. HUSSAIN
6. JONES
7. MICHAEL
8. PATEL
9. RICHARDS
10. TINDALL
11. WU
[6 marks]
\item State the maximum number of comparisons that need to be made to locate a name in an alphabetical list of 11 names. [1 mark]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2001 Q2 [7]}}