Algorithms, bin packing and sorting

Algorithms, bin packing and sorting Test

Spec 1.1–2 · Edexcel A-Level Further 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 A-Level Further Maths

Algorithms, bin packing and sorting

Total 27 marks

Name

Class

Date

  1. 1
    The following algorithm is applied to two positive integers aa and bb, where a>ba>b. Step 1: input aa and bb. Step 2: let rr be the remainder when aa is divided by bb. Step 3: if r=0r=0, output bb and stop. Step 4: replace aa by bb and replace bb by rr. Step 5: go back to Step 2.
    (a)
    Find the output when the algorithm is applied to a=84a=84 and b=36b=36.
    [1 mark]
    • A3636
    • B1212
    • C2424
    • D66
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    The algorithm is applied to a=252a=252 and b=105b=105. How many times is Step 2 performed?
    [1 mark]
    • A22
    • B44
    • C33
    • D55
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    State what the algorithm finds, and explain why it must eventually stop.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: it finds the highest common factor (greatest common divisor) of aa and bb
    B1: the remainder
    rr is a non-negative integer less than bb, so bb gets smaller each time and rr must reach 0
    Accept:
    bb strictly decreases, so cannot continue forever

    Total for question 1: 4 marks

  2. 2
    Nine files of sizes 7, 13, 8, 3, 5, 9, 4, 14 and 12 MB are to be saved on memory cards, each of capacity 20 MB. A file cannot be split between cards.
    (a)
    What is the lower bound on the number of cards needed?
    [1 mark]
    • A33
    • B3.753.75
    • C55
    • D44
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    The files are saved using the first-fit algorithm, in the order given. How many cards are used?
    [1 mark]
    • A55
    • B44
    • C66
    • D77
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Use the first-fit decreasing algorithm to pack the files. State the number of cards used and the contents of each.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: sort into descending order, 14, 13, 12, 9, 8, 7, 5, 4, 3, and apply first-fit
    A1: 4 cards,
    {14,5}\{14,5\}, {13,7}\{13,7\}, {12,8}\{12,8\}, {9,4,3}\{9,4,3\}
    Accept: the cards in any order

    Total for question 2: 4 marks

  3. 3
    The list 23, 8, 31, 15, 4, 19, 27 is to be sorted into ascending order using quick sort. The pivot is always the middle item of the list or sublist: in position N+12\frac{N+1}{2} if NN is odd and N+22\frac{N+2}{2} if NN is even. Items smaller than the pivot go to its left and larger items to its right, each keeping their original order.
    (a)
    Show the result of the first pass of quick sort, stating the pivot used.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: pivot is 15 (position 4 of 7)
    M1: smaller items to the left and larger items to the right, original order kept

    A1:
    8,4∣15∣23,31,19,278,4\mid15\mid23,31,19,27
    (b)
    Complete the quick sort, showing each pivot used.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: apply the middle-item rule to each sublist, e.g. pivot 4 for 8,48,4 and pivot 19 for 23,31,19,2723,31,19,27
    A1: left sublist gives
    4,84,8
    A1: right sublist gives
    19∣23,31,2719\mid23,31,27, then pivot 31 gives 23,27∣3123,27\mid31, then pivot 27
    B1: final list
    4,8,15,19,23,27,314,8,15,19,23,27,31

    Total for question 3: 7 marks

  4. 4
    The following algorithm sorts a list of nn different numbers into ascending order. Step 1: set pp equal to nn. Step 2: compare each pair of adjacent items in the first pp positions of the list, working from left to right, and swap the two items in a pair if they are in the wrong order. Step 3: reduce pp by 1. Step 4: if p=1p=1, stop; otherwise go back to Step 2.
    (a)
    Apply the algorithm to the list 8, 3, 6, 2, 5, showing the list at the end of each pass. State the total number of comparisons and the total number of swaps.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: first pass compares each adjacent pair left to right, swapping when out of order
    A1: after the pass with
    p=5p=5: 3,6,2,5,83,6,2,5,8
    A1: after the pass with
    p=4p=4: 3,2,5,6,83,2,5,6,8
    A1: after the passes with
    p=3p=3 and p=2p=2: 2,3,5,6,82,3,5,6,8
    B1: 10 comparisons

    B1: 7 swaps
    (b)
    The algorithm takes 2 ms to sort a list of 40 items on a computer. Find the number of comparisons used for 40 items, state the order of the algorithm, and estimate the time to sort a list of 400 items. Comment on the reliability of your estimate.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: comparisons =(n−1)+(n−2)+⋯+1=n(n−1)2=(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}
    A1:
    40×392=780\frac{40\times39}{2}=780
    B1: the order of the algorithm is
    n2n^2 (quadratic)
    M1: 400 items is 10 times as many, so time is multiplied by about
    10210^2
    A1: about 200 ms

    R1: only an estimate, since the order describes growth for large
    nn and ignores lower-order terms and fixed overheads
    Accept: 205 ms using
    400×3992\frac{400\times399}{2}

    Total for question 4: 12 marks

End of questions

Subtopic tests