Questions (33218 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
OCR MEI D1 2015 June Q4
16 marks Standard +0.3
4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.
ABCDEF
A32783
B345
C246
D75
E862
F32
  1. Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
  2. Jack wants to find a minimum spanning tree for the network.
    1. Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length. Jill suggests the following algorithm is easier.
      Step 1 Remove an arc of longest length which does not disconnect the network
      Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1
      Step 3 Stop
    2. Show the order in which arcs are removed when Jill's algorithm is applied to the network.
    3. Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
    4. In a complete network on \(n\) vertices there are \(\frac { n ( n - 1 ) } { 2 }\) arcs. There are \(n - 1\) arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm? For what values of \(n\) does Jill have more arcs to remove than Prim has to include?
OCR MEI D1 2015 June Q5
16 marks Moderate -0.3
5 The table lists activities which are involved in framing a picture. The table also lists their durations and their immediate predecessors. Except for activities C and H, each activity is undertaken by one person. Activities C and H require no people.
ActivityDuration (mins)Immediate predecessor(s)
Aselect mounting5-
Bglue picture to mounting5A
Callow mounting glue to dry20B
Dmeasure for frame5A
Eselect type of frame10A
Fcut four frame pieces5D, E
Gpin and glue frame pieces together5F
Hallow frame glue to dry20G
Icut and bevel glass30D
Jfit glass to frame5H, I
Kfit mounted picture to frame5C, J
  1. Draw an activity on arc network for these activities.
  2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. A picture is to be framed as quickly as possible. Two people are available to do the job.
  3. Produce a schedule to show how two people can complete the picture framing in the minimum time. To reduce the completion time an instant glue is to be used. This will reduce the time for activities C and H to 0 minutes.
  4. Produce a schedule for two people to complete the framing in the new minimum completion time, and give that time.
OCR MEI D1 2015 June Q6
16 marks Moderate -0.8
6 Adrian and Kleo like to go out for meals, sometimes to a French restaurant, and sometimes to a Greek restaurant. If their last meal out was at the French restaurant, then the probability of their next meal out being at the Greek restaurant is 0.7 , whilst the probability of it being at the French restaurant is 0.3 . If their last meal out was at the Greek restaurant, then the probability of their next meal out being at the French restaurant is 0.6 , whilst the probability of it being at the Greek restaurant is 0.4 .
  1. Construct two simulation rules, each using single-digit random numbers, to model their choices of where to eat.
  2. Their last meal out was at the Greek restaurant. Use the random digits printed in your answer book to simulate their choices for the next 10 of their meals out. Hence estimate the proportion of their meals out which are at the French restaurant, and the proportion which are at the Greek restaurant. Adrian and Kleo find a Hungarian restaurant which they like. The probabilities of where they eat next are now given in the following table.
    \backslashbox{last meal out}{next meal out}FrenchGreekHungarian
    French\(\frac { 1 } { 5 }\)\(\frac { 3 } { 5 }\)\(\frac { 1 } { 5 }\)
    Greek\(\frac { 1 } { 2 }\)\(\frac { 3 } { 10 }\)\(\frac { 1 } { 5 }\)
    Hungarian\(\frac { 1 } { 3 }\)\(\frac { 1 } { 3 }\)\(\frac { 1 } { 3 }\)
  3. Construct simulation rules, each using single-digit random numbers, to model this new situation.
  4. Their last meal out was at the Greek restaurant. Use the random digits printed in your answer book to simulate their choices for the next 10 of their meals out. Hence estimate the proportion of their meals out which are at each restaurant. \section*{END OF QUESTION PAPER}
OCR MEI D1 2016 June Q1
8 marks Moderate -0.8
1 Pierre knows that, if he gambles, he will lose money in the long run. Nicolas tries to convince him that this is not the case. Pierre stakes a sum of money in a casino game. If he wins then he gets back his stake plus the same amount again. If he loses then he loses his stake. Nicolas says that Pierre can guarantee to win by repeatedly playing the game, even though the probability of winning an individual game is less than 0.5 . His idea is that Pierre should bet in the first game with a stake of \(\pounds 100\). If he wins then he stops, as he will have won \(\pounds 100\). If he loses then he plays again with a stake of \(\pounds 200\). If he wins then he has lost \(\pounds 100\) and won \(\pounds 200\). This gives a total gain of \(\pounds 100\), and he stops. If he loses then he plays again with a stake of \(\pounds 400\). If he wins this time he has lost \(\pounds 100\) and \(\pounds 200\) and won \(\pounds 400\). This gives a total gain of \(\pounds 100\), and he stops. Nicolas's advice is that Pierre simply has to continue in this way, doubling his stake every time that he loses, until he eventually wins. Nicolas says that this guarantees that Pierre will win \(\pounds 100\). You are to simulate what might happen if Pierre tries this strategy in a casino game in which the probability of him winning an individual game is 0.4 , and in which he has \(\pounds 1000\) available.
  1. Give an efficient rule for using 1-digit random numbers to simulate the outcomes of individual games, given that the probability of Pierre winning an individual game is 0.4 .
  2. Explain why at most three random digits are needed for one simulation of Nicolas's strategy, given that Pierre is starting with \(\pounds 1000\).
  3. Simulate five applications of Nicolas's strategy, using the five sets of three 1-digit random numbers in your answer book.
  4. Summarise the results of your simulations, giving your mean result.
OCR MEI D1 2016 June Q2
8 marks Moderate -0.8
2 A bag contains 26 cards. A different letter of the alphabet is written on each one. A card is chosen at random and its letter is written down. The card is returned to the bag. The bag is shaken and the process is repeated several times. Tania wants to investigate the probability of a letter appearing twice. She wants to know how many cards need to be chosen for this probability to exceed 0.5. Tania uses the following algorithm. Step 1 Set \(n = 1\) Step 2 Set \(p = 1\) Step 3 Set \(n = n + 1\) Step 4 Set \(p = p \times \left( \frac { 27 - n } { 26 } \right)\) Step 5 If \(p < 0.5\) then stop
Step 6 Go to Step 3
  1. Run the algorithm.
  2. Interpret your results. A well-known problem asks how many randomly-chosen people need to be assembled in a room before the probability of at least two of them sharing a birthday exceeds 0.5 (ignoring anyone born on 29 February).
  3. Modify Tania's algorithm to answer the birthday problem. (Do not attempt to run your modified algorithm.)
  4. Why have 29 February birthdays been excluded?
OCR MEI D1 2016 June Q3
8 marks Moderate -0.3
3 The adjacency graph of a cube \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.
  1. Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
  2. (A) Draw the adjacency graph for an octahedron, and draw its complement.
    (B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}
OCR MEI D1 2016 June Q4
16 marks Moderate -0.3
4 Two products are to be made from material that is supplied in a single roll, 20 m long and 1 m wide. The two products require widths of 47 cm and 32 cm respectively. Two ways of cutting lengths of material are shown in the plans below. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_408_1538_520_269} \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_403_1533_952_274}
  1. Given that there should be no unnecessary waste, draw one other cutting plan that might be used for a cut of length \(z\) metres.
  2. Write down an expression for the total area that is wasted in terms of \(x , y\) and \(z\). All of the roll is to be cut, so \(x + y + z = 20\).
    There needs to be a total length of at least 20 metres of the material for the first product, the one requiring width 47 cm .
  3. Write this as a linear constraint on the variables. There needs to be a total length of at least 24 metres of the material for the second product, the one requiring width 32 cm .
  4. Write this as a linear constraint on the variables.
  5. Formulate an LP in terms of \(x\) and \(y\) to minimise the area that is wasted. You will need to use the relationship \(x + y + z = 20\), together with your answers to parts (ii), (iii) and (iv).
  6. Solve your LP graphically, and interpret the solution.
OCR MEI D1 2016 June Q5
16 marks Moderate -0.8
5 A village amateur dramatic society is planning its annual pantomime. Three rooms in the village hall have been booked for one evening per week for 12 weeks. The following activities must take place. Their durations are shown.
ActivityDuration (weeks)
Achoose lead actors1
Bchoose rest of actors1
Cchoose dancers1
Drehearse lead actors8
Erehearse rest of actors6
Frehearse dancers6
Gprepare scenery6
Hinstall scenery1
Iprepare music2
Jmake costumes4
Kdress rehearsals2
Each activity needs a room except for activities G, I and J.
Choosing actors and dancers can be done in the same week. Rehearsals can begin after this. Rehearsing the dancers cannot begin until the music has been prepared. The scenery must be installed after rehearsals, but before dress rehearsals.
Making the costumes cannot start until after the actors and dancers have been chosen. Everything must be ready for the dress rehearsals in the final two weeks of the 12-week preparation period.
  1. Complete the table in your answer book by showing the immediate predecessors for each activity.
  2. Draw an activity on arc network for these activities.
  3. Mark on your network the early time and the late time for each event. Give the critical activities. It is discovered that there is a double booking and that one of the rooms will not be available after week 6.
  4. Using the space provided, produce a schedule showing how the pantomime can be ready in time for its first performance.
OCR MEI D1 2016 June Q6
16 marks Standard +0.3
6 A mountain ridge separates two populated areas. Networks representing roads connecting the villages in each area are shown below. The numbers on the arcs represent distances in kilometres. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-7_524_1429_340_319} There is also a mountain road of length 15 kilometres connecting C to Z .
  1. A national bus company needs a route from A to X .
    1. Use Dijkstra's algorithm on the complete network, including CZ, to find the shortest route from A to X . Give the route and its corresponding distance.
    2. Would it need fewer computations to use Dijkstra's algorithm on the network for villages A to F to find the shortest route from A to C, and then use Dijkstra's algorithm on the network for villages U to Z to find the shortest route from Z to X? Give a brief justification for your answer.
  2. The local council needs to discover which roads it should keep clear of snow during the winter to keep all the villages connected, and the corresponding total length of road.
    1. Use Kruskal's algorithm on the network for villages A to F to find a minimum connector for \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } \}\). Show your use of the algorithm. Draw your minimum connector.
    2. Use Prim's algorithm on the network for villages U to Z to find a minimum connector for \(\{ \mathrm { U } , \mathrm { V } , \mathrm { W } , \mathrm { X } , \mathrm { Y } , \mathrm { Z } \}\), starting at U . Show your use of the algorithm. Draw your minimum connector.
    3. What is the total length of road that the council must keep clear of snow?
Edexcel D1 Q1
7 marks Standard +0.3
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
8 marks Easy -1.3
2.
  1. 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.
  2. Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
  3. 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
8 marks Moderate -0.8
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
8 marks Moderate -0.8
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
12 marks Moderate -0.3
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
15 marks Standard +0.3
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
17 marks Moderate -0.3
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}
    3. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
      \section*{Please hand this sheet in for marking}
    4. \(F \quad \bullet\)
      H •
      I •
      J •
      Complete matching:
      F •
      \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}
    5. \(\_\_\_\_\)
    6. \(\_\_\_\_\)
    7. \(\_\_\_\_\)
    8. \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
5 marks Moderate -0.8
  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
7 marks Moderate -0.8
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
11 marks Standard +0.3
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
11 marks Moderate -0.8
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
11 marks Moderate -0.8
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
15 marks Standard +0.3
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
15 marks Moderate -0.3
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}
    1. \(n\)\(x _ { n }\)\(a\)Any more data?\(x _ { n + 1 }\)\(b\)\(( b - a ) > 0\) ?\(a\)
      188Yes22No2
      2--
      Final output
    2. \(\_\_\_\_\) 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}
      (a) \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-12_764_1612_402_255}
    6. \(\_\_\_\_\)
    7. \(\_\_\_\_\)
    8. \(\_\_\_\_\)
    9. \(\_\_\_\_\)
Edexcel D1 Q1
6 marks Moderate -0.8
  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
7 marks Moderate -0.8
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.