Questions - OCR D1 - A-Level Maths

Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
Explain why a graph with five vertices of orders $1,2,2,3$ and 4 cannot be a tree.

OCR D1 2010 January Q2

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.

Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.
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$ - 5 3 8 2
$B$ 5 - 6 - -
$C$ 3 6 - 7 -
$D$ 8 - 7 - 9
$E$ 2 - - 9 -
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 .
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

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$$

What do the variables $x$ and $y$ represent?
Write down and simplify the constraints on the values of $x$ and $y$ from the availability of each of the pieces of apparatus.
What other constraints and restrictions apply to the values of $x$ and $y$ ?
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

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 packed	15	8	3	4
Length (cm)	10	40	20	10
Width (cm)	10	30	50	40
Height (cm)	10	20	10	10
Volume ( $\mathrm { cm } ^ { 3 }$ )	1000	24000	10000	4000
Weight (g)	1000	250	300	400

Jill tries to pack the items by weight using the first-fit decreasing method.

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.
List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.
Give another reason why a packing may not be possible.

OCR D1 2010 January Q5

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}$$

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}$$
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$.
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

Greatest number of arcs
for a network with five vertices $=$ $\_\_\_\_$
for a network with $n$ vertices $=$ $\_\_\_\_$
(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 = $\_\_\_\_$

\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$

$\_\_\_\_$

OCR D1 2011 January Q1

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}

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.
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.
Find a route on which the minimum number of traffic lights must be repeated. Explain your reasoning.

OCR D1 2011 January Q2

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$	-	12	30	15	22
	B	12	-	24	16	30
	C	30	24	-	20	25
	D	15	16	20	-	10
	E	22	30	25	10	-

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$.
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

10 marks

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.
Explain why there is no simply connected graph with exactly four vertices of orders $1,1,2$ and 4.
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.
What restrictions on the values of $a , b$ and $c$ follow from the graph being
(a) simple,
(b) connected,
(c) semi-Eulerian?
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.
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}$$
Use the first-fit method to find a way to cut the pieces.
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).
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.
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}$$
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

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 contents	Check postage	Check address
New	3	4	3
Occasional	5	3	4
Regular	2	3	3

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 .$$

What do the variables $x , y$ and $z$ represent?
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.
Explain what effect this has on the objective and simplify the constraints.
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.
Find the optimal strategy in this situation.
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

10 marks

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$.

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}$$
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

\multirow[t]{4}{*}{5 }



5










\multirow[t]{7}{*}{5 }






5

5	(continued)
$5 ( \mathrm { v } )$









5

6











6

\href{http://physicsandmathstutor.com}{physicsandmathstutor.com} 6

OCR D1 2012 January Q1

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

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.

What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph.
What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph.
What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning.
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}
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.
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.
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.

OCR D1 2012 January Q4

4 Lucy is making party bags which she will sell to raise money for charity. She has three colours of party bag: red, yellow and blue. The bags contain balloons, sweets and toys. Lucy has a stock of 40 balloons, 80 sweets and 30 toys. The table shows how many balloons, sweets and toys are needed for one party bag of each colour.

Colour of party bag	Balloons	Sweets	Toys
Red	5	3	5
Yellow	4	7	2
Blue	6	6	3

Lucy will raise $\pounds 1$ for each bag that she sells, irrespective of its colour. She wants to calculate how many bags of each colour she should make to maximise the total amount raised for charity. Lucy has started to model the problem as an LP formulation. $$\begin{array} { l l } \text { Maximise } & P = x + y + z ,
\text { subject to } & 3 x + 7 y + 6 z \leqslant 80 . \end{array}$$

What does the variable $x$ represent in Lucy's formulation?
Explain why the constraint $3 x + 7 y + 6 z \leqslant 80$ must hold and write down another two similar constraints.
What other constraints and restrictions apply to the values of $x , y$ and $z$ ?
What assumption is needed for the objective to be valid?
Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet.
Perform one iteration of the Simplex algorithm, choosing a pivot from the $\boldsymbol { x }$ column. Explain how the choice of pivot row was made and show how each row was calculated.
Write down the values of $x , y$ and $z$ from the first iteration of the Simplex algorithm and hence find the number of bags of each colour that Lucy should make according to this non-optimal tableau. In the optimal solution Lucy makes 10 bags.
Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags.

OCR D1 2012 January Q5

5 The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles. Ayr

250	Birmingham
350	103	Cardiff
235	104	209	Doncaster
446	157	121	261

$\quad$ Exeter

Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place.
List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. A sixth vertex, $F$, is added to the network. The distances, in miles, between $F$ and each of the other places are shown in the table below.
$A$ $B$ $C$ $D$ $E$
Distance from $F$ 200 50 150 59 250
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.
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.
Use the two least weight arcs through $A$ to form a least weight path of the form $S A T$, where $S$ and $T$ are two of $\{ B , C , D , E , F \}$, and give the weight of this path. Similarly write down a least weight path of the form $U E V$, where $U$ and $V$ are two of $\{ A , B , C , D , F \}$, and give the weight of this path. You should find that the two paths that you have written down use all six vertices.
Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour.

OCR D1 2012 January Q6

6 The function $\operatorname { INT } ( C )$ gives the largest integer that is less than or equal to $C$.
For example: $\operatorname { INT } ( 4.8 ) = 4 , \operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 0.8 ) = 0 , \operatorname { INT } ( - 0.8 ) = - 1 , \operatorname { INT } ( - 2.4 ) = - 3$.
Consider the following algorithm.

Line 10	Input $A$ and $B$
Line 20	Calculate $C = B \div A$
Line 30	Let $D = \operatorname { INT } ( C )$
Line 40	Calculate $E = A \times D$
Line 50	Calculate $F = B - E$
Line 60	Output the value of $F$
Line 70	Replace $B$ by the value of $D$
Line 80	If $B = 0$ then stop, otherwise go back to line 20

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.
Show what happens when the input values are $A = 10$ and $B = - 13$.

OCR D1 2013 January Q1

Use shuttle sort to put this list of values into decreasing order (from largest to smallest). $$\begin{array} { l l l l l l l l l } 18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22 \end{array}$$ Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
Suppose that some stronger boxes are available, each of which can hold at most $W \mathrm {~kg}$. Find the least value of $W$ for which only four boxes are needed. Show a packing using four of these stronger boxes.

OCR D1 2013 January Q2

2 A tetromino is a two-dimensional shape made by joining four squares edge-to-edge. Joins are along complete edges.

Represent each of the tetrominoes below by a graph in which the nodes represent the squares and two nodes are joined by an arc if the squares share a common edge. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_76_268_1206_420} \captionsetup{labelformat=empty} \caption{(A)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_208_1201_836} \captionsetup{labelformat=empty} \caption{(B)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_144_1201_1165} \captionsetup{labelformat=empty} \caption{(C)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_209_1201_1439} \captionsetup{labelformat=empty} \caption{(D)}
\end{figure}
Six simply connected graphs with four nodes are shown below. For each graph, either draw a tetromino that can be represented by the graph, as in part (i), or explain why this is not possible. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_126_1603_299} \captionsetup{labelformat=empty} \caption{(1)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_209_1603_529} \captionsetup{labelformat=empty} \caption{(2)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_125_1603_840} \captionsetup{labelformat=empty} \caption{(3)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_127_1603_1082} \captionsetup{labelformat=empty} \caption{(4)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1343} \captionsetup{labelformat=empty} \caption{(5)}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1603} \captionsetup{labelformat=empty} \caption{(6)}
\end{figure} Two tetrominoes are regarded as being the same if one can be rotated or reflected to form the other. Derek claims that each tetromino corresponds to a unique tree with four nodes, and each tree with four nodes corresponds to a unique tetromino. Derek's claim is wrong.
From the diagrams above, find:
(a) a tetromino whose graph does not correspond to a tree;
(b) two different tetrominoes whose graphs correspond to the same tree. A pentomino is a two-dimensional shape made by joining five squares edge-to-edge. Joins are along complete edges. Two pentominoes are regarded as being the same if one can be rotated or reflected to form the other. There are twelve distinct pentominoes.
When the pentominoes are represented by graphs, as in part (i), there are only four distinct graphs. Draw these four graphs.

OCR D1 2013 January Q3

3 The total weight of the arcs in the network below is 230 .
\includegraphics[max width=\textwidth, alt={}, center]{012e87d3-d157-485c-a8bc-2c59c0862f87-3_545_1394_310_331}

Apply Dijkstra's algorithm to the copy of the network in the answer book to find the least weight path from $A$ to $H$. Give the path and its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
The arc $A D$ is removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except $A D$ ) at least once.
Suppose, instead, that the arc $A D$ is available, but $\operatorname { arcs } A C$ and $C D$ are both removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except $A C$ and $C D$ ) at least once.

OCR D1 2013 January Q4

4 Pam has seven employees. When it snows they all need to be contacted by telephone.
The table shows the expected time, in minutes, that it will take Pam and her employees to contact each other.

	Pam	Alan	Bob	Caz	Dan	Ella	Fred	Gita
Pam	-	10	4	8	18	12	12	9
Alan	10	-	6	10	18	12	11	9
Bob	4	6	-	9	17	10	11	10
Caz	8	10	9	-	15	13	10	7
Dan	18	18	17	15	-	16	19	20
Ella	12	12	10	13	16	-	13	14
Fred	12	11	11	10	19	13	-	18
Gita	9	9	10	7	20	14	18	-

Use the nearest neighbour method, starting from Pam, to find a cycle through all the employees and Pam. If there is a choice of names choose the one that occurs first alphabetically. Calculate the total weight of this cycle.
Apply Prim's algorithm to the copy of the table in the answer book, starting by crossing out the row for Pam and looking down the column for Pam. List the arcs in the order in which they were chosen. Draw the resulting minimum spanning tree and calculate its total weight.
Find a lower bound for the minimum weight cycle through Pam and her seven employees by initially removing Gita from the minimum spanning tree. Pam realises that it takes less time if she splits the employees into teams.
Use the minimum spanning tree to suggest how to split the employees into two teams, so that Pam contacts the two team leaders and they each contact the members of their team. Using this solution, find the minimum elapsed time by which all the employees can be contacted.

OCR D1 2013 January Q5

5 Roland Neede, the baker, is making cupcakes. He makes three sizes of cupcake: miniature, small and standard. Miniature cupcakes are sold in boxes of 24 and each cupcake uses 3 units of topping and 2 decorations. Small cupcakes are sold in boxes of 20 and each cupcake uses 5 units of topping and 3 decorations. Standard cupcakes are sold in boxes of 12 and each cupcake uses 7 units of topping and 4 decorations. Roland has no restriction on the amount of cake mix that he uses but he only has 5000 units of topping and 3000 decorations available. Cupcakes are only sold in complete boxes, and Roland assumes that he can sell all the boxes of cupcakes that he makes. Irrespective of size, each box of cupcakes sold will give Roland a profit of $\pounds 1$. Roland wants to maximise his total profit. Let $x$ denote the number of boxes of miniature cupcakes, $y$ denote the number of boxes of small cupcakes and $z$ denote the number of boxes of standard cupcakes that Roland makes.

Construct an objective function, $P$, to be maximised.
By considering the number of units of topping used, show that $18 x + 25 y + 21 z \leqslant 1250$.
Construct a similar constraint by considering the number of decorations used, simplifying the coefficients so that they are integers with no common factor.
Set up an initial Simplex tableau to represent Roland's problem.
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.
Write down the values of $x , y$ and $z$ from the first iteration of the Simplex algorithm. Hence find the maximum profit that Roland can make, remembering that cupcakes can only be sold in complete boxes. Calculate the number of units of topping and the number of decorations that are left over with this solution.
The constraint from the number of units of topping can be rewritten as $18 P + 7 y + 3 z \leqslant 1250$. Form a similar expression for the constraint from the number of decorations. Use this to find the number of boxes of small cupcakes which maximises the profit when there are no decorations left over. Find the solution which gives the maximum profit using all the topping and all the decorations, and find the values of $x , y$ and $z$ for this solution. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}

OCR D1 2005 June Q1

1. Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg . $$\begin{array} { l l l l l l l l l l } 2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3 \end{array}$$
2. Find a packing that uses fewer bags.
The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

OCR D1 2005 June Q2

2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.

Draw a simple graph that connects four vertices using five arcs.
Explain why, in any graph, there must be an even number of odd vertices.
By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.

OCR D1 2005 June Q3

3 This diagram shows a network.
\includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}

Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
Use the nearest neighbour method, starting from vertex $A$, to find a cycle that passes through every vertex. The network represents a cubical die, with vertices labelled $A$ to $H$, and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
(a) List the vertices of each of the two faces that meet in the edge $A G$.
(b) What number is on the face $A C E G$ ?
(c) Which face is numbered 3?

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
\(A\)	-	5	3	8	2
\(B\)	5	-	6	-	-
\(C\)	3	6	-	7	-
\(D\)	8	-	7	-	9
\(E\)	2	-	-	9	-


\(D\)	2	\(E\)
\(A\)	3	\(E\)
\(A\)	4	\(C\)
\(C\)	5	\(D\)
\(B\)	6	\(E\)
\(B\)	7	\(C\)
\(A\)	8	\(B\)
\(C\)	9	\(E\)

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\).

\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
Distance from \(F\)	200	50	150	59	250

Line 10	Input \(A\) and \(B\)
Line 20	Calculate \(C = B \div A\)
Line 30	Let \(D = \operatorname { INT } ( C )\)
Line 40	Calculate \(E = A \times D\)
Line 50	Calculate \(F = B - E\)
Line 60	Output the value of \(F\)
Line 70	Replace \(B\) by the value of \(D\)
Line 80	If \(B = 0\) then stop, otherwise go back to line 20

\(\boldsymbol { M 4 }\)
Sorted list

Questions — OCR D1 (124 questions)

Browse by module

Browse by board

OCR D1 2009 January Q2

OCR D1 2010 January Q2

OCR D1 2010 January Q3

OCR D1 2010 January Q4

OCR D1 2010 January Q5

OCR D1 2010 January Q6

OCR D1 2011 January Q1

OCR D1 2011 January Q2

OCR D1 2011 January Q3

OCR D1 2011 January Q5

OCR D1 2011 January Q6

OCR D1 2011 January Q8

OCR D1 2012 January Q1

OCR D1 2012 January Q2

OCR D1 2012 January Q4

OCR D1 2012 January Q5

OCR D1 2012 January Q6

OCR D1 2013 January Q1

OCR D1 2013 January Q2

OCR D1 2013 January Q3

OCR D1 2013 January Q4

OCR D1 2013 January Q5

OCR D1 2005 June Q1

OCR D1 2005 June Q2

OCR D1 2005 June Q3