Algorithms, bin packing and sortingEdexcel A-Level Further Maths: Subtopic test

1. 1
   The following algorithm is applied to two positive integers $a$ and $b$, where $a>b$. Step 1: input $a$ and $b$. Step 2: let $r$ be the remainder when $a$ is divided by $b$. Step 3: if $r=0$, output $b$ and stop. Step 4: replace $a$ by $b$ and replace $b$ by $r$. Step 5: go back to Step 2.

   (a)

   Find the output when the algorithm is applied to $a=84$ and $b=36$.

   [1 mark]

   • A$36$
   • B$12$
   • C$24$
   • D$6$

   (b)

   The algorithm is applied to $a=252$ and $b=105$. How many times is Step 2 performed?

   [1 mark]

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

   (c)

   State what the algorithm finds, and explain why it must eventually stop.

   [2 marks]

   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]

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

   (b)

   The files are saved using the first-fit algorithm, in the order given. How many cards are used?

   [1 mark]

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

   (c)

   Use the first-fit decreasing algorithm to pack the files. State the number of cards used and the contents of each.

   [2 marks]

   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 $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ 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]

   (b)

   Complete the quick sort, showing each pivot used.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   The following algorithm sorts a list of $n$ different numbers into ascending order. Step 1: set $p$ equal to $n$. Step 2: compare each pair of adjacent items in the first $p$ 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 $p$ by 1. Step 4: if $p=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]

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

   Total for question 4: 12 marks

End of questions