Algorithms, flow charts and bin packingEdexcel International A Level Maths: Subtopic test

1. 1
   An algorithm is described as follows.
   Step 1: Input a number $N$.
   Step 2: Set $S$ equal to 0.
   Step 3: Add $N$ to $S$.
   Step 4: Replace $N$ by $N-3$.
   Step 5: If $N>0$, go to Step 3.
   Step 6: Print $S$.

   (a)

   Find the value printed when the input is $N=14$.

   [1 mark]

   • A$39$
   • B$38$
   • C$-1$
   • D$40$

   (b)

   For the input $N=14$, how many times is Step 3 performed?

   [1 mark]

   • A$5$
   • B$4$
   • C$6$
   • D$14$

   (c)

   Find the value printed when the input is $N=20$.

   [2 marks]

   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]

   • A$3$
   • B$4$
   • C$5$
   • D$8$

   (b)

   The files are packed in the order given using the first-fit algorithm. How many memory sticks are used?

   [1 mark]

   • A$4$
   • B$6$
   • C$5$
   • D$8$

   (c)

   Use the first-fit decreasing algorithm to pack the files, and write down the contents of each memory stick.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   An algorithm is described as follows.
   Step 1: Input two positive integers $A$ and $B$, with $A>B$.
   Step 2: Let $R$ be the remainder when $A$ is divided by $B$.
   Step 3: If $R=0$, print $B$ and stop.
   Step 4: Replace $A$ by $B$ and $B$ by $R$, then go to Step 2.

   (a)

   Apply the algorithm to the inputs $A=252$ and $B=105$, showing the values of $A$, $B$ and $R$ each time Step 2 is performed.

   [3 marks]

   (b)

   (i) State what the algorithm finds.
   (ii) Apply the algorithm to $A=89$ and $B=55$. State the value printed and the number of times Step 2 is performed.

   [4 marks]

   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 $T$.
   Step 1: Find the middle item of the list. For a list of $N$ items, the middle item is in position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even.
   Step 2: If the middle item equals $T$, stop: $T$ has been found.
   Step 3: If $T$ 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: $T$ 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=35$, showing the middle item chosen each time and the items that remain.
   (iii) Apply the algorithm with $T=10$ and state the outcome.

   [6 marks]

   (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 $T$ 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]

   Total for question 4: 12 marks

End of questions