| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Standard +0.3 This is a standard dynamic programming tabulation exercise from D2, requiring systematic application of the DP algorithm to find a shortest path. While it involves multiple steps and careful bookkeeping, it's a routine procedural question testing direct application of a taught method rather than problem-solving or insight. Part (ii) adds slight difficulty by requiring explanation of the traceback process, but this is still standard curriculum content. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Table structure correct (stage, state, action and 'working' columns) | B1 | |
| Stage and state values correct; Action values correct | M1, A1 | [3] |
| Working column substantially correct for stage 2 (calcs or totals, at most 1 error) | M1 | |
| Suboptimal minima \((10, 8, 7)\) correct for stage 2, cao | A1 | [2] |
| Working column substantially correct for stage 1 (at most 1 error) | M1 | |
| Suboptimal minima \((11, 10, 15)\) correct for stage 1, cao | A1 | [2] |
| Minimum route \(= (0;0)-(1;0)-(2;1)-(3;0)-(4;0)\); Weight \(= 17\) | B1 | Correct route from \((0;0)\) to \((4;0)\) |
| Weight \(= 17\) cao (written down, not just implied from table) | B1 | [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Start at \((0;0)\), action 0 or value 11 (theirs), hence \((1;0)\) | M1 | Start at \((0;0)\), action 0 or value 11 (theirs), hence \((1;0)\) |
| \((1;0)\), action 1 (theirs), hence \((2;1)\); clearly relating action to state for stage above | A1 | [2] |
# Question 3:
## Part (i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Table structure correct (stage, state, action and 'working' columns) | B1 | |
| Stage and state values correct; Action values correct | M1, A1 | [3] |
| Working column substantially correct for stage 2 (calcs or totals, at most 1 error) | M1 | |
| Suboptimal minima $(10, 8, 7)$ correct for stage 2, cao | A1 | [2] |
| Working column substantially correct for stage 1 (at most 1 error) | M1 | |
| Suboptimal minima $(11, 10, 15)$ correct for stage 1, cao | A1 | [2] |
| Minimum route $= (0;0)-(1;0)-(2;1)-(3;0)-(4;0)$; Weight $= 17$ | B1 | Correct route from $(0;0)$ to $(4;0)$ |
| Weight $= 17$ cao (written down, not just implied from table) | B1 | [2] |
## Part (ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Start at $(0;0)$, action 0 or value 11 (theirs), hence $(1;0)$ | M1 | Start at $(0;0)$, action 0 or value 11 (theirs), hence $(1;0)$ |
| $(1;0)$, action 1 (theirs), hence $(2;1)$; clearly relating action to state for stage above | A1 | [2] |
---3 (i) Set up a dynamic programming tabulation to find the minimum weight route from ( $0 ; 0$ ) to ( $4 ; 0$ ) on the following directed network.\\
\includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-03_707_1342_1594_443}
Give the route and its total weight.\\
(ii) Explain carefully how the route is obtained directly from the values in the table, without referring to the network.
\hfill \mbox{\textit{OCR D2 2010 Q3 [11]}}