Edexcel FD2 2024 June — Question 6 10 marks

Exam BoardEdexcel
ModuleFD2 (Further Decision 2)
Year2024
SessionJune
Marks10
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeDynamic programming shortest/longest path
DifficultyStandard +0.3 This is a standard dynamic programming problem on a staged network with clear structure. Students follow a mechanical backward pass algorithm filling in a table, then trace the optimal route. While it requires careful arithmetic and systematic working, it's a routine application of a well-practiced technique with no novel problem-solving or insight required.
Spec7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{931ccf1d-4b02-448c-b492-846b0f42c057-07_709_1507_214_280} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns. Elena plans to drive from S to T . She must arrive at T by 9 pm .
  1. By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm .
  2. Hence write down the route that Elena should take.
Question 6:
Part (a):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Stage 1: States H,I,J; actions HT, IT, JT; values \(2^*, 3^*, 4^*\)B1 3.1a
Stage 2: F: FH→H \(5+2=7^*\), FI→I \(4+3=7^*\), FJ→J \(6+4=10\); G: GH→H \(5+2=7\), GI→I \(3+3=6^*\)M1 A1 Correct method for stage 2
Stage 3: C: CF→F \(3+7=10^*\), CG→G \(4+6=10^*\); D: DF→F \(3+7=10\), DG→G \(1+6=7^*\); E: EG→G \(2+6=8^*\)M1 A1 Correct method and values for stage 3
Stage 4: A: AC→C \(4+10=14\), AE→E \(5+8=13^*\); B: BC→C \(4+10=14\), BD→D \(7+7=14\), BE→E \(4+8=12^*\)M1 A1ft ft on stage 3 values
Stage 5: S: SA→A \(3+13=16\), SB→B \(2+12=14^*\)A1 —
Latest time that Elena can start her journey is 7 amA1 3.2a
Part (b):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Route: SBEGITB1 2.2a
Question 6:
AnswerMarks Guidance
Answer/WorkingMark Guidance
CAO for first stageB1 Correct first stage values
Second stage completed, at least 4 rows, something in each cellM1 Must bring earlier optimal results into calculations
CAO for second stage exactly 5 rowsA1
Third stage completed, at least 4 rows, something in each cellM1 Must bring earlier optimal results into calculations
CAO for third stage exactly 5 rowsA1
Fourth stage completed, 5 rows, something in each cellM1 Must bring earlier optimal results into calculations
Correct ft from optimal values of third stageA1ft
CAO for fifth stageA1
Correct latest start time in context (e.g. 7 am, 07:00)A1
(b) Correct route (dependent on all previous M marks)B1
Special Case (Maximin/Minimax): B1 M1 A0 M1 A0 M1 A0 A0 A0 B0 — Max 4/10
# Question 6:

## Part (a):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Stage 1: States H,I,J; actions HT, IT, JT; values $2^*, 3^*, 4^*$ | B1 | 3.1a |
| Stage 2: F: FH→H $5+2=7^*$, FI→I $4+3=7^*$, FJ→J $6+4=10$; G: GH→H $5+2=7$, GI→I $3+3=6^*$ | M1 A1 | Correct method for stage 2 |
| Stage 3: C: CF→F $3+7=10^*$, CG→G $4+6=10^*$; D: DF→F $3+7=10$, DG→G $1+6=7^*$; E: EG→G $2+6=8^*$ | M1 A1 | Correct method and values for stage 3 |
| Stage 4: A: AC→C $4+10=14$, AE→E $5+8=13^*$; B: BC→C $4+10=14$, BD→D $7+7=14$, BE→E $4+8=12^*$ | M1 A1ft | ft on stage 3 values |
| Stage 5: S: SA→A $3+13=16$, SB→B $2+12=14^*$ | A1 | — |
| Latest time that Elena can start her journey is 7 am | A1 | 3.2a |

## Part (b):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Route: SBEGIT | B1 | 2.2a |

## Question 6:

| Answer/Working | Mark | Guidance |
|---|---|---|
| CAO for first stage | B1 | Correct first stage values |
| Second stage completed, at least 4 rows, something in each cell | M1 | Must bring earlier optimal results into calculations |
| CAO for second stage exactly 5 rows | A1 | |
| Third stage completed, at least 4 rows, something in each cell | M1 | Must bring earlier optimal results into calculations |
| CAO for third stage exactly 5 rows | A1 | |
| Fourth stage completed, 5 rows, something in each cell | M1 | Must bring earlier optimal results into calculations |
| Correct ft from optimal values of third stage | A1ft | |
| CAO for fifth stage | A1 | |
| Correct latest start time in context (e.g. 7 am, 07:00) | A1 | |
| **(b)** Correct route (dependent on all previous M marks) | B1 | |

**Special Case (Maximin/Minimax):** B1 M1 A0 M1 A0 M1 A0 A0 A0 B0 — Max 4/10

---
6.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{931ccf1d-4b02-448c-b492-846b0f42c057-07_709_1507_214_280}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns.

Elena plans to drive from S to T . She must arrive at T by 9 pm .
\begin{enumerate}[label=(\alph*)]
\item By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm .
\item Hence write down the route that Elena should take.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD2 2024 Q6 [10]}}
This paper (8 questions)
View full paper
Q1 10 Q2 3 Q3 12 Q4 9 Q5 10 Q6 10 Q7 13 Q8 8