Edexcel D1 (Decision Mathematics 1) 2021 January

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

2. A restaurant sells two sizes of pizza, small and large. The restaurant owner knows that, each evening, she needs to make

• at least 85 pizzas in total
• at least twice as many large pizzas as small pizzas

In addition, at most \(80 \%\) of the pizzas must be large.
Each small pizza costs \(\pounds 2\) to make and each large pizza costs \(\pounds 3\) to make.
The restaurant owner wants to minimise her costs. Let \(x\) represent the number of small pizzas made each evening and let \(y\) represent the number of large pizzas made each evening. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.

3. \(\quad \begin{array} { l l l l l l l l l l } 2.6 & 0.8 & 2.1 & 1.2 & 0.9 & 1.7 & 2.3 & 0.3 & 1.8 & 2.7 \end{array}\)

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.
   2. Write down, in the table in the answer book, the number of comparisons and the number of swaps performed during each of these two passes. After a third pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 2.6 & 2.1 & 1.7 & 2.3 & 1.2 & 1.8 & 2.7 & 0.9 & 0.8 & 0.3 \end{array}$$
3. Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
4. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 5

4. (a) Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between seven museums, A, B, C, D, E, F and G. Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Fran's route. Make your method clear. Starting at D, a second upper bound of 203 km was found.
(c) State whether this is a better upper bound than the answer to (b), giving a reason for your answer. A reduced network is formed by deleting \(G\) and all the arcs that are directly joined to \(G\).
(d) (i) Use Prim's algorithm, starting at A, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.
(ii) Hence calculate a lower bound for the length of Fran's route. By deleting A, a second lower bound was found to be 188 km .
(e) State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.
(f) Using only the results from (c) and (e), write down the smallest interval that you can be confident contains the length of Fran's optimal route.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 253] Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road. One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to H . State your path and its length. On another day, Mabintou wishes to travel from F to K via A.
2. Find a route of minimum length from F to K via A and state its length. The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
3. By considering the pairings of all relevant nodes, find the length of James' route. State the arcs that will need to be traversed twice. You must make your method and working clear.
   (6)
4. State the number of times that James will pass through F. It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
5. State the vertex where the new inspection route will finish.
6. Calculate the difference between the lengths of the two inspection routes.

6. The table above shows the activities required for the completion of a building project. For each activity the table shows the duration, in days, and the immediately preceding activities. Each activity requires one worker. The project is to be completed in the shortest possible time. \begin{figure}[h] \end{figure} Figure 2 shows a partially completed activity network used to model the project. The activities are represented by the arcs and the numbers in brackets on the arcs are the times taken, in days, to complete each activity.

1. Complete the network in Diagram 1 in the answer book by adding activities \(\mathrm { G } , \mathrm { H }\) and I and the minimum number of dummies.
2. Add the early event times and the late event times to Diagram 1 in the answer book.
3. State the critical activities.
4. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
5. Schedule the activities on Grid 1 in the answer book, using the minimum number of workers, so that the project is completed in the minimum time.

7. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The equations of two of the lines have been shown in Figure 3. Given that \(k\) is a positive constant,

1. determine, in terms of \(k\) where necessary, the inequalities that define \(R\). The objective is to maximise \(P = 5 x + k y\)
   Given that the value of \(P\) is 38 at the optimal vertex of \(R\),
2. determine the possible value(s) of \(k\). You must show algebraic working and make your method clear.
   (Total 11 marks)