OCR Further Discrete (Further Discrete) 2018 September

1 The design for the lines on a playing area for a game is shown below. The letters are not part of the design.
\includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-2_350_855_388_605} Priya paints the lines by pushing a machine. When she is pushing the machine she is about a metre behind the point being painted. She must not duplicate any line by painting it twice.

• To relocate the machine, it must be stopped and then started again to continue painting the lines.
• When the machine is being relocated it must still be pushed along the lines of the design, and not 'cut across' on a diagonal for example.
• The machine can be turned through \(90 ^ { \circ }\) without having to be stopped.
  1. What is the minimum number of times that the machine will need to be started to paint the design?

The design is horizontally and vertically symmetric. $$\mathrm { AB } = 6 \text { metres, } \mathrm { AE } = 26 \text { metres, } \mathrm { AF } = 1.5 \text { metres and } \mathrm { AS } = 9 \text { metres. }$$

(a) Find the minimum distance that Priya needs to walk to paint the design. You should show enough working to make your reasoning clear but you do not need to use an algorithmic method.
(b) Why, in practice, will the distance be greater than this?
(c) What additional information would you need to calculate a more accurate shortest distance?

2 A list is used to demonstrate how different sorting algorithms work.
After two passes through shuttle sort the resulting list is $$\begin{array} { l l l l l l l } 17 & 23 & 84 & 21 & 66 & 35 & 12 \end{array}$$

1. How many different possibilities are there for the original list? Suppose, instead, that the same sort was carried out using bubble sort on the original list.
2. Write down the list after two passes through bubble sort. The number of comparisons made is used as a measure of the run-time for a sorting algorithm.
3. For a list of six values, what is the maximum total number of comparisons made in the first two passes of
   (a) shuttle sort
   (b) bubble sort? Steve used both shuttle sort and bubble sort on a list of five values. He says that shuttle sort is more efficient than bubble sort because it made fewer comparisons in the first two passes.
4. Comment on what Steve said. The number of comparisons made when shuttle sort and bubble sort are used to sort every permutation of a list of four values is shown in the table below.

   	Number of comparisons	3	4	5	6
   Shuttle sort	Number of permutations	2	6	8	8
   Bubble sort	Number of permutations	1	0	7	16

5. Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.

3 The pay-off matrix for a zero-sum game is

1. Show that the game does not have a stable solution.
2. Use a graphical technique to find the optimal mixed strategy for the player on columns.
3. Formulate an initial simplex tableau for the problem of finding the optimal mixed strategy for the player on rows.

4 A project is represented by the activity network below. The times are in days.
\includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-4_384_935_1110_566}

1. Explain the reason for each dummy activity.
2. Calculate the early and late event times.
3. Identify the critical activities.
4. Calculate the independent float and interfering float on activity A .
5. (a) Draw a cascade chart to represent the project, using the grid in the Printed Answer Booklet.
   (b) Describe the effect on
   • the project completion
   • the critical activities
     if the duration of activity D is increased by 5 days.
   The number of workers needed for each activity is shown below.

   Activity	A	B	C	D	E	F	G	H
   Workers	2	1	1	2	1	1	1	1

   The project needs to be completed in at most 3 weeks ( 21 days).
   The duration of activity D is 9 days.
6. Find the minimum number of workers needed. You should explain your reasoning carefully.

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF }
\text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1
& \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5
& \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 ,
& \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

1. Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables \(\mathrm { AB } , \mathrm { AC } , \ldots\) correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
2. Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
3. Explain what is ensured by the constraint \(\mathrm { AB } + \mathrm { AC } \geqslant 1\). Julie claims that the solution to the problem will give the minimum spanning tree for the network.
4. Find the minimum spanning tree for the network.
   • State the algorithm you have used.
   • Show your method clearly.
   • Draw the tree.
   • State the total weight of the tree.
   • Find the solution to the problem given at the start of the question.
   • You do not need to use a formal method.
   • Draw the arcs in the solution.
   • State the minimum value of the objective function.
   Kim has a different network, exactly one of the arcs in this network is a directed arc.
   Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
5. Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

6 Kai mixes hot drinks using coffee and steamed milk.
The amounts ( ml ) needed and profit ( \(\pounds\) ) for a standard sized cup of four different drinks are given in the table. The table also shows the amount of the ingredients available. Kai makes the equivalent of \(w\) standard sized americanos, \(x\) standard sized cappuccinos, \(y\) standard sized flat whites and \(z\) standard sized lattes. He can make different sized drinks so \(w , x , y , z\) need not be integers. Kai wants to find the maximum profit that he can make, assuming that the customers want to buy the drinks he has made.

1. What is the minimum value of X for it to be worthwhile for Kai to make cappuccinos? Kai makes no cappuccinos.
2. Use the simplex algorithm to solve Kai's problem. The grids in the Printed Answer Booklet should have at least enough rows and columns and there should be at least enough grids to show all the iterations needed. Only record the output from each iteration, not any intermediate stages.
   Interpret the solution and state the maximum profit that Kai can make.

7 A simply connected graph has 6 vertices and 10 arcs.

1. What is the maximum vertex degree? You are now given that the graph is also Eulerian.
2. Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
3. Prove that the vertices of degree 2 cannot be adjacent to one another.
4. Use Kuratowski's theorem to show that the graph is planar.
5. Show that it is possible to make a non-planar graph by the addition of one more arc. A digraph is created from a simply connected graph with 6 vertices and \(10 \operatorname { arcs }\) by making each arc into a single directed arc.
6. What can be deduced about the indegrees and outdegrees?
7. If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees? \section*{OCR} \section*{Oxford Cambridge and RSA}