D1: AlgorithmsEdexcel International A Level Maths: Topic test

20 questions, 54 marks

Edexcel International A Level Maths

D1: Algorithms topic test

Total 54 marks

Name

Class

Date

1
An algorithm is given below.
Step 1: Input a positive integer $N$ .
Step 2: Set $S$ equal to 0.
Step 3: Let $D$ be the remainder when $N$ is divided by 10.
Step 4: Add $D$ to $S$ .
Step 5: Replace $N$ by the integer part of $N\div10$ .
Step 6: If $N>0$ , go to Step 3.
Step 7: Output $S$ .
(a)
Find the output when the input is $N=4729$ .
[1 mark]
A $18$
B $20$
C $22$
D $9$
(b)
Find the output when the input is $N=3050$ .
[1 mark]
A $8$
B $5$
C $0$
D $3$
(c)
Trace the algorithm for $N=6815$ . Write down the values of $D$ , $S$ and $N$ after the first two passes through Steps 3 to 6.
[2 marks]
Total for question 1: 4 marks
2
Eight parcels have masses, in kg, of 8, 14, 5, 11, 6, 9, 4 and 3, in that order. They are to be packed into boxes that each hold a maximum of 20 kg.
(a)
How many boxes are needed when the first-fit algorithm is used on the parcels in the order given?
[1 mark]
A $3$
B $4$
C $5$
D $6$
(b)
Which two parcels, with masses in kg, are placed together in the second box by first-fit?
[1 mark]
A14 and 3
B14 and 5
C14 and 6
D14 and 4
(c)
Explain why at least 3 boxes are needed, and find a way of packing the parcels into exactly 3 boxes.
[2 marks]
Total for question 2: 4 marks
3
The list 18, 7, 25, 12, 3, 21, 9 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared starting from the left of the list, and the largest remaining item moves to the end of the list.
(a)
Perform the first pass of the bubble sort. Write down the list at the end of the pass, and state the number of comparisons and the number of swaps made in the pass.
[3 marks]
(b)
Complete the bubble sort, writing down the list at the end of each pass. State the total number of passes needed, including the final pass in which no swaps are made.
[4 marks]
Total for question 3: 7 marks
4
The list 22, 9, 31, 14, 27, 5, 18, 36, 12 is to be sorted into ascending order using a quick sort. The pivot is always the middle item of the list or sub-list, found using the position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even.
(a)
Use quick sort to sort the list into ascending order. Show the pivot chosen and the resulting sub-lists at each stage.
[6 marks]
(b)
The sorted list is 5, 9, 12, 14, 18, 22, 27, 31, 36.
(i) Use a binary search to show that 20 is not in the list, stating the item chosen at each stage.
(ii) Explain why a binary search could not be used on the original, unsorted list.
[6 marks]
Total for question 4: 12 marks
5
An algorithm is given below.
Step 1: Set $X=1$ and $S=0$ .
Step 2: Add $X$ to $S$ .
Step 3: Replace $X$ by $X+3$ .
Step 4: If $S>40$ , go to Step 5; otherwise go to Step 2.
Step 5: Output $S$ and $X$ .
(a)
Find the value of $S$ that is output.
[1 mark]
A $51$
B $35$
C $40$
D $70$
(b)
How many times is Step 2 performed?
[1 mark]
A $5$
B $7$
C $6$
D $16$
(c)
The condition in Step 4 is changed to "If $S>100$ ". Find the values that are now output.
[2 marks]
Total for question 5: 4 marks
6
The numbers 6, 9, 13, 17, 21, 26, 30, 34, 39, 45 and 52 are in ascending order. A binary search is used to look for a given number, with the middle item found using the position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even.
(a)
Which number is examined first?
[1 mark]
A $21$
B $30$
C $17$
D $26$
(b)
How many numbers are examined, including the number found, when searching for 34?
[1 mark]
A $2$
B $3$
C $4$
D $5$
(c)
Use the binary search to find the number 13, writing down the item examined at each stage.
[2 marks]
Total for question 6: 4 marks
7
Eight recordings last 16, 10, 13, 19, 4, 11, 8 and 7 minutes, in that order. They are to be stored on discs that each hold a maximum of 30 minutes.
(a)
Use the first-fit algorithm to pack the recordings onto discs. State the number of discs used.
[3 marks]
(b)
Use the first-fit decreasing algorithm to pack the recordings. Show that this uses the minimum possible number of discs.
[4 marks]
Total for question 7: 7 marks
8
A courier has nine parcels with masses, in kg, of 7, 12, 4, 15, 9, 3, 11, 6 and 8. Each van can carry a maximum load of 25 kg.
(a)
Use a quick sort to sort the masses into descending order, with the pivot as the middle item, found using the position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even. Show the pivot chosen and the resulting sub-lists at each stage.
[6 marks]
(b)
The masses in descending order are 15, 12, 11, 9, 8, 7, 6, 4, 3.
(i) Use the first-fit decreasing algorithm to pack the parcels into vans.
(ii) Find a lower bound for the number of vans needed.
(iii) Show that all of the parcels can be carried in 3 vans, and comment on your answer to (i).
[6 marks]
Total for question 8: 12 marks

End of questions

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).