OCR Further Discrete AS 2021 November — Question 18 1 marks

Exam BoardOCR
ModuleFurther Discrete AS (Further Discrete AS)
Year2021
SessionNovember
Marks1
TopicSorting Algorithms

18
8
7
5
  1. Find the packing that results using each of these algorithms.
    1. The next-fit method
    2. The first-fit method
    3. The first-fit decreasing method
  2. A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists. Explain why the student is wrong. The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer.
    The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split.
  3. Determine the smallest value of \(M\) for which four bins are needed to pack these eight items. Explain your reasoning carefully. 3 The diagram shows a simplified map of the main streets in a small town.
    \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246} Some of the junctions have traffic lights, these junctions are labelled A to F .
    There are no traffic lights at junctions X and Y .
    The numbers show distances, in km, between junctions. Alex needs to check that the traffic lights at junctions A to F are working correctly.
  4. Find a route from A to E that has length 2.8 km . Alex has started to construct a table of shortest distances between junctions A to F.
    \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246} For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
  5. Complete the copy of the table in the Printed Answer Booklet.
  6. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
    • Write down the total length of the minimum spanning tree.
    • List which arcs of the original network correspond to the arcs used in your minimum spanning tree.
    Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
  7. Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c). 4 Li and Mia play a game in which they simultaneously play one of the strategies \(\mathrm { X } , \mathrm { Y }\) and Z . The tables show the points won by each player for each combination of strategies.
    A negative entry means that the player loses that number of points.
    Mia
    XYZ
    \multirow{3}{*}{Li}X5- 60
    \cline { 2 - 5 }Y- 234
    \cline { 2 - 5 }Z- 148
    \cline { 2 - 5 }
    Mia
    XYZ
    \multirow{2}{*}{Li}X4
    \cline { 2 - 5 }Y115
    \cline { 2 - 5 }Z1051
    \cline { 2 - 5 }
    The game can be converted into a zero-sum game, this means that the total number of points won by Li and Mia is the same for each combination of strategies.
    1. Complete the table in the Printed Answer Booklet to show the points won by Mia.
    2. Convert the game into a zero-sum game, giving the pay-offs for Li .
  8. Use dominance to reduce the pay-off matrix for the game to a \(2 \times 2\) table. You do not need to explain the dominance. Mia knows that Li will choose his play-safe strategy.
  9. Determine which strategy Mia should choose to maximise her points. 5 A linear programming problem is formulated as below. Maximise \(\quad \mathrm { P } = 4 \mathrm { x } - \mathrm { y }\)
    subject to \(2 x + 3 y \geqslant 12\)
    \(x + y \leqslant 10\)
    \(5 x + 2 y \leqslant 30\)
    \(x \geqslant 0 , y \geqslant 0\)
    1. Identify the feasible region by representing the constraints graphically and shading the regions where the inequalities are not satisfied.
    2. Hence determine the maximum value of the objective. The constraint \(x + y \leqslant 10\) is changed to \(x + y \leqslant k\), the other constraints are unchanged.
  10. Determine, algebraically, the value of \(k\) for which the maximum value of \(P\) is 3 . Do not draw on the graph from part (a) and do not use the spare grid.
  11. Determine, algebraically, the other value of \(k\) for which there is a (non-optimal) vertex of the feasible region at which \(P = 3\).
    Do not draw on the graph from part (a) and do not use the spare grid. 6 Sarah is having some work done on her garden.
    The table below shows the activities involved, their durations and their immediate predecessors. These durations and immediate predecessors are known to be correct.
    ActivityImmediate predecessorsDuration (hours)
    A Clear site-4
    B Mark out new designA1
    C Buy materials, turf, plants and trees-3
    D Lay pathsB, C1
    E Build patioB, C2
    F Plant treesD1
    G Lay turfD, E1
    H Finish plantingF, G1
    1. Use a suitable model to determine the following.
      • The minimum time in which the work can be completed
  12. The activities with zero float
    [0pt] (ii) State one practical issue that could affect the minimum completion time in part (a)(i). [1]
  13. Sarah needs the work to be completed as quickly as possible. There will be at least one activity happening at all times, but it may not always be possible to do all the activities that are needed at the same time.
  14. Determine the earliest and latest times at which building the patio (activity E) could start. There needs to be a 2-hour break after laying the paths (activity D). During this time other activities that do not depend on activity D can still take place.
  15. Describe how you would adapt your model to incorporate the 2-hour break.