Questions — Edexcel D1 (505 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 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 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 PURE 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 PURE S1 S2 S3 S4 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 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 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
Sort by: Default | Easiest first | Hardest first
Edexcel D1 2021 June Q2
10 marks Moderate -0.8
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-03_734_1361_237_360} \captionsetup{labelformat=empty} \caption{Figure 1}
\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.)
Edexcel D1 2021 June Q3
6 marks Standard +0.3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-04_997_1155_223_456} \captionsetup{labelformat=empty} \caption{Figure 2}
\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.
Edexcel D1 2021 June Q4
13 marks Moderate -0.3
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-05_618_1105_237_479} \captionsetup{labelformat=empty} \caption{Figure 3
[0pt] [The total weight of the network is 291]}
\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.
Edexcel D1 2021 June Q5
10 marks Moderate -0.3
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-06_965_1290_237_390} \captionsetup{labelformat=empty} \caption{Figure 4}
\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 .
Edexcel D1 2021 June Q6
9 marks Moderate -0.8
6.
ActivityImmediately preceding activities
A-
B-
C-
DA
EA
FA, B, C
GC
HG
ID, E, F, H
JI
KI
LI
ML
  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)
Edexcel D1 2021 June Q17
Moderate -0.8
17
25
31
15
11
46
17
27
-
15
47
E
32
F
35
G
-
} &
\hline & & & & & & & &
\hline
ABCDEFG
A-2117253141
B21-2627121520
C26-171146
D1727-1547
E25121715-632
F3115116-35
G412046473235-
\includegraphics[max width=\textwidth, alt={}]{44ddb176-e265-4545-b438-c1b5ffb40852-22_2646_1840_116_114}
6.
7. \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\)Leave blank\includegraphics[max width=\textwidth, alt={}]{44ddb176-e265-4545-b438-c1b5ffb40852-26_2652_103_115_1955}
\includegraphics[max width=\textwidth, alt={}]{44ddb176-e265-4545-b438-c1b5ffb40852-28_2647_1835_118_116}
Edexcel D1 2022 June Q1
9 marks Easy -1.8
  1. \(\quad \begin{array} { l l l l l l l l l l } 175 & 135 & 210 & 105 & 100 & 150 & 60 & 20 & 70 & 125 \end{array}\)
The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300 kg .
  1. Calculate a lower bound for the number of trucks that will be needed to transport the crates.
  2. Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each pass.
  3. Use the first-fit decreasing bin packing algorithm to allocate the crates to the trucks.
Edexcel D1 2022 June Q2
11 marks Standard +0.3
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-03_977_1537_205_264} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} The network in Figure 1 shows the activities that need to be undertaken to complete 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 and late event times are to be shown at each vertex and some have been completed. Given that
  • CHN is the critical path for the project
  • the total float on activity B is twice the duration of the total float on activity I
    1. find the value of \(x\) and show that the value of \(y\) is 7
    2. Calculate the missing early event times and late event times and hence complete Diagram 1 in your answer book.
Each activity requires one worker, and the project must be completed in the shortest possible time.
  • Draw a cascade chart for this project on Grid 1 in your answer book, and use it 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.
    •
    Edexcel D1 2022 June Q3
    14 marks Easy -1.2
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-04_876_1166_219_452} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} The network in Figure 2 shows the distances, in miles, between ten towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { H }\), \(\mathrm { L } , \mathrm { M } , \mathrm { P } , \mathrm { S } , \mathrm { W }\) and Y .
    1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
      (3)
      ABCHLMPSWY
      A-61815542916262974
      B6-2221603510323380
      C1822-17593112441180
      H152117-421429412863
      L54605942-4070286121
      M2935311440-43552161
      P161012297043-422390
      S26324441285542-5548
      W2933112861212355-82
      Y748080632161904882-
      The table shows the shortest distances, in miles, between the ten towns.
    2. Use Prim's algorithm on the table, starting at A, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
    3. State the weight of the minimum spanning tree found in (b). Sharon needs to visit all of the towns, starting and finishing in the same town, and wishes to minimise the total distance she travels.
    4. Use your answer to (c) to calculate an initial upper bound for the length of Sharon's route.
    5. Use the nearest neighbour algorithm on the table, starting at W , to find an upper bound for the length of Sharon's route. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at Y , an upper bound of length 212 miles was found.
    6. State the best upper bound that can be obtained by using this information and your answers from (d) and (e). Give the reason for your answer.
    7. By deleting W and all of its arcs, find a lower bound for the length of Sharon's route. Sharon decides to take the route found in (e).
    8. Interpret this route in terms of the actual towns visited.
    Edexcel D1 2022 June Q4
    7 marks Standard +0.8
    4. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = - x + y\) subject to $$\begin{gathered} x + 2 y + z \leqslant 15 \\ 3 x - 4 y + 2 z \geqslant 1 \\ 2 x + y + z = 14 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$
      1. Eliminate \(z\) from the first two inequality constraints, simplifying your answers.
      2. Hence state the maximum possible value of \(P\) Given that \(P\) takes the maximum possible value found in (a)(ii),
      1. determine the maximum possible value of \(x\)
      2. Hence find a solution to the linear programming problem.
    Edexcel D1 2022 June Q5
    9 marks Moderate -0.8
    5. The precedence table shows the eleven activities required to complete a project.
    ActivityImmediately preceding activities
    A-
    B-
    C-
    DA, B
    EA, B
    FB, C
    GB, C
    HD
    ID, E, F, G
    JH, I
    KD, E, F
    1. Draw the activity network for the project, using activity on arc and the minimum number of dummies.
      (5) \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-07_314_1385_1464_347} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} Figure 3 shows a schedule for the project. Each of the activities shown in the precedence table requires one worker. The time taken to complete each activity is in hours and the project is to be completed in the minimum possible time.
      1. State the minimum completion time for the project.
      2. State the critical activities.
      3. State the total float on activity G and the total float on activity K .
        (4)
    Edexcel D1 2022 June Q6
    15 marks Challenging +1.2
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-08_832_1171_169_445} \captionsetup{labelformat=empty} \caption{Figure 4}
    \end{figure} [The total weight of the network is \(383 + x\) ]
    Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\), H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible. The time taken to travel between towns G and J is unknown and is denoted by \(x\) minutes. Dijkstra's algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the "Order of labelling" and "Final value" at A and J, and the "Working values" at J , have already been completed.
    1. Use Dijkstra's algorithm to find the fastest time to travel from A to H . State the quickest route. Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A . It is given that his route will take at least 440 minutes.
    2. Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of \(x\).
    3. Write down a possible route for Ezra. A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A . It is given that this inspection route takes exactly 488 minutes.
    4. Determine the value of \(x\). You must give reasons for your answer.
    Edexcel D1 2022 June Q7
    10 marks Standard +0.3
    7. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-09_956_1290_212_383} \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 equations of two of the lines and the three intersection points, \(A\), \(B\) and \(C\), are shown. The coordinates of \(C\) are \(\left( \frac { 35 } { 4 } , \frac { 15 } { 4 } \right)\) The objective function is \(P = x + 3 y\) When the objective is to maximise \(x + 3 y\), the value of \(P\) is 24
    When the objective is to minimise \(x + 3 y\), the value of \(P\) is 10
      1. Find the coordinates of \(A\) and \(B\).
      2. Determine the inequalities that define \(R\). An additional constraint, \(y \geqslant k x\), where \(k\) is a positive constant, is added to the linear programming problem.
    2. Determine the greatest value of \(k\) for which this additional constraint does not affect the feasible region.
    Edexcel D1 2023 June Q1
    10 marks Moderate -0.3
    1. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{89702b66-cefb-484b-9c04-dd2be4fe2250-02_750_1321_342_372} \captionsetup{labelformat=empty} \caption{Figure 1}
    \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 days, to complete the activity. Each activity requires exactly 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. Calculate the maximum number of days by which activity H could be delayed without lengthening the completion time of the project. You must make the numbers used in your calculation clear.
    3. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
    4. Schedule the activities on Grid 1 in the answer book, using the minimum number of workers, so that the project is completed in the minimum time.
    Edexcel D1 2023 June Q2
    6 marks Easy -1.8
    2. A list of eleven numbers is to be sorted into descending order. After one pass, the quick sort algorithm produces the following list $$\begin{array} { l l l l l l l l l l l } 17 & 33 & 14 & 25 & 23 & 28 & 21 & 13 & 9 & 6 & 10 \end{array}$$
    1. State, with a reason, which number was used as a pivot for the first pass.
    2. Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
    3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85
    Edexcel D1 2023 June Q3
    6 marks Easy -1.8
    3. In this question, the function \(\operatorname { INT } ( X )\) is the largest integer less than or equal to \(X\). For example, $$\begin{aligned} \mathrm { INT } ( 5.7 ) & = 5 \\ \mathrm { INT } ( 8 ) & = 8 \\ \mathrm { INT } ( - 2.3 ) & = - 3 \end{aligned}$$ Consider the following algorithm.
    Step 1 Input \(N\) Step 2 Calculate \(A = N \div 10\) Step 3 Let \(B = \operatorname { INT } ( A )\) Step 4 Calculate \(C = B \times 10\) Step 5 Calculate \(D = N - C\) Step 6 Output \(D\) Step \(7 \quad\) Replace \(N\) by \(B\) Step 8 If \(N = 0\) then STOP, otherwise go back to Step 2
    1. Complete the table in the answer book, using \(N = 4217\), to show the results obtained at each step of the algorithm.
    2. Explain how the output values of the algorithm relate to the original input \(N\), where \(N\) is any positive integer.
    Edexcel D1 2023 June Q4
    11 marks Standard +0.3
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{89702b66-cefb-484b-9c04-dd2be4fe2250-05_1524_1360_203_356} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} Figure 2 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The equations of two of the lines are shown on the graph.
    1. Determine the inequalities that define the feasible region.
    2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = 2 x + k y\)
    3. For the case \(k = 3\), use the point testing method to find the optimal vertex of the feasible region and state the corresponding value of \(P\).
    4. Determine the range of values for \(k\) for which the optimal vertex found in (c) is still optimal.
    Edexcel D1 2023 June Q5
    7 marks Moderate -0.3
    5.
    ActivityImmediately preceding activities
    A-
    B-
    C-
    DA
    EA
    FB, C, E
    GB, C, E
    HC
    IC
    JD, F, G, H, I
    KD, F, G, H, I
    LI
    1. Draw the activity network described in the precedence table above, using activity on arc and the minimum number of dummies. A project is modelled by the activity network drawn in (a). Each activity requires exactly one worker. The project is to be completed in the shortest possible time. The table below gives the time, in hours, to complete three of the activities.
      ActivityDuration (in hours)
      A10
      E7
      F8
      The length of the critical path AEFK is 33 hours.
    2. Determine the range of possible values for the duration of activity J. You must make your method and working clear.
    Edexcel D1 2023 June Q6
    13 marks Challenging +1.2
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{89702b66-cefb-484b-9c04-dd2be4fe2250-07_688_1351_203_356} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} [The total weight of the network is 315]
    Figure 3 represents a network of roads between nine parks, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in miles, of the corresponding road.
      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 . The roads between the parks need to be inspected. Robin must travel along each road at least once. Robin wishes to minimise the length of the inspection route. Robin will start the inspection route at C and finish at E .
    2. By considering the pairings of all relevant nodes, find the length of Robin's route.
    3. State the number of times Robin will pass through G . It is now decided to start and finish the inspection route at A. Robin must still minimise the length of the route and travel along each road at least once.
    4. Calculate the difference between the lengths of the two inspection routes.
    5. State the edges that need to be traversed twice in the route that starts and finishes at A , but do not need to be traversed twice in the route that starts at C and finishes at E .
    Edexcel D1 2023 June Q7
    12 marks Standard +0.3
    7.
    ABCDEFGH
    A-3837\(x\)37424127
    B38-263233383734
    C3726-3938393039
    D\(x\)3239-37362936
    E37333837-323330
    F4238393632-3128
    G413730293331-33
    H27343936302833-
    The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H. A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is \(x \mathrm {~km}\) where \(32 \leqslant x \leqslant 35\)
    1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
    2. Use your answer to (a) to determine an initial upper bound for the length of the tourist's route.
    3. Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist's route. Write down the route that gives this upper bound. The nearest neighbour algorithm starting at E gives a route of $$\mathrm { E } - \mathrm { H } - \mathrm { A } - \mathrm { D } - \mathrm { G } - \mathrm { C } - \mathrm { B } - \mathrm { F } - \mathrm { E }$$
    4. State which of these two nearest neighbour routes gives the better upper bound. Give reasons for your answer. Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
    5. Determine the smallest interval that must contain the optimal length of the tourist's route. You must make your method and working clear.
    Edexcel D1 2023 June Q8
    10 marks Challenging +1.2
    8. A headteacher is deciding how to allocate prizes to the students who are leaving at the end of the school year. There are three categories of prize: academic, sport, and leadership.
    • Each academic prize costs \(\pounds 14\), each sport prize costs \(\pounds 8\), and each leadership prize costs \(\pounds 12\). The total amount available to spend on all prizes is \(\pounds 976\)
    • For every 5 academic prizes there must be at least 2 leadership prizes
    • At least half the prizes must be academic
    • \(20 \%\) of the prizes must be for sport
    The headteacher wishes to maximise the total number of prizes.
    Let \(x , y\) and \(z\) represent the number of academic, sport and leadership prizes respectively.
    1. Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective and listing the constraints as simplified inequalities with integer coefficients. Given that the headteacher awards 16 sport prizes,
    2. calculate the corresponding number of leadership prizes that the headteacher awards. You must show your working.
    Edexcel D1 2024 June Q1
    14 marks Easy -1.2
    1.
    5.24.76.54.53.15.11.82.93.43.81.2
    1. Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14
    2. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
    3. Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14
    4. Explain why the number of bins used in part (c) is optimal.
    5. Use the binary search algorithm to try to locate 3.0 in the list of numbers. Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.
    Edexcel D1 2024 June Q2
    10 marks Standard +0.3
    2. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-03_942_1587_242_239} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure} [The sum of the durations of all the activities is 59 days.]
    The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in days, of the corresponding activity is shown in brackets. 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. State the minimum completion time of the project.
    2. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
    3. Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.
    Edexcel D1 2024 June Q3
    8 marks Easy -1.2
    3. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-04_994_1616_242_223} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure} Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.
    1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route.
      (6)
    2. Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer. You do not need to find the minimum spanning tree.
    Edexcel D1 2024 June Q4
    14 marks Moderate -0.5
    4. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-06_873_1620_242_223} \captionsetup{labelformat=empty} \caption{Figure 3}
    \end{figure} [The total weight of the network is 494]
    Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3. The number on each arc represents the lengths, in kilometres, of the corresponding road.
    The table below shows the shortest distances, in kilometres, between the nine factories.
    ABCDEFGHJ
    A-157251542645146
    B15-22403057493631
    C722-322249715853
    D254032-1017577071
    E15302210-27676661
    F4257491727-405372
    G644971576740-1332
    H51365870665313-19
    J4631537161723219-
    \section*{Table of shortest distances}
    1. Starting at A, use Prim's algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.
      (3)
    2. State the weight of the minimum spanning tree.
      (1) A route is needed that minimises the total distance to traverse each road at least once. The route must start at E and finish at F .
    3. Determine the length of this route. You must give a reason for your answer. It is now decided to start the route at C and finish the route at A . The route must include every road at least once and must still minimise the total distance travelled.
    4. By considering the pairings of all relevant nodes, find the roads that need to be traversed twice. Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.
    5. Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko's route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.
    6. By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko's route.