Algorithms, bin packing and sortingEdexcel A-Level Further Maths: Mind map

Exam questions on Algorithms, bin packing and sorting

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.
   State what the algorithm finds, and explain why it must eventually stop.2 marks
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.
   Use the first-fit decreasing algorithm to pack the files. State the number of cards used and the contents of each.2 marks
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.
   Show the result of the first pass of quick sort, stating the pivot used.3 marks