Questions - OCR D1 - A-Level Maths

Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path from $A$ to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. Find the route of the shortest path from $A$ to $G$. The total weight of the arcs is 120 kilometres.
By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at $A$. You should explain your method.
Find the length of a shortest route that uses every road starting at $A$ and ending at $G$. You should explain your method.

OCR D1 2005 June Q5

5 Consider the following algorithm which is to be applied to a list of numbers.

Step 1

Let $N = 0 , T = 0$ and $S = 0$.

Step 2

Input the first number in the list and call it $X$.

Delete the first number from the list to give a list that has one number fewer than before.

Step 3

Increase $N$ by 1 , increase $T$ by $X$ and increase $S$ by $X ^ { 2 }$.

Step 4

If there are still numbers in the list then go back to Step 2. Otherwise go to Step 5.

Step 5

Calculate $M = ( T$ divided by $N )$.

Calculate $V = ( S$ divided by $N ) - ( M$ squared $)$.

Calculate $D = \sqrt { } V$.

Step 6

Output $M$ and $D$.

Apply the algorithm to this list. $$\begin{array} { l l l l l } 3 & 6 & 5 & 7 & 3 \end{array}$$ Record in a table the values of $X , N , T$ and $S$ at each pass through Step 3 and give the output values.
Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.
Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of $n$ numbers.
The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?

OCR D1 2006 June Q1

Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?

OCR D1 2006 June Q2

Draw three mathematically different graphs, labelled graph $A$, graph $B$ and graph $C$, each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
Explain how you know that none of the graphs from part (i) is Eulerian.

OCR D1 2006 June Q3

3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516} Alf wants to cycle from his home at $A$ to visit each of the other villages and return to $A$ in the shortest possible time.

Which standard network problem does Alf need to solve to find the quickest tour through all the villages?
Apply the nearest neighbour method starting at $A$ to find a tour through all the villages that starts and ends at $A$. Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?
Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex $A$ and all the arcs that are directly joined to $A$. Start building your tree at vertex $B$. (You do not need to represent the network as a matrix.) Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.
Write down a route for Alf that would take him 125 minutes.

OCR D1 2006 June Q4

4 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries.
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-03_1025_826_374_657}

Write down inequalities that define the feasible region.
Find the coordinates of the four vertices of the feasible region. The objective is to maximise $P$, where $P = x + 2 y$.
Find the values of $x$ and $y$ that maximise $P$, and the corresponding maximum value of $P$. The objective is changed to minimise $Q$, where $Q = 2 x - y$.
Find the minimum value of $Q$ and describe the set of feasible points for which $Q$ takes this value.
Show that there are no points in the feasible region for which the value of $P$ is the same as the value of $Q$.

OCR D1 2006 June Q5

5 Consider the linear programming problem:

maximise	$P = x - 2 y - 3 z$,
subject to	$2 x - 5 y + 2 z \leqslant 10$,
	$2 x \quad + 3 z \leqslant 30$,
and	$x \geqslant 0 , y \geqslant 0 , z \geqslant 0$.

Using slack variables, $s \geqslant 0$ and $t \geqslant 0$, express the two non-trivial constraints as equations.
Represent the problem as an initial Simplex tableau.
Explain why the pivot element must be chosen from the $x$-column and show the calculations that are used to choose the pivot.
Perform one iteration of the Simplex algorithm. Show how you obtained each row of your tableau and write down the values of $x , y , z$ and $P$ that result from this iteration. State whether or not this is the maximum feasible value of $P$ and describe how you know this from the values in the tableau.

OCR D1 2006 June Q12

12 JUNE 2006
Afternoon
1 hour 30 minutes

This insert should be used to answer Question 6.
Write your name, centre number and candidate number in the spaces provided at the top of this page.
Write your answers to Question 6 in the spaces provided in this insert, and attach it to your answer booklet.

Key:
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_193_949_214_712} Do not cross out your working values (temporary labels)
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_1157_1600_648_303} Route of shortest path from $A$ to $J =$ $\_\_\_\_$
Length of shortest path from $A$ to $J =$ $\_\_\_\_$ metres
1. $\_\_\_\_$
  Shortest distance $=$ $\_\_\_\_$ metres
2. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-11_979_1429_276_440}
  Shortest distance = $\_\_\_\_$ metres

OCR D1 2007 June Q1

1 Two graphs A and B are shown below. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_339_585_333_386} \captionsetup{labelformat=empty} \caption{Graph $A$}

\end{figure} \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_337_579_333_1174} \captionsetup{labelformat=empty} \caption{Graph B}

\end{figure}

Write down an example of a cycle on graph A .
W hy is $\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }$ not a path on graph B ?
How many arcs would there be in a spanning tree for graph A ?
For each graph state whether it is Eulerian, semi-Eulerian or neither.
The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?

OCR D1 2007 June Q2

2 A landscape gardener is designing a garden. Part of the garden will be decking, part will be flowers and the rest will be grass. Let d be the area of decking, f be the area of flowers and g be the area of grass, all measured in $\mathrm { m } ^ { 2 }$. The total area of the garden is $120 \mathrm {~m} ^ { 2 }$ of which at least $40 \mathrm {~m} ^ { 2 }$ must be grass. The area of decking must not be greater than the area of flowers. Also, the area of grass must not be more than four times the area of decking. Each square metre of grass will cost $\pounds 5$, each square metre of decking will cost $\pounds 10$ and each square metre of flowers will cost $\pounds 20$. These costs include labour. The landscape gardener has been instructed to come up with the design that will cost the least.

Write down a constraint in d , f and g from the total area of the garden.
Explain why the constraint $\mathrm { g } \leqslant 4 \mathrm {~d}$ is required.
Write down a constraint from the requirement that the area of decking must not be greater than the area of flowers.
Write down a constraint from the requirement that at least $40 \mathrm {~m} ^ { 2 }$ of the garden must be grass and write down the minimum feasible values for each of $d$ and $f$.
Write down the objective function to be minimised.
Write down the resulting LP problem, using slack variables to express the constraints from parts (ii) and (iii) as equations.
(You are not required to solve the resulting LP problem.)

OCR D1 2007 June Q3

Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step. Step 1: Input the original list and call it list A.
Step 2: Remove the first item in list $A$ and call this item $X$.
Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
Step 5: If there are still items in list A, repeat Step 4.
Step 6: Count the number of items in list $\mathbf { B }$ and call this $\mathbf { N }$.
Step 7: Put the items in list B at positions 1 to N of list A, item X at position $\mathrm { N } + 1$ of list A and the items in list C at positions $\mathrm { N } + 2$ onwards of list A.
Step 8: Display list A.

OCR D1 2007 June Q4

4 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 3 x - 5 y ,
\text { subject to } & x + 5 y \leqslant 12 ,
& x - 5 y \leqslant 10 ,
& 3 x + 10 y \leqslant 45 ,
\text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$

Represent the problem as an initial Simplex tableau.
Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
Perform oneiteration of the Simplex algorithm. Write down the values of $\mathrm { x } , \mathrm { y }$ and P after this iteration.
Show that $\mathrm { x } = 11 , \mathrm { y } = 0.2$ is a feasible solution and that it gives a bigger value of P than that in part (iii).

OCR D1 2009 June Q1

1 The memory requirements, in KB , for eight computer files are given below. $$\begin{array} { l l l l l l l l } 43 & 172 & 536 & 17 & 314 & 462 & 220 & 231 \end{array}$$ The files are to be grouped into folders. No folder is to contain more than 1000 KB , so that the folders are small enough to transfer easily between machines.

Use the first-fit method to group the files into folders.
Use the first-fit decreasing method to group the files into folders. First-fit decreasing is a quadratic order algorithm.
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?
Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.
(a) Draw a graph with five vertices of orders $1,1,2,2$ and 4 that is neither simple nor connected.
(b) Explain why your graph from part (a) is not semi-Eulerian.
(c) Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.
(a) Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour.
(b) Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour.

OCR D1 2009 June Q3

3 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries.
\includegraphics[max width=\textwidth, alt={}, center]{fe06fa02-9f5d-4082-8e96-feea705d3fa2-3_933_935_397_605}

Write down the inequalities that define the feasible region.
Write down the coordinates of the three vertices of the feasible region. The objective is to maximise $2 x + 3 y$.
Find the values of $x$ and $y$ at the optimal point, and the corresponding maximum value of $2 x + 3 y$. The objective is changed to maximise $2 x + k y$, where $k$ is positive.
Find the range of values of $k$ for which the optimal point is the same as in part (iii).

OCR D1 2009 June Q5

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 (£)
Laminated	15	5	50	100	4
Metallic	15	8	50	50	3
Plastic	30	10	50	20	1
Total time available	9000	3600	25000	10000

Suppose that the company makes $x$ hundred laminated badges, $y$ hundred metallic badges and $z$ hundred plastic badges.

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.
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.
Write down an appropriate objective function, to be maximised.
Represent Badgers' problem as an initial Simplex tableau.
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

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

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

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 it is impossible to draw a graph with exactly three vertices in which the vertex orders are 2, 3 and 4.
Draw a graph with exactly four vertices of orders 1, 2, 3 and 4 that is neither simple nor connected.
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.
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

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}

Write down the inequalities that define the feasible region. The objective is to maximise $P _ { 1 } = x + 6 y$.
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.
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).
Find the range of values of $k$ for which the point identified in part (ii) is still optimal.

OCR D1 2010 June Q4

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}

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$.
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 .
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.2 0.1 0.3 0.75
$C$ 0.2 - 0.3 0.5 0.95
$D$ 0.1 0.3 - 0.2 0.65
$F$ 0.3 0.5 0.2 - 0.45
$G$ 0.75 0.95 0.65 0.45 -
Apply the nearest neighbour method to this table, starting from $B$, to find an upper bound for the distance that Peter must travel.
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

4 (ii)




4 (iii)

4 (iv)

	$B$	$C$	$D$	$F$	$G$
$B$	-	0.2	0.1	0.3	0.75
$C$	0.2	-	0.3	0.5	0.95
$D$	0.1	0.3	-	0.2	0.65
$F$	0.3	0.5	0.2	-	0.45
$G$	0.75	0.95	0.65	0.45	-

4 (v)

	$B$	$C$	$D$	$F$
$B$	-	0.2	0.1	0.3
$C$	0.2	-	0.3	0.5
$D$	0.1	0.3	-	0.2
$F$	0.3	0.5	0.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

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}

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.
In the case when $m = 2$, calculate the values of $x$ and $y$ at the optimal point, and the corresponding value of $P _ { 2 }$.
(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

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

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.
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.
What does the algorithm achieve for positive inputs?
Show that the algorithm fails when it is applied to $N = - 4$.
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

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 it is impossible to draw a graph with exactly five vertices of orders $1,2,3,4$ and 5.
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.
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.
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}
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

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

Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the $x$ column.
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.
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

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

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

maximise	\(P = x - 2 y - 3 z\),
subject to	\(2 x - 5 y + 2 z \leqslant 10\),
	\(2 x \quad + 3 z \leqslant 30\),
and	\(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).

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

	\(B\)	\(C\)	\(D\)	\(F\)	\(G\)
\(B\)	-	0.2	0.1	0.3	0.75
\(C\)	0.2	-	0.3	0.5	0.95
\(D\)	0.1	0.3	-	0.2	0.65
\(F\)	0.3	0.5	0.2	-	0.45
\(G\)	0.75	0.95	0.65	0.45	-

Questions — OCR D1 (124 questions)

Browse by module

Browse by board

OCR D1 2005 June Q4

OCR D1 2005 June Q5

OCR D1 2006 June Q1

OCR D1 2006 June Q2

OCR D1 2006 June Q3

OCR D1 2006 June Q4

OCR D1 2006 June Q5

OCR D1 2006 June Q12

OCR D1 2007 June Q1

OCR D1 2007 June Q2

OCR D1 2007 June Q3

OCR D1 2007 June Q4

OCR D1 2009 June Q1

OCR D1 2009 June Q3

OCR D1 2009 June Q5

OCR D1 2010 June Q1

OCR D1 2010 June Q2

OCR D1 2010 June Q3

OCR D1 2010 June Q4

OCR D1 2010 June Q8

OCR D1 2011 June Q1

OCR D1 2011 June Q2

OCR D1 2011 June Q3

OCR D1 2011 June Q4

OCR D1 2011 June Q5