Edexcel A-Level Further Maths
Algorithms, bin packing and sorting
Total 27 marks
Name
Class
Date
- 1The following algorithm is applied to two positive integers and , where . Step 1: input and . Step 2: let be the remainder when is divided by . Step 3: if , output and stop. Step 4: replace by and replace by . Step 5: go back to Step 2.(a)Find the output when the algorithm is applied to and .[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)The algorithm is applied to and . How many times is Step 2 performed?[1 mark]- A
- B
- C
- D
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 and
B1: the remainder is a non-negative integer less than , so gets smaller each time and must reach 0
Accept: strictly decreases, so cannot continue foreverTotal for question 1: 4 marks
- 2Nine 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]
- A
- B
- C
- D
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]- A
- B
- C
- D
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, , , ,
Accept: the cards in any orderTotal for question 2: 4 marks
- 3The 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 if is odd and if 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:(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 and pivot 19 for
A1: left sublist gives
A1: right sublist gives , then pivot 31 gives , then pivot 27
B1: final listTotal for question 3: 7 marks
- 4The following algorithm sorts a list of different numbers into ascending order. Step 1: set equal to . Step 2: compare each pair of adjacent items in the first 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 by 1. Step 4: if , 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 :
A1: after the pass with :
A1: after the passes with and :
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
A1:
B1: the order of the algorithm is (quadratic)
M1: 400 items is 10 times as many, so time is multiplied by about
A1: about 200 ms
R1: only an estimate, since the order describes growth for large and ignores lower-order terms and fixed overheads
Accept: 205 ms usingTotal for question 4: 12 marks
End of questions