| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.8 This is a standard textbook dynamic programming question requiring systematic backward iteration through a network to find the longest path. The algorithm is mechanical and well-practiced in D2, with the table structure provided to guide students through each step. While it requires careful arithmetic and organization, it demands no novel insight or problem-solving beyond applying the taught algorithm. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities7.05c Total float: calculation and interpretation |
| Stage | State | From | Value |
| 1 | G | I | |
| H | I | ||
| 2 | |||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(G\): From \(I\), Value = \(15\) | B1 | Direct edge \(G \to I = 15\) |
| \(H\): From \(I\), Value = \(12\) | B1 | Direct edge \(H \to I = 12\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(E\): From \(G\), Value = \(15 + 15 = 30\) | M1 | Considering \(E \to G \to I\) |
| \(F\): From \(G\), Value = \(13 + 15 = 28\); From \(H\), Value = \(17 + 12 = 29\); max = \(29\), From \(H\) | A1 | Correct values and maximum selected |
| \(C\): From \(E\), Value = \(14 + 30 = 44\); From \(F\), Value = \(12 + 29 = 41\); max = \(44\), From \(E\) | A1 | Correct working shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B\): From \(E\), Value = \(16 + 30 = 46\) | M1 | Correct stage 3 working |
| \(D\): From \(F\), Value = \(15 + 29 = 44\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A\): From \(B\), Value = \(12 + 46 = 58\); From \(C\), Value = \(20 + 44 = 64\); From \(D\), Value = \(18 + 44 = 62\); max = \(64\), From \(C\) | A1 | Correct maximum of 64 identified |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A \to C \to E \to G \to I\) | B1 | Follow-through from table; route must be consistent with working |
# Question 7:
## Part (a) - Dynamic Programming Table (7 marks)
**Stage 1:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $G$: From $I$, Value = $15$ | B1 | Direct edge $G \to I = 15$ |
| $H$: From $I$, Value = $12$ | B1 | Direct edge $H \to I = 12$ |
**Stage 2:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $E$: From $G$, Value = $15 + 15 = 30$ | M1 | Considering $E \to G \to I$ |
| $F$: From $G$, Value = $13 + 15 = 28$; From $H$, Value = $17 + 12 = 29$; max = $29$, From $H$ | A1 | Correct values and maximum selected |
| $C$: From $E$, Value = $14 + 30 = 44$; From $F$, Value = $12 + 29 = 41$; max = $44$, From $E$ | A1 | Correct working shown |
**Stage 3:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $B$: From $E$, Value = $16 + 30 = 46$ | M1 | Correct stage 3 working |
| $D$: From $F$, Value = $15 + 29 = 44$ | A1 | |
**Stage 4:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $A$: From $B$, Value = $12 + 46 = 58$; From $C$, Value = $20 + 44 = 64$; From $D$, Value = $18 + 44 = 62$; max = $64$, From $C$ | A1 | Correct maximum of 64 identified |
## Part (b) - Optimal Route (1 mark)
| Answer | Mark | Guidance |
|--------|------|----------|
| $A \to C \to E \to G \to I$ | B1 | Follow-through from table; route must be consistent with working |7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road.
A collector is to drive from $A$ to $I$.\\
\includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-20_867_1644_552_191}
\begin{enumerate}[label=(\alph*)]
\item Working backwards from $\boldsymbol { I }$, use dynamic programming to find the maximum number of bags that can be collected when driving from $A$ to $I$.
You must complete the table opposite as your solution.
\item State the route that the collector should take in order to collect the maximum number of bags.
(a)
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Stage & State & From & Value \\
\hline
1 & G & I & \\
\hline
& H & I & \\
\hline
& & & \\
\hline
2 & & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
\end{tabular}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2013 Q7 [8]}}