Questions — OCR (4628 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 Stats 1 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 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 2012 January Q4
18 marks Moderate -0.8
4 Lucy is making party bags which she will sell to raise money for charity. She has three colours of party bag: red, yellow and blue. The bags contain balloons, sweets and toys. Lucy has a stock of 40 balloons, 80 sweets and 30 toys. The table shows how many balloons, sweets and toys are needed for one party bag of each colour.
Colour of party bagBalloonsSweetsToys
Red535
Yellow472
Blue663
Lucy will raise \(\pounds 1\) for each bag that she sells, irrespective of its colour. She wants to calculate how many bags of each colour she should make to maximise the total amount raised for charity. Lucy has started to model the problem as an LP formulation. $$\begin{array} { l l } \text { Maximise } & P = x + y + z , \\ \text { subject to } & 3 x + 7 y + 6 z \leqslant 80 . \end{array}$$
  1. What does the variable \(x\) represent in Lucy's formulation?
  2. Explain why the constraint \(3 x + 7 y + 6 z \leqslant 80\) must hold and write down another two similar constraints.
  3. What other constraints and restrictions apply to the values of \(x , y\) and \(z\) ?
  4. What assumption is needed for the objective to be valid?
  5. Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet.
  6. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(\boldsymbol { x }\) column. Explain how the choice of pivot row was made and show how each row was calculated.
  7. Write down the values of \(x , y\) and \(z\) from the first iteration of the Simplex algorithm and hence find the number of bags of each colour that Lucy should make according to this non-optimal tableau. In the optimal solution Lucy makes 10 bags.
  8. Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags.
OCR D1 2012 January Q5
18 marks Moderate -0.5
5 The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles. Ayr
250Birmingham
350103Cardiff
235104209Doncaster
446157121261
\(\quad\) Exeter
  1. Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place.
  2. List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. A sixth vertex, \(F\), is added to the network. The distances, in miles, between \(F\) and each of the other places are shown in the table below.
    \(A\)\(B\)\(C\)\(D\)\(E\)
    Distance from \(F\)2005015059250
  3. Use the weight of the minimum spanning tree from part (ii) to find a lower bound for the length of the minimum tour (cycle) that visits every vertex of the extended network with six vertices.
  4. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of the minimum tour (cycle) through the six vertices.
  5. Use the two least weight arcs through \(A\) to form a least weight path of the form \(S A T\), where \(S\) and \(T\) are two of \(\{ B , C , D , E , F \}\), and give the weight of this path. Similarly write down a least weight path of the form \(U E V\), where \(U\) and \(V\) are two of \(\{ A , B , C , D , F \}\), and give the weight of this path. You should find that the two paths that you have written down use all six vertices.
    Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour.
OCR D1 2012 January Q6
9 marks Moderate -0.8
6 The function \(\operatorname { INT } ( C )\) gives the largest integer that is less than or equal to \(C\).
For example: \(\operatorname { INT } ( 4.8 ) = 4 , \operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 0.8 ) = 0 , \operatorname { INT } ( - 0.8 ) = - 1 , \operatorname { INT } ( - 2.4 ) = - 3\).
Consider the following algorithm.
Line 10Input \(A\) and \(B\)
Line 20Calculate \(C = B \div A\)
Line 30Let \(D = \operatorname { INT } ( C )\)
Line 40Calculate \(E = A \times D\)
Line 50Calculate \(F = B - E\)
Line 60Output the value of \(F\)
Line 70Replace \(B\) by the value of \(D\)
Line 80If \(B = 0\) then stop, otherwise go back to line 20
  1. Apply the algorithm using the inputs \(A = 10\) and \(B = 128\). Record the values of \(A , B , C , D , E\), and \(F\) every time they change. Record the output each time line 60 is reached.
  2. Show what happens when the input values are \(A = 10\) and \(B = - 13\).
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:
    (a) a tetromino whose graph does not correspond to a tree;
    (b) 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.
  4. 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. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}
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.
OCR D1 2007 June Q4
13 marks Moderate -0.8
4 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 3 x - 5 y , \\ \text { subject to } & x + 5 y \leqslant 12 , \\ & x - 5 y \leqslant 10 , \\ & 3 x + 10 y \leqslant 45 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$
  1. Represent the problem as an initial Simplex tableau.
  2. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
  3. Perform oneiteration of the Simplex algorithm. Write down the values of \(\mathrm { x } , \mathrm { y }\) and P after this iteration.
  4. Show that \(\mathrm { x } = 11 , \mathrm { y } = 0.2\) is a feasible solution and that it gives a bigger value of P than that in part (iii).
OCR D1 2009 June Q1
8 marks Easy -1.2
1 The memory requirements, in KB , for eight computer files are given below. $$\begin{array} { l l l l l l l l } 43 & 172 & 536 & 17 & 314 & 462 & 220 & 231 \end{array}$$ The files are to be grouped into folders. No folder is to contain more than 1000 KB , so that the folders are small enough to transfer easily between machines.
  1. Use the first-fit method to group the files into folders.
  2. Use the first-fit decreasing method to group the files into folders. First-fit decreasing is a quadratic order algorithm.
  3. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers?
  4. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined 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.
  5. (a) Draw a graph with five vertices of orders \(1,1,2,2\) and 4 that is neither simple nor connected.
    (b) Explain why your graph from part (a) is not semi-Eulerian.
    (c) Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.
  6. (a) Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour.
    (b) Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour.
OCR D1 2009 June Q3
11 marks Standard +0.8
3 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]{fe06fa02-9f5d-4082-8e96-feea705d3fa2-3_933_935_397_605}
  1. Write down the inequalities that define the feasible region.
  2. Write down the coordinates of the three vertices of the feasible region. The objective is to maximise \(2 x + 3 y\).
  3. Find the values of \(x\) and \(y\) at the optimal point, and the corresponding maximum value of \(2 x + 3 y\). The objective is changed to maximise \(2 x + k y\), where \(k\) is positive.
  4. Find the range of values of \(k\) for which the optimal point is the same as in part (iii).