OCR Further Discrete AS (Further Discrete AS) 2022 June

1 The flowchart below has positive inputs \(X , Y\) and \(M\).
\includegraphics[max width=\textwidth, alt={}, center]{74b6f747-7045-4902-8b21-0b59c007f7f6-2_1274_643_392_242}

1. Trace through the flowchart above using the inputs \(X = 1 , Y = 2\) and \(M = 2\). You only need to record values when they change.
2. Explain why the process in the flowchart is finite.

2 The activities involved in a project and their durations, in hours, are represented in the activity network below.
\includegraphics[max width=\textwidth, alt={}, center]{74b6f747-7045-4902-8b21-0b59c007f7f6-3_446_1139_338_230}

1. Carry out a forward pass and a backward pass through the network.
2. Calculate the float for each activity. A delay means that activity B cannot finish until \(t\) hours have elapsed from the start of the project.
3. Determine the maximum value of \(t\) for which the project can be completed in 16 hours.

3

1. The list below is to be sorted into increasing order using bubble sort.
   \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
2. The list below is to be sorted into increasing order using shuttle sort.
   \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
3. Use the results from parts (a) and (b) to compare the efficiency of bubble sort with the efficiency of shuttle sort for the first three passes of this list. You do not need to consider what happens after these three passes.

4 Kareem and Sam play a game in which each holds a hand of three cards.

• Kareem's cards are numbered 1, 2 and 5.
• Sam's cards are numbered 3, 4 and 6 .

In each round Kareem and Sam simultaneously choose a card from their hand, they show their chosen card to the other player and then return the card to their own hand.

• If the sum of the numbers on the cards shown is even then the number of points that Kareem scores is \(2 k\), where \(k\) is the number on Kareem's card.
• If the sum of the numbers on the cards shown is odd then the number of points that Kareem scores is \(4 - s\), where \(s\) is the number on Sam's card.
  1. Complete the pay-off matrix for this game, to show the points scored by Kareem.
  2. Write down which card Kareem should play to maximise the number of points that he scores for each of Sam’s choices.
  3. Determine the play-safe strategy for Kareem.
  4. Explain why Kareem should never play the card numbered 1.

Sam chooses a card at random, so each of Sam’s three cards is equally likely.

Calculate Kareem's expected score for each of his remaining choices.

5 A baker makes three types of jam-and-custard doughnuts.

• Each batch of type X uses 6 units of jam and 4 units of custard.
• Each batch of type Y uses 7 units of jam and 3 units of custard.
• Each batch of type Z uses 8 units of jam and 2 units of custard.

The baker has 360 units of jam and 180 units of custard available. The baker has plenty of doughnut batter, so this does not restrict the number of batches made. From past experience the baker knows that they must make at most 30 batches of type X and at least twice as many batches of type Y as batches of type Z . Let \(x =\) number of batches of type X made
\(y =\) number of batches of type Y made
\(z =\) number of batches of type Z made.

1. Set up an LP formulation for the problem of maximising the total number of batches of doughnuts made. The baker finds that type Z doughnuts are not popular and decides to make zero batches of type Z .
2. Use a graphical method to find how many batches of each type the baker should make to maximise the total number of batches of doughnuts made.
3. Give a reason why this solution may not be practical. The baker finds that some of the jam has been used so there are only \(k\) units of jam (where \(k < 360\) ).
   There are still 180 units of custard available and the baker still makes zero batches of type Z .
4. Find the values of \(k\) if exactly one of the other (non-trivial) constraints is redundant. Express your answer using inequalities.

6 Eight footpaths connect six villages. The lengths of these footpaths, in km , are given in the table.

1. The shortest route from B to C using these footpaths has length 10 km . Without using an algorithm, write down this shortest route from B to C.
2. Use an appropriate algorithm to find the shortest route from A to F .
3. Write down all the pairs of villages for which the shortest route between them uses at least one footpath that is not in the minimum spanning tree for the six villages.

7

1. List the 15 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \}\) in which A and E are in the same subset.
2. By considering the number of subsets in each of the partitions in part (a), or otherwise, explain why there are 8 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \}\) into two subsets with A and E in different subsets. Ali says that each of the 15 partitions from part (a) can be used to give two partitions in which A and E are in different subsets by moving E into a subset on its own or by moving E into another subset.
   [0pt]
3. 1. By considering the partition from part (a) into just one subset, show that Ali is wrong. [1]
   2. By considering a partition from part (a) into more than two subsets, show that Ali is wrong.