| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.8 This is a straightforward application of the dynamic programming algorithm to find the shortest path in a small network. The method is algorithmic and routine for D2 students—working backwards from H to A, computing minimum costs at each stage. While it requires careful arithmetic (especially with negative edge weights), it demands no problem-solving insight or novel thinking, just systematic application of a standard procedure. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03h Best/worst/typical case: run-time analysis |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Working back from \(H\), starting from \(A\) (network); \(B\ 8^1\), \(F\ 5^2\ 4^3\) | B1 | First (stage) costs |
| Second stage attempt | M1 | Second stage indicated e.g. \(15^2\) etc |
| \(C\ 7^1\ 6^2\), \(H\ 16^2\ 14^4\ 14^5\) | M1 | Third stage attempt (two numbers crossed out) |
| \(D\ 9^1\ 6^2\ 5^3\), \(G\ 12^2\ 8^4\) | M1 | |
| \(E\ 8^1\) | A1 | Final value of 14 dependent on M2 earned |
| All correct with 2 clear routes to cost 14 | A1 | Total: 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Min cost \(= 14\) | B1 | |
| \(ABCFH\) | B1 | |
| and \(ABCDGH\) | B1 | Total: 3 |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Working back from $H$, starting from $A$ (network); $B\ 8^1$, $F\ 5^2\ 4^3$ | B1 | First (stage) costs |
| Second stage attempt | M1 | Second stage indicated e.g. $15^2$ etc |
| $C\ 7^1\ 6^2$, $H\ 16^2\ 14^4\ 14^5$ | M1 | Third stage attempt (two numbers crossed out) |
| $D\ 9^1\ 6^2\ 5^3$, $G\ 12^2\ 8^4$ | M1 | |
| $E\ 8^1$ | A1 | Final value of 14 dependent on M2 earned |
| All correct with 2 clear routes to cost 14 | A1 | Total: 6 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Min cost $= 14$ | B1 | |
| $ABCFH$ | B1 | |
| and $ABCDGH$ | B1 | Total: 3 |
---3 [Figure 3, printed on the insert, is provided for use in this question.]\\
The following network shows eight vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown.\\
\includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-03_595_1234_1866_386}
\begin{enumerate}[label=(\alph*)]
\item Use dynamic programming to find the minimum cost of travelling from $A$ to $H$. You may use Figure 3 for your working.
\item State the minimum cost and the possible routes corresponding to this minimum cost.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2006 Q3 [9]}}