Questions — OCR (4907 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
OCR Further Discrete AS 2019 June Q6
12 marks Challenging +1.2
6 Drew and Emma play a game in which they each choose a strategy and then use the tables below to determine the pay-off that each receives.
Drew's pay-offEmma
XYZ
\cline { 2 - 5 } \multirow{2}{*}{Drew}P31411
Q1247
R1146
Emma's pay-offEmma
XYZ
\cline { 2 - 5 } \multirow{3}{*}{Drew}P1325
Q4129
R51210
  1. Convert the game into a zero-sum game, giving the pay-off matrix for Drew.
  2. Determine the optimal mixed strategy for Drew.
  3. Determine the optimal mixed strategy for Emma.
OCR Further Discrete AS 2022 June Q1
4 marks Easy -1.2
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.
OCR Further Discrete AS 2022 June Q2
7 marks Standard +0.3
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.
OCR Further Discrete AS 2022 June Q3
10 marks Easy -1.8
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.
OCR Further Discrete AS 2022 June Q4
10 marks Standard +0.3
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.
    •
    OCR Further Discrete AS 2022 June Q5
    13 marks Standard +0.8
    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.
    OCR Further Discrete AS 2022 June Q6
    9 marks Moderate -0.8
    6 Eight footpaths connect six villages. The lengths of these footpaths, in km , are given in the table.
    Villages connectedA BA DB EB FC DC ED EE F
    Length of footpath, km32465731
    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.
    OCR Further Discrete AS 2022 June Q7
    7 marks Standard +0.8
    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]
      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.
    OCR Further Discrete AS 2023 June Q1
    3 marks Moderate -0.8
    1 Jane wants to travel from home to the local town. Jane can do this by train, by bus or by both train and bus.
    1. Give an example of a problem that Jane could be answering that would give a construction problem. A website gives Jane all the possible buses and trains that she could use.
      Jane finds 7 possible ways to make the journey.
    OCR Further Discrete AS 2023 June Q2
    6 marks Moderate -0.5
    2 A network is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c9fb5dad-1069-46cd-b167-80b77016f03c-2_533_869_1160_244}
    1. Use an appropriate algorithm to find the least weight (shortest) path from A to D.
    2. Use Kruskal's algorithm to find a minimum spanning tree for the network.
    OCR Further Discrete AS 2023 June Q3
    12 marks Easy -1.2
    3 The list of numbers below is to be sorted into increasing order. \(\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}\)
    1. Sort the list using bubble sort. You do not need to show intermediate working.
      1. Record the list that results at the end of each pass.
      2. Record the number of swaps used in each pass.
    2. Now sort the original list using shuttle sort. You do not need to show intermediate working.
      1. Record the list that results at the end of each pass.
      2. Record the number of swaps used in each pass.
    3. Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both \(\mathrm { O } \left( n ^ { 2 } \right)\).
    4. Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.
    OCR Further Discrete AS 2023 June Q4
    10 marks Standard +0.3
    4 Graph G is a simply connected Eulerian graph with 4 vertices.
      1. Explain why graph G cannot be a complete graph.
      2. Determine the number of arcs in graph G, explaining your reasoning.
      3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
        \captionsetup{labelformat=empty} \caption{To}
        ABCD
        A0101
        B0020
        C2101
        D0110
        \end{table}
      1. Write down a feature of the adjacency matrix that shows that H has no loops.
      2. Find the number of \(\operatorname { arcs }\) in H .
      3. Draw a possible digraph H .
      4. Show that digraph H is semi-Eulerian by writing down a suitable trail.
    OCR Further Discrete AS 2023 June Q5
    11 marks Moderate -0.5
    5 Hiro has been asked to organise a quiz.
    The table below shows the activities involved, together with the immediate predecessors and the duration of each activity in hours.
    ActivityImmediate predecessorsDuration (hours)
    AChoose the topics-0.5
    BFind questions for round 1A2
    CCheck answers for round 1B2.5
    DFind questions for round 2A2
    ECheck answers for round 2D2.5
    FChoose pictures for picture roundA1
    GGet permission to use picturesF1.5
    HChoose music for music roundA2
    IGet permission to use musicH1.5
    JProduce answer sheetsG0.5
    1. A sketch of the activity network is provided in the Printed Answer Booklet. Apply a forward pass to determine the minimum project completion time.
    2. Use a backward pass to determine the critical activities. You can show your working on the activity network from part (a).
    3. Give the total float for each non-critical activity. Hiro decides that there should be a final check of the answers which he will include as activity \(L\). Activity L needs to be done after checking the answers for rounds 1 and 2 and also after getting permission to use the pictures and music but before producing the answer sheets.
      1. Complete the activity network provided in the Printed Answer Booklet to show the new precedences, with the final check of the answers included as activity \(L\).
      2. As a result of including L , the minimum project completion time found in part (a) increases by 2.5 hours. Determine the duration of L .
    OCR Further Discrete AS 2023 June Q6
    6 marks Challenging +1.2
    6 Ryan and Casey are playing a card game in which they each have four cards.
    • Ryan's cards have the letters A, B, C and D.
    • Casey's cards have the letters W, X, Y and Z.
    Each player chooses one of their four cards and they simultaneously reveal their choices. The table shows the number of points won by Ryan for each combination of strategies. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Casey}
    WXYZ
    \cline { 2 - 6 } RyanA4021
    B02- 34
    C14- 45
    D6- 150
    \end{table} For example, if Ryan chooses A and Casey chooses W then Ryan wins 4 points (and Casey loses 4 points). Both Ryan and Casey are trying to win as many points as possible.
    1. Use dominance to reduce the \(4 \times 4\) table for the zero-sum game above to a \(4 \times 2\) table.
    2. Determine an optimal mixed strategy for Casey.
    OCR Further Discrete AS 2023 June Q7
    12 marks Challenging +1.2
    7 A linear programming problem is
    Maximise \(P = 4 x + y\) subject to $$\begin{aligned} 3 x - y & \leqslant 30 \\ x + y & \leqslant 15 \\ x - 3 y & \leqslant 6 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0\)
    1. Use a graphical method to find the optimal value of \(P\), and the corresponding values of \(x\) and \(y\). An additional constraint is introduced.
      This constraint means that the value of \(y\) must be at least \(k\) times the value of \(x\), where \(k\) is a positive constant.
      1. Determine the set of values of \(k\) for which the optimal value of \(P\) found in part (a) is unchanged.
      2. Determine, in terms of \(k\), the values of \(x , y\) and \(P\) in the cases when the optimal solution is different from that found in part (a).
    OCR Further Discrete AS 2024 June Q1
    8 marks Moderate -0.3
    1 There are six non-isomorphic trees with exactly six vertices.
    A student has drawn the diagram below showing six trees each with exactly six vertices. However, two of the trees that the student has drawn are isomorphic. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_222_243_388_246} \captionsetup{labelformat=empty} \caption{A}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_240_392_635} \captionsetup{labelformat=empty} \caption{B}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_241_392_1023} \captionsetup{labelformat=empty} \caption{C}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_218_246_758_246} \captionsetup{labelformat=empty} \caption{D}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_216_243_760_632} \captionsetup{labelformat=empty} \caption{E}
    \end{figure} \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_241_762_1023} \captionsetup{labelformat=empty} \caption{F}
    \end{figure}
    1. Identify which two of these trees are isomorphic.
    2. Draw an example of the missing tree. Graph G has exactly six vertices.
      The degree sequence of G is \(1,1,1,3,3,3\).
    3. Without using a sketch, calculate the number of edges in graph G.
    4. Explain how the result from part (c) shows that graph G is not a tree. In a simple graph with six vertices each vertex degree must be one of the values \(0,1,2,3,4\) or 5 .
    5. Use the pigeonhole principle to show that in a simple graph with six vertices there must be at least two vertices with the same vertex degree.
    OCR Further Discrete AS 2024 June Q2
    5 marks Moderate -0.5
    2 In a game two players are each dealt five cards from a set of ten different cards.
    Player 1 is dealt cards A, B, F, G and J.
    Player 2 is dealt cards C, D, E, H and I. Each player chooses a card to play.
    The players reveal their choices simultaneously. The pay-off matrix below shows the points scored by player 1 for each combination of cards. Pay-off for player 1 \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Player 2}
    C
    \cline { 3 - 7 } \multirow{4}{*}{Alayer 1}DEHI
    \cline { 3 - 7 }A41322
    \cline { 3 - 7 }B02121
    \cline { 3 - 7 }F01123
    \cline { 2 - 7 }G20333
    \cline { 3 - 7 }J12302
    \cline { 3 - 7 }
    \cline { 3 - 7 }
    \end{table}
    1. Determine the play-safe strategy for player 1, ignoring any effect on player 2. The pay-off matrix below shows the points scored by player 2 for each combination of cards.
      Pay-off for player 2 Player 1 \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Player 2}
      CDEH
      \cline { 2 - 6 } A2201I
      \cline { 2 - 6 } B31212
      \cline { 2 - 6 } F32210
      \cline { 2 - 6 } G13000
      \cline { 2 - 6 } J21031
      \cline { 2 - 6 }
      \cline { 2 - 6 }
      \end{table}
    2. Use a dominance argument to delete two columns from the pay-off matrix. You must show all relevant comparisons.
    3. Explain, with reference to specific combinations of cards, why the game cannot be converted to a zero-sum game.
    OCR Further Discrete AS 2024 June Q3
    6 marks Standard +0.3
    3 Heidi has a pack of cards.
    Each card has a single digit on one side and is blank on the other side.
    Each of the digits from 1 to 9 appears on exactly four cards.
    Apart from the numerical values of the digits, the cards are indistinguishable from each other.
    Heidi draws four cards from the pack, at random and without replacement. She places the four cards in a row to make a four-digit number. Determine how many different four-digit numbers Heidi could have made in each of the following cases.
    1. The four digits are all different.
    2. Two of the digits are the same and the other two digits are different.
    3. There is no restriction on whether any of the digits are the same or not.
    OCR Further Discrete AS 2024 June Q4
    9 marks Standard +0.8
    4 A project is represented by the activity network below. The activity durations are given in minutes. \includegraphics[max width=\textwidth, alt={}, center]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-5_447_1020_392_246}
    1. Give the reason for the dummy activity from event (3) to event (4).
    2. Complete a forward pass to determine the minimum project completion time.
    3. By completing a backward pass, calculate the float for each activity.
    4. Determine the effect on the minimum project completion time if the duration of activity A changes from 2 minutes to 3 minutes. The duration of activity C changes to \(m\) minutes, where \(m\) need not be an integer. This reduces the minimum project completion time.
    5. By considering the range of possible values of \(m\), determine the minimum project completion time, in terms of \(m\) where necessary.
    OCR Further Discrete AS 2024 June Q5
    10 marks Moderate -0.8
    5 A garden centre sells mixed packs of flower bulbs.
    Each pack contains bulbs which produce flowers of two different colours. The cost, in \(\pounds\), of a pack of each colour combination is shown in the table below.
    Pack typeABCDE
    ColoursRed, orangeRed, yellowOrange, yellowRed, pinkOrange, pink
    Cost \(( \pounds )\)1.503.004.005.256.50
    1. Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
    2. Construct a minimum spanning tree for the network. Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours. Taylor wants to minimise the total cost of these packs.
    3. Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
    4. Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.
    OCR Further Discrete AS 2024 June Q6
    9 marks Moderate -0.3
    6 Beth wants to buy some tokens for use in a game.
    Each token is either a silver token or a gold token.
    Silver tokens and gold tokens have different points values in the game.
    Silver tokens have a value of 1.5 points each.
    Gold tokens have a value of 4 points each.
    Beth already has 2 silver tokens and 1 gold token.
    She also has \(\pounds 10\) that can be spent on buying more tokens.
    Silver tokens can be bought for \(\pounds 2\) each.
    Gold tokens can be bought for \(\pounds 6\) each.
    After buying some tokens, Beth has \(x\) silver tokens and \(y\) gold tokens.
    She now has a total of at least 5 tokens and no more than 8 tokens.
    1. Set up an LP formulation in \(x\) and \(y\) for the problem of maximising the points value of tokens that she finishes with.
    2. Use a graphical method to determine how many tokens of each type Beth should buy to maximise the points value of her tokens.
    OCR Further Discrete AS 2024 June Q7
    13 marks Standard +0.3
    7 Six items need to be packed into bins. Each bin has size \(k\), where \(k\) is an integer. The sizes of the items are \(\begin{array} { l l l l l l } 8 & 5 & 4 & 7 & 3 & 3 \end{array}\)
    1. Show a way to pack the items into two bins of size \(k = 18\).
    2. If exactly three bins are needed, determine the possible values of \(k\).
    3. Use the first-fit method to pack the items into bins of size 12.
    4. Explain why, in general, the first-fit algorithm does not necessarily find the most efficient solution to a packing problem. A possible way to calculate the run-time of the first-fit method is to count for each item the number of bins, excluding full bins, that are considered before the bin where each item is packed. The total count for all packed items is then used to calculate the run-time of the method.
    5. Determine the total count for the packing used in part (c). A student says that when \(k = 13\) the total count is 0 because the first bin fills up before the second bin is considered.
    6. Explain why the student's argument is not correct.
    7. Determine the least possible value of \(k\) for which the total count is 0 . \section*{END OF QUESTION PAPER}
    OCR Further Discrete AS 2020 November Q1
    10 marks Standard +0.3
    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 .
    OCR Further Discrete AS 2020 November Q2
    8 marks Moderate -0.8
    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.
      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.
      PackageABCDEFGHIJ
      Volume \(\left( \mathrm { m } ^ { 3 } \right)\)0.200.050.150.250.040.030.020.020.120.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:
      Use the inclusion-exclusion principle to determine how many of the 8 ways include neither package F nor package G.
    OCR Further Discrete AS 2020 November Q3
    8 marks Moderate -0.3
    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.
        ABCDEFGH
        A-3-8--\(x\)-
        B3-5-----
        C-5-43---
        D8-4-5--9
        E--35-76-
        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.
      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?