Questions — Edexcel D1 (480 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 D1 Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-02_629_700_196_443} \captionsetup{labelformat=empty} \caption{Fig 1}
\end{figure}
  1. Find a Hamiltonian cycle for the graph shown in Figure 1.
  2. Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
    (5 marks)
Edexcel D1 Q2
2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.
Edexcel D1 Q3
3. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-03_744_1524_319_315} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows an activity network. The nodes represent events and the arcs represent the activities. The number in each bracket gives the time, in days, needed to complete the activity.
  1. Calculate the early and late times for each event using appropriate forward and backward scanning.
    (5 marks)
  2. Hence, determine the activities which lie on the critical path.
  3. State the minimum number of days needed to complete the entire project.
Edexcel D1 Q4
4. This question should be answered on the sheet provided. The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.
NameActivities
FatimaWindsurfing, Sailing
GavinClimbing, Orienteering
HassanWindsurfing, Climbing
IainSailing, Diving
JaneDiving, Sailing, Orienteering
  1. Draw a bipartite graph to model this situation. Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
  2. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.
    (6 marks)
Edexcel D1 Q5
5. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-05_834_1436_306_280} \captionsetup{labelformat=empty} \caption{Fig. 3}
\end{figure} Figure 3 shows a weighted network. The number on each arc indicates the weight of that arc.
  1. Use Dijkstra's algorithm to find a path of least weight from \(A\) to \(J\) and state the weight of the path. Your solution must show clearly how you have applied the algorithm including:
    1. the order in which the vertices were labelled,
    2. how you determined the path of least weight.
  2. Find if there are any other paths of least weight and explain your answer.
  3. Describe a practical problem that could be modelled by the above network.
Edexcel D1 Q6
6. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_723_1292_276_349} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure} Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
  1. Calculate the values of cut \(C _ { 1 }\) and \(C _ { 2 }\).
  2. Find the minimum cut and state its value.
    (2 marks) \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347} \captionsetup{labelformat=empty} \caption{Fig. 5}
    \end{figure} Figure 5 shows a feasible flow through the same network.
  3. State the values of \(x , y\) and \(z\).
  4. Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow. State how you know that you have found a maximal flow.
    (8 marks)
Edexcel D1 Q7
7. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that a maximum combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.
  1. Model this as a linear programming problem simplifying your expressions so that they have integer coefficients.
    (4 marks)
  2. Show that the initial tableau, when using the simplex algorithm, can be written as:
    Basic Variable\(x\)\(y\)\(z\)\(s\)\(t\)\(u\)Value
    \(s\)12410020
    \(t\)431401075
    \(u\)521000160
    \(R\)\({ } ^ { - } 10\)\({ } ^ { - } 12\)\({ } ^ { - } 8\)0000
  3. Explain the purpose of the variables \(s\), \(t\) and \(u\).
  4. By increasing the value of \(y\) first, work out the next two complete tableaus.
  5. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms. Sheet for answering question 3
    NAME \section*{Please hand this sheet in for marking}

  8. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
    \section*{Please hand this sheet in for marking}
  9. \(F \quad \bullet\)
    • \(W\)
      \(G \quad \bullet\)
    • \(S\)
    H •
    • \(C\)
    I •
    • \(O\)
    J •
    • \(D\)
    • Initial matching:
      \(\begin{array} { l l l l } F & \bullet & \bullet & W
      G & \bullet & \bullet & S
      H & \bullet & \bullet & C
      I & \bullet & \bullet & O
      J & \bullet & \bullet & D \end{array}\) \(\_\_\_\_\)
    Complete matching:
    F •
    • \(W\)
      \(G \quad \bullet\)
    • \(S\)
      H •
    • \(C\)
      I •
    • \(O\)
      J •
    • \(D\)
    \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking}
    \includegraphics[max width=\textwidth, alt={}]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-10_2398_643_248_1224}
    Sheet for answering question 6
    NAME \section*{Please hand this sheet in for marking}
  10. \(\_\_\_\_\)
  11. \(\_\_\_\_\)
  12. \(\_\_\_\_\)

  13. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-11_592_1292_1078_312}
    Sheet for answering question 6 (cont.)
    \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_595_1299_351_312}
    \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_597_1298_1409_308}
Edexcel D1 Q1
  1. This question should be answered on the sheet provided.
A College wants to connect the computerised registration equipment at its six sites, \(A\) to \(F\). The table below shows the cost, in pounds, of connecting any two of the sites.
ABCD\(E\)\(F\)
A-130190155140125
B130-215200190170
C190215-110180100
D155200110-7045
E14019018070-75
F1251701004575-
Starting at \(D\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. Hence, state the lowest cost of connecting all the sites.
(5 marks)
Edexcel D1 Q2
2. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-03_1239_1442_306_283} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} The data $$x _ { 1 } = 8 , \quad x _ { 2 } = 2 , \quad x _ { 3 } = 4 , \quad x _ { 4 } = 3 , \quad x _ { 5 } = 5 , \quad x _ { 6 } = 1 , \quad x _ { 7 } = 7 ,$$ is to be used in the algorithm given in Figure 1.
  1. Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output using the given data.
  2. Explain what the algorithm achieves for any set of data \(x _ { 1 }\) to \(x _ { n }\).
Edexcel D1 Q3
3. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-04_883_1317_317_315} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.
  1. Find the values of \(x\) and \(y\).
    1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
    2. Show your maximum flow pattern and state its value.
    1. Find a minimum cut, listing the arcs through which it passes.
    2. Explain why this proves that the flow found in part (b) is a maximum.
      (2 marks)
Edexcel D1 Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-05_501_493_196_529} \captionsetup{labelformat=empty} \caption{Fig. 3}
\end{figure} Figure 3 shows the graph \(K _ { 4 }\).
  1. State the features of the graph that identify it as \(K _ { 4 }\).
  2. In \(K _ { 4 }\), the Hamiltonian cycles \(A B C D A , B C D A B , C D A B C\) and \(D A B C D\) are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
    1. \(\quad K _ { 4 }\),
    2. \(K _ { 5 }\),
    3. \(K _ { 10 }\).
  3. In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.
Edexcel D1 Q5
5. A clothes manufacturer has a trademark "VE" which it wants to embroider on all its garments. The stitching must be done continuously but stitching along the same line twice is allowed. Logo 1:
\includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_524_1338_495_296} Logo 2: \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_531_1342_1155_299} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure} The weighted networks in Figure 4 represent two possible Logos.
The weights denote lengths in millimetres.
  1. Calculate the shortest length of stitch required to embroider Logo 1 .
  2. Calculate the shortest length of stitch required to embroider Logo 2.
  3. Hence, determine the difference in the length of stitching required for the two Logos.
Edexcel D1 Q6
6. A company makes lighting sets to be sold to stores for use during the Christmas period. As the product is only required at this time of year, all manufacturing takes place during September, October and November. The sets are delivered to stores at the end of each of these months. Any sets that have been made but do not need to be delivered at the end of each of September and October are put into storage which the company must pay for. Let \(x , y\) and \(z\) be the number of sets manufactured in September, October and November respectively. The demand for lighting sets and the relevant costs are shown in the table below.
MonthSeptemberOctoberNovember
Manufacturing costs per set during each month (£)500800600
Demand for sets at the end of each month8001000700
Cost of storing sets during each month ( £ )-100150
The company must be able to meet the demand at the end of each month and there must be no unsold articles at the end of November.
    1. Express \(z\) in terms of \(x\) and \(y\).
    2. Hence, find an expression for the total costs incurred in terms of \(x\) and \(y\). The company wishes to minimise its total costs by modelling this situation as a linear programming problem.
  2. Find as inequalities the constraints that apply in addition to \(x \geq 800\) and \(y \geq 0\).
    (2 marks)
  3. On graph paper, illustrate these inequalities and label clearly the feasible region.
    (4 marks)
  4. Use your graph to solve the problem. You must state how many sets should be produced in each month and the total costs incurred by the company.
    (3 marks)
Edexcel D1 Q7
7. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-08_586_1372_333_303} \captionsetup{labelformat=empty} \caption{Fig. 5}
\end{figure} The activity network in Figure 5 models the work involved in laying the foundations and putting in services for an industrial complex. The activities are represented by the arcs and the numbers in brackets give the time, in days, to complete each activity. Activity \(C\) is a dummy.
  1. Execute a forward scan to calculate the early times and a backward scan to calculate the late times, for each event.
  2. Determine which activities lie on the critical path and list them in order.
  3. State the minimum length of time needed to complete the project. The contractor is committed to completing the project in this minimum time and faces a penalty of \(\pounds 50000\) for each day that the project is late. Unfortunately, before any work has begun, flooding means that activity \(F\) will take 3 days longer than the 7 days allocated.
  4. Activity \(N\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
    (3 marks)
  5. If the time taken to complete any one activity, other than \(F\), could be reduced by 2 days at an extra cost of \(\pounds 80000\), for which activities on their own would this be profitable. Explain your reasoning.
    (3 marks) END \section*{Please hand this sheet in for marking}
    ABCDE\(F\)
    A-130190155140125
    B130-215200190170
    C190215-110180100
    D155200110-7045
    E14019018070-75
    \(F\)1251701004575-
    \section*{Please hand this sheet in for marking}
  6. \(n\)\(x _ { n }\)\(а\)Any more data?\(x _ { n + 1 }\)\(b\)\(( b - a ) > 0\) ?\(a\)
    188Yes22No2
    2--
    Final output
  7. \(\_\_\_\_\)
    Sheet for answering question 3
    NAME \section*{Please hand this sheet in for marking}

    1. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_716_1218_502_331}

    2. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-11_709_1214_1498_333} Maximum flow =
    1. \(\_\_\_\_\)
    2. \(\_\_\_\_\)
      \section*{Please hand this sheet in for marking}

  11. \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
  12. \(\_\_\_\_\)
  13. \(\_\_\_\_\)
  14. \(\_\_\_\_\)
  15. \(\_\_\_\_\)
Edexcel D1 Q1
  1. (a) Draw the complete graph \(K _ { 5 }\).
    (b) Demonstrate that no planar drawing is possible for \(K _ { 5 }\).
    (c) Draw the complete graph \(K _ { 3,3 }\).
    (d) Demonstrate that no planar drawing is possible for \(K _ { 3,3 }\).
  2. A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.
ActivityDepends onDuration (hours)
A-5
BA4
CA2
DB, C11
EC4
\(F\)D3
\(G\)D8
\(H\)D, E2
I\(F\)1
J\(F , G , H\)7
\(K\)\(I , J\)2
Draw an activity network for the project. You should number the nodes and use as few dummies as possible.
(7 marks)
Edexcel D1 Q3
3. A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$\begin{array} { l l l l l l l } 150 & 104 & 200 & 60 & 184 & 84 & 120 \end{array}$$
  1. Perform a quick sort to put the seven lengths in descending order. The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
  2. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed.
    (4 marks)
  3. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods.
    (1 mark)
Edexcel D1 Q4
4. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{64203218-06e8-46f8-8aa9-7841ee2096c8-03_807_1402_1201_278} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Figure 1 above shows distances in miles between 10 cities.
Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:
  1. the order in which you labelled the vertices,
  2. how you used your labelled diagram to find the shortest route.
Edexcel D1 Q5
5. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{64203218-06e8-46f8-8aa9-7841ee2096c8-04_794_1315_280_296} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.
  1. Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected.
    (4 marks)
  2. It is decided that a Greek translation is not needed. Find the minimum cost if:
    1. translations to and from Greek are not available,
    2. translations to and from Greek are still available.
  3. Comment on your findings. Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.
  4. How would you overcome the problem of having different costs for reverse translations?
  5. What algorithm would be suitable to find a computerised solution.
  6. State another assumption you have made in answering this question and comment on its validity.
    (2 marks) \section*{6. This question should be answered on the sheet provided.} There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.
    ComputerApplications
    EAnimation
    FOffice, Data
    GSimulation
    HAnimation, Office
    IData, CAD, Simulation
Edexcel D1 Q7
7. An engineer makes three components \(X , Y\) and \(Z\). Relevant details are as follows: Component \(X\) requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component \(Y\) requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component \(Z\) requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components \(X , Y\) and \(Z\) are \(\pounds 40 , \pounds 90\) and \(\pounds 60\) respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components \(X , Y\) and \(Z\) the engineer makes each day be \(x , y\) and \(z\) respectively.
  1. Write down the 3 inequalities that apply in addition to \(x \geq 0 , y \geq 0\) and \(z \geq 0\).
  2. Explain why it is not appropriate to use a graphical method to solve the problem. It is decided to use the simplex algorithm to solve the problem.
  3. Show that a possible initial tableau is: Workings:
  4. Workings:
    \(E\)\(\bullet\)\(\bullet\)\(O\)
    \(F\)\(\bullet\)\(\bullet\)\(D\)
    \(G\)\(\bullet\)\(\bullet\)\(C\)
    \(H\)\(\bullet\)\(\bullet\)\(A\)
    \(I\)\(\bullet\)\(\bullet\)\(S\)
    Alternative matching:
    \(E\)\(\bullet\)\(\bullet\)\(O\)
    \(F\)\(\bullet\)\(\bullet\)\(D\)
    \(G\)\(\bullet\)\(\bullet\)\(C\)
    \(H\)\(\bullet\)\(\bullet\)\(A\)
    \(I\)\(\bullet\)\(\bullet\)\(S\)
Edexcel D1 Q1
  1. This question should be answered on the sheet provided.
A cable TV company wishes to link 5 villages in the Scottish Highlands. The table below shows the shortest distances, in kilometres, between these 5 villages.
DurnessHelmsdaleInvernessThursoWick
Durness-681238192
Helmsdale68-1027264
Inverness123102-148127
Thurso8172148-48
Wick926412748-
  1. Starting at Thurso, use Prim's algorithm to find a minimum spanning tree. You should make your method clear, indicating the order in which you selected the arcs in your final tree.
  2. Calculate the minimum total length of cable required.
Edexcel D1 Q2
2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.
  1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
  2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.
Edexcel D1 Q3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-03_734_1353_196_317} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Figure 1 shows a graph in which \(y \geq 0\).
Given that the graph is a weighted network,
  1. find the range of values for the path of lowest weight from \(S\) to \(T\). Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
  2. find the range of values for the maximum flow from \(S\) to \(T\).
  3. Give an example of a practical problem which could be solved by using:
    1. the weighted network in part (a),
    2. the capacitated network in part (b).
Edexcel D1 Q4
4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.
MinisterGovernment Position
\(P\)Chancellor ( \(C\) )
\(Q\)Foreign Secretary ( \(F\) ), Minister for Education ( \(E\) )
\(R\)Minister for Defence ( \(D\) ), Minister for Industry ( \(I\) )
SMinister for Defence ( \(D\) ), Home Secretary ( \(H\) )
\(T\)Home Secretary (H)
\(U\)Chancellor ( \(C\) ), Foreign Secretary ( \(F\) )
  1. Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
  2. Draw this initial matching.
  3. Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
  4. Explain why no complete matching is now possible.
    (2 marks)
Edexcel D1 Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-05_863_1061_223_360} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} The network in Figure 2 represents the streets near Randolph Square in Newtown, Edinburgh. The weightings represent the average time, in seconds, taken to travel along each road in either direction. The large values for the roads \(C D\) and \(J L\) are due to traffic lights. In the course of his work, a van driver must travel along each road at least once each day. He starts and finishes at his depot, \(F\), and wishes to minimise the total time that this takes.
  1. Describe an appropriate algorithm that can be used to find this minimum time.
    (3 marks)
  2. Apply this algorithm to find a route that the driver can take and state the total time he can expect to spend on this journey each day.
    (5 marks)
    The section of road \(A B\) is to be turned into a pedestrian precinct.
  3. Assuming that the driver must still travel along all the other roads at least once each day, find the modified time he can expect to spend on his daily journey Comment on your answer.
    (3 marks) Turn over
Edexcel D1 Q6
6. The table below shows the maximum flows possible within a system.
To From\(S\)\(A\)\(B\)\(C\)D\(T\)
S-353055--
A-----50
B-12-8-20
C----1530
D-----14
T------
For example, the maximum flow from \(B\) to \(A\) is 12 units.
  1. Draw a digraph to represent this information.
  2. Give the capacity of the cut \(\{ S , A , B , C \} \mid \{ D , T \}\).
  3. Find the minimum cut, stating its capacity, and expressing it in the form \(\{ \quad \} \mid \{ \quad \}\).
  4. Use the labelling procedure to find the maximum flow from \(S\) to \(T\). You should list each flow-augmenting route you find together with its flow.
  5. Explain how you know that you have found the maximum possible flow.
  6. Give an example of a practical situation that could be modelled by the original table.