7.03j Sorting: bubble sort and shuttle sort

4. \(45 , \quad 56 , \quad 37 , \quad 79 , \quad 46 , \quad 18 , \quad 90 , \quad 81 , \quad 51\)

1. Using the quick sort algorithm, perform one complete iteration towards sorting these numbers into ascending order.
   (2)
2. Using the bubble sort algorithm, perform one complete pass towards sorting the original list into descending order. Another list of numbers, in ascending order, is $$7 , \quad 23 , \quad 31 , \quad 37 , \quad 41 , \quad 44 , \quad 50 , \quad 62 , \quad 71 , \quad 73 , \quad 94$$
3. Use the binary search algorithm to locate the number 73 in this list. \section*{5.} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-06_1246_1168_294_427}
   \end{figure} Figure 2 shows a network of roads connecting villages. The length of each road, in km, is shown. Village \(B\) has only a small footbridge over the river which runs through the village. It can be accessed by two roads, from \(A\) and \(D\). The driver of a snowplough, based at \(F\), is planning a route to enable her to clear all the roads of snow. The route should be of minimum length. Each road can be cleared by driving along it once. The snowplough cannot cross the footbridge. Showing all your working and using an appropriate algorithm,

1. $$\begin{array} { l l l l l l l l l l l } 4 & 6.5 & 7 & 1.3 & 2 & 5 & 1.5 & 6 & 4.5 & 6 & 1 \end{array}$$ The list of eleven numbers shown above is to be sorted into descending order.

1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
2. Use the first-fit decreasing bin packing algorithm to pack the numbers into bins of size 10
3. Determine whether your answer to part (b) uses the minimum number of bins. You must justify your answer. A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is
   1.6
   1.7
   1.5
   3.8
   3.3
   4.5
   4.8
   5.6
   5.4
   6.7
   9.1
4. Explain how you know that at least one of the first two passes of the bubble sort was not carried out correctly.

5. The nine distinct numbers in the following list are to be packed into bins of size 50 $$\begin{array} { l l l l l l l l l } 23 & 17 & 19 & x & 24 & 8 & 18 & 10 & 21 \end{array}$$ When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23178
Bin 2: \(19 \quad x \quad 10\) Bin 3: 2418
Bin 4: 21

1. Explain why \(13 < x < 21\) The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is $$\begin{array} { l l l l l l l l l } 23 & 19 & 17 & 24 & x & 18 & 10 & 21 & 8 \end{array}$$
2. Using this information, write down the smallest interval that must contain \(x\), giving your answer as an inequality. When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 2423
   Bin 2: 211910
   Bin 3: \(1817 x\) Bin 4: 8
   Given that only one of the bins is full and that \(x\) is an integer,
3. calculate the value of \(x\). You must give reasons for your answer.

30312522318136101524

1. The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. The ten numbers are to be packed into bins of size \(n\), where \(n\) is a positive integer.
   When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained.

   Bin 1:	30	12	2
   Bin 2:	5	23	10
   Bin 3:	18	15
   Bin 4:	36
   Bin 5:	24

2. Explain why the value of the integer \(n\) must be either 44 or 45
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45
   

6. The following algorithm determines the number of comparisons made when Prim's algorithm is applied to \(\mathrm { K } _ { n }\) Step 1 Start
Step 2 Input the value of \(n\) Step 3 Let \(a = 1\) Step 4 Let \(b = n - 2\) Step 5 Let \(c = b\) Step 6 Let \(a = a + 1\) Step \(7 \quad\) Let \(b = b - 1\) Step 8 Let \(c = c + ( a \times b ) + ( a - 1 )\) Step 9 If \(b > 0\) go to Step 6
Step 10 Output \(C\) Step 11 Stop

1. For \(\mathrm { K } _ { 5 }\), complete the table in the answer book to show the results obtained at each step of the algorithm. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-11_595_703_175_680} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} The weights of the ten arcs in Figure 4 are $$\begin{array} { l l l l l l l l l l } 17 & 21 & 24 & 14 & 23 & 13 & 15 & 19 & 28 & 20 \end{array}$$
2. 1. Starting at the left-hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.
   2. Find the total number of comparisons performed during the sort.
3. Find the maximum total number of comparisons required to sort the weights of the 10 arcs of \(\mathrm { K } _ { 5 }\) into ascending order using bubble sort. It is given that the maximum total number of comparisons required to sort the weights of the arcs of \(\mathrm { K } _ { n }\) into ascending order using bubble sort is $$\lambda n ( n - 1 ) ( n + 1 ) ( n - 2 )$$ where \(\lambda\) is a constant.
4. Determine the maximum total number of comparisons required to sort the weights of the arcs of \(\mathrm { K } _ { 50 }\) into ascending order using bubble sort. You must make your method and working clear.

4. The eleven distinct numbers listed below are to be packed into bins of size 40 $$\begin{array} { l l l l l l l l l l l } 15 & 22 & 3 & 9 & 23 & x & 5 & 4 & 18 & 20 & 13 \end{array}$$ It is known that \(x\)

• is an integer less than 40
• is the largest number in the list
  1. Explain why it is not possible to pack the numbers into 3 bins of size 40

Given that it is possible to pack the numbers into 4 bins of size 40

determine the range of values for \(x\)

Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40

Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin.

Determine the value of \(x\). You must give reasons for your answer.

1. $$\begin{array} { l l l l l l l l l l l } 17 & 8 & 16 & 12 & 24 & 19 & 23 & 11 & 20 & 13 & 4 \end{array}$$ The eleven numbers listed above are to be packed into bins of size \(n\) where \(n\) is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: 17812
Bin 2: 1624
Bin 3: 19114
Bin 4: 2313
Bin 5: 20

1. Explain why this packing means that the value of \(n\) must be 40 The original list of eleven numbers is to be sorted into descending order.
2. Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40

A list of \(n\) numbers needs to be sorted into descending order starting at the left-hand end of the list.

1. Describe how to carry out the first pass of a bubble sort on the numbers in the list. Bubble sort is a quadratic order algorithm.
   A computer takes approximately 0.021 seconds to apply a bubble sort to a list of 2000 numbers.
2. Estimate the time it would take the computer to apply a bubble sort to a list of 50000 numbers. Make your method clear.
   

4 Answer this question on the insert provided. The list of numbers below is to be sorted into decreasing order using shuttle sort. $$\begin{array} { l l l l l l l l l } 21 & 76 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$

1. How many passes through shuttle sort will be required to sort the list? After the first pass the list is as follows. $$\begin{array} { l l l l l l l l l } 76 & 21 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
2. State the number of comparisons and the number of swaps that were made in the first pass.
3. Write down the list after the second pass. State the number of comparisons and the number of swaps that were used in making the second pass.
4. Complete the table in the insert to show the results of the remaining passes, recording the number of comparisons and the number of swaps made in each pass. You may not need all the rows of boxes printed. When the original list is sorted into decreasing order using bubble sort there are 30 comparisons and 17 swaps.
5. Use your results from part (iv) to compare the efficiency of these two methods in this case. Katie makes and sells cookies. Each batch of plain cookies takes 8 minutes to prepare and then 12 minutes to bake. Each batch of chocolate chip cookies takes 12 minutes to prepare and then 12 minutes to bake. Each batch of fruit cookies takes 10 minutes to prepare and then 12 minutes to bake. Katie can only bake one batch at a time. She has the use of the kitchen, including the oven, for at most 1 hour.
   [0pt]

1. Each batch of cookies must be prepared before it is baked. By considering the maximum time available for baking the cookies, explain why Katie can make at most 4 batches of cookies. [2] Katie models the constraints as $$\begin{gathered} x + y + z \leqslant 4 \\ 4 x + 6 y + 5 z \leqslant 24 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$ where \(x\) is the number of batches of plain cookies, \(y\) is the number of batches of chocolate chip cookies and \(z\) is the number of batches of fruit cookies that Katie makes.
2. Each batch of cookies that Katie prepares must be baked within the hour available. By considering the maximum time available for preparing the cookies, show how the constraint \(4 x + 6 y + 5 z \leqslant 24\) was formed.
3. In addition to the constraints, what other restriction is there on the values of \(x , y\) and \(z\) ? Katie will make \(\pounds 5\) profit on each batch of plain cookies, \(\pounds 4\) on each batch of chocolate chip cookies and \(\pounds 3\) on each batch of fruit cookies that she sells. Katie wants to maximise her profit.
4. Write down an expression for the objective function to be maximised. State any assumption that you have made.
5. Represent Katie's problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm, choosing to pivot on an element from the \(x\)-column. Show how each row was obtained. Write down the number of batches of cookies of each type and the profit at this stage. After carrying out market research, Katie decides that she will not make fruit cookies. She also decides that she will make at least twice as many batches of chocolate chip cookies as plain cookies.
6. Represent the constraints for Katie's new problem graphically and calculate the coordinates of the vertices of the feasible region. By testing suitable integer-valued coordinates, find how many batches of plain cookies and how many batches of chocolate chip cookies Katie should make to maximise her profit. Show your working.

6 This list is to be sorted into decreasing order, ending up with 31 in the first position and 4 in the last position.
15
4
12
23
14
16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12

16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12
   9
   4 The sorting is then continued using shuttle sort on this list.
2. Record the list at the end of each of the first, second and third passes of shuttle sort. You do not need to show the individual swaps in each pass.
3. How many passes through shuttle sort are needed to complete the sort? Explain your reasoning.
4. A digraph is represented by the adjacency matrix below. $$\begin{gathered} \\ \\ \\ \\ \\ \\ \text { from } \end{gathered} \begin{gathered} \\ \mathrm { A } \\ \mathrm {~B} \\ \mathrm { C } \end{gathered} \quad \quad \left( \begin{array} { c c c } 1 & \mathrm {~B} & \mathrm { C } \\ 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right)$$
   1. For each vertex, write down
      • the indegree,
      • the outdegree.
      • Explain how the indegrees and outdegrees show that the digraph is semi-Eulerian.
      • A graph is represented by the adjacency matrix below.
      $$\left. \begin{array} { c } \\ \mathrm { D } \\ \mathrm { E } \\ \mathrm {~F} \end{array} \quad \begin{array} { c c c } \mathrm { D } & \mathrm { E } & \mathrm {~F} \\ 2 & 1 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 0 \end{array} \right)$$ (a) Explain how the numerical entries in the matrix show that this can be drawn as an undirected graph.
      (b) Explain how the adjacency matrix shows that this graph is semi-Eulerian.
   2. By referring to the vertex degrees, explain why the loop from A to itself is shown as a 1 in the adjacency matrix in part (i) but the loop from \(D\) to itself is shown as 2 in the adjacency matrix in part (ii).
      1. List the 15 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } \}\). Amy, Bao, Cal and Dana want to travel by taxi from a meeting to the railway station. They book taxis but only two taxis turn up. Each taxi must have a minimum of one passenger and can carry a maximum of four passengers. Dana jumps into one of the taxis.
      2. Find the number of ways that Amy, Bao and Cal can be split between the two taxis. Amy does not want to travel in the same taxi as Bao.
      3. Determine the number of ways that Amy, Bao and Cal can be split between taxis with this additional restriction. Six people want to travel by taxi from a hotel to the railway station using taxis. There must be a minimum of one passenger and a maximum of four passengers in each taxi. The taxis may be regarded as being indistinguishable.
      4. Calculate how many ways there are of splitting the six people between taxis. \section*{END OF QUESTION PAPER} \section*{OCR} Oxford Cambridge and RSA

2 A list is used to demonstrate how different sorting algorithms work.
After two passes through shuttle sort the resulting list is $$\begin{array} { l l l l l l l } 17 & 23 & 84 & 21 & 66 & 35 & 12 \end{array}$$

1. How many different possibilities are there for the original list? Suppose, instead, that the same sort was carried out using bubble sort on the original list.
2. Write down the list after two passes through bubble sort. The number of comparisons made is used as a measure of the run-time for a sorting algorithm.
3. For a list of six values, what is the maximum total number of comparisons made in the first two passes of
   1. shuttle sort
   2. bubble sort? Steve used both shuttle sort and bubble sort on a list of five values. He says that shuttle sort is more efficient than bubble sort because it made fewer comparisons in the first two passes.
   3. Comment on what Steve said. The number of comparisons made when shuttle sort and bubble sort are used to sort every permutation of a list of four values is shown in the table below.

      	Number of comparisons	3	4	5	6
      Shuttle sort	Number of permutations	2	6	8	8
      Bubble sort	Number of permutations	1	0	7	16

   4. Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.

1. 11
17
10
14
8
13
6
4
15
7

1. 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.
2. 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
3. Calculate a lower bound for the minimum number of bins required. You must show your working.

4
15
7

1. 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.
2. 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
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \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.
   1. 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.
   2. 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.
   3. 1. 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.
      2. 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.
      3. State the new minimum cost of connecting the nine buildings.
         3. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
         \end{figure} \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
         \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.
   4. Define the term 'matching'.
      (2)
   5. 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.
   6. 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.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. 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 .
   9. 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.

17
10
14
8
13
6
4
15
7

1. 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.
2. 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
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \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.
   1. 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.
   2. 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.
   3. 1. 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.
      2. 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.
      3. State the new minimum cost of connecting the nine buildings.
         3. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
         \end{figure} \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
         \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.
   4. Define the term 'matching'.
      (2)
   5. 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.
   6. 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.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. 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 .
   9. 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.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-6_560_1134_251_470} \captionsetup{labelformat=empty} \caption{Figure 5}
      \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road.
   10. Use Dijkstra's algorithm to find the shortest route from S to T . State your route and its length. The road represented by arc CE is now closed for repairs.
   11. Find two shortest routes from S to T that do not include arc CE . State the length of these routes.
       (3)
       6. A linear programming problem in \(x\) and \(y\) is described as follows. Minimise \(\quad C = 2 x + 5 y\) subject to $$\begin{aligned} x + y & \geqslant 500 \\ 5 x + 4 y & \geqslant 4000 \\ y & \leqslant 2 x \\ y & \geqslant x - 250 \\ x , y & \geqslant 0 \end{aligned}$$
   12. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
   13. Use point testing to determine the exact coordinates of the optimal point, P. You must show your working. The first constraint is changed to \(x + y \geqslant k\) for some value of \(k\).
   14. Determine the greatest value of \(k\) for which P is still the optimal point.
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-8_582_1226_248_422} \captionsetup{labelformat=empty} \caption{Figure 6}
       \end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   15. Complete Diagram 1 in the answer book to show the early event times and late event times.
   16. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
   17. Use your cascade chart to determine a lower bound for the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. The project is to be completed in the minimum time using as few workers as possible.
   18. Schedule the activities, using Grid 2 in the answer book.
       8. A charity produces mixed packs of posters and flyers to send out to sponsors. Pack A contains 40 posters and 20 flyers.
       Pack B contains 30 posters and 50 flyers.
       The charity must send out at least 15000 flyers.
       The charity wants between \(40 \%\) and \(60 \%\) of the total packs produced to be Pack As.
       Posters cost 15p each and flyers cost 3p each.
       The charity wishes to minimise its costs.
       Let \(x\) represent the number of Pack As produced, and \(y\) represent the number of Pack Bs produced.
       Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
       You should not attempt to solve the problem.
       (Total 6 marks)

4. Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan

1. Use the quick sort algorithm to sort the above list into alphabetical order.
   (5)
2. Use the binary search algorithm to locate the name Louis.

10. & Freya
A binary search is to be performed on the names in the list above to locate the name Kim.

1. Explain why a binary search cannot be performed with the list in its present form.
2. Using an appropriate algorithm, alter the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
3. Use the binary search algorithm to locate the name Kim in the list you obtained in (b). You must make your method clear.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-3_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
   1. Define the terms
      1. tree,
      2. minimum spanning tree.
         (3)
      3. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 1. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
         (3)
      4. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
   2. State whether your minimum spanning tree is unique. Justify your answer.
      (1)
      3. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-4_1492_1298_210_379} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} Figure 2 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
   3. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
   4. Find the optimal values of \(x\) and \(y\). You must make your method clear.
   5. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
   6. write down the optimal values of \(x\) and \(y\).
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_620_582_287_1098} \captionsetup{labelformat=empty} \caption{Figure 4}
      \end{figure} Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching.
      There are three possible alternating paths that start at A .
      One of them is $$A - 3 = R - 4 = C - 5$$
   7. Find the other two alternating paths that start at A .
   8. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
   9. Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-6_835_913_219_575} \captionsetup{labelformat=empty} \caption{Figure 5
      [0pt] [The total weight of the network is 98 km ]}
      \end{figure} Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.
   10. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   11. Write down a possible shortest inspection route, giving its length. It is now decided to start the inspection route at D . The route must still traverse each pipe at least once but may finish at any node.
   12. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.
       6. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-7_823_1374_226_347} \captionsetup{labelformat=empty} \caption{Figure 6}
       \end{figure} Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.
   13. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
   14. Explain how you determined your shortest route from your labelled diagram. The track between E and F is now closed for resurfacing and cannot be used.
   15. Find the shortest route from A to H and state its length.
       (2)
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-8_798_1497_258_283} \captionsetup{labelformat=empty} \caption{Figure 7}
       \end{figure} A project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   16. Complete the precedence table in the answer book.
       (3)
   17. Complete Diagram 1 in the answer book, to show the early event times and late event times.
   18. State the critical activities.
   19. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
   20. By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.
       8. A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:
       Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is \(\pounds 15\).
       The profit on each type B radio is \(\pounds 12\).
       The firm wishes to maximise its weekly profit.
       Formulate this situation as a linear programming problem, defining your variables.
       (Total 7 marks)

1. Use the binary search algorithm to try to locate the name NIGEL in the following alphabetical list. Clearly indicate how you chose your pivots and which part of the list is being rejected at each stage.

10. & Verity
2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

1. Find an alternating path linking George with 5. List the resulting improved matching this gives.
2. Explain why it is not possible to find a complete matching. George now has task 2 added to his possible allocation.
3. Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-04_586_1417_205_317} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} The network in Figure 3 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.
   1. Find a minimum spanning tree for the network in Figure 3, showing clearly the order in which you selected the arcs for your tree, using
      1. Kruskal's algorithm,
      2. Prim's algorithm, starting from \(A\). Given that footpaths are already in place along \(A B\) and \(F I\) and so should be included in the spanning tree,
      3. explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.)
         4. \(\quad \begin{array} { l l l l l l l l l l } 650 & 431 & 245 & 643 & 455 & 134 & 710 & 234 & 162 & 452 \end{array}\)
      4. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
      5. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.)
      6. Determine whether your solution to part (b) is optimal. Give a reason for your answer.
         5. (a) Explain why a network cannot have an odd number of vertices of odd degree. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-06_615_1143_338_461} \captionsetup{labelformat=empty} \caption{Figure 4}
         \end{figure} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.
      7. Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
      8. Find the length of Hamish's route.
         [0pt] [The total weight of the network in Figure 4 is 4180 m .]
         (1)
         6. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-07_627_1408_223_331} \captionsetup{labelformat=empty} \caption{Figure 5}
         \end{figure} Figure 5 shows a network of roads. The number on each arc represents the length of that road in km .
      9. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(J\). State your shortest route and its length.
      10. Explain how you determined the shortest route from your labelled diagram. The road from \(C\) to \(F\) will be closed next week for repairs.
      11. Find a shortest route from \(A\) to \(J\) that does not include \(C F\) and state its length.
          7. \begin{figure}[h]
          \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-08_1501_1650_201_210} \captionsetup{labelformat=empty} \caption{Figure 6}
          \end{figure} The captain of the Malde Mare takes passengers on trips across the lake in her boat.
          The number of children is represented by \(x\) and the number of adults by \(y\). Two of the constraints limiting the number of people she can take on each trip are $$x < 10$$ and $$2 \leqslant y \leqslant 10$$ These are shown on the graph in Figure 6, where the rejected regions are shaded out.
      12. Explain why the line \(x = 10\) is shown as a dotted line.
      13. Use the constraints to write down statements that describe the number of children and the number of adults that can be taken on each trip.
          (3) For each trip she charges \(\pounds 2\) per child and \(\pounds 3\) per adult. She must take at least \(\pounds 24\) per trip to cover costs. The number of children must not exceed twice the number of adults.
      14. Use this information to write down two inequalities.
          (2)
   2. Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R .
      (4)
   3. Use your graph to determine how many children and adults would be on the trip if the captain takes:
      1. the minimum number of passengers,
      2. the maximum number of passengers.
         8. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-10_622_1441_194_312} \captionsetup{labelformat=empty} \caption{Figure 7}
         \end{figure} An engineering project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest time.
      3. Calculate the early time and late time for each event. Write these in the boxes in Diagram 1 in the answer book.
      4. State the critical activities.
      5. Find the total float on activities \(D\) and \(F\). You must show your working.
      6. On the grid in the answer book, draw a cascade (Gantt) chart for this project. The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,
      7. which activities must be happening on each of these two days?

4

1. A student is using a bubble sort to rearrange seven numbers into ascending order.
   Her correct solution is as follows:

   Initial list	18	17	13	26	10	14	24
   After 1st pass	17	13	18	10	14	24	26
   After 2nd pass	13	17	10	14	18	24	26
   After 3rd pass	13	10	14	17	18	24	26
   After 4th pass	10	13	14	17	18	24	26
   After 5th pass	10	13	14	17	18	24	26

   Write down the number of comparisons and swaps on each of the five passes.
2. Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.

7 The numbers 17, 3, 16 and 4 are to be sorted into ascending order.
The following four methods are to be compared: bubble sort, shuttle sort, Shell sort and quick sort (with the first number used as the pivot). A student uses each of the four methods and produces the correct solutions below. Each solution shows the order of the numbers after each pass.

1. Write down which of the four solutions is the bubble sort, the shuttle sort, the Shell sort and the quick sort.
2. For each of the four solutions, write down the number of comparisons and swaps (exchanges) on the first pass.

2

1. Use a bubble sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 13 & 16 & 10 & 11 & 4 & 12 & 6 & 7 \end{array}$$
2. State the number of comparisons and the number of swaps (exchanges) for each of the first three passes.

2

1. Use a shuttle sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 18 & 2 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$
2. State the number of comparisons and swaps (exchanges) for each of the first three passes.

2

1. Use a Shell sort to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 28 & 22 & 20 & 17 & 14 & 11 & 6 & 5 \end{array}$$
2. 1. Write down the number of comparisons on the first pass.
   2. Write down the number of swaps on the first pass.
3. Find the total number of comparisons needed to rearrange the original list of 8 numbers into ascending order using a shuttle sort.
   (You do not need to perform a shuttle sort.)