OCR D2 2009 June — Question 2 20 marks

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2009
SessionJune
Marks20
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeDynamic programming shortest/longest path
DifficultyStandard +0.3 This is a standard D2 dynamic programming question requiring tabulation for longest path, followed by routine critical path analysis with forward/backward passes. Both are textbook algorithms with no novel insight required, making it slightly easier than average since it's purely procedural application of learned methods.
Spec7.01a Types of problem: existence, construction, enumeration, optimisation7.03b Algorithm awareness: uses and practical limitations7.03c Working with algorithms: trace, interpret, adapt7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities7.05c Total float: calculation and interpretation7.05d Latest start and earliest finish: independent and interfering float
2
  1. Set up a dynamic programming tabulation to find the maximum weight route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
  2. The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.
    ActivityDurationImmediate predecessors
    \(A\)8-
    \(B\)9-
    C7-
    D5\(A\)
    E6\(A\)
    \(F\)4\(B\)
    \(G\)5B
    \(H\)6\(B\)
    \(I\)10C
    \(J\)9\(C\)
    \(K\)6\(C\)
    \(L\)7D, F, I
    \(M\)6\(E , G , J\)
    \(N\)8\(H\), \(K\)
    Make a large copy of the network with the activities \(A\) to \(N\) labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
  3. Compare the solutions to parts (i) and (ii).
Question 2(i): Dynamic Programming
AnswerMarks Guidance
Answer/WorkingMark Guidance
Table structure correctB1 Structure of table correct
Stage and state values correctM1
Action values correctA1 [3]
Working backwards from stage 2: 7, 6, 8 correct in suboptimal maxima column for stage 2B1
Working column substantially correct for stage 1M1
Sums correct for stage 1A1 [3]
Suboptimal maxima values correct for stage 1B1
Working column substantially correct for stage 0M1
Sums correct for stage 0A1 [3]
Maximum route \(= (0;0)-(1;2)-(2;0)-(3;0)\)B1 Correct route from \((0;0)\) to \((3;0)\)
Weight \(= 24\)B1 24 cao
Question 2(ii): Activity Network (Critical Path)
AnswerMarks Guidance
Answer/WorkingMark Guidance
Assigning \(A\) to \(N\) appropriatelyB1
Substantially correct forward passM1
Forward pass correctA1
Substantially correct backward passM1
Backward pass correctA1
Minimum completion time \(= 24\)B1 24 (cao)
Critical activities: \(C, I, L\)B1 \(C, I, L\) (cao)
Question 2(iii): Relationship Between Methods
AnswerMarks Guidance
Answer/WorkingMark Guidance
The critical path is the maximum pathM1 Same path is found in both
The critical activities form a continuous path with no slack, i.e. the longest pathA1 Recognition of why the solutions are the same, in general 
# Question 2(i): Dynamic Programming

| Answer/Working | Mark | Guidance |
|---|---|---|
| Table structure correct | B1 | Structure of table correct |
| Stage and state values correct | M1 | |
| Action values correct | A1 | [3] |
| Working backwards from stage 2: 7, 6, 8 correct in suboptimal maxima column for stage 2 | B1 | |
| Working column substantially correct for stage 1 | M1 | |
| Sums correct for stage 1 | A1 | [3] |
| Suboptimal maxima values correct for stage 1 | B1 | |
| Working column substantially correct for stage 0 | M1 | |
| Sums correct for stage 0 | A1 | [3] |
| Maximum route $= (0;0)-(1;2)-(2;0)-(3;0)$ | B1 | Correct route from $(0;0)$ to $(3;0)$ |
| Weight $= 24$ | B1 | 24 cao |

---

# Question 2(ii): Activity Network (Critical Path)

| Answer/Working | Mark | Guidance |
|---|---|---|
| Assigning $A$ to $N$ appropriately | B1 | |
| Substantially correct forward pass | M1 | |
| Forward pass correct | A1 | |
| Substantially correct backward pass | M1 | |
| Backward pass correct | A1 | |
| Minimum completion time $= 24$ | B1 | 24 (cao) |
| Critical activities: $C, I, L$ | B1 | $C, I, L$ (cao) |

---

# Question 2(iii): Relationship Between Methods

| Answer/Working | Mark | Guidance |
|---|---|---|
| The critical path is the maximum path | M1 | Same path is found in both |
| The critical activities form a continuous path with no slack, i.e. the longest path | A1 | Recognition of why the solutions are the same, in general |

---
2 (i) Set up a dynamic programming tabulation to find the maximum weight route from ( $0 ; 0$ ) to ( $3 ; 0$ ) on the following directed network.\\
\includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587}

Give the route and its total weight.\\
(ii) The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.

\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Activity & Duration & Immediate predecessors \\
\hline
$A$ & 8 & - \\
\hline
$B$ & 9 & - \\
\hline
C & 7 & - \\
\hline
D & 5 & $A$ \\
\hline
E & 6 & $A$ \\
\hline
$F$ & 4 & $B$ \\
\hline
$G$ & 5 & B \\
\hline
$H$ & 6 & $B$ \\
\hline
$I$ & 10 & C \\
\hline
$J$ & 9 & $C$ \\
\hline
$K$ & 6 & $C$ \\
\hline
$L$ & 7 & D, F, I \\
\hline
$M$ & 6 & $E , G , J$ \\
\hline
$N$ & 8 & $H$, $K$ \\
\hline
\end{tabular}
\end{center}

Make a large copy of the network with the activities $A$ to $N$ labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.\\
(iii) Compare the solutions to parts (i) and (ii).

\hfill \mbox{\textit{OCR D2 2009 Q2 [20]}}
This paper (4 questions)
View full paper
Q1 13 Q2 20 Q3 19 Q4 20