| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 9 |
| 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 systematic substitution through given steps with no conceptual insight needed. Students follow mechanical instructions to trace Euclid's algorithm twice, then recognize its purpose—all routine D1 content requiring only careful arithmetic and pattern recognition. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(C=2, D=32, E=4\) | M1 | Correct first iteration |
| \(A=16, B=4\); then \(C=4, D=16, E=0\) | A1 | Second iteration correct |
| Print \(B=4\) | A1 | Correct output |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(C=1, D=7, E=4\) | M1 | First iteration |
| \(A=7, B=4\); \(C=1, D=4, E=3\) | A1 | Second iteration |
| \(A=4, B=3\); \(C=1, D=3, E=1\) | A1 | Third iteration |
| \(A=3, B=1\); \(C=3, D=3, E=0\) | A1 | Fourth iteration |
| Print \(B=1\) | A1 | Correct output |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Finds the Highest Common Factor (HCF/GCD) of two numbers | B1 | Accept "greatest common divisor" |
## Question 6:
### Part (a)(i) – Trace $A=36$, $B=16$
| Answer/Working | Marks | Guidance |
|---|---|---|
| $C=2, D=32, E=4$ | M1 | Correct first iteration |
| $A=16, B=4$; then $C=4, D=16, E=0$ | A1 | Second iteration correct |
| Print $B=4$ | A1 | Correct output |
### Part (a)(ii) – Trace $A=11$, $B=7$
| Answer/Working | Marks | Guidance |
|---|---|---|
| $C=1, D=7, E=4$ | M1 | First iteration |
| $A=7, B=4$; $C=1, D=4, E=3$ | A1 | Second iteration |
| $A=4, B=3$; $C=1, D=3, E=1$ | A1 | Third iteration |
| $A=3, B=1$; $C=3, D=3, E=0$ | A1 | Fourth iteration |
| Print $B=1$ | A1 | Correct output |
### Part (b) – Purpose
| Answer/Working | Marks | Guidance |
|---|---|---|
| Finds the Highest Common Factor (HCF/GCD) of two numbers | B1 | Accept "greatest common divisor" |6 A student is tracing the following algorithm. The function INT gives the integer part of any number, eg $\operatorname { INT } ( 2.3 ) = 2$ and $\operatorname { INT } ( 6.7 ) = 6$.
Line 10 Input $A , B$\\
Line $20 \quad$ Let $C = \operatorname { INT } ( A \div B )$\\
Line 30 Let $D = B \times C$\\
Line $40 \quad$ Let $E = A - D$\\
Line 50 If $E = 0$ then go to Line 90\\
Line 60 Let $A = B$\\
Line $70 \quad$ Let $B = E$\\
Line 80 Go to Line 20\\
Line 90 Print $B$\\
Line 100 Stop
\begin{enumerate}[label=(\alph*)]
\item Trace the algorithm when the input values are:
\begin{enumerate}[label=(\roman*)]
\item $A = 36$ and $B = 16$;
\item $A = 11$ and $B = 7$.
\end{enumerate}\item State the purpose of the algorithm.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q6 [9]}}