Questions — Edexcel (9670 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics Stats 1 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Edexcel FD1 2020 June Q4
Challenging +1.2
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-06_1171_1758_269_150} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
  1. Write down the inequalities that define \(R\). The objective is to maximise \(P\), where \(P = 3 x + y\)
  2. Obtain the exact value of \(P\) at each of the three vertices of \(R\) and hence find the optimal vertex, \(V\). The objective is changed to maximise \(Q\), where \(Q = 3 x + a y\). Given that \(a\) is a constant and the optimal vertex is still \(V\),
  3. find the range of possible values of \(a\).
Edexcel FD1 2020 June Q5
Standard +0.3
5. The nine distinct numbers in the following list are to be packed into bins of size 50 $$\begin{array} { l l l l l l l l l } 23 & 17 & 19 & x & 24 & 8 & 18 & 10 & 21 \end{array}$$ When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23178
Bin 2: \(19 \quad x \quad 10\)
Bin 3: 2418
Bin 4: 21
  1. Explain why \(13 < x < 21\) The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is $$\begin{array} { l l l l l l l l l } 23 & 19 & 17 & 24 & x & 18 & 10 & 21 & 8 \end{array}$$
  2. Using this information, write down the smallest interval that must contain \(x\), giving your answer as an inequality. When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 2423
    Bin 2: 211910
    Bin 3: \(1817 x\)
    Bin 4: 8
    Given that only one of the bins is full and that \(x\) is an integer,
  3. calculate the value of \(x\). You must give reasons for your answer.
Edexcel FD1 2020 June Q6
Challenging +1.8
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-08_638_1107_212_479} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} [The total weight of the network is \(320 + x + y\) ]
  1. State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. The weights on the arcs in Figure 4 represent distances. The weight on arc EF is \(x\) where \(12 < x < 26\) and the weight on arc DG is \(y\) where \(0 < y < 10\) An inspection route of minimum length that traverses each arc at least once is found.
    The inspection route starts and finishes at A and has a length of 409
    It is also given that the length of the shortest route from F to G via A is 140
  2. Using appropriate algorithms, find the value of \(x\) and the value of \(y\).
Edexcel FD1 2020 June Q7
Challenging +1.2
7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below.
Basic variable\(x\)\(y\)\(z\)\(S _ { 1 }\)\(S _ { 2 }\)\(S _ { 3 }\)\(a _ { 1 }\)\(a _ { 2 }\)Value
\(S _ { 1 }\)1231000045
\(a _ { 1 }\)3200-10109
\(a _ { 2 }\)-10400-1014
\(P\)-2-1-3000000
A
  1. Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.
  2. Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.
    Basic variable\(x\)\(y\)\(z\)\(S _ { 1 }\)\(S _ { 2 }\)\(S _ { 3 }\)\(a _ { 1 }\)\(a _ { 2 }\)Value
    \(S _ { 1 }\)0\(\frac { 5 } { 6 }\)01\(\frac { 7 } { 12 }\)\(\frac { 3 } { 4 }\)\(- \frac { 7 } { 12 }\)\(- \frac { 3 } { 4 }\)\(\frac { 147 } { 4 }\)
    \(x\)1\(\frac { 2 } { 3 }\)00\(- \frac { 1 } { 3 }\)0\(\frac { 1 } { 3 }\)03
    \(z\)0\(\frac { 1 } { 6 }\)10\(- \frac { 1 } { 12 }\)\(- \frac { 1 } { 4 }\)\(\frac { 1 } { 12 }\)\(\frac { 1 } { 4 }\)\(\frac { 7 } { 4 }\)
    \(P\)0\(\frac { 5 } { 6 }\)00\(- \frac { 11 } { 12 }\)\(- \frac { 3 } { 4 }\)\(\frac { 11 } { 12 }\)\(\frac { 3 } { 4 }\)\(\frac { 45 } { 4 }\)
    A000000110
    1. Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
    2. Write down the basic feasible solution for the second stage.
  4. 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, \(T\). Make your method clear by stating the row operations you use.
    1. Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
    2. Write down the value of the objective function.
    3. State the values of the basic variables.
Edexcel FD1 2021 June Q1
Standard +0.8
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-02_606_670_260_699} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} A Hamiltonian cycle for the graph in Figure 1 begins \(\mathrm { C } , \mathrm { V } , \mathrm { E } , \mathrm { X } , \mathrm { A } , \mathrm { W } , \ldots\).
  1. Complete the Hamiltonian cycle.
  2. Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.
Edexcel FD1 2021 June Q2
Standard +0.8
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-03_700_1412_258_331} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} A project is modelled by the activity network shown in Figure 2. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity.
  1. Complete Diagram 1 in the answer book to show the early event times and the late event times. Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.
  2. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. You must show your working.
  3. Schedule the activities using Grid 1 in the answer book.
Edexcel FD1 2021 June Q3
Moderate -0.5
3. \begin{table}[h]
\cline { 2 - 9 } \multicolumn{1}{c|}{}ABCDEFGH
A-24424834373222
B24-403530413944
C4240-2126453836
D483521-32372927
E34302632-344028
F3741453734-4341
G323938294043-38
H22443627284138-
\captionsetup{labelformat=empty} \caption{Table 1}
\end{table} Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.
  1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree.
  2. State the weight of the minimum spanning tree. \begin{table}[h]
    \cline { 2 - 9 } \multicolumn{1}{c|}{}\(\mathbf { A }\)\(\mathbf { B }\)\(\mathbf { C }\)\(\mathbf { D }\)\(\mathbf { E }\)\(\mathbf { F }\)\(\mathbf { G }\)\(\mathbf { H }\)
    \(\mathbf { J }\)3127502943254935
    \captionsetup{labelformat=empty} \caption{Table 2}
    \end{table} Table 2 shows the distances, in miles, between town J and towns A , B , \(\mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .
    Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.
  3. Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
  4. Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.
Edexcel FD1 2021 June Q4
Standard +0.3
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-05_668_1424_169_322} \captionsetup{labelformat=empty} \caption{Figure 3
[0pt] [The total weight of the network is 1648]}
\end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. 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 six cities.
An initial route matrix is given in the answer book.
  1. Set up the initial time matrix.
  2. Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.
    \cline { 2 - 7 } \multicolumn{1}{c|}{}ABCDEF
    A-579514763220
    B57-72204120197
    C9572-242158125
    D147204242-84275
    E6312015884-191
    F220197125275191-
    A route is needed that minimises the total time taken to traverse each road at least once.
    The route must start at B and finish at E .
  3. Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
  4. Write down the length of the route.
Edexcel FD1 2021 June Q5
Moderate -0.8
  1. 30312522318136101524
    1. The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
    The ten numbers 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 original list of ten numbers, the following allocation is obtained.
    Bin 1:30122
    Bin 2:52310
    Bin 3:1815
    Bin 4:36
    Bin 5:24
  2. Explain why the value of the integer \(n\) must be either 44 or 45
  3. Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45
Edexcel FD1 2021 June Q6
Standard +0.3
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-07_728_1465_248_301} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} In Figure 4 the weights on the arcs represent distances.
    1. Use Dijkstra's algorithm to find the shortest path from A to H .
    2. State the length of the shortest path from A to H . One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
  2. Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
  3. Explain why your answer to part (b) can only be an approximation.
Edexcel FD1 2021 June Q7
Moderate -0.5
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-08_583_670_260_699} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 shows a partially completed activity network for a project that consists of 14 activities.
  1. Complete the precedence table in the answer book for the 8 activities in Figure 5. The precedence table for the remaining 6 activities is given below.
    ActivityImmediately preceding activities
    ID, E, G, H
    JD, E, G, H
    KE, G, H
    LI, J, K
    MJ, K
    NJ, K
  2. Complete the activity network in the answer book for the project. Your completed activity network must contain only the minimum number of dummies. Given that all 14 activities have the same duration,
  3. explain why activity D cannot be critical.
Edexcel FD1 2021 June Q8
Moderate -0.3
8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should
  • maximise the total time spent cycling and running
  • train for at most 39 hours
  • spend at least \(40 \%\) of her time swimming
  • spend a total of at least 28 hours of her time swimming and running
Susie needs to determine how long she should spend next week training for each activity. Let
  • \(x\) represent the number of hours swimming
  • \(y\) represent the number of hours cycling
  • \(z\) represent the number of hours running
    1. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.
      (5)
Susie 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 using slack variables, exactly one surplus variable and exactly one artificial variable
    • the rows for the two objective functions are formed
      (6)
    The following tableau \(T\) is obtained after one iteration of the second stage of the two-stage Simplex method.
    b.v.\(x\)\(y\)\(z\)\(s _ { 1 }\)\(\mathrm { S } _ { 2 }\)\(S _ { 3 }\)Value
    \(y\)01010111
    \(s _ { 2 }\)005-21-562
    \(x\)10100-128
    \(P\)00-110111
  • Obtain a suitable pivot for a second iteration. You must give reasons for your answer.
  • Starting from tableau \(T\), solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.
    •
    Edexcel FD1 2022 June Q1
    Easy -1.2
    1. A gardener needs the following lengths of string. All lengths are in metres.
      0.4
      1.7
      1.3
      2.5
      2.1
      3.4
      4.3
      4.7
      5.1
      5.9
      6.1
    She cuts the lengths from balls of string. Each ball contains 10 m of string.
    1. Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.
    2. Use the first-fit bin packing algorithm to determine how the lengths could be cut from the balls of string.
    Edexcel FD1 2022 June Q2
    Challenging +1.2
    2. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-03_563_1445_214_312} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.
      1. Use Dijkstra's algorithm to find the shortest path from A to K .
      2. State the length of the shortest path from A to K .
        (6) The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
      1. State the edges that will need to be traversed twice.
      2. Find the length of Blanche's route. It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
    3. By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.
    Edexcel FD1 2022 June Q3
    Moderate -0.5
    3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only. \begin{table}[h]
    ABCDEF
    A-1232242911
    B12-178\(\infty\)\(\infty\)
    C3217-412\(\infty\)
    D24\(\infty\)4-\(\infty\)13
    E\(\infty\)\(\infty\)1218-12
    F11\(\infty\)\(\infty\)1312-
    \captionsetup{labelformat=empty} \caption{Table 1}
    \end{table}
    1. By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. Floyd's algorithm is to be used to find the complete network of shortest distances between the six classrooms. The distance matrix after two iterations of Floyd's algorithm is shown in Table 2. \begin{table}[h]
      ABCDEF
      A-1229202911
      B12-1784123
      C2917-41240
      D24364-5313
      E\(\infty\)\(\infty\)1218-12
      F1123401312-
      \captionsetup{labelformat=empty} \caption{Table 2}
      \end{table}
    2. Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration. The final distance matrix after completion of Floyd's algorithm is shown in Table 3.
      ABCDEF
      A-1224202311
      B12-1282421
      C2817-41217
      D24214-1613
      E23291216-12
      F1123171312-
      \section*{Table 3} Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.
      1. Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.
      2. Find the length of each of the two cycles.
      3. State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka's route.
    Edexcel FD1 2022 June Q4
    Standard +0.8
    4. A linear programming problem in \(x , y\) and \(z\) is to be solved using the big-M method. The initial tableau is shown below.
    b.v.\(x\)\(y\)\(z\)\(S _ { 1 }\)\(s _ { 2 }\)\(S _ { 3 }\)\(a _ { 1 }\)\(a _ { 2 }\)Value
    \(\mathrm { S } _ { 1 }\)2341000013
    \(a _ { 1 }\)1-220-10108
    \(a _ { 2 }\)30-400-10112
    P2-4M\(- 3 + 2 M\)\(- 1 + 2 M\)0MM00\(- 20 M\)
    1. Using the information in the above tableau, formulate the linear programming problem. You should
      • list each of the constraints as an inequality
      • state the two possible objectives
      • Obtain the most efficient pivot for a first iteration of the big-M method. You must give reasons for your answer.
      \section*{Please turn over for Question 5}
    Edexcel FD1 2022 June Q5
    Moderate -0.5
    5. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-08_1099_1700_194_139} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} The network in Figure 2 shows the activities that need to be completed for a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times are shown in Figure 2.
    1. Complete Table 1 in the answer book to show the immediately preceding activities for each activity. It is given that \(4 < x \leqslant m\)
    2. 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.
    4. 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}
    5. Complete Table 2 in the answer book to show the number of workers required for each activity of the project.
    6. Draw a Gantt chart on Grid 1 in the answer book to represent the activity network.
    Edexcel FD1 2022 June Q6
    Moderate -0.5
    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
    1. 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.
    3. 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.
    4. 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
    Standard +0.3
    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.
    1. 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 }\)001\(- \frac { 3 } { 5 }\)0\(\frac { 1 } { 5 }\)1
      \(x\)100\(\frac { 1 } { 5 }\)0\(- \frac { 2 } { 5 }\)2
      \(S _ { 3 }\)000\(- \frac { 11 } { 5 }\)1\(\frac { 12 } { 5 }\)22
      \(y\)010\(\frac { 2 } { 5 }\)0\(\frac { 1 } { 5 }\)5
      \(P\)000\(\frac { 1 } { 5 } + \frac { 2 } { 5 } k\)0\(- \frac { 2 } { 5 } + \frac { 1 } { 5 } k\)\(5 k + 2\)
    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.
    3. 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
    Moderate -0.8
    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.
    1. State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
    2. Write down an example of a Hamiltonian cycle on G.
    3. State whether or not G is planar, justifying your answer.
    4. 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.
    5. 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]
      ABCDE
      A-1013155
      B10-354
      C133-27
      D1552-7
      E5477-
      \captionsetup{labelformat=empty} \caption{Table 1}
      \end{table}
    6. 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
    Standard +0.3
    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.
        ActivityNumber of workers
        A2
        B1
        C2
        D2
        E3
        F2
        G1
        H3
        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
    Standard +0.3
    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.
    2. 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
    Standard +0.3
    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
    Challenging +1.2
    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]
    ABCDEFGHJ
    A-345131792085561
    B34-17654554422127
    C5117-822871592210
    D316582-8722238692
    E79452887-65873018
    F2054712265-287581
    G84259238728-6369
    H55212286307563-12
    J6127109218816912-
    \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.
    2. 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.
    3. 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.
    4. 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).
    5. Interpret the route in terms of the actual towns visited.
    Edexcel FD1 2023 June Q6
    Standard +0.3
    6. The precedence table below shows the twelve activities required to complete a project.
    ActivityImmediately preceding activities
    A-
    B-
    C-
    DA
    EA, B
    FD, E
    GA, B, C
    HF, G
    ID, E
    JD, E
    KF, G, I, J
    LI
    1. 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.
    2. State the critical activities. Given that the total float of activity F is 2 hours,
    3. 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 .