Questions — OCR D1 (127 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 D1 2011 January Q1
12 marks Standard +0.3
1 In the network below, the arcs represent the roads in Ayton, the vertices represent roundabouts, and the arc weights show the number of traffic lights on each road. Sam is an evening class student at Ayton Academy ( \(A\) ). She wants to drive from the academy to her home ( \(H\) ). Sam hates waiting at traffic lights so she wants to find the route for which the number of traffic lights is a minimum. \includegraphics[max width=\textwidth, alt={}, center]{bb7fb141-ef42-42af-b052-d8e20d6e5157-02_786_1097_482_523}
  1. Apply Dijkstra's algorithm to find the route that Sam should use to travel from \(A\) to \(H\). At each vertex, show the temporary labels, the permanent label and the order of permanent labelling. In the daytime, Sam works for the highways department. After an electrical storm, the highways department wants to check that all the traffic lights are working. Sam is sent from the depot ( \(D\) ) to drive along every road and return to the depot. Sam needs to pass every traffic light, but wants to repeat as few as possible.
  2. Find the minimum number of traffic lights that must be repeated. Show your working. Suppose, instead, that Sam wants to start at the depot, drive along every road and end at her home, passing every traffic light but repeating as few as possible.
  3. Find a route on which the minimum number of traffic lights must be repeated. Explain your reasoning.
OCR D1 2011 January Q2
8 marks Moderate -0.8
2 Five rooms, \(A , B , C , D , E\), in a building need to be connected to a computer network using expensive cabling. Rob wants to find the cheapest way to connect the rooms by finding a minimum spanning tree for the cable lengths. The length of cable, in metres, needed to connect each pair of rooms is given in the table below.
\multirow{2}{*}{}Room
\(A\)\(B\)\(C\)\(D\)\(E\)
\multirow{5}{*}{Room}\(A\)-12301522
B12-241630
C3024-2025
D151620-10
E22302510-
  1. Apply Prim's algorithm in matrix (table) form, starting at vertex \(A\) and showing all your working. Write down the order in which arcs were added to the tree. Draw the resulting tree and state the length of cable needed. A sixth room, \(F\), is added to the computer network. The distances from \(F\) to each of the other rooms are \(A F = 32 , B F = 29 , C F = 31 , D F = 35 , E F = 30\).
  2. Use your answer to part (i) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour.
OCR D1 2011 January Q3
8 marks Moderate -0.8
3
  1. Explain why it is impossible to draw a graph with exactly four vertices of orders 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
    A simply connected graph is one that is both simple and connected.
  2. Explain why there is no simply connected graph with exactly four vertices of orders \(1,1,2\) and 4.
  3. A connected graph has four vertices \(A , B , C\) and \(D\), in which \(A , B\) and \(C\) have order 2 and \(D\) has order 4. Explain how you know that the graph is Eulerian. Draw an example of such a graph and write down an Eulerian trail for your graph. A graph has three vertices, \(A , B\) and \(C\) of orders \(a , b\) and \(c\), respectively.
  4. What restrictions on the values of \(a , b\) and \(c\) follow from the graph being
    1. simple,
    2. connected,
    3. semi-Eulerian?
      1. Describe carefully how to carry out the first pass through bubble sort when we are using it to sort a list of \(n\) numbers into increasing order. State which value is guaranteed to be in its correct final position after the first pass and hence explain how to carry out the second pass on a reduced list. Write down the stopping condition for bubble sort.
      2. Show the list of six values that results at the end of each pass when we use bubble sort to sort this list into increasing order. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$ You do not need to count the number of comparisons and the number of swaps that are used. Zack wants to cut lengths of wood from planks that are 20 feet long. The following lengths, in feet, are required. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$
      3. Use the first-fit method to find a way to cut the pieces.
      4. Use the first-fit decreasing method to find a way to cut the pieces. Give a reason why this might be a more useful cutting plan than that from part (iii).
      5. Find a more efficient way to cut the pieces. How many planks will Zack need with this cutting plan and how many cuts will he need to make? 5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
        1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
        2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
          [0pt] [10]
OCR D1 2011 January Q5
17 marks Moderate -0.8
5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
Check contentsCheck postageCheck address
New343
Occasional534
Regular233
The manager in charge of checking at the company has allocated each type of parcel a 'value' to represent how useful it is for generating additional income. In suitable units, these values are as follows. $$\text { new } = 8 \text { points } \quad \text { occasional } = 7 \text { points } \quad \text { regular } = 4 \text { points }$$ The manager wants to find out how many parcels of each type her department should check each hour, on average, to maximise the total value. She models this objective as $$\text { Maximise } P = 8 x + 7 y + 4 z .$$
  1. What do the variables \(x , y\) and \(z\) represent?
  2. Write down the constraints on the values of \(x , y\) and \(z\). The manager changes the value of parcels for regular customers to 0 points.
  3. Explain what effect this has on the objective and simplify the constraints.
  4. Use a graphical method to represent the feasible region for the manager's new problem. You should choose scales so that the feasible region can be clearly seen. Hence determine the optimal strategy. Now suppose that there is exactly one hour available for checking and the manager wants to find out how many parcels of each type her department should check in that hour to maximise the total value. The value of parcels for regular customers is still 0 points.
  5. Find the optimal strategy in this situation.
  6. Give a reason why, even if all the timings and values are correct, the total value may be less than this maximum. \section*{Question 6 is printed overleaf.}
OCR D1 2011 January Q6
13 marks Standard +0.3
6 Consider the following LP problem.
Minimise\(2 a - 4 b + 5 c - 30\),
subject to\(3 a + 2 b - c \geqslant 10\),
\(- 2 a + 4 c \leqslant 35\),
\(4 a - b \leqslant 20\),
and\(a \leqslant 6 , b \leqslant 8 , c \leqslant 10\).
  1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
    [0pt] [10]
OCR D1 2011 January Q8
Easy -2.0
8
\multirow[t]{4}{*}{5
  1. }
5
  • \multirow[t]{7}{*}{5
  • }
    • 5
  • 5
  		• (continued)
    \(5 ( \mathrm { v } )\)
    5
  • 6
  • 6
  • {} 6
  • (continued)
    \multirow[t]{24}{*}{
    6
  • 6
  • }    		(ontnued)
    •
    OCR D1 2013 January Q1
    9 marks Easy -1.8
    1
    1. Use shuttle sort to put this list of values into decreasing order (from largest to smallest). $$\begin{array} { l l l l l l l l l } 18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22 \end{array}$$ Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
    2. The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
    3. Suppose that some stronger boxes are available, each of which can hold at most \(W \mathrm {~kg}\). Find the least value of \(W\) for which only four boxes are needed. Show a packing using four of these stronger boxes.
    OCR D1 2013 January Q2
    10 marks Moderate -0.5
    2 A tetromino is a two-dimensional shape made by joining four squares edge-to-edge. Joins are along complete edges.
    1. Represent each of the tetrominoes below by a graph in which the nodes represent the squares and two nodes are joined by an arc if the squares share a common edge. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_76_268_1206_420} \captionsetup{labelformat=empty} \caption{(A)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_208_1201_836} \captionsetup{labelformat=empty} \caption{(B)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_144_1201_1165} \captionsetup{labelformat=empty} \caption{(C)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_209_1201_1439} \captionsetup{labelformat=empty} \caption{(D)}
      \end{figure}
    2. Six simply connected graphs with four nodes are shown below. For each graph, either draw a tetromino that can be represented by the graph, as in part (i), or explain why this is not possible. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_126_1603_299} \captionsetup{labelformat=empty} \caption{(1)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_209_1603_529} \captionsetup{labelformat=empty} \caption{(2)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_125_1603_840} \captionsetup{labelformat=empty} \caption{(3)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_127_1603_1082} \captionsetup{labelformat=empty} \caption{(4)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1343} \captionsetup{labelformat=empty} \caption{(5)}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1603} \captionsetup{labelformat=empty} \caption{(6)}
      \end{figure} Two tetrominoes are regarded as being the same if one can be rotated or reflected to form the other. Derek claims that each tetromino corresponds to a unique tree with four nodes, and each tree with four nodes corresponds to a unique tetromino. Derek's claim is wrong.
    3. From the diagrams above, find:
      1. a tetromino whose graph does not correspond to a tree;
      2. two different tetrominoes whose graphs correspond to the same tree. A pentomino is a two-dimensional shape made by joining five squares edge-to-edge. Joins are along complete edges. Two pentominoes are regarded as being the same if one can be rotated or reflected to form the other. There are twelve distinct pentominoes.
      3. When the pentominoes are represented by graphs, as in part (i), there are only four distinct graphs. Draw these four graphs.
    OCR D1 2013 January Q3
    14 marks Standard +0.3
    3 The total weight of the arcs in the network below is 230 . \includegraphics[max width=\textwidth, alt={}, center]{012e87d3-d157-485c-a8bc-2c59c0862f87-3_545_1394_310_331}
    1. Apply Dijkstra's algorithm to the copy of the network in the answer book to find the least weight path from \(A\) to \(H\). Give the path and its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
    2. The arc \(A D\) is removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A D\) ) at least once.
    3. Suppose, instead, that the arc \(A D\) is available, but \(\operatorname { arcs } A C\) and \(C D\) are both removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A C\) and \(C D\) ) at least once.
    OCR D1 2013 January Q4
    17 marks Moderate -0.3
    4 Pam has seven employees. When it snows they all need to be contacted by telephone.
    The table shows the expected time, in minutes, that it will take Pam and her employees to contact each other.
    PamAlanBobCazDanEllaFredGita
    Pam-10481812129
    Alan10-6101812119
    Bob46-917101110
    Caz8109-1513107
    Dan18181715-161920
    Ella1212101316-1314
    Fred121111101913-18
    Gita99107201418-
    1. Use the nearest neighbour method, starting from Pam, to find a cycle through all the employees and Pam. If there is a choice of names choose the one that occurs first alphabetically. Calculate the total weight of this cycle.
    2. Apply Prim's algorithm to the copy of the table in the answer book, starting by crossing out the row for Pam and looking down the column for Pam. List the arcs in the order in which they were chosen. Draw the resulting minimum spanning tree and calculate its total weight.
    3. Find a lower bound for the minimum weight cycle through Pam and her seven employees by initially removing Gita from the minimum spanning tree. Pam realises that it takes less time if she splits the employees into teams.
    4. Use the minimum spanning tree to suggest how to split the employees into two teams, so that Pam contacts the two team leaders and they each contact the members of their team. Using this solution, find the minimum elapsed time by which all the employees can be contacted.
    OCR D1 2013 January Q5
    22 marks Moderate -0.8
    5 Roland Neede, the baker, is making cupcakes. He makes three sizes of cupcake: miniature, small and standard. Miniature cupcakes are sold in boxes of 24 and each cupcake uses 3 units of topping and 2 decorations. Small cupcakes are sold in boxes of 20 and each cupcake uses 5 units of topping and 3 decorations. Standard cupcakes are sold in boxes of 12 and each cupcake uses 7 units of topping and 4 decorations. Roland has no restriction on the amount of cake mix that he uses but he only has 5000 units of topping and 3000 decorations available. Cupcakes are only sold in complete boxes, and Roland assumes that he can sell all the boxes of cupcakes that he makes. Irrespective of size, each box of cupcakes sold will give Roland a profit of \(\pounds 1\). Roland wants to maximise his total profit. Let \(x\) denote the number of boxes of miniature cupcakes, \(y\) denote the number of boxes of small cupcakes and \(z\) denote the number of boxes of standard cupcakes that Roland makes.
    1. Construct an objective function, \(P\), to be maximised.
    2. By considering the number of units of topping used, show that \(18 x + 25 y + 21 z \leqslant 1250\).
    3. Construct a similar constraint by considering the number of decorations used, simplifying the coefficients so that they are integers with no common factor.
    4. Set up an initial Simplex tableau to represent Roland's problem.
    5. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated.
    6. Write down the values of \(x , y\) and \(z\) from the first iteration of the Simplex algorithm. Hence find the maximum profit that Roland can make, remembering that cupcakes can only be sold in complete boxes. Calculate the number of units of topping and the number of decorations that are left over with this solution.
    7. The constraint from the number of units of topping can be rewritten as \(18 P + 7 y + 3 z \leqslant 1250\). Form a similar expression for the constraint from the number of decorations. Use this to find the number of boxes of small cupcakes which maximises the profit when there are no decorations left over. Find the solution which gives the maximum profit using all the topping and all the decorations, and find the values of \(x , y\) and \(z\) for this solution. {}
    OCR D1 2005 June Q1
    6 marks Easy -1.2
    1
      1. Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg . $$\begin{array} { l l l l l l l l l l } 2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3 \end{array}$$
      2. Find a packing that uses fewer bags.
    2. The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?
    OCR D1 2005 June Q2
    6 marks Standard +0.8
    2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.
    1. Draw a simple graph that connects four vertices using five arcs.
    2. Explain why, in any graph, there must be an even number of odd vertices.
    3. By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.
    OCR D1 2005 June Q3
    8 marks Moderate -0.5
    3 This diagram shows a network. \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}
    1. Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
    2. Use the nearest neighbour method, starting from vertex \(A\), to find a cycle that passes through every vertex. The network represents a cubical die, with vertices labelled \(A\) to \(H\), and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
    3. (a) List the vertices of each of the two faces that meet in the edge \(A G\).
      (b) What number is on the face \(A C E G\) ?
      (c) Which face is numbered 3?
    OCR D1 2005 June Q4
    10 marks Standard +0.8
    4 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-3_918_1242_351_443} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the lengths of roads in kilometres.
    1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. Find the route of the shortest path from \(A\) to \(G\). The total weight of the arcs is 120 kilometres.
    2. By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at \(A\). You should explain your method.
    3. Find the length of a shortest route that uses every road starting at \(A\) and ending at \(G\). You should explain your method.
    OCR D1 2005 June Q5
    10 marks Easy -1.8
    5 Consider the following algorithm which is to be applied to a list of numbers.
    Step 1Let \(N = 0 , T = 0\) and \(S = 0\).
    Step 2
    Input the first number in the list and call it \(X\).
    Delete the first number from the list to give a list that has one number fewer than before.
    Step 3Increase \(N\) by 1 , increase \(T\) by \(X\) and increase \(S\) by \(X ^ { 2 }\).
    Step 4If there are still numbers in the list then go back to Step 2. Otherwise go to Step 5.
    Step 5
    Calculate \(M = ( T\) divided by \(N )\).
    Calculate \(V = ( S\) divided by \(N ) - ( M\) squared \()\).
    Calculate \(D = \sqrt { } V\).
    Step 6Output \(M\) and \(D\).
    1. Apply the algorithm to this list. $$\begin{array} { l l l l l } 3 & 6 & 5 & 7 & 3 \end{array}$$ Record in a table the values of \(X , N , T\) and \(S\) at each pass through Step 3 and give the output values.
    2. Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.
    3. Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of \(n\) numbers.
    4. The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?
    OCR D1 2006 June Q1
    7 marks Easy -1.8
    1
    1. Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
    2. Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
    3. First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?
    OCR D1 2006 June Q2
    7 marks Moderate -0.8
    2
    1. Draw three mathematically different graphs, labelled graph \(A\), graph \(B\) and graph \(C\), each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
    2. Explain how you know that none of the graphs from part (i) is Eulerian.
    OCR D1 2006 June Q3
    13 marks Moderate -0.3
    3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516} Alf wants to cycle from his home at \(A\) to visit each of the other villages and return to \(A\) in the shortest possible time.
    1. Which standard network problem does Alf need to solve to find the quickest tour through all the villages?
    2. Apply the nearest neighbour method starting at \(A\) to find a tour through all the villages that starts and ends at \(A\). Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?
    3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(A\) and all the arcs that are directly joined to \(A\). Start building your tree at vertex \(B\). (You do not need to represent the network as a matrix.) Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.
    4. Write down a route for Alf that would take him 125 minutes.
    OCR D1 2006 June Q4
    16 marks Moderate -0.8
    4 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-03_1025_826_374_657}
    1. Write down inequalities that define the feasible region.
    2. Find the coordinates of the four vertices of the feasible region. The objective is to maximise \(P\), where \(P = x + 2 y\).
    3. Find the values of \(x\) and \(y\) that maximise \(P\), and the corresponding maximum value of \(P\). The objective is changed to minimise \(Q\), where \(Q = 2 x - y\).
    4. Find the minimum value of \(Q\) and describe the set of feasible points for which \(Q\) takes this value.
    5. Show that there are no points in the feasible region for which the value of \(P\) is the same as the value of \(Q\).
    OCR D1 2006 June Q5
    13 marks Standard +0.3
    5 Consider the linear programming problem:
    maximise\(P = x - 2 y - 3 z\),
    subject to\(2 x - 5 y + 2 z \leqslant 10\),
    \(2 x \quad + 3 z \leqslant 30\),
    and\(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
    1. Using slack variables, \(s \geqslant 0\) and \(t \geqslant 0\), express the two non-trivial constraints as equations.
    2. Represent the problem as an initial Simplex tableau.
    3. Explain why the pivot element must be chosen from the \(x\)-column and show the calculations that are used to choose the pivot.
    4. Perform one iteration of the Simplex algorithm. Show how you obtained each row of your tableau and write down the values of \(x , y , z\) and \(P\) that result from this iteration. State whether or not this is the maximum feasible value of \(P\) and describe how you know this from the values in the tableau.
    OCR D1 2006 June Q12
    Moderate -0.5
    12 JUNE 2006
    Afternoon
    1 hour 30 minutes
    • This insert should be used to answer Question 6.
    • Write your name, centre number and candidate number in the spaces provided at the top of this page.
    • Write your answers to Question 6 in the spaces provided in this insert, and attach it to your answer booklet.
    6

    1. Key: \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_193_949_214_712} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_1157_1600_648_303} Route of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) Length of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) metres
      1. \(\_\_\_\_\) Shortest distance \(=\) \(\_\_\_\_\) metres
      2. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-11_979_1429_276_440}
        Shortest distance = \(\_\_\_\_\) metres
    OCR D1 2007 June Q1
    9 marks Moderate -0.8
    1 Two graphs A and B are shown below. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_339_585_333_386} \captionsetup{labelformat=empty} \caption{Graph \(A\)}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_337_579_333_1174} \captionsetup{labelformat=empty} \caption{Graph B}
    \end{figure}
    1. Write down an example of a cycle on graph A .
    2. W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
    3. How many arcs would there be in a spanning tree for graph A ?
    4. For each graph state whether it is Eulerian, semi-Eulerian or neither.
    5. The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
    6. Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?
    OCR D1 2007 June Q2
    10 marks Easy -1.2
    2 A landscape gardener is designing a garden. Part of the garden will be decking, part will be flowers and the rest will be grass. Let d be the area of decking, f be the area of flowers and g be the area of grass, all measured in \(\mathrm { m } ^ { 2 }\). The total area of the garden is \(120 \mathrm {~m} ^ { 2 }\) of which at least \(40 \mathrm {~m} ^ { 2 }\) must be grass. The area of decking must not be greater than the area of flowers. Also, the area of grass must not be more than four times the area of decking. Each square metre of grass will cost \(\pounds 5\), each square metre of decking will cost \(\pounds 10\) and each square metre of flowers will cost \(\pounds 20\). These costs include labour. The landscape gardener has been instructed to come up with the design that will cost the least.
    1. Write down a constraint in d , f and g from the total area of the garden.
    2. Explain why the constraint \(\mathrm { g } \leqslant 4 \mathrm {~d}\) is required.
    3. Write down a constraint from the requirement that the area of decking must not be greater than the area of flowers.
    4. Write down a constraint from the requirement that at least \(40 \mathrm {~m} ^ { 2 }\) of the garden must be grass and write down the minimum feasible values for each of \(d\) and \(f\).
    5. Write down the objective function to be minimised.
    6. Write down the resulting LP problem, using slack variables to express the constraints from parts (ii) and (iii) as equations.
      (You are not required to solve the resulting LP problem.)
    OCR D1 2007 June Q3
    11 marks Easy -1.8
    3
    1. Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
    2. The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step. Step 1: Input the original list and call it list A.
      Step 2: Remove the first item in list \(A\) and call this item \(X\).
      Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
      Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
      Step 5: If there are still items in list A, repeat Step 4.
      Step 6: Count the number of items in list \(\mathbf { B }\) and call this \(\mathbf { N }\).
      Step 7: Put the items in list B at positions 1 to N of list A, item X at position \(\mathrm { N } + 1\) of list A and the items in list C at positions \(\mathrm { N } + 2\) onwards of list A.
      Step 8: Display list A.