| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.5 This is a standard textbook dynamic programming question with clearly labeled stages and states. Part (i) is routine backward recursion with straightforward arithmetic. Part (ii) requires recognizing the minimax problem and simple inspection of the network, but no novel insight. Slightly easier than average due to explicit stage/state labeling and small network size. |
| Spec | 7.01a Types of problem: existence, construction, enumeration, optimisation7.03b Algorithm awareness: uses and practical limitations7.03c Working with algorithms: trace, interpret, adapt |
| Stage 5 | (5;0) to (4;0): 6 plants (5;0) to (4;1): 8 plants | |||
| Stage 4 | (4;0) to (3;0): 5 plants (4;0) to (3;1): 8 plants | (4;1) to (3;0): 7 plants (4;1) to (3;2): 5 plants | ||
| Stage 3 | ( \(3 ; 0\) ) to ( \(2 ; 1\) ): 8 plants (3;0) to (2;3): 6 plants | (3;1) to (2;0): 7 plants \(( 3 ; 1 )\) to (2;2): 6 plants | (3;2) to (2;0): 7 plants (3;2) to (2;2): 6 plants ( \(3 ; 2\) ) to ( \(2 ; 3\) ): 8 plants | |
| Stage 2 | (2; 0) to (1; 0): 4 plants ( \(2 ; 0\) ) to ( \(1 ; 1\) ): 5 plants | (2; 1) to (1; 0): 6 plants | (2;2) to (1;1): 7 plants | (2;3) to (1;0): 5 plants (2;3) to (1;1): 6 plants |
| Stage 1 | (1;0) to (0;0): 4 plants | (1; 1) to (0;0): 4 plants |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Table structure correct | M1 | For structure of table correct |
| Stage and state columns correct | A1 | |
| Action values correct | A1 | |
| All calculations correct for stages 1 and 2 (may be seen as addition or result; may be shown in final column); suboptimal maxima identified correctly (may be implied from next stage) | M1 | |
| A1 | ||
| Correct calculations for stage 3 (follow through from stage 2 if possible); suboptimal maxima correct | M1 | |
| A1 | ||
| Correct calculations for stages 4 and 5 (follow through from stage 3) | M1 | |
| A1 | ||
| Calculations correct for entire table | B1 | |
| Route: \((0;0)-(1;0)-(2;1)-(3;0)-(4;1)-(5;0)\) | B1 | cao or in reverse |
| Giles will be able to see 33 plants | B1 | For 33 (cao) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimax | B1 | For 'minimax' |
| Route: \((0;0)-(1;0)-(2;3)-(3;0)-(4;0)-(5;0)\) or \((0;0)-(1;1)-(2;3)-(3;0)-(4;0)-(5;0)\) | M1 | For a path with at most one path \(> 6\) plants |
| A1 | ||
| B1 | For either correct path | |
| At stage 5 all paths have at least 6 plants | Or stage 3 or any equivalent argument in words |
# Question 4:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Table structure correct | M1 | For structure of table correct |
| Stage and state columns correct | A1 | |
| Action values correct | A1 | |
| All calculations correct for stages 1 and 2 (may be seen as addition or result; may be shown in final column); suboptimal maxima identified correctly (may be implied from next stage) | M1 | |
| | A1 | |
| Correct calculations for stage 3 (follow through from stage 2 if possible); suboptimal maxima correct | M1 | |
| | A1 | |
| Correct calculations for stages 4 and 5 (follow through from stage 3) | M1 | |
| | A1 | |
| Calculations correct for entire table | B1 | |
| Route: $(0;0)-(1;0)-(2;1)-(3;0)-(4;1)-(5;0)$ | B1 | cao or in reverse |
| Giles will be able to see 33 plants | B1 | For 33 (cao) |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimax | B1 | For 'minimax' |
| Route: $(0;0)-(1;0)-(2;3)-(3;0)-(4;0)-(5;0)$ or $(0;0)-(1;1)-(2;3)-(3;0)-(4;0)-(5;0)$ | M1 | For a path with at most one path $> 6$ plants |
| | A1 | |
| | B1 | For either correct path |
| At stage 5 all paths have at least 6 plants | | Or stage 3 or any equivalent argument in words |
---4 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit.
Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( $5 ; 0$ ) and the exit as ( $0 ; 0$ ). He then counted the numbers of plants along paths. These numbers are shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage 5 & (5;0) to (4;0): 6 plants (5;0) to (4;1): 8 plants & & & \\
\hline
Stage 4 & (4;0) to (3;0): 5 plants (4;0) to (3;1): 8 plants & (4;1) to (3;0): 7 plants (4;1) to (3;2): 5 plants & & \\
\hline
Stage 3 & ( $3 ; 0$ ) to ( $2 ; 1$ ): 8 plants (3;0) to (2;3): 6 plants & (3;1) to (2;0): 7 plants $( 3 ; 1 )$ to (2;2): 6 plants & (3;2) to (2;0): 7 plants (3;2) to (2;2): 6 plants ( $3 ; 2$ ) to ( $2 ; 3$ ): 8 plants & \\
\hline
Stage 2 & (2; 0) to (1; 0): 4 plants ( $2 ; 0$ ) to ( $1 ; 1$ ): 5 plants & (2; 1) to (1; 0): 6 plants & (2;2) to (1;1): 7 plants & (2;3) to (1;0): 5 plants (2;3) to (1;1): 6 plants \\
\hline
Stage 1 & (1;0) to (0;0): 4 plants & (1; 1) to (0;0): 4 plants & & \\
\hline
\end{tabular}
\end{center}
(i) Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route?
Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.\\
(ii) Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 .
You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.
\hfill \mbox{\textit{OCR D2 2005 Q4 [15]}}