Algorithms, flow charts and bin packing

Algorithms, flow charts and bin packing Test

Spec 1.1–2 · Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

Algorithms, flow charts and bin packing

Total 27 marks

Name

Class

Date

  1. 1
    An algorithm is described as follows.
    Step 1: Input a number
    NN.
    Step 2: Set
    SS equal to 0.
    Step 3: Add
    NN to SS.
    Step 4: Replace
    NN by N−3N-3.
    Step 5: If
    N>0N>0, go to Step 3.
    Step 6: Print
    SS.
    (a)
    Find the value printed when the input is N=14N=14.
    [1 mark]
    • A3939
    • B3838
    • C−1-1
    • D4040
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    For the input N=14N=14, how many times is Step 3 performed?
    [1 mark]
    • A55
    • B44
    • C66
    • D1414
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Find the value printed when the input is N=20N=20.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: NN takes the values 20,17,14,11,8,5,220, 17, 14, 11, 8, 5, 2 (at least five correct), each added to SS
    A1:
    7777

    Total for question 1: 4 marks

  2. 2
    Eight files of sizes 9, 7, 11, 6, 5, 13, 12 and 10 megabytes (MB) are to be stored on memory sticks. Each memory stick can hold at most 20 MB.
    (a)
    Find the lower bound for the number of memory sticks needed.
    [1 mark]
    • A33
    • B44
    • C55
    • D88
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    The files are packed in the order given using the first-fit algorithm. How many memory sticks are used?
    [1 mark]
    • A44
    • B66
    • C55
    • D88
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    Use the first-fit decreasing algorithm to pack the files, and write down the contents of each memory stick.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: files in decreasing order 13,12,11,10,9,7,6,513, 12, 11, 10, 9, 7, 6, 5 and first-fit applied, with at least the first two sticks correct
    A1:
    {13,7}\{13,7\}, {12,6}\{12,6\}, {11,9}\{11,9\}, {10,5}\{10,5\}, four sticks

    Total for question 2: 4 marks

  3. 3
    An algorithm is described as follows.
    Step 1: Input two positive integers
    AA and BB, with A>BA>B.
    Step 2: Let
    RR be the remainder when AA is divided by BB.
    Step 3: If
    R=0R=0, print BB and stop.
    Step 4: Replace
    AA by BB and BB by RR, then go to Step 2.
    (a)
    Apply the algorithm to the inputs A=252A=252 and B=105B=105, showing the values of AA, BB and RR each time Step 2 is performed.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: first pass A=252A=252, B=105B=105, R=42R=42
    M1: second pass
    A=105A=105, B=42B=42, R=21R=21
    A1: third pass
    A=42A=42, B=21B=21, R=0R=0, output 2121
    (b)
    (i) State what the algorithm finds.
    (ii) Apply the algorithm to
    A=89A=89 and B=55B=55. State the value printed and the number of times Step 2 is performed.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) the highest common factor (greatest common divisor) of AA and BB
    M1: (ii) remainders
    34,21,13,8,5,…34, 21, 13, 8, 5, \ldots (at least the first four correct)
    A1: (ii)
    11 printed
    A1: (ii) Step 2 performed
    99 times

    Total for question 3: 7 marks

  4. 4
    A list of numbers is written in ascending order. The following algorithm is used to search the list for a number TT.
    Step 1: Find the middle item of the list. For a list of
    NN items, the middle item is in position N+12\frac{N+1}{2} if NN is odd and N+22\frac{N+2}{2} if NN is even.
    Step 2: If the middle item equals
    TT, stop: TT has been found.
    Step 3: If
    TT is smaller than the middle item, delete the middle item and every item after it. Otherwise delete the middle item and every item before it.
    Step 4: If no items remain, stop:
    TT is not in the list. Otherwise go to Step 1.
    (a)
    The list is 4, 9, 13, 17, 21, 26, 30, 35, 41, 47.
    (i) State the position and value of the middle item of the whole list.

    (ii) Apply the algorithm with
    T=35T=35, showing the middle item chosen each time and the items that remain.
    (iii) Apply the algorithm with
    T=10T=10 and state the outcome.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) the 6th item, 2626
    M1: (ii)
    26<3526<35, leaving 30,35,41,4730, 35, 41, 47
    M1: (ii) middle item (3rd of 4) is
    41>3541>35, leaving 30,3530, 35
    A1: (ii) middle item (2nd of 2) is
    3535, found
    M1: (iii) middle items
    2626 then 1313 then 99 used in turn
    A1: (iii) no items remain, so
    1010 is not in the list
    (b)
    (i) Explain why the list must be in ascending order for the algorithm to work.
    (ii) The algorithm is applied to a list of 15 items with
    TT smaller than every item. State the position of the middle item chosen each time.
    (iii) Find the greatest number of times Step 1 is performed for a list of 20 items.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) so that deleting the middle item and everything on one side is valid, because all the deleted items are on the wrong side of TT
    M1: (ii) positions
    88 then 44
    A1: (ii) positions
    8,4,2,18, 4, 2, 1
    M1: (iii)
    N=20N=20 gives middle position 1111, leaving at most 1010 items
    M1: (iii) sizes
    10,5,2,1,010, 5, 2, 1, 0 in the worst case
    A1: (iii)
    55 times

    Total for question 4: 12 marks

End of questions

Subtopic tests