Questions D1 (932 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
OCR D1 2008 January Q5
12 marks Moderate -0.8
Mark wants to decorate the walls of his study. The total wall area is 24 m\(^2\). Mark can cover the walls using any combination of three materials: panelling, paint and pinboard. He wants at least 2 m\(^2\) of pinboard and at least 10 m\(^2\) of panelling. Panelling costs £8 per m\(^2\) and it will take Mark 15 minutes to put up 1 m\(^2\) of panelling. Paint costs £4 per m\(^2\) and it will take Mark 30 minutes to paint 1 m\(^2\). Pinboard costs £10 per m\(^2\) and it will take Mark 20 minutes to put up 1 m\(^2\) of pinboard. He has all the equipment that he will need for the decorating jobs. Mark is able to spend up to £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: $$x + y + z = 24,$$ $$4x + 2y + 5z \leqslant 75,$$ $$x \geqslant 10,$$ $$y \geqslant 0,$$ $$z \geqslant 2.$$
  1. Identify the meaning of each of the variables \(x\), \(y\) and \(z\). [2]
  2. Show how the constraint \(4x + 2y + 5z \leqslant 75\) was formed. [2]
  3. Write down an objective function, to be minimised. [1]
Mark rewrites the first constraint as \(z = 24 - x - y\) and uses this to eliminate \(z\) from the problem.
  1. Rewrite and simplify the objective and the remaining four constraints as functions of \(x\) and \(y\) only. [3]
  2. Represent your constraints from part (iv) graphically and identify the feasible region. Your graph should show \(x\) and \(y\) values from 0 to 15 only. [4]
OCR D1 2008 January Q6
13 marks Moderate -0.3
  1. Represent the linear programming problem below by an initial Simplex tableau. [2] Maximise \quad \(P = 25x + 14y - 32z\), subject to \quad \(6x - 4y + 3z \leqslant 24\), \qquad\qquad\quad \(5x - 3y + 10z \leqslant 15\), and \qquad\qquad \(x \geqslant 0\), \(y \geqslant 0\), \(z \geqslant 0\).
  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]
  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. [7]
  4. Explain why the Simplex algorithm cannot be used to find the optimal value of \(P\) for this problem. [1]
OCR D1 2008 January Q7
13 marks Moderate -0.8
In this question, the function INT(\(X\)) is the largest integer less than or equal to \(X\). For example, $$\text{INT}(3.6) = 3,$$ $$\text{INT}(3) = 3,$$ $$\text{INT}(-3.6) = -4.$$ Consider the following algorithm. \begin{align} \text{Step 1} \quad & \text{Input } B
\text{Step 2} \quad & \text{Input } N
\text{Step 3} \quad & \text{Calculate } F = N \div B
\text{Step 4} \quad & \text{Let } G = \text{INT}(F)
\text{Step 5} \quad & \text{Calculate } H = B \times G
\text{Step 6} \quad & \text{Calculate } C = N - H
\text{Step 7} \quad & \text{Output } C
\text{Step 8} \quad & \text{Replace } N \text{ by the value of } G
\text{Step 9} \quad & \text{If } N = 0 \text{ then stop, otherwise go back to Step 3} \end{align}
  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. [5]
  2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = -5\). [4]
  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? [4]
OCR D1 2012 January Q1
6 marks Easy -1.8
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. 3 \quad 6 \quad 2 \quad 6 \quad 5 \quad 7 \quad 1 \quad 4 \quad 9 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. [6]
OCR D1 2012 January Q2
8 marks Moderate -0.8
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]
  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. [2]
  3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning. [2]
  4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. [2]
\includegraphics{figure_2}
OCR D1 2012 January Q3
13 marks Moderate -0.8
\includegraphics{figure_3}
  1. 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. [6]
In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
  1. 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. [3]
  2. 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. [4]
OCR D1 2012 January Q4
18 marks Moderate -0.8
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 £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. Maximise \quad \(P = x + y + z\), subject to \quad \(3x + 7y + 6z \leq 80\).
  1. What does the variable \(x\) represent in Lucy's formulation? [1]
  2. Explain why the constraint \(3x + 7y + 6z \leq 80\) must hold and write down another two similar constraints. [3]
  3. What other constraints and restrictions apply to the values of \(x\), \(y\) and \(z\)? [1]
  4. What assumption is needed for the objective to be valid? [1]
  5. Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet. [3]
  6. 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]
  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. [2]
In the optimal solution Lucy makes 10 bags.
  1. Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags. [1]
OCR D1 2012 January Q5
18 marks Moderate -0.8
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
446157121261Exeter
  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]
  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. [4]
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.
ABCDE
Distance from F2005015059250
  1. 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. [2]
  2. 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. [2]
  3. Use the two least weight arcs through A to form a least weight path of the form \(SAT\), 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 \(UEV\), 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. [8]
OCR D1 2012 January Q6
9 marks Easy -1.2
The function INT(\(C\)) gives the largest integer that is less than or equal to \(C\). For example: INT(4.8) = 4, INT(7) = 7, INT(0.8) = 0, INT(−0.8) = −1, INT(−2.4) = −3. Consider the following algorithm. Line 10 \quad Input \(A\) and \(B\) Line 20 \quad Calculate \(C = B \div A\) Line 30 \quad Let \(D =\) INT(\(C\)) Line 40 \quad Calculate \(E = A \times D\) Line 50 \quad Calculate \(F = B - E\) Line 60 \quad Output the value of \(F\) Line 70 \quad Replace \(B\) by the value of \(D\) Line 80 \quad If \(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. [4]
  2. Show what happens when the input values are \(A = 10\) and \(B = -13\). [5]
OCR D1 2009 June Q1
8 marks Easy -1.3
The memory requirements, in KB, for eight computer files are given below. 43 \quad 172 \quad 536 \quad 17 \quad 314 \quad 462 \quad 220 \quad 231 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. [3]
  2. Use the first-fit decreasing method to group the files into folders. [3]
First-fit decreasing is a quadratic order algorithm.
  1. 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? [2]
OCR D1 2009 June Q2
9 marks Easy -1.2
  1. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3. [1]
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.
    1. Draw a graph with five vertices of orders 1, 1, 2, 2 and 4 that is neither simple nor connected. [2]
    2. Explain why your graph from part (a) is not semi-Eulerian. [1]
    3. Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. [1]
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.
    1. Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour. [2]
    2. 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. [2]
OCR D1 2009 June Q3
11 marks Moderate -0.8
The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics{figure_3}
  1. Write down the inequalities that define the feasible region. [4]
  2. Write down the coordinates of the three vertices of the feasible region. [2]
The objective is to maximise \(2x + 3y\).
  1. Find the values of \(x\) and \(y\) at the optimal point, and the corresponding maximum value of \(2x + 3y\). [3]
The objective is changed to maximise \(2x + ky\), where \(k\) is positive.
  1. Find the range of values of \(k\) for which the optimal point is the same as in part (iii). [2]
OCR D1 2009 June Q4
25 marks Moderate -0.3
Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton (A). The arcs represent the roads and the weights on the arcs represent distances in miles. \includegraphics{figure_4}
  1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from A to H. 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 H and give its length in miles. [7]
Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.
  1. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? [1]
The total weight of all the arcs is 67.5 miles.
  1. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) [5]
Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from A and ending at H.
  1. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? [2]
There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.
  1. Show that the nearest neighbour method fails on this network if it is started from A. [1]
  2. Apply the nearest neighbour method starting from C to find an upper bound for the distance that Amber must travel. [3]
  3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node A and all the arcs that are directly joined to node A. Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel. [6]
OCR D1 2009 June Q5
19 marks Standard +0.3
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 100 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 + 2z \leq 600\). Write down and simplify constraints for the time spent on each of the other production stages. [4]
  2. What other constraint is there on the values of \(x\), \(y\) and \(z\)? [1]
The company wants to maximise the profit from the sale of badges.
  1. Write down an appropriate objective function, to be maximised. [1]
  2. Represent Badgers' problem as an initial Simplex tableau. [4]
  3. 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. [9]
OCR MEI D1 2007 January Q1
8 marks Easy -1.3
Each of the following symbols consists of boundaries enclosing regions. \includegraphics{figure_1} The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics{figure_2} is \(\bullet \longrightarrow \bullet \longrightarrow \bullet\).
  1. Produce the graph for the symbol \includegraphics{figure_3}. [1]
  2. Give two symbols each having the graph \(\bullet \longrightarrow \bullet\). [2]
  3. Produce the graph for the symbol \includegraphics{figure_4}. [2]
  4. Produce a single graph for the composite symbol \includegraphics{figure_5}. [2]
  5. Give the name of a connected graph with \(n\) nodes and \(n - 1\) arcs. [1]
OCR MEI D1 2007 January Q2
8 marks Easy -1.2
The following algorithm is a version of bubble sort. Step 1 \quad Store the values to be sorted in locations L(1), L(2), \(\ldots\) , L(n) and set i to be the number, n, of values to be sorted. Step 2 \quad Set j = 1. Step 3 \quad Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is larger than that in L(j+1). Step 4 \quad Add 1 to j. Step 5 \quad If j is less than i then go to step 3. Step 5 \quad Write out the current list, L(1), L(2), \(\ldots\) , L(n). Step 6 \quad Subtract 1 from i. Step 7 \quad If i is larger than 1 then go to step 2. Step 8 \quad Stop.
  1. Apply this algorithm to sort the following list. 109 \quad 32 \quad 3 \quad 523 \quad 58. Count the number of comparisons and the number of swaps which you make in applying the algorithm. [4]
  2. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number. [2]
  3. Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100 000 values? (Give your answer in hours and minutes.) [2]
OCR MEI D1 2007 January Q3
8 marks Easy -1.2
A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
  1. Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work. [3]
  2. Use the random numbers in your answer book to run your simulation 5 times, recording your results. [2]
  3. From your results compute an estimate of the mean number of draws needed to get a vowel. [2]
  4. State how you could produce a more accurate estimate. [1]
OCR MEI D1 2007 January Q4
16 marks Moderate -0.8
Cassi is managing the building of a house. The table shows the major activities that are involved, their durations and their precedences.
ActivityDuration (days)Immediate predecessors
ABuild concrete frame10\(-\)
BLay bricks7A
CLay roof tiles10A
DFirst fit electrics5B
EFirst fit plumbing4B
FPlastering6C, D, E
GSecond fit electrics3F
HSecond fit plumbing2F
ITiling10G, H
JFit sanitary ware2H
KFit windows and doors5I
  1. Draw an activity-on-arc network to represent this information. [5]
  2. Find the early time and the late time for each event. Give the project duration and list the critical activities. [6]
  3. Calculate total and independent floats for each non-critical activity. [2]
Cassi's clients wish to take delivery in 42 days. Some durations can be reduced, at extra cost, to achieve this.
  • The tiler will finish activity I in 9 days for an extra £250, or in 8 days for an extra £500.
  • The bricklayer will cut his total of 7 days on activity B by up to 3 days at an extra cost of £350 per day.
  • The electrician could be paid £300 more to cut a day off activity D, or £600 more to cut two days.
  1. What is the cheapest way in which Cassi can get the house built in 42 days? [3]
OCR MEI D1 2007 January Q5
16 marks Moderate -0.8
Leone is designing her new garden. She wants to have at least 1000 m\(^2\), split between lawn and flower beds. Initial costs are £0.80 per m\(^2\) for lawn and £0.40 per m\(^2\) for flowerbeds. Leone's budget is £500. Leone prefers flower beds to lawn, and she wants the area for flower beds to be at least twice the area for lawn. However, she wants to have at least 200 m\(^2\) of lawn. Maintenance costs each year are £0.15 per m\(^2\) for lawn and £0.25 per m\(^2\) for flower beds. Leone wants to minimize the maintenance costs of her garden.
  1. Formulate Leone's problem as a linear programming problem. [7]
  2. Produce a graph to illustrate the inequalities. [6]
  3. Solve Leone's problem. [2]
  4. If Leone had more than £500 available initially, how much extra could she spend to minimize maintenance costs? [1]
OCR MEI D1 2007 January Q6
16 marks Moderate -0.3
In a factory a network of pipes connects 6 vats, A, B, C, D, E and F. Two separate connectors need to be chosen from the network The table shows the lengths of pipes (metres) connecting the 6 vats.
ABCDEF
A\(-\)7\(-\)\(-\)12\(-\)
B7\(-\)5366
C\(-\)5\(-\)847
D\(-\)38\(-\)15
E12641\(-\)7
F\(-\)6757\(-\)
  1. Use Kruskal's algorithm to find a minimum connector. Show the order in which you select pipes, draw your connector and give its total length. [5]
  2. Produce a new table excluding the pipes which you selected in part (i). Use the tabular form of Prim's algorithm to find a second minimum connector from this reduced set of pipes. Show your working, draw your connector and give its total length. [7]
  3. The factory manager prefers the following pair of connectors: \(\{\)AB, BC, BD, BE, BF\(\}\) and \(\{\)AE, BF, CE, DE, DF\(\}\). Give two possible reasons for this preference. [4]
Edexcel D1 Q1
6 marks Standard +0.3
  1. Draw the complete graph \(K_5\). [1 mark]
  2. Demonstrate that no planar drawing is possible for \(K_5\). [2 marks]
  3. Draw the complete graph \(K_{3,3}\). [1 mark]
  4. Demonstrate that no planar drawing is possible for \(K_{3,3}\). [2 marks]
Edexcel D1 Q2
7 marks Moderate -0.8
A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.
ActivityDepends onDuration (hours)
\(A\)\(-\)5
\(B\)\(A\)4
\(C\)\(A\)2
\(D\)\(B, C\)11
\(E\)\(C\)4
\(F\)\(D\)3
\(G\)\(D\)8
\(H\)\(D, E\)2
\(I\)\(F\)1
\(J\)\(F, G, H\)7
\(K\)\(I, J\)2
Draw an activity network for the project. You should number the nodes and use as few dummies as possible. [7 marks]
Edexcel D1 Q3
9 marks Easy -1.2
A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$150 \quad 104 \quad 200 \quad 60 \quad 184 \quad 84 \quad 120$$
  1. Perform a quick sort to put the seven lengths in descending order. [4 marks]
The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
  1. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
  2. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]
Edexcel D1 Q4
10 marks Moderate -0.5
This question should be answered on the sheet provided. \includegraphics{figure_1} Figure 1 above shows distances in miles between 10 cities. Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:
  1. the order in which you labelled the vertices,
  2. how you used your labelled diagram to find the shortest route. [10 marks]
Edexcel D1 Q5
12 marks Moderate -0.5
This question should be answered on the sheet provided. \includegraphics{figure_2} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.
  1. Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected. [4 marks]
  2. It is decided that a Greek translation is not needed. Find the minimum cost if:
    1. translations to and from Greek are not available,
    2. translations to and from Greek are still available. [3 marks]
  3. Comment on your findings. [1 mark]
Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.
  1. How would you overcome the problem of having different costs for reverse translations? [1 mark]
  2. What algorithm would be suitable to find a computerised solution. [1 mark]
  3. State another assumption you have made in answering this question and comment on its validity. [2 marks]