Questions D1 (932 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 2004 November Q3
8 marks Easy -1.2
3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.
123456
A\(\checkmark\)
B\(\checkmark\)\(\checkmark\)
C\(\checkmark\)\(\checkmark\)\(\checkmark\)
D\(\checkmark\)
E\(\checkmark\)\(\checkmark\)\(\checkmark\)
F\(\checkmark\)
  1. Show these possible allocations on the bipartite graph on the diagram in the answer book. A possible matching is
    A to 5,
    C to 1 ,
    E to 6,
    F to 4
  2. Show this information, in a distinctive way, on the diagram in the answer book.
    (1)
  3. Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
  4. Explain why it is not possible to find a complete matching.
Edexcel D1 2004 November Q4
8 marks Easy -1.8
4. \(45 , \quad 56 , \quad 37 , \quad 79 , \quad 46 , \quad 18 , \quad 90 , \quad 81 , \quad 51\)
  1. Using the quick sort algorithm, perform one complete iteration towards sorting these numbers into ascending order.
    (2)
  2. Using the bubble sort algorithm, perform one complete pass towards sorting the original list into descending order. Another list of numbers, in ascending order, is $$7 , \quad 23 , \quad 31 , \quad 37 , \quad 41 , \quad 44 , \quad 50 , \quad 62 , \quad 71 , \quad 73 , \quad 94$$
  3. Use the binary search algorithm to locate the number 73 in this list. \section*{5.} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-06_1246_1168_294_427}
    \end{figure} Figure 2 shows a network of roads connecting villages. The length of each road, in km, is shown. Village \(B\) has only a small footbridge over the river which runs through the village. It can be accessed by two roads, from \(A\) and \(D\). The driver of a snowplough, based at \(F\), is planning a route to enable her to clear all the roads of snow. The route should be of minimum length. Each road can be cleared by driving along it once. The snowplough cannot cross the footbridge. Showing all your working and using an appropriate algorithm,
Edexcel D1 2004 November Q8
17 marks Moderate -0.3
8. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-10_1042_1847_335_115}
\end{figure} The network in Figure 5 shows activities that need to be undertaken in order to complete a project. Each activity is represented by an arc. The number in brackets is the duration of the activity in hours. The early and late event times are shown at each node. The project can be completed in 24 hours.
  1. Find the values of \(x , y\) and \(z\).
  2. Explain the use of the dummy activity in Figure 5.
  3. List the critical activities.
  4. Explain what effect a delay of one hour to activity \(B\) would have on the time taken to complete the whole project. The company which is to undertake this project has only two full time workers available. The project must be completed in 24 hours and in order to achieve this, the company is prepared to hire additional workers at a cost of \(\pounds 28\) per hour. The company wishes to minimise the money spent on additional workers. Any worker can undertake any task and each task requires only one worker.
  5. Explain why the company will have to hire additional workers in order to complete the project in 24 hours.
  6. Schedule the tasks to workers so that the project is completed in 24 hours and at minimum cost to the company.
  7. State the minimum extra cost to the company.
Edexcel D1 2002 June Q4
10 marks Moderate -0.3
  1. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(I\). Show all necessary working in the boxes in the answer booklet and state your shortest route and its length.
    (5) The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at \(A\).
    1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
    2. Find a route of minimum length.
    3. Find the total length of this shortest route.
      (5)
Edexcel D1 2002 November Q4
7 marks Standard +0.3
  1. Use the Route Inspection algorithm to find which paths, if any, need to be traversed twice. It is decided to start the inspection at node \(C\). The inspection must still traverse each pipe at least once but may finish at any node.
  2. Explaining your reasoning briefly, determine the node at which the inspection should finish if the route is to be minimised. State the length of your route.
    (3)
Edexcel D1 2004 November Q5
10 marks Standard +0.3
  1. find the route the driver should follow, starting and ending at \(F\), to clear all the roads of snow. Give the length of this route. The local authority decides to build a road bridge over the river at \(B\). The snowplough will be able to cross the road bridge.
  2. Reapply the algorithm to find the minimum distance the snowplough will have to travel (ignore the length of the new bridge). \section*{6.} \section*{Figure 3}
    \includegraphics[max width=\textwidth, alt={}]{4bbe6272-3900-42de-b287-599638ca75e4-07_1131_1118_347_502}
    Peter wishes to minimise the time spent driving from his home \(H\), to a campsite at \(G\). Figure 3 shows a number of towns and the time, in minutes, taken to drive between them. The volume of traffic on the roads into \(G\) is variable, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x \geq 0\).
    1. On the diagram in the answer book, use Dijkstra's algorithm to find two routes from \(H\) to \(G\) (one via \(A\) and one via \(B\) ) that minimise the travelling time from \(H\) to \(G\). State the length of each route in terms of \(x\).
    2. Find the range of values of \(x\) for which Peter should follow the route via \(A\). \section*{7.} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-08_1495_1335_322_392}
      \end{figure} The company EXYCEL makes two types of battery, X and Y . Machinery, workforce and predicted sales determine the number of batteries EXYCEL make. The company decides to use a graphical method to find its optimal daily production of X and Y . The constraints are modelled in Figure 4 where $$\begin{aligned} & x = \text { the number (in thousands) of type } \mathrm { X } \text { batteries produced each day, } \\ & y = \text { the number (in thousands) of type } \mathrm { Y } \text { batteries produced each day. } \end{aligned}$$ The profit on each type X battery is 40 p and on each type Y battery is 20 p . The company wishes to maximise its daily profit.
    3. Write this as a linear programming problem, in terms of \(x\) and \(y\), stating the objective function and all the constraints.
    4. Find the optimal number of batteries to be made each day. Show your method clearly.
    5. Find the daily profit, in \(\pounds\), made by EXYCEL.
OCR D1 2006 June Q6
16 marks Standard +0.3
  1. Calculate the shortest distance that the mole must travel if it starts and ends at vertex \(A\).
  2. The pipe connecting \(B\) to \(H\) is removed for repairs. By considering every possible pairing of odd vertices, and showing your working clearly, calculate the shortest distance that the mole must travel to pass along each pipe on this reduced network, starting and finishing at \(A\).
OCR MEI D1 2006 January Q2
8 marks Easy -1.2
  1. Complete the table in the insert showing the outcome of applying the algorithm to the following two lists: $$\begin{array} { l r l l l l l } \text { List 1: } & 2 , & 34 , & 35 , & 56 & & \\ \text { List 2: } & 13 , & 22 , & 34 , & 81 , & 90 , & 92 \end{array}$$
  2. What does the algorithm achieve?
  3. How many comparisons did you make in applying the algorithm?
  4. If the number of elements in List 1 is \(x\), and the number of elements in List 2 is \(y\), what is the maximum number of comparisons that will have to be made in applying the algorithm, and what is the minimum number?
OCR D1 2006 January Q1
5 marks Easy -1.2
1 Answer this question on the insert provided.
\includegraphics[max width=\textwidth, alt={}]{8f17020a-14bf-4459-9241-1807b954a629-2_956_1203_349_493}
This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
OCR D1 2006 January Q2
6 marks Moderate -0.8
2 Answer this question on the insert provided.
\includegraphics[max width=\textwidth, alt={}]{8f17020a-14bf-4459-9241-1807b954a629-2_659_1136_1720_530}
This diagram shows part of a network. There are other arcs connecting \(D\) and \(E\) to other parts of the network. Apply Dijkstra's algorithm starting from \(A\), as far as you are able, showing your working. Note: you will not be able to give permanent labels to all the vertices shown.
OCR D1 2007 January Q5
16 marks Moderate -0.3
5 Answer part (i) of this question on the insert provided. Rhoda Raygh enjoys driving but gets extremely irritated by speed cameras.
The network represents a simplified map on which the arcs represent roads and the weights on the arcs represent the numbers of speed cameras on the roads. The sum of the weights on the arcs is 72 . \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-05_874_1484_664_333}
  1. Rhoda lives at Ayton ( \(A\) ) and works at Kayton ( \(K\) ). Use Dijkstra's algorithm on the diagram in the insert to find the route from \(A\) to \(K\) that involves the least number of speed cameras and state the number of speed cameras on this route.
  2. In her job Rhoda has to drive along each of the roads represented on the network to check for overhanging trees. This requires finding a route that covers every arc at least once, starting and ending at Kayton (K). Showing all your working, find a suitable route for Rhoda that involves the least number of speed cameras and state the number of speed cameras on this route.
  3. If Rhoda checks the roads for overhanging trees on her way home, she will instead need a route that covers every arc at least once, starting at Kayton and ending at Ayton. Calculate the least number of speed cameras on such a route, explaining your reasoning.
OCR D1 2009 January Q3
23 marks Moderate -0.3
3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}
  1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
  2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
  3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
  4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
  5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
  6. The sum of the weights of all the arcs is 300 . Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.
OCR D1 2009 January Q4
12 marks Easy -1.2
4 Answer this question on the insert provided. The list of numbers below is to be sorted into decreasing order using shuttle sort. $$\begin{array} { l l l l l l l l l } 21 & 76 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
  1. How many passes through shuttle sort will be required to sort the list? After the first pass the list is as follows. $$\begin{array} { l l l l l l l l l } 76 & 21 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
  2. State the number of comparisons and the number of swaps that were made in the first pass.
  3. Write down the list after the second pass. State the number of comparisons and the number of swaps that were used in making the second pass.
  4. Complete the table in the insert to show the results of the remaining passes, recording the number of comparisons and the number of swaps made in each pass. You may not need all the rows of boxes printed. When the original list is sorted into decreasing order using bubble sort there are 30 comparisons and 17 swaps.
  5. Use your results from part (iv) to compare the efficiency of these two methods in this case. Katie makes and sells cookies. Each batch of plain cookies takes 8 minutes to prepare and then 12 minutes to bake. Each batch of chocolate chip cookies takes 12 minutes to prepare and then 12 minutes to bake. Each batch of fruit cookies takes 10 minutes to prepare and then 12 minutes to bake. Katie can only bake one batch at a time. She has the use of the kitchen, including the oven, for at most 1 hour.
    [0pt]
  6. Each batch of cookies must be prepared before it is baked. By considering the maximum time available for baking the cookies, explain why Katie can make at most 4 batches of cookies. [2] Katie models the constraints as $$\begin{gathered} x + y + z \leqslant 4 \\ 4 x + 6 y + 5 z \leqslant 24 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$ where \(x\) is the number of batches of plain cookies, \(y\) is the number of batches of chocolate chip cookies and \(z\) is the number of batches of fruit cookies that Katie makes.
  7. Each batch of cookies that Katie prepares must be baked within the hour available. By considering the maximum time available for preparing the cookies, show how the constraint \(4 x + 6 y + 5 z \leqslant 24\) was formed.
  8. In addition to the constraints, what other restriction is there on the values of \(x , y\) and \(z\) ? Katie will make \(\pounds 5\) profit on each batch of plain cookies, \(\pounds 4\) on each batch of chocolate chip cookies and \(\pounds 3\) on each batch of fruit cookies that she sells. Katie wants to maximise her profit.
  9. Write down an expression for the objective function to be maximised. State any assumption that you have made.
  10. Represent Katie's problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm, choosing to pivot on an element from the \(x\)-column. Show how each row was obtained. Write down the number of batches of cookies of each type and the profit at this stage. After carrying out market research, Katie decides that she will not make fruit cookies. She also decides that she will make at least twice as many batches of chocolate chip cookies as plain cookies.
  11. Represent the constraints for Katie's new problem graphically and calculate the coordinates of the vertices of the feasible region. By testing suitable integer-valued coordinates, find how many batches of plain cookies and how many batches of chocolate chip cookies Katie should make to maximise her profit. Show your working.
OCR D1 2010 January Q1
11 marks Standard +0.3
1 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{e1495f6b-c09f-46a1-a6f8-02354e28887a-02_533_1353_342_395}
  1. Apply Dijkstra's algorithm to the copy of this network in the insert to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight.
  2. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. Write down a closed route that has this least weight. An extra arc is added, joining \(B\) to \(E\), with weight 2 .
  3. Write down the new least weight path from \(A\) to \(F\). Explain why the new least weight closed route, that uses every arc at least once, has no repeated arcs.
OCR D1 2007 June Q5
16 marks Standard +0.3
5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres. \includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}
  1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
  2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
  3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?
OCR D1 2007 June Q6
13 marks Moderate -0.5
6 Answer this question on the insert provided. The table shows the distances, in miles, along the direct roads between six villages, \(A\) to \(F\). A dash ( - ) indicates that there is no direct road linking the villages.
ABCDEF
A-63---
B6-56-14
C35-8410
D-68-38
E--43--
F-14108--
  1. On the table in the insert, use Prim's algorithm to find a minimum spanning tree. Start by crossing out row A. Show which entries in the table are chosen and indicate the order in which the rows are deleted. Draw your minimum spanning tree and state its total weight.
  2. By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.
  3. A pply the nearest neighbour method to the table above, starting from \(F\), to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.
    {}
OCR MEI D1 Q2
Moderate -0.3
2 Answer this question on the insert provided.
  1. Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
    \end{figure}
  2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
    \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.
OCR MEI D1 2005 January Q2
8 marks Moderate -0.3
2 Answer this question on the insert provided.
  1. Use Dijkstra's algorithm to find the least weight route from \(A\) to \(G\) in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
    \end{figure}
  2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
    \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.
OCR MEI D1 2005 January Q4
16 marks Moderate -0.8
4 Answer this question on the insert provided. The table shows activities involved in a "perm" in a hair salon, their durations and immediate predecessors. \begin{table}[h]
ActivityDuration (mins)Immediate predecessor(s)
Ashampoo5-
Bprepare perm lotion2-
Cmake coffee for customer3-
Dtrim5A
Eclean sink3A
Fput rollers in15D
Gclean implements3D
Happly perm lotion5B, F
Ileave to set20C,H
Jclean lotion pot and spreaders3H
Kneutralise and rinse10I, E
Ldry10K
Mwash up and clean up15K
Nstyle4G, L
\captionsetup{labelformat=empty} \caption{Table 4}
\end{table}
  1. Complete the activity-on-arc network in the insert to represent the precedences.
  2. Perform a forward pass and a backward pass to find early and late event times. Give the critical activities and the time needed to complete the perm.
  3. Give the total float time for the activity \(G\). Activities \(\mathrm { D } , \mathrm { F } , \mathrm { H } , \mathrm { K }\) and N require a stylist.
    Activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { E } , \mathrm { G } , \mathrm { J }\) and M are done by a trainee.
    Activities \(I\) and \(L\) require no-one in attendance.
    A stylist and a trainee are to give a perm to a customer.
  4. Use the chart in the insert to show a schedule for the activities, assuming that all activities are started as early as possible.
  5. Which activity would be better started at its latest start time?
OCR MEI D1 2005 June Q1
8 marks Easy -1.8
1 Answer this question on the insert provided. The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-2_486_879_623_607} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.
  1. Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number. The electrician has a junction box. This can be represented by an eighth node on the graph.
  2. What is the minimum number of connections which the electrician will have to make if he uses the junction box?
  3. The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway? The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.
  4. Will this result in the minimum number of connections? Justify your answer.
OCR MEI D1 2005 June Q2
8 marks Moderate -0.8
2 Answer this question on the insert provided. A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_495_717_470_671} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
\end{figure} On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."
  1. On the insert for this question show Janet's route through the maze. On the insert show John's route.
  2. Will these strategies always find a way through such mazes? Justify your answer. In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where \(\mathbf { X }\) is the marked point. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
    \end{figure} In the maze shown in Fig. 2.2 Janet's algorithm takes her to \(\mathbf { X }\). John's algorithm does not take him to \(\mathbf { X }\). John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting \(\mathbf { X }\). He will then move onwards, continuing to keep a hand in contact with the wall on the left.
  3. Will this modified algorithm take John to the point \(\mathbf { X }\) in the maze in Fig. 2.2?
  4. Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.
OCR MEI D1 2005 June Q4
16 marks Standard +0.3
4 Answer parts (i) and (ii) on the insert provided. Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-5_536_828_573_642} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure}
  1. Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
  2. Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector. A bridge is built giving a direct road between P and Q of length 12 km .
  3. What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
  4. What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
  5. Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once. Give this town and justify your answer.
OCR MEI D1 2006 June Q1
8 marks Moderate -0.3
1 Answer this question on the insert provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-2_658_739_466_662} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure}
  1. Apply Dijkstra's algorithm to the copy of Fig. 1 in the insert to find the least weight route from A to D. Give your route and its weight.
  2. Arc DE is now deleted. Write down the weight of the new least weight route from A to D , and explain how your working in part (i) shows that it is the least weight.
    [0pt] [2]
OCR MEI D1 2006 June Q6
16 marks Moderate -0.5
6 Answer parts (ii)(A) and (iii)(B) of this question on the insert provided. A particular component of a machine sometimes fails. The probability of failure depends on the age of the component, as shown in Table 6.
Year of lifefirstsecondthirdfourthfifthsixth
Probability of failure during year,
given no earlier failure
0.100.050.020.200.200.30
\section*{Table 6} You are to simulate six years of machine operation to estimate the probability of the component failing during that time. This will involve you using six 2-digit random numbers, one for each year.
  1. Give a rule for using a 2-digit random number to simulate failure of the component in its first year of life. Similarly give rules for simulating failure during each of years 2 to 6 .
  2. (A) Use your rules, together with the random numbers given in the insert, to complete the simulation table in the insert. This simulates 10 repetitions of six years operation of the machine. Start in the first column working down cell-by-cell. In each cell enter a tick if there is no simulated failure and a cross if there is a simulated failure. Stop and move on to the next column if a failure occurs.
    (B) Use your results to estimate the probability of a failure occurring. It is suggested that any component that has not failed during the first three years of its life should automatically be replaced.
  3. (A) Describe how to simulate the operation of this policy.
    (B) Use the table in the insert to simulate 10 repetitions of the application of this policy. Re-use the same random numbers that are given in the insert.
    (C) Use your results to estimate the probability of a failure occurring.
  4. How might the reliability of your estimates in parts (ii) and (iii) be improved?
OCR MEI D1 2006 January Q5
16 marks Moderate -0.8
5 Answer this question on the insert provided. Table 5 specifies a road network connecting 7 towns, A, B, \(\ldots\), G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads. \begin{table}[h]
ABCDEFG
A-10---1215
B10-1520--8
C-15-7--11
D-207-20-13
E---20-179
F12---17-13
G1581113913-
\captionsetup{labelformat=empty} \caption{Table 5}
\end{table}
  1. Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices. Draw the resulting tree, give its total length and describe a practical application.
  2. The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E. Give your route and its length.
  3. A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?