Edexcel FD1 (Further Decision 1) Specimen

1. A list of \(n\) numbers needs to be sorted into descending order starting at the left-hand end of the list.
   1. Describe how to carry out the first pass of a bubble sort on the numbers in the list.
   Bubble sort is a quadratic order algorithm.
   A computer takes approximately 0.021 seconds to apply a bubble sort to a list of 2000 numbers.
2. Estimate the time it would take the computer to apply a bubble sort to a list of 50000 numbers. Make your method clear.

2. \begin{figure}[h] \end{figure}

1. Define what is meant by a planar graph.
2. Starting at A, find a Hamiltonian cycle for the graph in Figure 1. Arc AG is added to Figure 1 to create the graph shown in Figure 2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-03_568_666_1226_701} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Taking ABCDEFGA as the Hamiltonian cycle,
3. use the planarity algorithm to determine whether the graph shown in Figure 2 is planar. You must make your working clear and justify your answer.

3. (a) Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem. The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G . The least distance between B and G is \(x \mathrm {~km}\), where \(x > 25\) Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.
(b) Starting by deleting B and all of its arcs, find a lower bound for Preety's route. Preety found the nearest neighbour routes from each of A and C . Given that the sum of the lengths of these routes is 331 km ,
(c) find \(x\), making your method clear.
(d) Write down the smallest interval that you can be confident contains the optimal length of Preety's route. Give your answer as an inequality.

4. \begin{figure}[h] \end{figure} The network in Figure 3 shows the roads linking a depot, D, and three collection points \(\mathrm { A } , \mathrm { B }\) and C . The number on each arc represents the length, in miles, of the corresponding road. The road from B to D is a one-way road, as indicated by the arrow.

1. Explain clearly if Dijkstra's algorithm can be used to find a route from D to A . The initial distance and route tables for the network are given in the answer book.
2. Use Floyd's algorithm to find a table of least distances. You should show both the distance table and the route table after each iteration.
3. Explain how the final route table can be used to find the shortest route from D to B . State this route. There are items to collect at \(\mathrm { A } , \mathrm { B }\) and C . A van will leave D to make these collections in any order and then return to D. A minimum route is required. Using the final distance table and the Nearest Neighbour algorithm starting at D,
4. find a minimum route and state its length. Floyd's algorithm and Dijkstra's algorithm are applied to a network. Each will find the shortest distance between vertices of the network.
5. Describe how the results of these algorithms differ.

5. A garden centre makes hanging baskets to sell to its customers. Three types of hanging basket are made, Sunshine, Drama and Peaceful. The plants used are categorised as Impact, Flowering or Trailing. Each Sunshine basket contains 2 Impact plants, 4 Flowering plants and 3 Trailing plants. Each Drama basket contains 3 Impact plants, 2 Flowering plants and 4 Trailing plants. Each Peaceful basket contains 1 Impact plant, 3 Flowering plants and 2 Trailing plants. The garden centre can use at most 80 Impact plants, at most 140 Flowering plants and at most 96 Trailing plants each day. The profit on Sunshine, Drama and Peaceful baskets are \(\pounds 12 , \pounds 20\) and \(\pounds 16\) respectively. The garden centre wishes to maximise its profit. Let \(x , y\) and \(z\) be the number of Sunshine, Drama and Peaceful baskets respectively, produced each day.

1. Formulate this situation as a linear programming problem, giving your constraints as inequalities.
2. State the further restriction that applies to the values of \(x , y\) and \(z\) in this context. The Simplex algorithm is used to solve this problem. After one iteration, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(- \frac { 1 } { 4 }\)	0	\(- \frac { 1 } { 2 }\)	1	0	\(- \frac { 3 } { 4 }\)	8
   \(s\)	\(\frac { 5 } { 2 }\)	0	2	0	1	\(- \frac { 1 } { 2 }\)	92
   \(y\)	\(\frac { 3 } { 4 }\)	1	\(\frac { 1 } { 2 }\)	0	0	\(\frac { 1 } { 4 }\)	24
   \(P\)	3	0	-6	0	0	5	480

3. State the variable that was increased in the first iteration. Justify your answer.
4. Determine how many plants in total are being used after only one iteration of the Simplex algorithm.
5. Explain why for a second iteration of the Simplex algorithm the 2 in the \(z\) column is the pivot value. After a second iteration, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac { 3 } { 8 }\)	0	0	1	\(\frac { 1 } { 4 }\)	\(- \frac { 7 } { 8 }\)	31
   \(s\)	\(\frac { 5 } { 4 }\)	0	1	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 4 }\)	46
   \(y\)	\(\frac { 1 } { 8 }\)	1	0	0	\(- \frac { 1 } { 4 }\)	\(\frac { 3 } { 8 }\)	1
   \(P\)	\(\frac { 21 } { 2 }\)	0	0	0	3	\(\frac { 7 } { 2 }\)	756

6. Use algebra to explain why this tableau is optimal.
7. State the optimal number of each type of basket that should be made. The manager of the garden centre is able to increase the number of Impact plants available each day from 80 to 100 . She wants to know if this would increase her profit.
8. Use your final tableau to determine the effect of this increase. (You should not carry out any further calculations.)

6. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete that activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

1. Calculate the early time and the late time for each event, using Diagram 1 in the answer book.
2. On Grid 1 in the answer book, complete the cascade (Gantt) chart for this project.
3. On Grid 2 in the answer book, draw a resource histogram to show the number of workers required each day when each activity begins at its earliest time. The supervisor of the project states that only three workers are required to complete the project in the minimum time.
4. Use Grid 2 to determine if the project can be completed in the minimum time by only three workers. Give reasons for your answer.

7. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(P = 3 x + 2 y + 2 z\)
subject to $$\begin{aligned} & 2 x + 2 y + z \leqslant 25
& x + 4 y \leqslant 15
& x \geqslant 3 \end{aligned}$$

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem. The big-M method is to be used to solve this linear programming problem.
2. Define, in this context, what M represents. You must use correct mathematical language in your answer. The initial tableau for a big-M solution to the problem is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	2	2	1	1	0	0	0	25
   \(s _ { 2 }\)	1	4	0	0	1	0	0	15
   \(t _ { 1 }\)	1	0	0	0	0	-1	1	3
   \(P\)	\(- ( 3 + M )\)	-2	-2	0	0	M	0	\(- 3 M\)

3. Explain clearly how the equation represented in the b.v. \(t _ { 1 }\) row was derived.
4. Show how the equation represented in the b.v. \(P\) row was derived. The tableau obtained from the first iteration of the big-M method is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	0	2	1	1	0	2	-2	19
   \(s _ { 2 }\)	0	4	0	0	1	1	-1	12
   \(x\)	1	0	0	0	0	-1	1	3
   P	0	-2	-2	0	0	-3	\(3 +\) M	9

5. Solve the linear programming problem, starting from this second tableau. You must
   • give a detailed explanation of your method by clearly stating the row operations you use and
   • state the solution by deducing the final values of \(P , x , y\) and \(z\).