OCR FD1 AS (Further Decision 1 AS) 2017 December

1
\includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-2_953_559_347_753}

1. Trace through the flowchart above using the input \(N = 97531\). You only need to record values when they change.
2. Explain why the process in the flowchart is finite.

2 Rahul is decorating a room. He needs to decorate at least \(30 \mathrm {~m} ^ { 2 }\) of the walls using paint, panelling or wallpaper. The cost ( \(\pounds\) ) and the time required (hours) to decorate \(1 \mathrm {~m} ^ { 2 }\) of wall are shown in the table. Rahul wants to complete decorating the walls in no more than 8 hours and wants to minimise the cost.
Set up an LP formulation for Rahul's problem, defining your variables. You are not required to solve this LP problem.

3 The activities involved in a project and their durations are represented in the activity network below.
\includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-3_494_700_306_683}

1. Carry out a forward pass and a backward pass through the network.
2. Find the float for each activity. A delay means that the duration of activity E increases to \(x\).
3. Find the values of \(x\) for which activity E is not a critical activity.

4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places \(\mathrm { A } , \mathrm { B }\) and C (once each, in any order) and then finish at his own house (T).

1. Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk. Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
2. (a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?
   (b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem? The distance matrix below shows the direct distances, in km , between places.

   	S	A	B	C	T
   n S	0	3	2	5	4
   nA	3	0	2	2.5	2
   nB	2	2	0	3.2	2.5
   n	5	2.5	3.2	0	2
   \cline { 2 - 6 } T	4	2	2.5	2	0
   \cline { 2 - 6 }
   \cline { 2 - 6 }

3. - Use an appropriate algorithm to find a minimum spanning tree for Tom's network.
   • Give the total weight of the minimum spanning tree.
   • - Find the route that solves Tom's problem.
   • Give the minimum distance that Tom must walk.

5 In each round of a card game two players each have four cards. Every card has a coloured number.

• Player A's cards are red 1 , blue 2 , red 3 and blue 4.
• Player B's cards are red 1 , red 2 , blue 3 and blue 4 .

Each player chooses one of their cards. The players then show their choices simultaneously and deduce how many points they have won or lost as follows:

• If the numbers are the same both players score 0 .
• If the numbers are different but are the same colour, the player with the lower value card scores the product of the numbers on the cards.
• If the numbers are different and are different colours, the player with the higher value card scores the sum of the numbers on the cards.
• The game is zero-sum.
  1. Complete the pay-off matrix for this game, with player A on rows.
  2. Determine the play-safe strategy for each player.
  3. Use dominance to show that player A should not choose red 3 . You do not need to identify other rows or columns that are dominated.
  4. Determine, with a reason, whether the game is stable or unstable.

6 This list is to be sorted into decreasing order, ending up with 31 in the first position and 4 in the last position.
15
4
12
23
14
16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12

15
4
12
23
14

16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12
   9
   4 The sorting is then continued using shuttle sort on this list.
2. Record the list at the end of each of the first, second and third passes of shuttle sort. You do not need to show the individual swaps in each pass.
3. How many passes through shuttle sort are needed to complete the sort? Explain your reasoning.
4. A digraph is represented by the adjacency matrix below. $$\begin{gathered}
   
   
   
   
   
   \text { from } \end{gathered} \begin{gathered}
   \mathrm { A }
   \mathrm {~B}
   \mathrm { C } \end{gathered} \quad \quad \left( \begin{array} { c c c } 1 & \mathrm {~B} & \mathrm { C }
   1 & 1 & 0
   0 & 0 & 0
   0 & 1 & 0 \end{array} \right)$$ (a) For each vertex, write down
   • the indegree,
   • the outdegree.
     (b) Explain how the indegrees and outdegrees show that the digraph is semi-Eulerian.
   • A graph is represented by the adjacency matrix below.
   $$\left. \begin{array} { c }
   \mathrm { D }
   \mathrm { E }
   \mathrm {~F} \end{array} \quad \begin{array} { c c c } \mathrm { D } & \mathrm { E } & \mathrm {~F}
   2 & 1 & 0
   1 & 0 & 2
   0 & 2 & 0 \end{array} \right)$$ (a) Explain how the numerical entries in the matrix show that this can be drawn as an undirected graph.
   (b) Explain how the adjacency matrix shows that this graph is semi-Eulerian.
5. By referring to the vertex degrees, explain why the loop from A to itself is shown as a 1 in the adjacency matrix in part (i) but the loop from \(D\) to itself is shown as 2 in the adjacency matrix in part (ii).
6. List the 15 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } \}\). Amy, Bao, Cal and Dana want to travel by taxi from a meeting to the railway station. They book taxis but only two taxis turn up. Each taxi must have a minimum of one passenger and can carry a maximum of four passengers. Dana jumps into one of the taxis.
7. Find the number of ways that Amy, Bao and Cal can be split between the two taxis. Amy does not want to travel in the same taxi as Bao.
8. Determine the number of ways that Amy, Bao and Cal can be split between taxis with this additional restriction. Six people want to travel by taxi from a hotel to the railway station using taxis. There must be a minimum of one passenger and a maximum of four passengers in each taxi. The taxis may be regarded as being indistinguishable.
9. Calculate how many ways there are of splitting the six people between taxis. \section*{END OF QUESTION PAPER} \section*{OCR} Oxford Cambridge and RSA