Edexcel D1 (Decision Mathematics 1) 2018 June

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) Define the terms

1. alternating path,
2. complete matching.
   (4) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_521_614_450_351} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_509_604_456_1098} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 1 shows the possible allocations of six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3,4,5\) and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task. Figure 2 shows an initial matching.
   (b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from F to 1. Hence find an improved matching. You must write down the alternating path used and state your improved matching.
   (3)
   (c) Explain why it is not possible to find a complete matching.
   (1) Worker C has task 1 added to his possible allocations.
   (d) Starting from the improved matching found in (b), use the maximum matching algorithm to find a complete matching. You must write down the alternating path used and state your complete matching.

3. \begin{figure}[h] \end{figure} Figure 3 shows a graph G that contains \(17 \operatorname { arcs }\) and 8 vertices.

1. State how many arcs there are in a spanning tree for G .
   (1)
2. Explain why a path on G cannot contain 10 vertices.
   (2)
3. Determine the number of arcs that would need to be added to G to make G a complete graph with 8 vertices.
   (1) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_684_1326_1420_370} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} Figure 4 shows a weighted graph.
4. Use Prim's algorithm, starting at C , to find the minimum spanning tree for the weighted graph. You must clearly state the order in which you select the arcs of the tree.
   (3)
5. State the weight of the minimum spanning tree.
   (1)

4. \begin{figure}[h] \end{figure} [The total weight of the network is 275]
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. On Monday, Mandeep must travel from D to H via A.
2. Find the shortest time needed to travel from D to H via A . State the quickest route. On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
3. Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, giving its duration. On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
5. State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.

5. \begin{figure}[h] \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 hours, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Complete the precedence table in the answer book.
2. Complete Diagram 1 in the answer book to show the early event times and late event times.
3. State the minimum project completion time and list the critical activities.
4. Calculate the maximum number of hours by which activity E could be delayed without affecting the shortest possible completion time of the project. You must make the numbers used in your calculation clear.
5. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working. The project is to be completed in the minimum time using as few workers as possible.
6. Schedule the activities using Grid 1 in the answer book.
   (3) Before the project begins it becomes apparent that activity E will require an additional 6 hours to complete. The project is still to be completed in the shortest possible time and the time to complete all other activities is unchanged.
7. State the new minimum project completion time and list the new critical activities.