Algorithms, bin packing and sortingEdexcel A-Level Further Maths: Revision notes

An algorithm is a finite, unambiguous sequence of steps that solves a problem. It may be given as text (numbered steps) or a flow chart, which uses boxes for input/output and instructions, diamonds for decisions (yes or no) and arrows for the flow, with start and stop terminals. To implement an algorithm, follow each step exactly, keeping a trace table of the value of each variable after every step. Example (Euclid): input $a>b$; $r$ = remainder of $a\div b$; if $r=0$ output $b$; otherwise replace $a$ by $b$, $b$ by $r$ and repeat. For $a=252$, $b=105$ the remainders are 42, 21, 0, giving output 21, the highest common factor.

The size of a problem is the amount of data, such as the number of items $n$. The order of an algorithm describes how the running time grows with $n$ for large $n$: it keeps only the highest power. An algorithm of order $n^2$ takes about 100 times as long if $n$ is multiplied by 10. Bubble sort and first-fit bin packing are of order $n^2$; a quadratic count such as $\frac{n(n-1)}{2}$ has order $n^2$. Common orders from fastest to slowest growth: $\log n$, $n$, $n^2$, $n^3$, $2^n$. The order is a guide to efficiency, not an exact time: lower-order terms and constants are ignored.

Bin packing fits items into the fewest bins of a fixed capacity. Three algorithms: first-fit, taking items in the given order and placing each in the first bin with room; first-fit decreasing, which first sorts the items into descending order and then applies first-fit; and full-bin, which looks for combinations of items that exactly fill a bin. The lower bound on the number of bins is the total size divided by the capacity, rounded up. Example (capacity 20): items $7,13,8,3,5,9,4,14,12$ total 75, so at least 4 bins. First-fit uses 5 bins: $\{7,13\}$, $\{8,3,5,4\}$, $\{9\}$, $\{14\}$, $\{12\}$; first-fit decreasing uses 4: $\{14,5\}$, $\{13,7\}$, $\{12,8\}$, $\{9,4,3\}$. These are heuristics: none guarantees the optimum, except when the bound is met.

Bubble sort compares adjacent items from the left, swapping any pair in the wrong order. After the first pass the largest item is in its final place at the end; each later pass can ignore the items already placed. The list is sorted when a pass makes no swaps (or after $n-1$ passes). Example: sort $8,3,6,2,5$. Pass 1: $3,6,2,5,8$. Pass 2: $3,2,5,6,8$. Pass 3: $2,3,5,6,8$. Pass 4: no swaps. The maximum number of comparisons for $n$ items is $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$, so bubble sort is of order $n^2$.

Quick sort chooses a pivot, the middle item: 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 ones to its right, each keeping the original order. The pivot is now in its final place. Repeat on each sublist with more than one item until every item is a pivot or alone. Example: $23,8,31,15,4,19,27$. $N=7$, pivot 15: $8,4\mid15\mid23,31,19,27$. Left, $N=2$, pivot 4: $4,8$. Right, $N=4$, pivot 19: $19\mid23,31,27$; then $N=3$, pivot 31: $23,27\mid31$; then pivot 27. Result: $4,8,15,19,23,27,31$. Quick sort is usually much faster than bubble sort on long lists.

Write every pass or trace step. Label pivots, state bin contents and totals, and give the number of bins. For order questions give the power of $n$ and use a ratio argument: multiply $n$ by $k$ and the time is multiplied by about $k^2$. Mention that estimates ignore lower-order terms.