Edexcel FD1 AS 2018 June — Question 1 9 marks

Exam BoardEdexcel
ModuleFD1 AS (Further Decision 1 AS)
Year2018
SessionJune
Marks9
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeAlgorithmic complexity calculations
DifficultyModerate -0.5 Part (a) is a standard Dijkstra's algorithm application on a small network (routine AS Further Maths). Part (b) involves straightforward proportional reasoning with O(n²) complexity (ratio of squares calculation). Part (c) requires brief explanation of big-O notation limitations. All parts are textbook exercises with no novel problem-solving required, making this easier than average A-level questions overall, though the algorithmic content is appropriate for Further Maths.
Spec7.03f Worst case complexity: T(n) as function of problem size7.03g Order notation: O(n^k) for k = 0,1,2,3,47.04a Shortest path: Dijkstra's algorithm
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{3e853c6d-e90e-4a09-b990-1c2c146b54e1-2_1105_1459_463_402} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents a network of roads.
The number on each arc represents the time taken, in minutes, to drive along the corresponding road.
    1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to H .
    2. State the quickest route. For a network with \(n\) vertices, Dijkstra's algorithm has order \(n ^ { 2 }\)
  2. If it takes 1.5 seconds to run the algorithm when \(n = 250\), calculate approximately how long it will take, in seconds, to run the algorithm when \(n = 9500\). You should make your method and working clear.
  3. Explain why your answer to part (b) is only an approximation.
Question 1:
Part (a)(i):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Dijkstra's algorithm applied correctly — larger number replaced by smaller number in working value boxes at D, G or HM1 For a larger number replaced by a smaller number in the working value boxes at either D, G or H
All values correct (and in correct order) at A, B, C, I and EA1
All values correct (and in correct order) at F and DA1
All values correct (and in correct order) on the follow through at J, G and HA1ft
Shortest time to travel from A to H is 39 minutesA1ft Follow through their final value at H (condone lack of units)
Part (a)(ii):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Quickest route is AIFGHA1 cao
Part (b):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
\(1.5 \times \left(\dfrac{9500}{250}\right)^2\)M1 Complete method — allow \(\frac{250}{9500}\) (but must be squared) — allow slips in values e.g. 950 for 9500
\(= 2166\) secondsA1 cao (accept 2170 but only with correct working) — accept 2166 with no working for M1 only
Part (c):
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Order of \(n^2\) does not mean that the order is proportional to \(n^2\) (which is the assumption behind the answer in (b)) but merely means that the dominant term is of order \(n^2\)B1 Any indication that run-time is not exactly proportional to \(n^2\), e.g. may suggest other terms \((n^2 + \ldots)\), or that \(n^2\) is the dominant term, or that order does not imply proportionality. Do not accept only that "\(n^2\) is not exact". 
## Question 1:

### Part (a)(i):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly — larger number replaced by smaller number in working value boxes at D, G or H | M1 | For a larger number replaced by a smaller number in the working value boxes at either D, G or H |
| All values correct (and in correct order) at A, B, C, I and E | A1 | |
| All values correct (and in correct order) at F and D | A1 | |
| All values correct (and in correct order) on the follow through at J, G and H | A1ft | |
| Shortest time to travel from A to H is **39 minutes** | A1ft | Follow through their final value at H (condone lack of units) |

### Part (a)(ii):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Quickest route is **AIFGH** | A1 | cao |

### Part (b):

| Answer/Working | Marks | Guidance |
|---|---|---|
| $1.5 \times \left(\dfrac{9500}{250}\right)^2$ | M1 | Complete method — allow $\frac{250}{9500}$ (but must be squared) — allow slips in values e.g. 950 for 9500 |
| $= 2166$ seconds | A1 | cao (accept 2170 but only with correct working) — accept 2166 with no working for M1 only |

### Part (c):

| Answer/Working | Marks | Guidance |
|---|---|---|
| Order of $n^2$ does not mean that the order is proportional to $n^2$ (which is the assumption behind the answer in (b)) but merely means that the dominant term is of order $n^2$ | B1 | Any indication that run-time is not **exactly** proportional to $n^2$, e.g. may suggest other terms $(n^2 + \ldots)$, or that $n^2$ is the dominant term, or that order does not imply proportionality. Do **not** accept only that "$n^2$ is not exact". |
1.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{3e853c6d-e90e-4a09-b990-1c2c146b54e1-2_1105_1459_463_402}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

Figure 1 represents a network of roads.\\
The number on each arc represents the time taken, in minutes, to drive along the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest time needed to travel from A to H .
\item State the quickest route.

For a network with $n$ vertices, Dijkstra's algorithm has order $n ^ { 2 }$
\end{enumerate}\item If it takes 1.5 seconds to run the algorithm when $n = 250$, calculate approximately how long it will take, in seconds, to run the algorithm when $n = 9500$. You should make your method and working clear.
\item Explain why your answer to part (b) is only an approximation.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 AS 2018 Q1 [9]}}
This paper (4 questions)
View full paper
Q1 9 Q2 10 Q3 10 Q4 11