OCR MEI D1 2013 June — Question 7

Exam BoardOCR MEI
ModuleD1 (Decision Mathematics 1)
Year2013
SessionJune
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeBasic Dijkstra's algorithm application
DifficultyModerate -0.8 This is a straightforward application of Dijkstra's algorithm on a small network with clear arc weights, followed by a conceptual question about adapting the network for time rather than distance. The algorithm application is mechanical and routine for D1 students, requiring no novel insight. The adaptation question (part ii) is a standard extension testing understanding of the relationship between distance, speed, and time.
Spec7.04a Shortest path: Dijkstra's algorithm
7 Let the new value of \(i\) be \(i + 1\).
  1. Apply the sorting algorithm to the list of numbers shown below. Record in the table provided the state of the list after each pass. Record the number of comparisons and the number of swaps that you make in each pass. (The result of the first pass has already been recorded.) List: \(\begin{array} { l l l l l l } 9 & 11 & 7 & 3 & 13 & 5 \end{array}\)
  2. Suppose now that the list is split into two sublists, \(\{ 9,11,7 \}\) and \(\{ 3,13,5 \}\). The sorting algorithm is adapted to apply to three numbers, and is applied to each sublist separately. This gives \(\{ 7,9,11 \}\) and \(\{ 3,5,13 \}\). How many comparisons and swaps does this need?
  3. How many further swaps would the original algorithm need to sort the revised list \(\{ 7,9,11,3,5,13 \}\) into increasing order? 3 The network below represents a number of villages together with connecting roads. The numbers on the arcs represent distances (in miles). \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-3_684_785_1612_625}
  4. Use Dijkstra's algorithm to find the shortest routes from A to each of the other villages. Give these shortest routes and the corresponding distances. Traffic in the area travels at 30 mph . An accident delays all traffic passing through C by 20 minutes.
  5. Describe how the network can be adapted and used to find the fastest journey time from A to F .
7 Let the new value of $i$ be $i + 1$.\\
(i) Apply the sorting algorithm to the list of numbers shown below. Record in the table provided the state of the list after each pass. Record the number of comparisons and the number of swaps that you make in each pass. (The result of the first pass has already been recorded.)

List: $\begin{array} { l l l l l l } 9 & 11 & 7 & 3 & 13 & 5 \end{array}$\\
(ii) Suppose now that the list is split into two sublists, $\{ 9,11,7 \}$ and $\{ 3,13,5 \}$. The sorting algorithm is adapted to apply to three numbers, and is applied to each sublist separately. This gives $\{ 7,9,11 \}$ and $\{ 3,5,13 \}$.

How many comparisons and swaps does this need?\\
(iii) How many further swaps would the original algorithm need to sort the revised list $\{ 7,9,11,3,5,13 \}$ into increasing order?

3 The network below represents a number of villages together with connecting roads. The numbers on the arcs represent distances (in miles).\\
\includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-3_684_785_1612_625}\\
(i) Use Dijkstra's algorithm to find the shortest routes from A to each of the other villages.

Give these shortest routes and the corresponding distances.

Traffic in the area travels at 30 mph . An accident delays all traffic passing through C by 20 minutes.\\
(ii) Describe how the network can be adapted and used to find the fastest journey time from A to F .

\hfill \mbox{\textit{OCR MEI D1 2013 Q7}}
This paper (7 questions)
View full paper
Q1 8 Q2 8 Q3 8 Q4 16 Q5 16 Q6 16 Q7