Binary Search Execution

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

1. (a) Use the binary search algorithm to locate the name PENICUIK in the following list.

\begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
(b) Use the same algorithm to attempt to locate PENDINE.
(c) Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}

1. Use the binary search algorithm to try to locate the word "Parallelogram" in the following alphabetical list. Clearly indicate how you choose your pivots and which part of the list you are rejecting at each stage.

Arc Centre Chord Circle Circumference Diameter Radius Sector Segment Tangent

1. $$\begin{aligned} & \text { Kerry (K) } \\ & \text { Nikki (N) } \\ & \text { Violet (V) } \\ & \text { Dev (D) } \\ & \text { Henri (H) } \\ & \text { Leslie (L) } \\ & \text { Enlai (E) } \\ & \text { Sylvester (S) } \\ & \text { Joan (J) } \end{aligned}$$ A binary search is to be performed on the names in the list above to locate the name Leslie.

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. You should state the name of the algorithm you use and show the list after each complete iteration.
3. Use the binary search algorithm to locate the name Leslie in the altered list you obtained in (b). You must make your method clear. The binary search algorithm is to be used to search for a name in an alphabetical list of 727 names.
4. Find the maximum number of iterations needed. You should justify your answer.

2. (a) Starting with a list of all the letters of the alphabet in alphabetical order, demonstrate how a binary search is used to locate the letter P. In each iteration, you must make clear your pivot and the part of the list you are retaining.
(4)
(b) Find the maximum number of iterations needed to locate any particular letter of the alphabet. Justify your answer.

4.

1. Sam (S)
2. Janelle (J)
3. Haoyu (H)
4. Alfie (A)
5. Cyrus (C)
6. Komal (K)
7. Polly (P)
8. David (D)
9. Tom (T)
10. Lydia (L)

A binary search is to be performed on the names in the list above to locate the name Lydia.

1. Using an appropriate algorithm, rearrange 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.
2. Use the binary search algorithm to locate the name Lydia in the list you obtained in (a). You must make your method clear.

2. $$\begin{array} { l l l l l l l l l l } 18 & 29 & 48 & 9 & 42 & 31 & 37 & 24 & 27 & 41 \end{array}$$ The numbers above are Alan's batting scores for the first 10 cricket matches of the season.

1. Use a quick sort to sort this list of numbers into ascending order. You must make your pivots clear. Alan's batting scores for the final 10 cricket matches of the same season were \(\begin{array} { l l l l l l l l l l } 72 & 53 & 89 & 91 & 68 & 67 & 90 & 77 & 83 & 75 \end{array}\)
2. Carry out a bubble sort on this second list of numbers to produce a list of these scores in ascending order. You need only give the state of the list after each pass. Alan's combined batting scores for the entire season were $$\begin{array} { l l l l l l l l l l l l l l l l l l l l } 9 & 18 & 24 & 27 & 29 & 31 & 37 & 41 & 42 & 48 & 53 & 67 & 68 & 72 & 75 & 77 & 83 & 89 & 90 & 91 \end{array}$$
3. Use the binary search algorithm to locate 68 in the combined list of 20 scores. You must make your method clear.

2. Use the binary search algorithm to try to locate the name Hannah in the following alphabetical list. Clearly indicate how you selected your pivots and which part of the list is being rejected at each stage. \begin{displayquote} Adam
Ben
Charlie
Eleanor
Freya
Greg
Jenny
Richard
Toby \end{displayquote}

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. 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?

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. 1. Bhavika 2. Clive 3. Elizabeth 4. John 5. Mark 6. Nicky 7. Preety 8. Steve 9. Trevor 10. Verity (Total 4 marks)

1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth

A binary search is to be performed on the names in the list above to locate the name Newcastle.

1. Explain why a binary search cannot be performed with the list in its present form. [1]
2. Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use. [4]
3. Use the binary search algorithm on your new list to locate the name Newcastle. [4]