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 2007 January Q2
8 marks Moderate -0.8
2 A baker can make apple cakes, banana cakes and cherry cakes.
The baker has exactly enough flour to make either 30 apple cakes or 20 banana cakes or 40 cherry cakes. The baker has exactly enough sugar to make either 30 apple cakes or 40 banana cakes or 30 cherry cakes. The baker has enough apples for 20 apple cakes, enough bananas for 25 banana cakes and enough cherries for 10 cherry cakes. The baker has an order for 30 cakes. The profit on each apple cake is 4 p , on each banana cake is 3 p and on each cherry cake is 2 p . The baker wants to maximise the profit on the order.
  1. The availability of flour leads to the constraint \(4 a + 6 b + 3 c \leqslant 120\). Give the meaning of each of the variables \(a , b\) and \(c\) in this constraint.
  2. Use the availability of sugar to give a second constraint of the form \(X a + Y b + Z c \leqslant 120\), where \(X , Y\) and \(Z\) are numbers to be found.
  3. Write down a constraint from the total order size. Write down constraints from the availability of apples, bananas and cherries.
  4. Write down the objective function to be maximised.
    [0pt] [You are not required to solve the resulting LP problem.]
OCR D1 2007 January Q3
9 marks Moderate -0.8
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 connected, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.
  1. A simply connected graph is drawn with 6 vertices and 9 arcs.
    (a) What is the sum of the orders of the vertices?
    (b) Explain why if the graph has two vertices of order 5 it cannot have any vertices of order 1.
    (c) Explain why the graph cannot have three vertices of order 5 .
  2. Draw an example of a simply connected graph with 6 vertices and 9 arcs in which one of the vertices has order 5 and all the orders of the vertices are odd numbers.
  3. Draw an example of a simply connected graph with 6 vertices and 9 arcs that is also Eulerian.
OCR D1 2007 January Q4
14 marks Moderate -0.5
4
  1. ↓
    \(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)
    A0453256
    \(B\)4012476
    C5103467
    \(D\)3230264
    \(E\)2442066
    \(F\)57666010
    \(G\)66746100
    Order in which rows were deleted: \(\_\_\_\_\) \(A\) Minimum spanning tree: A
    • \(D\)
    F
    B E \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_33_28_1302_1101} III
    o D C \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_38_38_1297_1491}
    • G Total weight: \(\_\_\_\_\)
  2. \(\_\_\_\_\)
  3. \(\_\_\_\_\) Lower bound: \(\_\_\_\_\)
  4. Tour: \(\_\_\_\_\) Upper bound: \(\_\_\_\_\)
OCR D1 2007 January Q6
18 marks Standard +0.8
6 Consider the linear programming problem: $$\begin{array} { l r } \text { maximise } & P = 3 x - 5 y + 4 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x + 5 y - 8 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  1. Represent the problem as an initial Simplex tableau.
  2. Explain why it is not possible to pivot on the \(z\) column of this tableau. 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 one iteration of the Simplex algorithm. Write down the values of \(x , y\) and \(z\) after this iteration.
  4. Explain why \(P\) has no finite maximum. The coefficient of \(z\) in the objective is changed from + 4 to - 40 .
  5. Describe the changes that this will cause to the initial Simplex tableau and the tableau that results after one iteration. What is the maximum value of \(P\) in this case? Now consider this linear programming problem: $$\begin{array} { l l } \text { maximise } & Q = 3 x - 5 y + 7 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x - 7 y + 10 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ Do not use the Simplex algorithm for these parts.
  6. By adding the two constraints, show that \(Q\) has a finite maximum.
  7. There is an optimal point with \(y = 0\). By substituting \(y = 0\) in the two constraints, calculate the values of \(x\) and \(z\) that maximise \(Q\) when \(y = 0\).
OCR D1 2008 January Q1
6 marks Easy -1.8
1 Five boxes weigh \(5 \mathrm {~kg} , 2 \mathrm {~kg} , 4 \mathrm {~kg} , 3 \mathrm {~kg}\) and 8 kg . They are stacked, in the order given, with the first box at the top of the stack. The boxes are to be packed into bins that can each hold up to 10 kg .
  1. Use the first-fit method to put the boxes into bins. Show clearly which boxes are packed in which bins.
  2. Use the first-fit decreasing method to put the boxes into bins. You do not need to use an algorithm for sorting. Show clearly which boxes are packed in which bins.
  3. Why might the first-fit decreasing method not be practical?
  4. Show that if the bins can only hold up to 8 kg each it is still possible to pack the boxes into three bins.
OCR D1 2008 January Q2
5 marks Moderate -0.5
2 A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4 . This arrangement of tiles will be called position 4. \begin{table}[h]
  1. Apply the algorithm with the inputs \(B = 2\) and \(N = 5\). Record the values of \(F , G , H , C\) and \(N\) each time Step 9 is reached.
  2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = - 5\).
  3. Apply the algorithm with the inputs \(B = 10\) and \(N = 37\). Record the values of \(F , G , H , C\) and \(N\) each time Step 9 is reached. What are the output values when \(B = 10\) and \(N\) is any positive integer?
OCR D1 2008 January Q3
11 marks Moderate -0.5
3
  1. \includegraphics[max width=\textwidth, alt={}, center]{1ecf9738-d968-49f6-8c70-0aa50b57cb69-10_629_951_276_596} \(A D = 16\) \(C D = 18\) \(C F = 21\) \(A C = 23\) \(D F = 34\) \(B E = 35\) \(B G = 46\) \(C \bullet \quad \bullet D\) B \(A B = 50\) \(E G = 55\) \(F G = 58\) \(A E = 80\) \(A F = 100\) \includegraphics[max width=\textwidth, alt={}, center]{1ecf9738-d968-49f6-8c70-0aa50b57cb69-10_497_56_1073_1084}
    • \(E\) G
    Total weight of arcs in minimum spanning tree \(=\) \(\_\_\_\_\)
  2. \(\_\_\_\_\) Weight of spanning tree for the network with vertex \(G\) removed = \(\_\_\_\_\) Lower bound for travelling salesperson problem on original network = \(\_\_\_\_\)
  3. \(\_\_\_\_\) Upper bound for travelling salesperson problem on original network = \(\_\_\_\_\)
OCR D1 2008 January Q5
12 marks Moderate -0.8
5 Mark wants to decorate the walls of his study. The total wall area is \(24 \mathrm {~m} ^ { 2 }\). Mark can cover the walls using any combination of three materials: panelling, paint and pinboard. He wants at least \(2 \mathrm {~m} ^ { 2 }\) of pinboard and at least \(10 \mathrm {~m} ^ { 2 }\) of panelling. Panelling costs \(\pounds 8\) per \(\mathrm { m } ^ { 2 }\) and it will take Mark 15 minutes to put up \(1 \mathrm {~m} ^ { 2 }\) of panelling. Paint costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and it will take Mark 30 minutes to paint \(1 \mathrm {~m} ^ { 2 }\). Pinboard costs \(\pounds 10\) per \(\mathrm { m } ^ { 2 }\) and it will take Mark 20 minutes to put up \(1 \mathrm {~m} ^ { 2 }\) of pinboard. He has all the equipment that he will need for the decorating jobs. Mark is able to spend up to \(\pounds 150\) on the materials for the decorating. He wants to know what area should be covered with each material to enable him to complete the whole job in the shortest time possible. Mark models the problem as an LP with five constraints. His constraints are: $$\begin{aligned} & x + y + z = 24 \\ & 4 x + 2 y + 5 z \leqslant 75 \\ & x \geqslant 10 \\ & y \geqslant 0 \\ & z \geqslant 2 \end{aligned}$$
  1. Identify the meaning of each of the variables \(x , y\) and \(z\).
  2. Show how the constraint \(4 x + 2 y + 5 z \leqslant 75\) was formed.
  3. Write down an objective function, to be minimised. Mark rewrites the first constraint as \(z = 24 - x - y\) and uses this to eliminate \(z\) from the problem.
  4. Rewrite and simplify the objective and the remaining four constraints as functions of \(x\) and \(y\) only.
  5. Represent your constraints from part (iv) graphically and identify the feasible region. Your graph should show \(x\) and \(y\) values from 9 to 15 only.
OCR D1 2008 January Q6
13 marks Standard +0.8
6
  1. Represent the linear programming problem below by an initial Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 25 x + 14 y - 32 z , \\ \text { subject to } & 6 x - 4 y + 3 z \leqslant 24 , \\ & 5 x - 3 y + 10 z \leqslant 15 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  2. Explain how you know that the first iteration will use a pivot from the \(x\) column. Show the calculations used to find the pivot element.
  3. Perform one iteration of the Simplex algorithm. Show how each row was calculated and write down the values of \(x , y , z\) and \(P\) that result from this iteration.
  4. Explain why the Simplex algorithm cannot be used to find the optimal value of \(P\) for this problem.
OCR D1 2008 January Q7
13 marks Easy -1.2
7 In this question, the function INT( \(X\) ) is the largest integer less than or equal to \(X\). For example, $$\begin{aligned} & \operatorname { INT } ( 3.6 ) = 3 , \\ & \operatorname { INT } ( 3 ) = 3 , \\ & \operatorname { INT } ( - 3.6 ) = - 4 . \end{aligned}$$ Consider the following algorithm.
Step 1Input \(B\)
Step 2Input \(N\)
Step 3Calculate \(F = N \div B\)
Step 4Let \(G = \operatorname { INT } ( F )\)
Step 5Calculate \(H = B \times G\)
Step 6Calculate \(C = N - H\)
Step 7Output C
Step 8Replace \(N\) by the value of \(G\)
Step 9If \(N = 0\) then stop, otherwise go back to Step 3
  1. Apply the algorithm with the inputs \(B = 2\) and \(N = 5\). Record the values of \(F , G , H , C\) and \(N\) each time Step 9 is reached.
  2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = - 5\).
  3. Apply the algorithm with the inputs \(B = 10\) and \(N = 37\). Record the values of \(F , G , H , C\) and \(N\) each time Step 9 is reached. What are the output values when \(B = 10\) and \(N\) is any positive integer?
OCR D1 2009 January Q1
6 marks Easy -1.8
1 The flow chart shows an algorithm for which the input is a three-digit positive integer. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-2_1294_1493_356_328}
  1. Trace through the algorithm using the input \(A = 614\) to show that the output is 297 . Write down the values of \(A , B , C\) and \(D\) in each pass through the algorithm.
  2. What is the output when \(A = 616\) ?
  3. Explain why the counter \(C\) is needed.
OCR D1 2009 January Q2
6 marks Moderate -0.8
2
  1. Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
  2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
  3. Explain why a graph with five vertices of orders \(1,2,2,3\) and 4 cannot be a tree.
OCR D1 2010 January Q2
10 marks Moderate -0.3
2 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.
  1. Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.
  2. A simply connected graph has five vertices \(A , B , C , D\) and \(E\), in which \(A\) has order \(4 , B\) has order 2, \(C\) has order 3, \(D\) has order 3 and \(E\) has order 2. Explain how you know that the graph is semi-Eulerian and write down a semi-Eulerian trail on this graph. A network is formed from the graph in part (ii) by weighting the arcs as given in the table below.
    \(A\)\(B\)\(C\)\(D\)\(E\)
    \(A\)-5382
    \(B\)5-6--
    \(C\)36-7-
    \(D\)8-7-9
    \(E\)2--9-
  3. Apply Prim's algorithm to the network, showing all your working, starting at vertex \(A\). Draw the resulting tree and state its total weight. A sixth vertex, \(F\), is added to the network using arcs \(C F\) and \(D F\), each of which has weight 6 .
  4. Use your answer to part (iii) 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. Explain why the nearest neighbour method fails if it is started from vertex \(F\).
OCR D1 2010 January Q3
11 marks Moderate -0.8
3 Maggie is a personal trainer. She has twelve clients who want to lose weight. She decides to put some of her clients on weight loss programme \(X\), some on programme \(Y\) and the rest on programme \(Z\). Each programme involves a strict diet; in addition programmes \(X\) and \(Y\) involve regular exercise at Maggie's home gym. The programmes each last for one month. In addition to the diet, clients on programme \(X\) spend 30 minutes each day on the spin cycle, 10 minutes each day on the rower and 20 minutes each day on free weights. At the end of one month they can each expect to have lost 9 kg more than a client on just the diet. In addition to the diet, clients on programme \(Y\) spend 10 minutes each day on the spin cycle and 30 minutes each day on free weights; they do not use the rower. At the end of one month they can each expect to have lost 6 kg more than a client on just the diet. Because of other clients who use Maggie's home gym, the spin cycle is available for the weight loss clients for 180 minutes each day, the rower for 40 minutes each day and the free weights for 300 minutes each day. Only one client can use each piece of apparatus at any one time. Maggie wants to decide how many clients to put on each programme to maximise the total expected weight loss at the end of the month. She models the objective as follows. $$\text { Maximise } P = 9 x + 6 y$$
  1. What do the variables \(x\) and \(y\) represent?
  2. Write down and simplify the constraints on the values of \(x\) and \(y\) from the availability of each of the pieces of apparatus.
  3. What other constraints and restrictions apply to the values of \(x\) and \(y\) ?
  4. Use a graphical method to represent the feasible region for Maggie's problem. You should use graph paper and choose scales so that the feasible region can be clearly seen. Hence determine how many clients should be put on each programme.
OCR D1 2010 January Q4
11 marks Moderate -0.8
4 Jack and Jill are packing food parcels. The boxes for the food parcels can each carry up to 5000 g in weight and can each hold up to \(30000 \mathrm {~cm} ^ { 3 }\) in volume. The number of each item to be packed, their dimensions and weights are given in the table below.
Item type\(A\)\(B\)\(C\)\(D\)
Number to be packed15834
Length (cm)10402010
Width (cm)10305040
Height (cm)10201010
Volume ( \(\mathrm { cm } ^ { 3 }\) )100024000100004000
Weight (g)1000250300400
Jill tries to pack the items by weight using the first-fit decreasing method.
  1. List the 30 items in order of decreasing weight and hence show Jill's packing. Explain why Jill's packing is not possible. Jack tries to pack the items by volume using the first-fit decreasing method.
  2. List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.
  3. Give another reason why a packing may not be possible.
OCR D1 2010 January Q5
16 marks Standard +0.8
5 Consider the following LP problem. $$\begin{aligned} \text { Minimise } & 2 a - 3 b + c + 18 , \\ \text { subject to } & a + b - c \geqslant 14 , \\ & - 2 a + 3 c \leqslant 50 , \\ \text { and } & a \leqslant 4 a \leqslant 5 b , \\ & a \leqslant 20 , b \leqslant 10 , c \leqslant 8 . \end{aligned}$$
  1. By replacing \(a\) by \(20 - x , b\) by \(10 - y\) and \(c\) by \(8 - z\), show that the problem can be expressed as follows. $$\begin{aligned} \text { Maximise } & 2 x - 3 y + z , \\ \text { subject to } & x + y - z \leqslant 8 , \\ & 2 x - 3 z \leqslant 66 , \\ & 4 x - 5 y \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{aligned}$$
  2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm. Explain how the choice of pivot was made and show how each row was obtained. Write down the values of \(x , y\) and \(z\) at this stage. Hence write down the corresponding values of \(a , b\) and \(c\).
  3. If, additionally, the variables \(a , b\) and \(c\) are non-negative, what additional constraints are there on the values of \(x , y\) and \(z\) ?
OCR D1 2010 January Q6
13 marks Easy -1.8
6
  1. Greatest number of arcs
    for a network with five vertices \(=\) \(\_\_\_\_\) for a network with \(n\) vertices \(=\) \(\_\_\_\_\)
  2. (a) For a network with five vertices
    maximum number of passes \(=\) \(\_\_\_\_\) maximum number of comparisons
    in the first pass \(=\) \(\_\_\_\_\) in the second pass = \(\_\_\_\_\) in the third pass = \(\_\_\_\_\) maximum total number of comparisons = \(\_\_\_\_\) (b) For a network with \(n\) vertices
    maximum total number of comparisons = \(\_\_\_\_\)
  3. M1
    Vertices in tree
    M2
    Arcs in tree
    M3
    Vertices not in tree
    A B C D E
    DE
    D
    2
    \(E\)
    		\(A B C\)
    \includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_109_220_1879_786}
    \includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_163_220_2005_786}
    \multirow{3}{*}{}
    \includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_231_220_2174_786}
    \(\boldsymbol { M 4 }\)
    Sorted list
    \(|\)
    \(D\)2\(E\)
    \(A\)3\(E\)
    \(A\)4\(C\)
    \(C\)5\(D\)
    \(B\)6\(E\)
    \(B\)7\(C\)
    \(A\)8\(B\)
    \(C\)9\(E\)
  4. \(\_\_\_\_\)
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
    (a) simple,
    (b) connected,
    (c) semi-Eulerian?
  5. 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.
  6. 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}$$
  7. Use the first-fit method to find a way to cut the pieces.
  8. 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).
  9. 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.
  10. 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}$$
  11. 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
  • \href{http://physicsandmathstutor.com}{physicsandmathstutor.com} 6
  • (continued)
    \multirow[t]{24}{*}{
    6
  • 6
  • }    		(ontnued)
    •
    OCR D1 2012 January Q1
    6 marks Easy -1.2
    1 Tom has some packages that he needs to sort into order of decreasing weight. The weights, in kg , given on the packages are as follows. $$\begin{array} { l l l l l l l l l } 3 & 6 & 2 & 6 & 5 & 7 & 1 & 4 & 9 \end{array}$$ Use shuttle sort to put the weights into decreasing order (from largest to smallest). 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. Write down the total number of passes, the total number of comparisons and the total number of swaps used.
    OCR D1 2012 January Q2
    8 marks Easy -1.3
    2 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.
    1. What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph.
    2. What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph.
    3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning.
    4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. \includegraphics[max width=\textwidth, alt={}, center]{f0ac479b-2187-4335-bcb9-c0e354145bca-2_654_887_1457_587} \includegraphics[max width=\textwidth, alt={}, center]{f0ac479b-2187-4335-bcb9-c0e354145bca-3_549_1360_324_347}
    5. Apply Dijkstra's algorithm to the copy of this network in the answer booklet to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
    6. 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.
    7. Find the weight of the least weight route that uses every arc at least once, starting at \(A\) and ending at \(F\). Explain how you reached your answer.