OCR Further Discrete AS (Further Discrete AS) 2020 November

1 Algorithm X is given below: STEP 1: \(\quad\) Let \(A = 0\)
STEP 2: Input the value of \(B \quad [ B\) must be a positive integer]
STEP 3: \(\quad C = \operatorname { INT } ( B \div 3 )\)
STEP 4: \(D = B + 3 C\)
STEP 5: \(\quad\) Replace \(A\) with \(( D - A )\)
STEP 6: Decrease \(B\) by 1
STEP 7: If \(B > 0\) go to STEP 3
STEP 8: Display the value of \(\operatorname { ABS } ( A )\) and STOP

1. Trace through algorithm X when the input is \(B = 5\). Only record changes to the values of the variables, \(A , B , C\) and \(D\), using a new column of the table in the Printed Answer Booklet each time one of these variables changes.
2. Explain carefully how you know that algorithm X is finite for all positive integer values of \(B\).
3. Explain what it means to say that an algorithm is deterministic. The run-time of algorithm X is \(k \times\) (number of times that STEP 6 is used), for some positive constant \(k\).
4. Explain, with reference to your answer to part (b), why the order of algorithm X is \(\mathrm { O } ( n )\), where \(n\) is the input value of \(B\). For each input \(B\), algorithm Y achieves the same output as algorithm X , but the run-time of algorithm Y is \(m \times\) (the number of digits in \(B\) ), where \(m\) is a positive constant.
5. Show that algorithm Y is more efficient than algorithm X .

2 Jameela needs to store ten packages in boxes. She has a list showing the size of each package. The boxes are all the same size and Jameela can use up to six of these boxes to store all the packages.

1. Which of the following is a question that Jameela could ask which leads to a construction problem? Justify your choice.
   • In how many different ways can I fit the packages in the boxes?
   • How can I fit the packages in the boxes?
   The total volume of the packages is \(1 \mathrm {~m} ^ { 3 }\). The volume of each of the six boxes is \(0.25 \mathrm {~m} ^ { 3 }\).
2. Explain why a solution to the problem of storing all the packages in six boxes may not exist. The volume of each package is given below.

   Package	A	B	C	D	E	F	G	H	I	J
   Volume \(\left( \mathrm { m } ^ { 3 } \right)\)	0.20	0.05	0.15	0.25	0.04	0.03	0.02	0.02	0.12	0.12

3. By considering the five largest packages (A, C, D, I and J) first, explain what happens if Jameela tries to pack the 10 packages using only four boxes. You may now assume that the packages will always fit in the boxes if there is enough volume.
4. Use first-fit to find a way of storing the packages in the boxes. Show the letters of the packages in each box, in the order that they are packed into that box. The order of the packages within a box does not matter and the order of the boxes does not matter. So, for example, having A and E in box 1 is the same as having E and A in box 2 , but different from having A in one box and E in a different box.
5. Suppose that packages A and B are not in the same box. In this case the following are true:
   • there are 8 different ways to put any or none of \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H with A
   • 3 include F with A
   • 3 include G with A
   • 1 includes both F and G with A
   Use the inclusion-exclusion principle to determine how many of the 8 ways include neither package F nor package G.

3
\includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-4_399_1331_255_367}

1. By listing the vertices passed through, in the order they are used, give an example for the graph above of:
   1. a walk from A to H that is not a trail,
   2. a trail from A to H that is not a path,
   3. a path from A to H that is not a cycle. The arcs are weighted to form a network. The arc weights are shown in the table, apart from the weight of arc AG. The arcs model a system of roads and the weights represent distances in km.

      	A	B	C	D	E	F	G	H
      A	-	3	-	8	-	-	\(x\)	-
      B	3	-	5	-	-	-	-	-
      C	-	5	-	4	3	-	-	-
      D	8	-	4	-	5	-	-	9
      E	-	-	3	5	-	7	6	-
      F	-	-	-	-	7	-	-	-
      G	\(x\)	-	-	-	6	-	-	2
      H	-	-	-	9	-	-	2	-

      The road modelled by arc AG is temporarily closed.
2. Use the matrix form of Prim's algorithm to find a minimum spanning tree, of total weight 30 km , that does not include arc AG. The road modelled by arc AG is now reopened.
3. 1. For what set of values of \(x\) could AG be included in a minimum spanning tree for the full network?
   2. Which arc from the minimum spanning tree in part (b) is not used when arc AG is included?

4 Bob is extending his attic with the help of some friends, including his architect friend Archie. The activities involved, their durations (in days) and Bob's notes are given below. Archie has started to construct an activity network to represent the project.
\includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-5_401_1253_1475_406}

1. Complete the activity network in the Printed Answer Booklet and use it to determine
   • the minimum completion time
   • the critical activities
     for the project.
   • Give two different reasons why the project might take longer than the minimum completion time.
   • For the activity with the longest float
   • calculate this float, in days
   • interpret this float in context.

5 The number of points won by player 1 in a zero-sum game is shown in the pay-off matrix below, where \(k\) is a constant. \begin{table}[h] \end{table}

1. In one game, player 2 chooses strategy H. Write down the greatest number of points that player 2 could win. You are given that strategy A is a play-safe strategy for player 1.
2. Determine the range of possible values for \(k\).
3. Determine the column minimax value.

6 Tamsin is planning how to spend a day off. She will divide her time between walking the coast path, visiting a bird sanctuary and visiting the garden centre. Tamsin has given a value to each hour spent doing each activity. She wants to decide how much time to spend on each activity to maximise the total value of the activities. Tamsin's requirements are that she will spend:

• a total of exactly 6 hours on the three activities
• at most 3.5 hours walking the coast path
• at least as long at the bird sanctuary as at the garden centre
• at least 1 hour at the garden centre.
  1. If Tamsin spends \(x\) hours walking the coast path and \(y\) hours visiting the bird sanctuary, how many hours does she spend visiting the garden centre?

Tamsin models her problem as the linear programming formulation Maximise \(P = 3 x + y\)
Subject to $$\begin{aligned} & x \leqslant 3.5
& x + 2 y \geqslant 6
& x + y \leqslant 5
& x \geqslant 0 \end{aligned}$$ and

1. Explain why the maximum total value of the activities done is achieved when \(3 x + y\) is maximised.
2. Show how the requirement that she spends at least as long at the bird sanctuary as at the garden centre leads to the constraint \(x + 2 y \geqslant 6\).
3. Explain why there is no need to require that \(y \geqslant 0\).

Represent the constraints graphically and hence find a solution to Tamsin's problem.