Edexcel FD1 AS (Further Decision 1 AS) 2023 June

1. $$\begin{array} { l l l l l l l l l l l } 67 & 59 & 46 & 71 & 40 & 48 & 53 & 63 & 45 & 54 & 56 \end{array}$$ The list of eleven numbers shown above is to be sorted into descending order.
Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.

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 required, in hours, to complete the corresponding activity. The numbers in circles are the event numbers. Each activity requires one worker, and the project is to be completed in the shortest possible time.

1. Explain the significance of the dummy activity from event 3 to event 4
2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
3. State the critical activities.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
5. Draw a Gantt chart for this project on Grid 1 in the answer book.

3. \begin{figure}[h] \end{figure} Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track.
Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel. Given that Dijkstra's algorithm is to be applied only once to find Dyfan's route,

1. explain why the algorithm should begin at C.
2. Use Dijkstra's algorithm to find the shortest route from A to J via C. State this route and its length.
3. Use Prim's algorithm, starting at C , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. State the total length, in km , of the minimum spanning tree.

4. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.

1. State the inequalities that define the feasible region. The maximum value of the objective function is \(\frac { 160 } { 3 }\) The minimum value of the objective function is \(\frac { 883 } { 41 }\)
2. Determine the objective function, showing your working clearly.

5. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 3\) ] Figure 4 shows a graph G that contains 8 arcs and 6 vertices.

1. State the minimum number of arcs that would need to be added to make G into an Eulerian graph.
2. Explain whether or not the route \(\mathrm { A } - \mathrm { C } - \mathrm { F } - \mathrm { E } - \mathrm { C } - \mathrm { D } - \mathrm { B }\) is an example of a path on G. Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that \(x > 1.6\)
   A route is required that
   • starts and finishes at the same vertex
   • traverses each road at least once
   • minimises the total time taken
   The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice,
3. determine the range of possible values of \(x\), making your reasoning clear.