- 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.
- Bhavika
- Clive
- Elizabeth
- John
- Mark
- Nicky
- Preety
- Steve
- Trevor
- Verity
(Total 4 marks)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{6a0cf9b1-e6a0-4c38-a2d9-deb9c0c76015-03_554_535_278_372}
\end{figure}
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{6a0cf9b1-e6a0-4c38-a2d9-deb9c0c76015-03_558_538_276_1064}
\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.
- Find an alternating path linking George with 5. List the resulting improved matching this gives.
- Explain why it is not possible to find a complete matching.
George now has task 2 added to his possible allocation.
- 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.