Edexcel D1 (Decision Mathematics 1) 2021 June

1. \(\begin{array} { l l l l l l l l l l l l l } 16 & 23 & 18 & 9 & 4 & 20 & 35 & 5 & 17 & 13 & 6 & 11 \end{array}\)
The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45 kg .

1. Calculate a lower bound for the number of containers needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to allocate the parcels to the containers.
3. Carry out a bubble sort, starting at the left-hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.
4. Use the first-fit decreasing bin packing algorithm to allocate the parcels to the containers.

2. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 1. 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 Diagram 1 in the answer book to show the early event times and the late event times.
2. Draw a cascade chart for this project on Grid 1 in the answer book.
3. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

3. \begin{figure}[h] \end{figure} An algorithm for finding the positive real root of the equation \(8 x ^ { 4 } + 5 x - 12 = 0\) is described by the flow chart shown in Figure 2.

1. Use the flow chart, with \(a = 1\), to complete the table in the answer book, stating values to at least 6 decimal places. Give the final output correct to 5 decimal places. Given that the value of the input \(a\) is a non-negative real number,
2. determine the set of values for \(a\) that cannot be used to find the positive real root of \(8 x ^ { 4 } + 5 x - 12 = 0\) using this flow chart.

4. \begin{figure}[h] \end{figure} Figure 3 models a network of roads. The number on each edge gives the length, in km , of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances in the answer book.
2. Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek's route. Write down the route that gives this upper bound.
3. Interpret the route found in (b) in terms of the towns actually visited.
4. Starting by deleting A and all of its arcs, find a lower bound for the route length. Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G .
5. By considering the pairings of all relevant nodes, find the length of Clive's route. State the edges that need to be traversed twice. You must make your method and working clear.

5. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Tamasi, who lives at A, needs to collect a caravan. Tamasi can collect a caravan from either J or K. Tamasi decides to use Dijkstra's algorithm once to find the shortest routes between A and J and between A and K.

1. State, with a reason, which vertex should be chosen as the starting vertex for the algorithm.
2. Use Dijkstra's algorithm to find the shortest routes from A to J and from A to K . You should state the routes and their corresponding lengths. Tamasi's brother lives at F . He needs to visit Tamasi at A and then visit their mother who lives at H .
3. Find a route of minimal length that goes from F to H via A .

6.

1. Draw the activity network for the project described in the precedence table above, using activity on arc and the minimum number of dummies.
   (5)
2. State which activity is guaranteed to be critical, giving a reason for your answer.
   (2) It is given that each activity in the table takes two hours to complete.
3. State the minimum completion time and write down the critical path for the project.
   (2)

17
25
31
15
11
46
17
27
-
15
47
E
32
F
35
G
-
\end{tabular}} &
\hline & & & & & & & &
\hline \end{tabular} \end{center} 6.