| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | December |
| Marks | 13 |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Moderate -0.5 This is a routine trace table completion exercise for Floyd's algorithm. While it requires careful attention to detail and understanding of the algorithm's flow, it's a standard procedural task with no novel problem-solving required. The pattern recognition and systematic following of the flowchart makes it easier than average, though the length and potential for arithmetic errors prevent it from being trivial. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt |
| 0 | 3 | 5 | 2 |
| 3 | 0 | 4 | 3 |
| 5 | 4 | 0 | 1 |
| 2 | 3 | 1 | 0 |
| \(n\) | \(i\) | \(j\) | \(\mathrm { d } ( i , j )\) | A | \(t\) | \(m\) |
| 4 | ||||||
| 1 | ||||||
| 1 | ||||||
| 1 | 100 | |||||
| 1 | ||||||
| 0 | ||||||
| 2 | ||||||
| 3 | ||||||
| 2 | 3 | |||||
| 3 | ||||||
| 5 | ||||||
| 4 | ||||||
| 2 | ||||||
| 4 | 2 | |||||
| 4 | ||||||
| 1, 4 | 100 | |||||
| 1 | ||||||
| 2 | ||||||
| 2 | ||||||
| 3 | ||||||
| 2 | 3 | |||||
| 3 | ||||||
| 1 | ||||||
| 3 | 1 | |||||
| 4 | ||||||
| 0 |
| Answer | Marks |
|---|---|
| 1 | 100 |
| Answer | Marks |
|---|---|
| 2 | 3 |
| Answer | Marks |
|---|---|
| 4 | 2 |
| Answer | Marks |
|---|---|
| 1, 4 | 100 |
| Answer | Marks |
|---|---|
| 2 | 3 |
| Answer | Marks |
|---|---|
| 3 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| From | to | Travel time |
| A | B | 5 |
| B | C | 3 |
| C | D | 9 |
| From | to | Travel time |
| B | F | 2 |
| F | E | 3 |
| E | D | 2 |
| From | to | Travel time |
| E | G | 5 |
| G | H | 6 |
| H | A | 4 |
| Suitable for vegans | Suitable for vegetarians | Suitable for meat eaters |
| Type X | 3 | |
| Type Y | 3 | 3 |
| Type Z | 3 | 3 |
| P | x | y |
Question 4:
4
1
1
1 | 100
1
0
2
3
2 | 3
3
5
4
2
4 | 2
4
1, 4 | 100
1
2
2
3
2 | 3
3
1
3 | 1
4
0
6
The next box to be used is the box ‘Let i = t’.
(a) Complete the trace in the Printed Answer Booklet. [4]
The table of inputs represents a weighted matrix for a network, where the weights represent
distances.
(b) (i) State how the output of the algorithm relates to the network represented by the matrix.
[1]
(ii) How can the list A be used in the solution of the travelling salesperson problem on the
network represented by the matrix? [1]
(iii) Write down a limitation on the distances d(i, j ) for this algorithm. [1]
(c) Explain why the algorithm is finite for any table of inputs. [2]
Suppose that, for a problem with n vertices, the run-time for the algorithm is given by aD+bT ,
where a and b are constants, D is the number of times that a value of d(i, j ) is looked up and T is
the number of times that t is updated.
(d) Show how this means that the algorithm has O(n2) complexity. [1]
A computer takes 3 seconds to run the algorithm for a problem with n = 35.
(e) Use the complexity to calculate an approximate run-time for a problem with n = 100. [2]
The run-time using a second algorithm has O(n!) complexity.
A computer takes 2.8 seconds to run the second algorithm for a problem with n = 35.
(f) Without performing any further calculations, give a reason why the first algorithm is likely to
be more efficient than the second for a problem with n = 100. [1]
© OCR 2018 Practice paper Y544/01
From | to | Travel time
A | B | 5
B | C | 3
C | D | 9
From | to | Travel time
B | F | 2
F | E | 3
E | D | 2
From | to | Travel time
E | G | 5
G | H | 6
H | A | 4
Suitable for vegans | Suitable for vegetarians | Suitable for meat eaters
Type X | 3
Type Y | 3 | 3
Type Z | 3 | 3 | 3
P | x | y | z | s | t | u | v | RHS4 An algorithm is represented by the flow diagram below.\\
\includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173}
The algorithm is applied with $n = 4$ and the table of inputs $\mathrm { d } ( i , j )$ :
$$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$
$$\begin{aligned}
& i = 1 \\
& i = 2 \\
& i = 3 \\
& i = 4
\end{aligned}$$
\begin{center}
\begin{tabular}{ | l | l | l | l | }
\hline
0 & 3 & 5 & 2 \\
\hline
3 & 0 & 4 & 3 \\
\hline
5 & 4 & 0 & 1 \\
\hline
2 & 3 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
An incomplete trace through the algorithm is shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$n$ & $i$ & $j$ & $\mathrm { d } ( i , j )$ & A & $t$ & $m$ \\
\hline
4 & & & & & & \\
\hline
& & & & & 1 & \\
\hline
& 1 & & & & & \\
\hline
& & & & 1 & & 100 \\
\hline
& & 1 & & & & \\
\hline
& & & 0 & & & \\
\hline
& & 2 & & & & \\
\hline
& & & 3 & & & \\
\hline
& & & & & 2 & 3 \\
\hline
& & 3 & & & & \\
\hline
& & & 5 & & & \\
\hline
& & 4 & & & & \\
\hline
& & & 2 & & & \\
\hline
& & & & & 4 & 2 \\
\hline
& 4 & & & & & \\
\hline
& & & & 1, 4 & & 100 \\
\hline
& & 1 & & & & \\
\hline
& & & 2 & & & \\
\hline
& & 2 & & & & \\
\hline
& & & 3 & & & \\
\hline
& & & & & 2 & 3 \\
\hline
& & 3 & & & & \\
\hline
& & & 1 & & & \\
\hline
& & & & & 3 & 1 \\
\hline
& & 4 & & & & \\
\hline
& & & 0 & & & \\
\hline
\end{tabular}
\end{center}
The next box to be used is the box 'Let $i = t$ '.
\begin{enumerate}[label=(\alph*)]
\item Complete the trace in the Printed Answer Booklet.
The table of inputs represents a weighted matrix for a network, where the weights represent distances.
\item \begin{enumerate}[label=(\roman*)]
\item State how the output of the algorithm relates to the network represented by the matrix.
\item How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
\item Write down a limitation on the distances $\mathrm { d } ( i , j )$ for this algorithm.
\end{enumerate}\item Explain why the algorithm is finite for any table of inputs.
Suppose that, for a problem with $n$ vertices, the run-time for the algorithm is given by $\alpha D + \beta T$, where $\alpha$ and $\beta$ are constants, $D$ is the number of times that a value of $\mathrm { d } ( i , j )$ is looked up and $T$ is the number of times that $t$ is updated.
\item Show how this means that the algorithm has $\mathrm { O } \left( n ^ { 2 } \right)$ complexity.
A computer takes 3 seconds to run the algorithm for a problem with $n = 35$.
\item Use the complexity to calculate an approximate run-time for a problem with $n = 100$.
The run-time using a second algorithm has $\mathrm { O } ( n ! )$ complexity.\\
A computer takes 2.8 seconds to run the second algorithm for a problem with $n = 35$.
\item Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with $n = 100$.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q4 [13]}}