Questions FD1 - A-Level Maths

Complete Table 1 in the answer book to show the immediately preceding activities for each activity. It is given that $4 < x \leqslant m$
State the largest possible integer value of $m$.
1. Complete Diagram 1 in the answer book to show the late event times.
2. State the activities that must be critical.
Calculate the total float for activity G. The resource histogram in Figure 3 shows the number of workers required when each activity starts at its earliest possible time. The histogram also shows which activities happen at each time. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-09_682_1612_356_230} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure}
Complete Table 2 in the answer book to show the number of workers required for each activity of the project.
Draw a Gantt chart on Grid 1 in the answer book to represent the activity network.

Edexcel FD1 2022 June Q6

6. The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to $\mathrm { K } _ { n }$ Step 1 Start
Step 2 Input the value of $n$
Step 3 Let $a = 1$
Step 4 Let $b = n - 2$
Step 5 Let $c = b$
Step 6 Let $a = a + 1$
Step $7 \quad$ Let $b = b - 1$
Step 8 Let $c = c + ( a \times b ) + ( a - 1 )$
Step 9 If $b > 0$ go to Step 6
Step 10 Output $C$
Step 11 Stop

For $\mathrm { K } _ { 5 }$, complete the table in the answer book to show the results obtained at each step of the algorithm. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-11_595_703_175_680} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} The weights of the ten arcs in Figure 4 are $$\begin{array} { l l l l l l l l l l } 17 & 21 & 24 & 14 & 23 & 13 & 15 & 19 & 28 & 20 \end{array}$$
1. Starting at the left-hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.
2. Find the total number of comparisons performed during the sort.
Find the maximum total number of comparisons required to sort the weights of the 10 arcs of $\mathrm { K } _ { 5 }$ into ascending order using bubble sort. It is given that the maximum total number of comparisons required to sort the weights of the arcs of $\mathrm { K } _ { n }$ into ascending order using bubble sort is $$\lambda n ( n - 1 ) ( n + 1 ) ( n - 2 )$$ where $\lambda$ is a constant.
Determine the maximum total number of comparisons required to sort the weights of the arcs of $\mathrm { K } _ { 50 }$ into ascending order using bubble sort. You must make your method and working clear.

Edexcel FD1 2022 June Q7

7. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-12_885_1130_210_456} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} Figure 5 shows the constraints of a linear programming problem in $x$ and $y$ where $R$ is the feasible region. The objective is to maximise $P = x + k y$, where $k$ is a positive constant.
The optimal vertex of $R$ is to be found using the Simplex algorithm.

Set up an initial tableau for solving this linear programming problem using the Simplex algorithm. After two iterations of the Simplex algorithm a possible tableau $T$ is

b.v.	$x$	$y$	$S _ { 1 }$	$s _ { 2 }$	$S _ { 3 }$	$s _ { 4 }$	Value
$s _ { 1 }$	0	0	1	$- \frac { 3 } { 5 }$	0	$\frac { 1 } { 5 }$	1
$x$	1	0	0	$\frac { 1 } { 5 }$	0	$- \frac { 2 } { 5 }$	2
$S _ { 3 }$	0	0	0	$- \frac { 11 } { 5 }$	1	$\frac { 12 } { 5 }$	22
$y$	0	1	0	$\frac { 2 } { 5 }$	0	$\frac { 1 } { 5 }$	5
$P$	0	0	0	$\frac { 1 } { 5 } + \frac { 2 } { 5 } k$	0	$- \frac { 2 } { 5 } + \frac { 1 } { 5 } k$	$5 k + 2$

State the value of each variable after the second iteration.
(1) It is given that $T$ does not give an optimal solution to the linear programming problem.
After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.
Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for $P$. You should state the row operations you use and make your method and working clear.
(9)

Edexcel FD1 2023 June Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-02_476_727_210_683} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} Figure 1 shows the graph G.

State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
Write down an example of a Hamiltonian cycle on G.
State whether or not G is planar, justifying your answer.
State the number of arcs that would need to be added to G to make the graph $\mathrm { K } _ { 5 }$ \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-03_467_716_178_671} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
For the network represented in Figure 2, complete the initial time matrix in the answer book. The time matrix after four iterations of Floyd's algorithm is shown in Table 1. \begin{table}[h]
A B C D E
A - 10 13 15 5
B 10 - 3 5 4
C 13 3 - 2 7
D 15 5 2 - 7
E 5 4 7 7 -
\captionsetup{labelformat=empty} \caption{Table 1}
\end{table}
Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.

Edexcel FD1 2023 June Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-04_474_958_210_555} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} The network in Figure 3 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. State the minimum completion time of the project. The table below lists the number of workers required for each activity in the project.
  Activity Number of workers
  A 2
  B 1
  C 2
  D 2
  E 3
  F 2
  G 1
  H 3
  Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption. It is given that each activity begins at its earliest possible start time.
1. On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time.
2. Hence state the time interval(s) when six workers are required.

Edexcel FD1 2023 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-05_862_1460_219_299} \captionsetup{labelformat=empty} \caption{Figure 4}

\end{figure} Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J.
The number on each edge gives the length of the corresponding edge.

1. Use Dijkstra's algorithm to find the shortest path from A to J.
2. State the length of the shortest path from A to J . One application of Dijkstra's algorithm has order $n ^ { 2 }$, where $n$ is the number of nodes in the network. It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.
Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes.

Edexcel FD1 2023 June Q4

4. The eleven distinct numbers listed below are to be packed into bins of size 40 $$\begin{array} { l l l l l l l l l l l } 15 & 22 & 3 & 9 & 23 & x & 5 & 4 & 18 & 20 & 13 \end{array}$$ It is known that $x$

is an integer less than 40
is the largest number in the list
1. Explain why it is not possible to pack the numbers into 3 bins of size 40

Given that it is possible to pack the numbers into 4 bins of size 40

determine the range of values for $x$

Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40

Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin.

Determine the value of $x$. You must give reasons for your answer.

Edexcel FD1 2023 June Q5

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-08_657_1066_214_502} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} [The total weight of the network is 423]
Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. \begin{table}[h]

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

\captionsetup{labelformat=empty} \caption{Table of shortest distances}

\end{table} A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J .

1. By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.
2. State the total length of this route.
Starting at A, use Prim's algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.
Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete's route. Write down the route that gives this upper bound.
By deleting G and all of its arcs, find a lower bound for the length of Pete's route. Pete decides to take the route he found in (c).
Interpret the route in terms of the actual towns visited.

Edexcel FD1 2023 June Q6

6. The precedence table below shows the twelve activities required to complete a project.

Activity	Immediately preceding activities
A	-
B	-
C	-
D	A
E	A, B
F	D, E
G	A, B, C
H	F, G
I	D, E
J	D, E
K	F, G, I, J
L	I

Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain the minimum number of dummies only.
(5) \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-11_654_1358_153_356} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} Figure 6 shows a partially completed cascade chart for the project. The non-critical activities F, J and K are not shown in Figure 6. The time taken to complete each activity is given in hours and the project is to be completed in the minimum possible time.
State the critical activities. Given that the total float of activity F is 2 hours,
state the duration of activity F . The duration of activity J is $x$ hours, and the duration of activity K is $y$ hours, where $x > 0$ and $y > 0$
1. State, in terms of $y$, the maximum possible total float for activity K.
2. State, in terms of $x$ and $y$, the total float for activity J .

Edexcel FD1 2023 June Q7

7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.

Each paperback takes 4 minutes to print and 1 minute to bind
Each hardcover takes 8 minutes to print and 5 minutes to bind
Each deluxe edition takes 15 minutes to print and 12 minutes to bind

The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours. The publisher decides to produce

at least 1600 books in total
at least three times as many paperbacks as hardcovers

The profit on each paperback sold is $\pounds 8$, the profit on each hardcover sold is $\pounds 20$ and the profit on each deluxe edition sold is $\pounds 40$ Let $x , y$ and $z$ represent the number of paperbacks, hardcovers and deluxe editions produced.

Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. The publisher decides to solve this linear programming problem by using the two-stage simplex method.

Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how

the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
the rows for the two objective functions are formed

The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

b.v.	$x$	$y$	$z$	$\mathrm { S } _ { 1 }$	$S _ { 2 }$	$S _ { 3 }$	$s _ { 4 }$	$a _ { 1 }$	$a _ { 2 }$	Value
$\mathrm { S } _ { 1 }$	0	0	0	1	1	3	0	-1	-3	600
$z$	0	$\frac { 4 } { 11 }$	1	0	$- \frac { 1 } { 11 }$	$\frac { 1 } { 11 }$	0	$\frac { 1 } { 11 }$	$- \frac { 1 } { 11 }$	$\frac { 2000 } { 11 }$
$x$	1	$\frac { 7 } { 11 }$	0	0	$\frac { 1 } { 11 }$	$- \frac { 12 } { 11 }$	0	$- \frac { 1 } { 11 }$	$\frac { 12 } { 11 }$	$\frac { 15600 } { 11 }$
$s _ { 4 }$	0	$\frac { 40 } { 11 }$	0	0	$\frac { 1 } { 11 }$	$- \frac { 12 } { 11 }$	1	$- \frac { 1 } { 11 }$	$\frac { 12 } { 11 }$	$\frac { 15600 } { 11 }$
$P$	0	$- \frac { 4 } { 11 }$	0	0	$- \frac { 32 } { 11 }$	$- \frac { 56 } { 11 }$	0	$\frac { 32 } { 11 }$	$\frac { 56 } { 11 }$	$\frac { 204800 } { 11 }$
I	0	0	0	0	0	0	0	1	1	0

Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use. After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.

b.v.	$x$	$y$	$z$	$\mathrm { S } _ { 1 }$	$S _ { 2 }$	$S _ { 3 }$	$s _ { 4 }$	Value
$s _ { 2 }$	0	0	0	1	1	3	0	600
$z$	0	0	1	$\frac { 1 } { 10 }$	0	$\frac { 1 } { 2 }$	$- \frac { 1 } { 10 }$	100
$x$	1	0	0	$- \frac { 3 } { 40 }$	0	$- \frac { 9 } { 8 }$	$- \frac { 7 } { 40 }$	1125
$y$	0	1	0	$- \frac { 1 } { 40 }$	0	$- \frac { 3 } { 8 }$	$\frac { 11 } { 40 }$	375
$P$	0	0	0	$\frac { 29 } { 10 }$	0	$\frac { 7 } { 2 }$	$\frac { 1 } { 10 }$	20500

Given that the publisher produces the optimal number of each version of the book,

1. state the maximum profit the publisher can earn,
2. find the number of hours the binding machine will be used.
Give a reason why the publisher may not earn the profit stated in (d)(i).

Edexcel FD1 2024 June Q1

1. $$\begin{array} { l l l l l l l l l l l } 17 & 8 & 16 & 12 & 24 & 19 & 23 & 11 & 20 & 13 & 4 \end{array}$$ The eleven numbers listed above are to be packed into bins of size $n$ where $n$ is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: 17812
Bin 2: 1624
Bin 3: 19114
Bin 4: 2313
Bin 5: 20

Explain why this packing means that the value of $n$ must be 40 The original list of eleven numbers is to be sorted into descending order.
Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40

Edexcel FD1 2024 June Q2

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-

Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
State the weight of the minimum spanning tree found in part (a).
Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
1. Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
2. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
(2) By deleting J and all of its arcs, a lower bound of length 274 miles was found.
State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

Edexcel FD1 2024 June Q3

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-06_764_1136_258_466} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure} [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

Use Dijkstra's algorithm to find the shortest path from A to J. Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track.
By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
- state which tracks she will repeat in her route
- state the total length of her route
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route.
Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.

Edexcel FD1 2024 June Q4

4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 A tree, T , has exactly six nodes. The degrees of the six nodes of T are
1
2
$( 4 - x )$
$( 2 x - 5 )$
$( 4 x - 11 )$
$( 3 x - 5 )$
where $x$ is an integer.
(b) Explain how you know that T cannot be Eulerian.
(c) (i) Determine the value of $x$
(ii) Hence state whether T is semi-Eulerian or not. You must justify your answer.
(5)
\includegraphics[max width=\textwidth, alt={}, center]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-07_588_579_977_744} \section*{Figure 2} Figure 2 shows a graph, $G$, with six nodes with degrees $1,2,3,3,3$ and 4
(d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees $1,2,3,3,3$ and 4 that is not isomorphic to G .

Edexcel FD1 2024 June Q5

5. Two friends, Anaira and Tommi, play a game involving two positive numbers $x$ and $y$ Anaira gives Tommi the following clues to see if he can correctly determine the value of $x$ and the value of $y$

$x$ is greater than $y$ and the difference between the two is at least 100
$x$ is at most 5 times as large as $y$
the sum of $2 x$ and $3 y$ is at least 350
the sum of $x$ and $y$ is as small as possible

Tommi decides to solve this problem by using the big-M method.

Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show
- how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables
- how the objective function was formed
The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.
b.v. $x$ $y$ $s _ { 1 }$ $S _ { 2 }$ $\mathrm { S } _ { 3 }$ $a _ { 1 }$ $a _ { 2 }$ Value
$x$ 1 0 $- \frac { 3 } { 5 }$ 0 $- \frac { 1 } { 5 }$ $\frac { 3 } { 5 }$ $\frac { 1 } { 5 }$ 130
1. State the value of $x$
2. Hence deduce the value of $y$, making your reasoning clear.

Edexcel FD1 2024 June Q6

6. The precedence table below shows the 12 activities required to complete a project.

Activity	Immediately preceding activities
A	-
B	-
C	-
D	A
E	A, B, C
F	A, B, C
G	C
H	D, E
I	D, E
J	D, E
K	F, G, J
L	F, G

Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain the minimum number of dummies only.
(5) Each of the activities shown in the precedence table requires one worker. The project is to be completed in the minimum possible time. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-11_303_1547_296_260} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows a schedule for the project using three workers.
1. State the critical path for the network.
2. State the minimum completion time for the project.
3. Calculate the total float on activity B.
4. Calculate the total float on activity G. Immediately after the start of the project, it is found that the duration of activity I, as shown in Figure 3, is incorrect. In fact, activity I will take 8 hours.
  The durations of all the other activities remain as shown in Figure 3.
Determine whether the project can still be completed in the minimum completion time using only three workers when the duration of activity I is 8 hours. Your answer must make specific reference to workers, times and activities.

Edexcel FD1 2024 June Q7

7. A maximisation linear programming problem in $x , y$ and $z$ is to be solved using the Simplex method. The tableau after the 1st iteration is shown below.

b.v.	$x$	$y$	$z$	$s _ { 1 }$	$S _ { 2 }$	$S _ { 3 }$	Value
$s _ { 1 }$	0	$- \frac { 1 } { 2 }$	$\frac { 3 } { 2 }$	1	$- \frac { 1 } { 2 }$	0	30
$x$	1	$\frac { 1 } { 4 }$	$- \frac { 1 } { 4 }$	0	$\frac { 1 } { 4 }$	0	10
$S _ { 3 }$	0	1	1	0	0	1	26
$P$	0	$- \frac { 1 } { 4 }$	$- \frac { 11 } { 4 }$	0	$\frac { 3 } { 4 }$	0	30

State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer.
By considering the equations represented in the above tableau, formulate the linear programming problem in $x , y$ and $z$ only. State the objective and list the constraints as inequalities with integer coefficients.
Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T . Make your method clear by stating the row operations you use.

Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.

State the values of the basic variables after the 2nd iteration. A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.

b.v.	$x$	$y$	$z$	$s _ { 1 }$	$S _ { 2 }$	$\mathrm { S } _ { 3 }$	Value
z	0	0	1	$\frac { 1 } { 2 }$	$- \frac { 1 } { 4 }$	$\frac { 1 } { 4 }$	$\frac { 43 } { 2 }$
$x$	1	0	0	$\frac { 1 } { 4 }$	$\frac { 1 } { 8 }$	$- \frac { 1 } { 8 }$	$\frac { 57 } { 4 }$
$y$	0	1	0	$- \frac { 1 } { 2 }$	$\frac { 1 } { 4 }$	$\frac { 3 } { 4 }$	$\frac { 9 } { 2 }$
$P$	0	1	0	$\frac { 5 } { 4 }$	$\frac { 1 } { 8 }$	$\frac { 7 } { 8 }$	$\frac { 361 } { 4 }$

Explain how you know that the student's attempt at the 3rd iteration is not correct.

Edexcel FD1 Specimen Q1

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.
Estimate the time it would take the computer to apply a bubble sort to a list of 50000 numbers. Make your method clear.

Edexcel FD1 Specimen Q2

2. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-03_570_663_175_701} \captionsetup{labelformat=empty} \caption{Figure 1}

\end{figure}

Define what is meant by a planar graph.
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,
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.

Edexcel FD1 Specimen Q3

3. (a) Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

	A	B	C	D	E	F	G
A	-	17	24	16	21	18	41
B	17	-	35	25	30	31	$x$
C	24	35	-	28	20	35	32
D	16	25	28	-	29	19	45
E	21	30	20	29	-	22	35
F	18	31	35	19	22	-	37
G	41	$x$	32	45	35	37	-

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.

Edexcel FD1 Specimen Q4

4. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-05_572_799_228_632} \captionsetup{labelformat=empty} \caption{Figure 3}

\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.

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.
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.
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,
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.
Describe how the results of these algorithms differ.

Edexcel FD1 Specimen Q5

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.

Formulate this situation as a linear programming problem, giving your constraints as inequalities.

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

State the variable that was increased in the first iteration. Justify your answer.
Determine how many plants in total are being used after only one iteration of the Simplex algorithm.

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

Use algebra to explain why this tableau is optimal.
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.
Use your final tableau to determine the effect of this increase. (You should not carry out any further calculations.)

Edexcel FD1 Specimen Q6

6. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-08_1113_1319_169_374} \captionsetup{labelformat=empty} \caption{Figure 4}

\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.

Calculate the early time and the late time for each event, using Diagram 1 in the answer book.
On Grid 1 in the answer book, complete the cascade (Gantt) chart for this project.
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.
Use Grid 2 to determine if the project can be completed in the minimum time by only three workers. Give reasons for your answer.

Edexcel FD1 Specimen Q7

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}$$

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.
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$
Explain clearly how the equation represented in the b.v. $t _ { 1 }$ row was derived.
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
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$.

b.v.	\(x\)	\(y\)	\(S _ { 1 }\)	\(s _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
\(s _ { 1 }\)	0	0	1	\(- \frac { 3 } { 5 }\)	0	\(\frac { 1 } { 5 }\)	1
\(x\)	1	0	0	\(\frac { 1 } { 5 }\)	0	\(- \frac { 2 } { 5 }\)	2
\(S _ { 3 }\)	0	0	0	\(- \frac { 11 } { 5 }\)	1	\(\frac { 12 } { 5 }\)	22
\(y\)	0	1	0	\(\frac { 2 } { 5 }\)	0	\(\frac { 1 } { 5 }\)	5
\(P\)	0	0	0	\(\frac { 1 } { 5 } + \frac { 2 } { 5 } k\)	0	\(- \frac { 2 } { 5 } + \frac { 1 } { 5 } k\)	\(5 k + 2\)

b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
\(\mathrm { S } _ { 1 }\)	0	0	0	1	1	3	0	-1	-3	600
\(z\)	0	\(\frac { 4 } { 11 }\)	1	0	\(- \frac { 1 } { 11 }\)	\(\frac { 1 } { 11 }\)	0	\(\frac { 1 } { 11 }\)	\(- \frac { 1 } { 11 }\)	\(\frac { 2000 } { 11 }\)
\(x\)	1	\(\frac { 7 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	0	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
\(s _ { 4 }\)	0	\(\frac { 40 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	1	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
\(P\)	0	\(- \frac { 4 } { 11 }\)	0	0	\(- \frac { 32 } { 11 }\)	\(- \frac { 56 } { 11 }\)	0	\(\frac { 32 } { 11 }\)	\(\frac { 56 } { 11 }\)	\(\frac { 204800 } { 11 }\)
I	0	0	0	0	0	0	0	1	1	0

b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
\(s _ { 2 }\)	0	0	0	1	1	3	0	600
\(z\)	0	0	1	\(\frac { 1 } { 10 }\)	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 10 }\)	100
\(x\)	1	0	0	\(- \frac { 3 } { 40 }\)	0	\(- \frac { 9 } { 8 }\)	\(- \frac { 7 } { 40 }\)	1125
\(y\)	0	1	0	\(- \frac { 1 } { 40 }\)	0	\(- \frac { 3 } { 8 }\)	\(\frac { 11 } { 40 }\)	375
\(P\)	0	0	0	\(\frac { 29 } { 10 }\)	0	\(\frac { 7 } { 2 }\)	\(\frac { 1 } { 10 }\)	20500

b.v.	\(x\)	\(y\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
\(x\)	1	0	\(- \frac { 3 } { 5 }\)	0	\(- \frac { 1 } { 5 }\)	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)	130

b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	Value
\(s _ { 1 }\)	0	\(- \frac { 1 } { 2 }\)	\(\frac { 3 } { 2 }\)	1	\(- \frac { 1 } { 2 }\)	0	30
\(x\)	1	\(\frac { 1 } { 4 }\)	\(- \frac { 1 } { 4 }\)	0	\(\frac { 1 } { 4 }\)	0	10
\(S _ { 3 }\)	0	1	1	0	0	1	26
\(P\)	0	\(- \frac { 1 } { 4 }\)	\(- \frac { 11 } { 4 }\)	0	\(\frac { 3 } { 4 }\)	0	30

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-

Activity	Number of workers
A	2
B	1
C	2
D	2
E	3
F	2
G	1
H	3

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-

Questions FD1 (49 questions)

Browse by module

Browse by board

Edexcel FD1 2022 June Q5

Edexcel FD1 2022 June Q6

Edexcel FD1 2022 June Q7

Edexcel FD1 2023 June Q1

Edexcel FD1 2023 June Q2

Edexcel FD1 2023 June Q3

Edexcel FD1 2023 June Q4

Edexcel FD1 2023 June Q5

Edexcel FD1 2023 June Q6

Edexcel FD1 2023 June Q7

Edexcel FD1 2024 June Q1

Edexcel FD1 2024 June Q2

Edexcel FD1 2024 June Q3

Edexcel FD1 2024 June Q4

Edexcel FD1 2024 June Q5

Edexcel FD1 2024 June Q6

Edexcel FD1 2024 June Q7

Edexcel FD1 Specimen Q1

Edexcel FD1 Specimen Q2

Edexcel FD1 Specimen Q3

Edexcel FD1 Specimen Q4

Edexcel FD1 Specimen Q5

Edexcel FD1 Specimen Q6

Edexcel FD1 Specimen Q7

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-