| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Algorithm Tracing |
| Difficulty | Easy -1.2 This is a straightforward algorithm tracing exercise requiring careful bookkeeping but no mathematical insight. Students follow explicit instructions step-by-step, count comparisons mechanically, and identify that the algorithm finds the median. Part (iv) requires only recall of what 'quadratic order' means—a standard D1 definition. No problem-solving or novel reasoning is needed, making this easier than average A-level questions. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt7.03d Order of algorithm: dominant term and scaling run-times |
| Answer | Marks |
|---|---|
| 5, 14, 153, 6, 24, 2, 14, 15 → 5, 14, 153 → 5, 2 | M1 |
| 5, 14, 6, 24, 14, 15 → 5, 14, 24 → 5 | M1 |
| 14, 6, 14, 15, → 14, 15 → 14, 6 | M1 |
| 14, 14 | M1 |
| Answer = 14; Comparisons = 30 | A1 A1 |
| Answer | Marks |
|---|---|
| 5, 14, 153, 6, 24, 2, 14 → 5, 14, 153 → 5, 2 | M1 |
| 5, 14, 6, 24, 14 → 5, 14, 24 → 5 | M1 |
| 14, 6, 14 → 14 → 14, 6 | M1 |
| 14 | M1 |
| Answer = 14; Comparisons = 24 | A1 A1 |
| Answer | Marks |
|---|---|
| Median | B1 |
| Answer | Marks |
|---|---|
| Time taken approximately proportional to square of length of list (or twice length takes four times the time, or equivalent). | B1 |
**(i)**
| 5, 14, 153, 6, 24, 2, 14, 15 → 5, 14, 153 → 5, 2 | M1 | |
| 5, 14, 6, 24, 14, 15 → 5, 14, 24 → 5 | M1 | |
| 14, 6, 14, 15, → 14, 15 → 14, 6 | M1 | |
| 14, 14 | M1 | |
| Answer = 14; Comparisons = 30 | A1 A1 | |
**(ii)**
| 5, 14, 153, 6, 24, 2, 14 → 5, 14, 153 → 5, 2 | M1 | |
| 5, 14, 6, 24, 14 → 5, 14, 24 → 5 | M1 | |
| 14, 6, 14 → 14 → 14, 6 | M1 | |
| 14 | M1 | |
| Answer = 14; Comparisons = 24 | A1 A1 | |
**(iii)**
| Median | B1 | |
**(iv)**
| Time taken approximately proportional to square of length of list (or twice length takes four times the time, or equivalent). | B1 | |2 The following algorithm acts on a list of three or more numbers.\\
Step 1: Set both X and Y equal to the first number on the list.\\
Step 2: If there is no next number then go to Step 5.\\
Step 3: If the next number on the list is bigger than X then set X equal to it. If it is less than Y then set Y equal to it.
Step 4: Go to Step 2.\\
Step 5: Delete a number equal to X from the list and delete a number equal to Y from the list.\\
Step 6: If there is one number left then record it as the answer and stop.\\
Step 7: If there are two numbers left then record their mean as the answer and stop.\\
Step 8: Go to Step 1.\\
(i) Apply the algorithm to the list $5,14,153,6,24,2,14,15$, counting the number of comparisons which you have to make.\\
(ii) Apply the algorithm to the list $5,14,153,6,24,2,14$, counting the number of comparisons which you have to make.\\
(iii) Say what the algorithm is finding.\\
(iv) The order of the algorithm is quadratic. Explain what this means when it is applied to long lists.
\hfill \mbox{\textit{OCR MEI D1 2008 Q2 [8]}}