OCR Further Discrete AS (Further Discrete AS) 2023 June

1 Jane wants to travel from home to the local town. Jane can do this by train, by bus or by both train and bus.

1. Give an example of a problem that Jane could be answering that would give a construction problem. A website gives Jane all the possible buses and trains that she could use.
   Jane finds 7 possible ways to make the journey.
   • 2 of the 7 journeys involve travelling by train for at least part of the journey
   • 6 of the 7 journeys involve travelling by bus for at least part of the journey
   • Use the inclusion-exclusion principle to find how many of the 7 journeys involve travelling by both train and bus.

2 A network is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{c9fb5dad-1069-46cd-b167-80b77016f03c-2_533_869_1160_244}

1. Use an appropriate algorithm to find the least weight (shortest) path from A to D.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network.

3 The list of numbers below is to be sorted into increasing order.
\(\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}\)

1. Sort the list using bubble sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
2. Now sort the original list using shuttle sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
3. Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both \(\mathrm { O } \left( n ^ { 2 } \right)\).
4. Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.

4 Graph G is a simply connected Eulerian graph with 4 vertices.

1. 1. Explain why graph G cannot be a complete graph.
   2. Determine the number of arcs in graph G, explaining your reasoning.
   3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{To}

      	A	B	C	D
      A	0	1	0	1
      B	0	0	2	0
      C	2	1	0	1
      D	0	1	1	0

      \end{table}
2. 1. Write down a feature of the adjacency matrix that shows that H has no loops.
   2. Find the number of \(\operatorname { arcs }\) in H .
   3. Draw a possible digraph H .
   4. Show that digraph H is semi-Eulerian by writing down a suitable trail.

5 Hiro has been asked to organise a quiz.
The table below shows the activities involved, together with the immediate predecessors and the duration of each activity in hours.

1. A sketch of the activity network is provided in the Printed Answer Booklet. Apply a forward pass to determine the minimum project completion time.
2. Use a backward pass to determine the critical activities. You can show your working on the activity network from part (a).
3. Give the total float for each non-critical activity. Hiro decides that there should be a final check of the answers which he will include as activity \(L\). Activity L needs to be done after checking the answers for rounds 1 and 2 and also after getting permission to use the pictures and music but before producing the answer sheets.
4. 1. Complete the activity network provided in the Printed Answer Booklet to show the new precedences, with the final check of the answers included as activity \(L\).
   2. As a result of including L , the minimum project completion time found in part (a) increases by 2.5 hours. Determine the duration of L .

6 Ryan and Casey are playing a card game in which they each have four cards.

• Ryan's cards have the letters A, B, C and D.
• Casey's cards have the letters W, X, Y and Z.

Each player chooses one of their four cards and they simultaneously reveal their choices. The table shows the number of points won by Ryan for each combination of strategies. \begin{table}[h] \end{table} For example, if Ryan chooses A and Casey chooses W then Ryan wins 4 points (and Casey loses 4 points). Both Ryan and Casey are trying to win as many points as possible.

1. Use dominance to reduce the \(4 \times 4\) table for the zero-sum game above to a \(4 \times 2\) table.
2. Determine an optimal mixed strategy for Casey.

7 A linear programming problem is
Maximise \(P = 4 x + y\)
subject to $$\begin{aligned} 3 x - y & \leqslant 30
x + y & \leqslant 15
x - 3 y & \leqslant 6 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0\)

1. Use a graphical method to find the optimal value of \(P\), and the corresponding values of \(x\) and \(y\). An additional constraint is introduced.
   This constraint means that the value of \(y\) must be at least \(k\) times the value of \(x\), where \(k\) is a positive constant.
2. 1. Determine the set of values of \(k\) for which the optimal value of \(P\) found in part (a) is unchanged.
   2. Determine, in terms of \(k\), the values of \(x , y\) and \(P\) in the cases when the optimal solution is different from that found in part (a).