| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Moderate -0.8 This is a straightforward application of standard dynamic programming techniques to a maximin path problem. The question provides clear stage-state labels, requires only drawing a network from a diagram, identifying it as a maximin problem, and applying tabulation—all routine procedures for D2 students with no novel problem-solving required. |
| Spec | 7.01a Types of problem: existence, construction, enumeration, optimisation7.03a Algorithm definition: input, output, deterministic, finite |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct structure (vertex labels and graph correct) | B1 | |
| Assigning weights to their graph (no more than 1 error or no more than 2 arcs missing/extra) | M1 | |
| Completely correct network | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Maximin | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Four or five columns including 'stage', 'state' and 'action' | B1 | |
| Stage and state columns completed correctly | B1 | |
| Action column completed correctly | B1 | |
| Min values correct for stage 1; suboptimal maximin values correct for stages 2 and 1 | M1, A1 | Follow through their network if possible, no more than 2 arcs missing/extra |
| Min values correct for stage 0; maximin value for stage 0 | M1, A1 | Follow through their network |
| Weight of heaviest truck \(= 8\) tonnes | B1 | 8, cao |
| Maximin route \(= (0;0)-(1;0)-(2;2)-(3;0)\) | B1 | Correct route, or in reverse |
# Question 4:
## Part (i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct structure (vertex labels and graph correct) | B1 | |
| Assigning weights to their graph (no more than 1 error or no more than 2 arcs missing/extra) | M1 | |
| Completely correct network | A1 | |
## Part (ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Maximin | B1 | cao |
## Part (iii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Four or five columns including 'stage', 'state' and 'action' | B1 | |
| Stage and state columns completed correctly | B1 | |
| Action column completed correctly | B1 | |
| Min values correct for stage 1; suboptimal maximin values correct for stages 2 and 1 | M1, A1 | Follow through their network if possible, no more than 2 arcs missing/extra |
| Min values correct for stage 0; maximin value for stage 0 | M1, A1 | Follow through their network |
| Weight of heaviest truck $= 8$ tonnes | B1 | 8, cao |
| Maximin route $= (0;0)-(1;0)-(2;2)-(3;0)$ | B1 | Correct route, or in reverse |
---4 The diagram represents a map of an army truck-driving course that includes several bridges. The start and a 'safe point' just after each bridge have been given (stage; state) labels. The number below each bridge shows its weight limit, in tonnes.\\
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-4_698_1413_438_365}
An army cadet needs to drive a truck through the course from start to finish, crossing exactly three bridges.\\
(i) Draw a network, using the (stage; state) labels given, to represent the routes through the course. The weights on the arcs should show the weight limits for the bridges.
The cadet wants to find out the weight of the heaviest truck she can use.\\
(ii) Which network problem does she need to solve?\\
(iii) Set up a dynamic programming tabulation to solve the cadet's problem. Write down the weight of the heaviest truck she can use and write down the (stage; state) labels for the route she should take.
\hfill \mbox{\textit{OCR D2 2010 Q4 [13]}}