OCR Further Discrete AS 2021 November — Question 5

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

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.