Edexcel International A Level Maths
Algorithms, flow charts and bin packing
Total 27 marks
Name
Class
Date
- 1An algorithm is described as follows.
Step 1: Input a number .
Step 2: Set equal to 0.
Step 3: Add to .
Step 4: Replace by .
Step 5: If , go to Step 3.
Step 6: Print .(a)Find the value printed when the input is .[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(b)For the input , how many times is Step 3 performed?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)Find the value printed when the input is .[2 marks]Show the mark scheme
Mark scheme
M1: takes the values (at least five correct), each added to
A1:Total for question 1: 4 marks
- 2Eight 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]
- A
- B
- C
- D
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]- A
- B
- C
- D
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 and first-fit applied, with at least the first two sticks correct
A1: , , , , four sticksTotal for question 2: 4 marks
- 3An algorithm is described as follows.
Step 1: Input two positive integers and , with .
Step 2: Let be the remainder when is divided by .
Step 3: If , print and stop.
Step 4: Replace by and by , then go to Step 2.(a)Apply the algorithm to the inputs and , showing the values of , and each time Step 2 is performed.[3 marks]Show the mark scheme
Mark scheme
B1: first pass , ,
M1: second pass , ,
A1: third pass , , , output(b)(i) State what the algorithm finds.[4 marks]
(ii) Apply the algorithm to and . State the value printed and the number of times Step 2 is performed.Show the mark scheme
Mark scheme
B1: (i) the highest common factor (greatest common divisor) of and
M1: (ii) remainders (at least the first four correct)
A1: (ii) printed
A1: (ii) Step 2 performed timesTotal for question 3: 7 marks
- 4A list of numbers is written in ascending order. The following algorithm is used to search the list for a number .
Step 1: Find the middle item of the list. For a list of items, the middle item is in position if is odd and if is even.
Step 2: If the middle item equals , stop: has been found.
Step 3: If 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: is not in the list. Otherwise go to Step 1.(a)The list is 4, 9, 13, 17, 21, 26, 30, 35, 41, 47.[6 marks]
(i) State the position and value of the middle item of the whole list.
(ii) Apply the algorithm with , showing the middle item chosen each time and the items that remain.
(iii) Apply the algorithm with and state the outcome.Show the mark scheme
Mark scheme
B1: (i) the 6th item,
M1: (ii) , leaving
M1: (ii) middle item (3rd of 4) is , leaving
A1: (ii) middle item (2nd of 2) is , found
M1: (iii) middle items then then used in turn
A1: (iii) no items remain, so is not in the list(b)(i) Explain why the list must be in ascending order for the algorithm to work.[6 marks]
(ii) The algorithm is applied to a list of 15 items with 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.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
M1: (ii) positions then
A1: (ii) positions
M1: (iii) gives middle position , leaving at most items
M1: (iii) sizes in the worst case
A1: (iii) timesTotal for question 4: 12 marks
End of questions