| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Fixed Point Iteration |
| Type | Apply iteration to find root (pure fixed point) |
| Difficulty | Moderate -0.8 This is a straightforward algorithm trace question requiring systematic step-by-step execution with simple arithmetic operations (addition, multiplication), followed by routine function evaluation and a basic interpretation. The algorithm is clearly specified with no ambiguity, the arithmetic is elementary, and part (iii) requires only recognition that a cubic function indicates O(n³) complexity—a standard observation in algorithms. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt7.03f Worst case complexity: T(n) as function of problem size |
2 The following algorithm computes the number of comparisons made when Prim's algorithm is applied to a complete network on $n$ vertices ( $n > 2$ ).
Step 1 Input the value of $n$\\
Step 2 Let $i = 1$\\
Step 3 Let $j = n - 2$\\
Step 4 Let $k = j$\\
Step 5 Let $i = i + 1$\\
Step 6 Let $j = j - 1$\\
Step 7 Let $k = k + ( i \times j ) + ( i - 1 )$\\
Step 8 If $j > 0$ then go to Step 5\\
Step 9 Print $k$\\
Step 10 Stop\\
(i) Apply the algorithm when $n = 5$, showing the intermediate values of $i , j$ and $k$.
The function $\mathrm { f } ( n ) = \frac { 1 } { 6 } n ^ { 3 } - \frac { 7 } { 6 } n + 1$ gives the same output as the algorithm.\\
(ii) Showing your working, check that $\mathrm { f } ( 5 )$ is the same value as your answer to part (i).\\
(iii) What does the structure of $\mathrm { f } ( n )$ tell you about Prim's algorithm?
\hfill \mbox{\textit{OCR MEI D1 2009 Q2 [8]}}