OCR Further Discrete AS (Further Discrete AS) Specimen

1 Hussain wants to travel by train from Edinburgh to Southampton, leaving Edinburgh after 9 am and arriving in Southampton by 4 pm . He wants to leave Edinburgh as late as possible.
Hussain rings the train company to find out about the train times. Write down a question he might ask that leads to
(A) an existence problem,
(B) an optimisation problem.

2 Some of the activities that may be involved in making a cup of tea are listed below. A: Boil water.
B: Put teabag in teapot, pour on boiled water and let tea brew.
C: Get cup from cupboard.
D: Pour tea into cup.
E: Add milk to cup.
F: Add sugar to cup. Activity A must happen before activity B.
Activities B and C must happen before activity D .
Activities E and F cannot happen until after activity C.
Other than that, the activities can happen in any order.

1. Lisa does not take milk or sugar in her tea, so she only needs to use activities \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . In how many different orders can activities \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D be arranged, subject to the restrictions above?
2. Mick takes milk but no sugar, so he needs to use activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . Explain carefully why there are exactly nine different orders for these activities, subject to the restrictions above.
3. Find the number of different orders for all six activities, subject to the restrictions above. Explain your reasoning carefully.

3 A zero-sum game is being played between two players, \(X\) and \(Y\). The pay-off matrix for \(X\) is given below. \section*{Player X}

1. Find an optimal mixed strategy for player \(X\).
2. Give one assumption that must be made about the behaviour of \(Y\) in order to make the mixed strategy of Player \(X\) valid.

4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 . \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down a semi-Eulerian route for graph 1 .
2. Explain how the vertex orders show that graph 2 is also semi-Eulerian.
3. By referring to specific vertices, explain how you know that these graphs are not simple.
4. By referring to specific vertices, explain how you know that these graphs are not isomorphic.

5 There are three non-isomorphic trees on five vertices.

1. Draw an example of each of these trees.
2. State three properties that must be satisfied by the vertex orders of a tree on six vertices.
3. List the five different sets of possible vertex orders for trees on six vertices.
4. Draw an example of each type listed in part (iii).

6 The following masses, in kg, are to be packed into bins. $$\begin{array} { l l l l l l l l l l } 8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8 \end{array}$$

1. Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins. First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.
2. What can be deduced, in this case, about the order of the time complexity, \(\mathrm { T } ( n )\), for first-fit decreasing?

7 A complete graph on five vertices is weighted to form a network, as given in the weighted matrix below.

1. Apply Prim's algorithm to the copy of this weighted matrix in the Printed Answer Booklet to construct a minimum spanning tree for the five vertices.
   Draw your minimum spanning tree, stating the order in which you built the tree and giving its total weight.
2. (a) Using only the arcs in the minimum spanning tree, which vertex should be chosen to find the smallest total of the weights of the paths from that vertex to each of the other vertices?
   (b) State the minimum total for this vertex.
3. Show that the total number of comparisons needed to find a minimum spanning tree for a \(5 \times 5\) matrix is 16 .
4. If a computer takes 4 seconds to find a minimum spanning tree for a network with 100 vertices, how long would it take to find a minimum spanning tree for a network with 500 vertices?

8 A sweet shop sells three different types of boxes of chocolate truffles. The cost of each type of box and the number of truffles of each variety in each type of box are given in the table below. Narendra wants to buy some boxes of truffles so that in total he has at least 20 milk chocolate, 10 plain chocolate, 16 white chocolate and 12 nutty chocolate truffles.

1. Explain why Narendra needs to buy at least four boxes of truffles.
2. Narendra decides that he will buy exactly four boxes. Determine the minimum number of Assorted boxes that Narendra must buy.
3. For your answer in part (ii),
   • list all the feasible solutions and
   • find the cheapest solution.
   Narendra finds that the sweet shop has sold out of Assorted boxes, but he then spots that it also sells small boxes of milk chocolate truffles and small boxes of nutty chocolate truffles. Each small box contains 4 truffles (all of one variety) and costs \(\pounds 0.50\). He decides to buy \(x\) boxes of No Nuts and \(y\) boxes of Speciality, where \(x + y < 4\), so that he has at least 10 plain chocolate and 16 white chocolate truffles. He will then buy as many small boxes as he needs to give a total of at least 20 milk chocolate and 12 nutty chocolate truffles.
4. (a) Set up constraints on the values of \(x\) and \(y\).
   (b) Represent the feasible region graphically.
   (c) Hence determine the cheapest cost for Narendra. {www.ocr.org.uk}) after the live examination series. If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
   OCR is part of the Cambridge Assessment Group; Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge. }