| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2024 |
| Session | June |
| Marks | 1 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Identify Best Lower Bound |
| Difficulty | Easy -2.0 This is a trivial conceptual question testing only the definitions of 'best' lower and upper bounds (largest lower bound, smallest upper bound). It requires no calculation, algorithm application, or problem-solving—just direct recall that 19 > 15 and 48 < 51. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Best Lower Bound | Best Upper Bound | |
| 15 | 48 | \(\square\) |
| 15 | 51 | \(\square\) |
| 19 | 48 | \(\square\) |
| 19 | 51 | \(\square\) |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | Ticks 3rd box | 1.1b |
| Question total | 1 | |
| Q | Marking instructions | AO |
Question 2:
2 | Ticks 3rd box | 1.1b | B1 | 19, 48
Question total | 1
Q | Marking instructions | AO | Marks | Typical solutionA student is trying to find the solution to the travelling salesperson problem for a network.
They correctly find two lower bounds for the solution: 15 and 19
They also correctly find two upper bounds for the solution: 48 and 51
Based on the above information only, which of the following pairs give the best lower bound and best upper bound for the solution of this problem?
Tick $(\checkmark)$ one box.
[1 mark]
\begin{tabular}{|c|c|c|}
\hline Best Lower Bound & Best Upper Bound & \\
\hline 15 & 48 & $\square$ \\
\hline 15 & 51 & $\square$ \\
\hline 19 & 48 & $\square$ \\
\hline 19 & 51 & $\square$ \\
\end{tabular}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2024 Q2 [1]}}