| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2021 |
| Session | January |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Binary Search Execution |
| Difficulty | Easy -1.8 This is a purely algorithmic recall question requiring mechanical application of binary search to a simple alphabetical list. It involves no mathematical problem-solving, just following a memorized procedure with straightforward alphabetical comparisons. The word isn't even in the list, making it even more routine. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(\left\lceil\frac{1+10}{2}\right\rceil = 6\) Diameter – reject \(1-6\) | M1 | Choosing middle right pivot (choosing middle left 'Circumference' is M0) + an attempt at discarding/retaining half the list (condone if retaining the wrong half or if only rejecting \(1-5\)) |
| \(\left\lceil\frac{7+10}{2}\right\rceil = 9\) Segment – reject \(9-10\) | A1 | First pass correct i.e. 6th item and using \(7-10\) in second pass (must not be using the 6th item in second pass) – need not choose 9th item or reject \(9-10\) for this mark |
| \(\left\lceil\frac{7+8}{2}\right\rceil = 8\) Sector – reject \(8\) | A1 | Second and third passes correct i.e. 9th (Segment) and 8th (Sector) items (no sticky pivots) – need not be rejecting the 8th item for this mark |
| \([7] = 7\) Radius – reject; Parallelogram is not in list | A1 (4) | CAO search complete (rejecting 8th and 7th items) + 'not found' – must consider Radius by name or the '7th item' after rejecting Sector. Condone if Radius is rejected on same line as Sector (but must be after Sector). Condone candidates that correctly state Radius is not Parallelogram or who do not explicitly reject Radius e.g. '\([7]=7\) Radius therefore Parallelogram is not in the list.' |
## Question 1:
| Answer/Working | Mark | Guidance |
|---|---|---|
| $\left\lceil\frac{1+10}{2}\right\rceil = 6$ Diameter – reject $1-6$ | M1 | Choosing middle right pivot (choosing middle left 'Circumference' is M0) + an attempt at discarding/retaining half the list (condone if retaining the wrong half or if only rejecting $1-5$) |
| $\left\lceil\frac{7+10}{2}\right\rceil = 9$ Segment – reject $9-10$ | A1 | First pass correct i.e. 6th item **and** using $7-10$ in second pass (must not be using the 6th item in second pass) – need not choose 9th item or reject $9-10$ for this mark |
| $\left\lceil\frac{7+8}{2}\right\rceil = 8$ Sector – reject $8$ | A1 | Second and third passes correct i.e. 9th (Segment) and 8th (Sector) items (no sticky pivots) – need not be rejecting the 8th item for this mark |
| $[7] = 7$ Radius – reject; Parallelogram is not in list | A1 **(4)** | CAO search complete (rejecting 8th and 7th items) + 'not found' – must consider Radius by name or the '7th item' after rejecting Sector. Condone if Radius is rejected on same line as Sector (but must be after Sector). Condone candidates that correctly state Radius is not Parallelogram or who do not explicitly reject Radius e.g. '$[7]=7$ Radius therefore Parallelogram is not in the list.' |
**Total: 4 marks**\begin{enumerate}
\item Use the binary search algorithm to try to locate the word "Parallelogram" in the following alphabetical list. Clearly indicate how you choose your pivots and which part of the list you are rejecting at each stage.
\end{enumerate}
Arc
Centre
Chord
Circle
Circumference
Diameter
Radius
Sector
Segment
Tangent\\
\hfill \mbox{\textit{Edexcel D1 2021 Q1 [4]}}