Moderate -0.8 This is a routine D1 question testing standard algorithms (bubble sort, quicksort, bin packing lower bound, Prim's and Kruskal's MST algorithms) with straightforward application. All parts require mechanical execution of learned procedures with no novel problem-solving or insight, making it easier than average A-level maths questions.
Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order.
The original list is now to be sorted into descending order.
Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear.
The numbers are to be packed into bins of size 26
Calculate a lower bound for the minimum number of bins required. You must show your working.
2.
\begin{figure}[h]
\end{figure}
Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
State the minimum cost of connecting the alarm systems in the nine buildings.
It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case.
Since arcs BC and EF already exist, there is no cost for these connections.
State the new minimum cost of connecting the nine buildings.
3.
\begin{figure}[h]
\end{figure}
Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6.
Figure 3 shows an initial matching.
Define the term 'matching'.
(2)
Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
(3)
After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
(3)
4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390}
\captionsetup{labelformat=empty}
\caption{Figure 4 [0pt]
[The total weight of the network is 367 metres]}
\end{figure}
Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe.
A robot will travel along each pipe to check that the pipe is in good repair.
The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
Write down the length of a shortest inspection route.
A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
\(AE + IJ = 56 + 38 = 94\); \(AI + EJ = 54 + 39 = 93^*\); \(AJ + EI = 47 + 48 = 95\); Repeat arcs AB, BD, DH, HI, EG and GJ.
M1; 1A1; 2A1; 3A1; 4A1 (5)
a1M1: Three distinct pairings of their four odd nodes. a1A1: One row correct including pairing and total. a2A1: Two rows correct including pairing and total. a3A1: Three rows correct including pairing and total. a4A1: CAO correct arcs identified AB, BD, DH, HI, EG, GJ (accept ABDHI and EGJ).
Part (b)
Answer
Marks
Guidance
Length: \(367 + 93 = 460\) metres
B1ft (1)
Must have a choice of at least two pairs seen in part (a). \(379 +\) their least from (a).
Part (c)
Answer
Marks
Guidance
Only AE needs to be repeated so new length is \(367 + 35 + 56 = 458\) metres; So the distance travelled by the robot is decreased
M1; A1ft (2)
c1M1: Aim to include their AE (56) [ft from (a)] and add IJ (35) or \(35 + \text{'56'}\) or \(367 + 35 + \text{'56'}\). Must see a numerical argument. c1A1ft: Correct calculation and conclusion from their working.
# Question 4:
## Part (a)
$AE + IJ = 56 + 38 = 94$; $AI + EJ = 54 + 39 = 93^*$; $AJ + EI = 47 + 48 = 95$; Repeat arcs AB, BD, DH, HI, EG and GJ. | M1; 1A1; 2A1; 3A1; 4A1 **(5)** | a1M1: Three distinct pairings of **their** four odd nodes. a1A1: One row correct including pairing **and** total. a2A1: Two rows correct including pairing **and** total. a3A1: Three rows correct including pairing **and** total. a4A1: CAO correct **arcs** identified AB, BD, DH, HI, EG, GJ (accept ABDHI and EGJ).
## Part (b)
Length: $367 + 93 = 460$ metres | B1ft **(1)** | Must have a choice of at least two pairs seen in part (a). $379 +$ their least from (a).
## Part (c)
Only AE needs to be repeated so new length is $367 + 35 + 56 = 458$ metres; So the distance travelled by the robot is decreased | M1; A1ft **(2)** | c1M1: Aim to include their AE (56) [ft from (a)] and add IJ (35) **or** $35 + \text{'56'}$ **or** $367 + 35 + \text{'56'}$. Must see a numerical argument. c1A1ft: Correct calculation and conclusion from their working.
---
4\\
15\\
7
\begin{enumerate}[label=(\alph*)]
\item Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order.
The original list is now to be sorted into descending order.
\item Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear.
The numbers are to be packed into bins of size 26
\item Calculate a lower bound for the minimum number of bins required. You must show your working.\\
2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.\\
(a) Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.\\
(b) State the minimum cost of connecting the alarm systems in the nine buildings.
It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.\\
(c) (i) Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.\\
(ii) Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case.
Since arcs BC and EF already exist, there is no cost for these connections.
\item State the new minimum cost of connecting the nine buildings.\\
3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6.
Figure 3 shows an initial matching.\\
(a) Define the term 'matching'.\\
(2)\\
(b) Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.\\
(3)
After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.\\
(c) Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.\\
(3)\\
4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390}
\captionsetup{labelformat=empty}
\caption{Figure 4\\[0pt]
[The total weight of the network is 367 metres]}
\end{center}
\end{figure}
Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe.
A robot will travel along each pipe to check that the pipe is in good repair.\\
The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.\\
(a) Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.\\
(b) Write down the length of a shortest inspection route.
A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .\\
(c) Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2014 Q4 [8]}}