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 2009 June Q5
19 marks Moderate -0.3
5 Badgers is a small company that makes badges to customers' designs. Each badge must pass through four stages in its production: printing, stamping out, fixing pin and checking. The badges can be laminated, metallic or plastic. The times taken for \(\mathbf { 1 0 0 }\) badges of each type to pass through each of the stages and the profits that Badgers makes on every 100 badges are shown in the table below. The table also shows the total time available for each of the production stages.
Printing (seconds)Stamping out (seconds)Fixing pin (seconds)Checking (seconds)Profit (£)
Laminated155501004
Metallic15850503
Plastic301050201
Total time available900036002500010000
Suppose that the company makes \(x\) hundred laminated badges, \(y\) hundred metallic badges and \(z\) hundred plastic badges.
  1. Show that the printing time leads to the constraint \(x + y + 2 z \leqslant 600\). Write down and simplify constraints for the time spent on each of the other production stages.
  2. What other constraint is there on the values of \(x , y\) and \(z\) ? The company wants to maximise the profit from the sale of badges.
  3. Write down an appropriate objective function, to be maximised.
  4. Represent Badgers' problem as an initial Simplex tableau.
  5. Use the Simplex algorithm, pivoting first on a value chosen from the \(x\)-column and then on a value chosen from the \(y\)-column. Interpret your solution and the values of the slack variables in the context of the original problem.
OCR D1 2010 June Q1
14 marks Easy -1.8
1 Owen and Hari each want to sort the following list of marks into decreasing order. $$\begin{array} { l l l l l l l l l l } 31 & 28 & 75 & 87 & 42 & 43 & 70 & 56 & 61 & 95 \end{array}$$
  1. Owen uses bubble sort, starting from the left-hand end of the list.
    (a) Show the result of the first pass through the list. Record the number of comparisons and the number of swaps used in this first pass. Which marks, if any, are guaranteed to be in their correct final positions after the first pass?
    (b) Write down the list at the end of the second pass of bubble sort.
    (c) How many more passes are needed to get the value 95 to the start of the list?
  2. Hari uses shuttle sort, starting from the left-hand end of the list. Show the results of the first and the second pass through the list. Record the number of comparisons and the number of swaps used in each of these passes.
  3. Explain why, for this particular list, the total number of comparisons will be greater using bubble sort than using shuttle sort. Shuttle sort is a quadratic order algorithm.
  4. If it takes Hari 20 seconds to sort a list of ten marks using shuttle sort, approximately how long will it take Hari to sort a list of fifty marks?
OCR D1 2010 June Q2
9 marks Standard +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 it is impossible to draw a graph with exactly three vertices in which the vertex orders are 2, 3 and 4.
  2. Draw a graph with exactly four vertices of orders 1, 2, 3 and 4 that is neither simple nor connected.
  3. Explain why there is no simply connected graph with exactly four vertices of orders \(1,2,3\) and 4. State which of the properties 'simple' and 'connected' cannot be achieved.
  4. A simply connected Eulerian graph has exactly five vertices.
    (a) Explain why there cannot be exactly three vertices of order 4.
    (b) By considering the vertex orders, explain why there are only four such graphs. Draw an example of each.
OCR D1 2010 June Q3
10 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]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-03_908_915_392_614}
  1. Write down the inequalities that define the feasible region. The objective is to maximise \(P _ { 1 } = x + 6 y\).
  2. Find the values of \(x\) and \(y\) at the optimal point, and the corresponding value of \(P _ { 1 }\). The objective is changed to maximise \(P _ { k } = k x + 6 y\), where \(k\) is positive.
  3. Calculate the coordinates of the optimal point, and the corresponding value of \(P _ { k }\) when the optimal point is not the same as in part (ii).
  4. Find the range of values of \(k\) for which the point identified in part (ii) is still optimal.
OCR D1 2010 June Q4
17 marks Standard +0.3
4 The network below represents a small village. The arcs represent the streets and the weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-04_503_1179_324_482}
  1. Use Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(G\). Hannah wants to deliver newsletters along every street; she will start and end at \(A\).
  2. Which standard network problem does Hannah need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 3.7 km .
  3. Hannah knows that she will need to travel \(A B\) and \(E F\) twice, once in each direction. With this information, use an appropriate algorithm to find the length of the shortest route that Hannah can use. Show all your working. (You may find the lengths of shortest paths between vertices by inspection.) There are street name signs at each vertex except for \(A\) and \(E\). Hannah's friend Peter wants to check that the signs have not been vandalised. He will start and end at \(B\). The table below shows the complete set of shortest distances between vertices \(B , C , D , F\) and \(G\).
    \(B\)\(C\)\(D\)\(F\)\(G\)
    \(B\)-0.20.10.30.75
    \(C\)0.2-0.30.50.95
    \(D\)0.10.3-0.20.65
    \(F\)0.30.50.2-0.45
    \(G\)0.750.950.650.45-
  4. Apply the nearest neighbour method to this table, starting from \(B\), to find an upper bound for the distance that Peter must travel.
  5. Apply Prim's algorithm to the matrix formed by deleting the row and column for vertex \(G\) from the table. Start building your tree at vertex \(B\). Draw your tree. Give the order in which vertices are built into your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Peter must travel.
OCR D1 2010 June Q8
Moderate -0.8
8
4 (ii)
4 (iii)
4 (iv)
\(B\)\(C\)\(D\)\(F\)\(G\)
\(B\)-0.20.10.30.75
\(C\)0.2-0.30.50.95
\(D\)0.10.3-0.20.65
\(F\)0.30.50.2-0.45
\(G\)0.750.950.650.45-
4 (v)
\(B\)\(C\)\(D\)\(F\)
\(B\)-0.20.10.3
\(C\)0.2-0.30.5
\(D\)0.10.3-0.2
\(F\)0.30.50.2-
\(B\)
\(\bullet { } ^ { D }\)
- \({ } ^ { F }\)
\(C _ { \bullet }\)
5 (i)
5 (ii)
\multirow[t]{12}{*}{5 (ii)}(continued)
\multirow{19}{*}{5 (iii)}
\section*{PLEASE DO NOT WRITE ON THIS PAGE} RECOGNISING ACHIEVEMENT
OCR D1 2011 June Q1
6 marks Standard +0.8
1 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]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-2_885_873_388_635}
  1. Write down the inequalities that define the feasible region. The objective is to maximise \(P _ { m } = x + m y\), where \(m\) is a positive, real-valued constant.
  2. In the case when \(m = 2\), calculate the values of \(x\) and \(y\) at the optimal point, and the corresponding value of \(P _ { 2 }\).
  3. (a) Write down the values of \(m\) for which point \(A\) is optimal.
    (b) Write down the values of \(m\) for which point \(B\) is optimal.
OCR D1 2011 June Q2
8 marks Moderate -0.8
2 Consider the following algorithm.
STEP 1 Input a number \(N\) STEP 2 Calculate \(R = N \div 2\) STEP 3 Calculate \(S = ( ( N \div R ) + R ) \div 2\) STEP 4 If \(R\) and \(S\) are the same when rounded to 2 decimal places, go to STEP 7
STEP 5 Replace \(R\) with the value of \(S\) STEP 6 Go to STEP 3
STEP 7 Output the value of \(R\) correct to 2 decimal places
  1. Work through the algorithm starting with \(N = 16\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
  2. Work through the algorithm starting with \(N = 2\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
  3. What does the algorithm achieve for positive inputs?
  4. Show that the algorithm fails when it is applied to \(N = - 4\).
  5. Describe what happens when the algorithm is applied to \(N = - 2\). Suggest how the algorithm could be improved to avoid this problem, without imposing a restriction on the allowable input values.
OCR D1 2011 June Q3
9 marks Standard +0.3
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.
  1. Explain why it is impossible to draw a graph with exactly five vertices of orders \(1,2,3,4\) and 5.
  2. Explain why there is no simply connected graph with exactly five vertices of orders \(2,2,3,4\) and 5 . State which of the properties 'simple' and 'connected' cannot be achieved.
  3. Calculate the number of arcs in a simply connected graph with exactly five vertices of orders 1 , 1, 2, 2 and 4 . Hence explain why such a graph cannot be a tree.
  4. Draw a simply connected semi-Eulerian graph with exactly five vertices that is also a tree. By considering the orders of the vertices, explain why it is impossible to draw a simply connected Eulerian graph with exactly five vertices that is also a tree. In the graph below the vertices represent buildings and the arcs represent pathways between those buildings. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-4_426_1081_1297_532}
  5. By considering the orders of the vertices, explain why it is impossible to walk along these pathways in a continuous route that uses every arc once and only once. Write down the minimum number of arcs that would need to be travelled twice to walk in a continuous route that uses every arc at least once.
OCR D1 2011 June Q4
13 marks Standard +0.8
4 Consider the following LP problem.
Maximise\(P = - 3 w + 5 x - 7 y + 2 z\),
subject to\(w + 2 x - 2 y - z \leqslant 10\),
\(2 w + 3 y - 4 z \leqslant 12\),
and\(4 w + 5 x + y \leqslant 30\),
\(w \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
  1. Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the \(x\) column.
  2. Perform one iteration of the Simplex algorithm. Show how each row was obtained and write down the values of \(w , x , y , z\) and \(P\) at this stage.
  3. Perform a second iteration of the Simplex algorithm. Write down the values of \(w , x , y , z\) and \(P\) at this stage and explain how you can tell from this tableau that \(P\) can be increased without limit. How could you have known from the LP formulation above that \(P\) could be increased without limit?
OCR D1 2011 June Q5
14 marks Standard +0.3
5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438} Dijkstra's algorithm is to be used to find the shortest path from \(A\) to \(G\).
  1. Apply Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from \(A\) to \(G\) and give its length. The track joining \(B\) and \(D\) is washed away in a flood. It is replaced by a new track of unknown length, \(x \mathrm {~km}\). \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
  2. What is the smallest value that \(x\) can take so that the route found in part (i) is still a shortest path? If the value of \(x\) is smaller than this, what is the weight of the shortest path from \(A\) to \(G\) ?
  3. (a) For what values of \(x\) will vertex \(E\) have two temporary labels? Write down the values of these temporary labels.
    (b) For what values of \(x\) will vertex \(C\) have two temporary labels? Write down the values of these temporary labels. Dijkstra's algorithm has quadratic order.
  4. If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?
OCR D1 2011 June Q6
22 marks Challenging +1.8
6 The arcs in the network represent the tracks in a forest. The weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-7_535_1267_395_440} Richard wants to walk along every track in the forest. The total weight of the arcs is \(26.7 + x\).
  1. Find, in terms of \(x\), the length of the shortest route that Richard could use to walk along every track, starting at \(A\) and ending at \(G\). Show all of your working.
  2. Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at \(A\). Show that for \(x \leqslant 1.8\) this route has length \(( 32.4 + 2 x ) \mathrm { km }\), and for \(x \geqslant 1.8\) it has length \(( 34.2 + x ) \mathrm { km }\). Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at \(A\), passing through every vertex at least once. Consider first the case when \(x\) is less than 3.2.
  3. (a) Apply Prim's algorithm to the network, starting from vertex \(A\), to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
    (b) Use the nearest neighbour strategy, starting from vertex \(A\), and show that it stalls before it has visited every vertex. Now consider the case when \(x\) is greater than 3.2 but less than 4.6.
  4. (a) Draw the minimum spanning tree and state its total weight.
    (b) Use the nearest neighbour strategy, starting from vertex \(A\), to find a route from \(A\) to \(G\) passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from \(A\) to \(G\) passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.
OCR D1 2012 June Q1
9 marks Moderate -0.5
1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places). \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ccb12789-cd5f-40dc-9f10-f8bb45399580-2_712_1386_431_335} \captionsetup{labelformat=empty} \caption{Fort Effleigh (F)}
\end{figure}
  1. Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting \(A\) to \(B\) of weight 22, and also arcs connecting \(A\) to \(C , D\), and \(E\). There is no arc connecting \(A\) to \(F\) (because there is no route from \(A\) to \(F\) that does not pass through another place).
  2. Apply Dijkstra's algorithm, starting at \(A\), to find the shortest route from \(A\) to \(F\). Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ).
  3. If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.
OCR D1 2012 June Q2
9 marks Moderate -0.8
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. (a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.
    (b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.
    (c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4. A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Revision classes}
    Student numberC1C2C3C4M1M2S1S2D1D2
    1✓✓
    2✓✓
    3✓✓
    4✓✓
    5✓✓
    6✓✓
    7✓✓
    8✓✓
    9✓✓
    10✓✓
    \end{table}
  2. (a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.
    (b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session. An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.
    (c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).
OCR D1 2012 June Q3
13 marks Moderate -0.3
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]{ccb12789-cd5f-40dc-9f10-f8bb45399580-4_919_917_322_575}
  1. Obtain the four inequalities that define the feasible region.
  2. Calculate the coordinates of the vertices of the feasible region, giving your values as fractions. The objective is to maximise \(P = x + 4 y\).
  3. Calculate the value of \(P\) at each vertex of the feasible region. Hence write down the coordinates of the optimal point, and the corresponding value of \(P\). Suppose that the solution must have integer values for both \(x\) and \(y\).
  4. Find the coordinates of the optimal point with integer-valued \(x\) and \(y\), and the corresponding value of \(P\). Explain how you know that this is the optimal solution.
OCR D1 2012 June Q4
14 marks Standard +0.3
4 Consider the following linear programming problem. $$\begin{array} { l r } \text { Maximise } & P = - 5 x - 6 y + 4 z , \\ \text { subject to } & 3 x - 4 y + z \leqslant 12 , \\ & 6 x + 2 z \leqslant 20 , \\ & - 10 x - 5 y + 5 z \leqslant 30 , \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  1. Use slack variables \(s , t\) and \(u\) to rewrite the first three constraints as equations. What restrictions are there on the values of \(s , t\) and \(u\) ?
  2. Represent the problem as an initial Simplex tableau.
  3. Show why the pivot for the first iteration of the Simplex algorithm must be the coefficient of \(z\) in the third constraint.
  4. Perform one iteration of the Simplex algorithm, showing how the elements of the pivot row were calculated and how this was used to calculate the other rows.
  5. Perform a second iteration of the Simplex algorithm and record the values of \(x , y , z\) and \(P\) at the end of this iteration.
  6. Write down the values of \(s , t\) and \(u\) from your final tableau and explain what they mean in terms of the original constraints.
OCR D1 2012 June Q5
13 marks Moderate -0.5
5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.
M\(N\)\(P\)\(R\)\(S\)\(T\)\(V\)\(W\)
M-701101906019014090
N70-4013012017080150
\(P\)11040-10080140120110
\(R\)190130100-1304050160
\(S\)6012080130-1708030
\(T\)19017014040170-90200
\(V\)14080120508090-110
W9015011016030200110-
  1. Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
  2. Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
  3. Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
  4. Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight. Jess insists that they must include shop \(W\).
  5. Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.
OCR D1 2012 June Q6
14 marks Moderate -0.5
6 The following flow chart has been written to find a root of the cubic equation \(x ^ { 3 } + A x ^ { 2 } + B x + C = 0\), given a starting value \(X\) that is thought to be near the root. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-8_1410_1648_324_212}
  1. Work through the algorithm, recording the values of \(X , Y , Z\) and \(W\) each time they change, for the equation \(x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0\), with a starting value of \(X = 0\).
  2. Show what happens when the algorithm is used for the equation \(x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0\), with a starting value of \(X = 1\).
  3. Show what happens when the algorithm is used for the equation \(x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0\), with a starting value of \(X = - 1\).
  4. Identify a possible problem with using this algorithm.
OCR D1 2013 June Q1
6 marks Easy -1.8
1 The list below is to be sorted into increasing order using bubble sort, starting at the left-hand end of the list. $$\begin{array} { l l l l l l } 24 & 57 & 9 & 31 & 16 & 4 \end{array}$$
  1. Show which values are compared and which are swapped in the first pass. Write down the list that results at the end of the first pass.
  2. Without showing the individual comparisons and swaps, write down the lists that result after the second pass and after the third pass.
  3. In total there will be five passes made in carrying out bubble sort on the list. Write down how many swaps are made in each pass.
OCR D1 2013 June Q2
8 marks Moderate -0.8
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. (a) Draw a connected Eulerian graph that has exactly four vertices and five arcs but is not simple.
    (b) Explain why it is not possible to have a simply connected Eulerian graph with exactly four vertices and five arcs. A simply connected Eulerian graph is drawn that has exactly eight vertices and ten arcs.
  2. (a) Explain how you know that the sum of the vertex orders must be 20 .
    (b) Write down the minimum and maximum possible vertex order and draw a diagram that includes both the minimum and the maximum cases.
    (c) Draw a diagram to show a simply connected Eulerian graph with exactly eight vertices and ten arcs in which the number of vertices of order 4 is as large as possible.
OCR D1 2013 June Q3
10 marks Easy -1.2
3 Holly has written an algorithm.
Step 1Input two positive integers \(A\) and \(B\)
Step 2Let \(C = A - B\)
Step 3If \(C < 0\), let \(D = B\) then let \(E = B + C\)
Step 4If \(C = 0\), jump to Step 10
Step 5If \(C > 0\), let \(D = A\) and let \(E = B\)
Step 6Let \(F = D - E\)
Step 7If \(F < 0\), let \(D = E\) then let \(E = F + D\) and go back to Step 6
Step 8If \(F = 0\), let \(F = D\) then jump to Step 11
Step 9If \(F > 0\), let \(D = F\) then go back to Step 6
Step 10Let \(F = A\)
Step 11Let \(G = A \div F\)
Step 12Let \(M = G \times B\)
Step 13Print the values \(F\) and \(M\)
  1. Work through Holly's algorithm using the input values \(A = 30\) and \(B = 18\). Set out your working using the table in the answer book. Use one row for each step where any values change and only write down values when they change. Write down the values that are printed.
  2. Describe what happens when \(A = 18\) and \(B = 30\). You need only record enough rows of the table to be able to show what happens.
  3. Without doing further working, state the output values of \(F\) and \(M\) when \(A = 12\) and \(B = 8\).
OCR D1 2013 June Q4
12 marks Moderate -0.8
4 A simplified map of an area of moorland is shown below. The vertices represent farmhouses and the arcs represent the paths between the farmhouses. The weights on the arcs show distances in km. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-4_618_1420_356_319} Ted wants to visit each farmhouse and then return to his starting point.
  1. In your answer book the arcs have been sorted into increasing order of weight. Use Kruskal’s algorithm to find a minimum spanning tree for the network, and give its total weight. Hence find a route visiting each farmhouse, and returning to the starting point, which has length 82 km .
  2. Give the weight of the minimum spanning tree for the six vertices \(A , B , C , E , F , G\). Hence find a route visiting each of the seven farmhouses once, and returning to the starting point, which has length 81 km .
  3. Show that the nearest neighbour method fails to produce a cycle through every vertex when started from \(A\) but that it succeeds when started from \(B\). Adapt this cycle to find a complete cycle of total weight less than 70 , and find the total length of the shorter cycle.
OCR D1 2013 June Q5
15 marks Standard +0.3
5 This question uses the same network as question 4. The total weight of the arcs in the network is 224. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}
  1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(G\).
  2. Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.
  3. How much shorter would the path \(C E\) need to be for it to become part of a shortest path from \(A\) to \(G\) ? Following a landslip, the paths \(A C\) and \(C E\) become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
  4. Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex \(C\). Show your working.
OCR D1 2013 June Q6
21 marks Moderate -0.3
6 Consider the following linear programming problem.
Maximise\(P = 5 x + 8 y\),
subject to\(3 x - 2 y \leqslant 12\),
\(3 x + 4 y \leqslant 30\),
\(3 x - 8 y \geqslant - 24\),
\(x \geqslant 0 , y \geqslant 0\).
  1. Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
  2. Calculate the coordinates of the vertices of the feasible region, apart from the origin, and calculate the value of \(P\) at each vertex. Hence find the optimal values of \(x\) and \(y\), and state the maximum value of the objective.
  3. Suppose that, additionally, \(x\) and \(y\) must both be integers. Find the maximum feasible value of \(y\) for every feasible integer value of \(x\). Calculate the value of \(P\) at each of these points and hence find the optimal values of \(x\) and \(y\) with this additional restriction. Tom wants to use the Simplex algorithm to solve the original (non-integer) problem. He reformulates it as follows.
    Maximise\(\quad P = 5 x + 8 y\),
    subject to\(3 x - 2 y \leqslant 12\),
    \(3 x + 4 y \leqslant 30\),
    \(- 3 x + 8 y \leqslant 24\),
    \(x \geqslant 0 , y \geqslant 0\).
  4. Explain why Tom needed to change the third constraint.
  5. Represent the problem by an initial Simplex tableau.
  6. Perform one iteration of the Simplex algorithm, choosing your pivot from the \(\boldsymbol { y }\) column. Show how the pivot row was used to calculate the other rows. Write down the values of \(x , y\) and \(P\) that result from this iteration. Perform a second iteration of the Simplex algorithm to achieve the optimum point.
OCR D1 2014 June Q1
9 marks Easy -1.2
1 Sangita needs to move some heavy boxes to her new house. She has borrowed a van that can carry at most 600 kg . She will have to make several deliveries to her new house. The masses of the boxes have been recorded in kg as: $$\begin{array} { l l l l l l l l l l l } 120 & 120 & 120 & 100 & 150 & 200 & 250 & 150 & 200 & 250 & 120 \end{array}$$
  1. Use the first-fit method to show how Sangita could pack the boxes into the van. How many deliveries does this solution require?
  2. Use the first-fit decreasing method to show how Sangita could pack the boxes into the van. There is no need to use a sorting algorithm, but you should write down the sorted list before showing the packing. How many deliveries does this solution require? Sangita then realises that she cannot fit more than four boxes in the van at a time.
  3. Find a way to pack the boxes into the van so that she makes as few deliveries as possible.