Algorithms, flow charts and bin packingEdexcel International A Level Maths: Revision notes

An algorithm is a finite sequence of precise, unambiguous steps that solves a problem and always stops. It can be written as numbered text instructions or drawn as a flow chart. To use an algorithm, follow the steps exactly. Inputs are the values you start with, a loop repeats steps (here by going back to an earlier step) and a decision chooses between two routes (Yes or No). You are not expected to work out the order (efficiency class) of an algorithm.

In a flow chart: an oval is Start or Stop; a parallelogram is Input or Print; a rectangle is a process such as $S=S+N$; a diamond is a decision with Yes and No branches; arrows show the order. Apply an algorithm by writing a trace table with one column for each variable and a new row each time a value changes. Example: Step 3 add $N$ to $S$, Step 4 replace $N$ by $N-3$, Step 5 repeat while $N>0$. For $N=14$, $N$ takes 14, 11, 8, 5, 2 and then $-1$, and $S=14+11+8+5+2=40$. The loop test is applied after $N$ changes, so the final $N=-1$ is not added.

Whenever an algorithm needs the middle item of a list, use the glossary method. In 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. So $N=9$ gives the 5th item and $N=6$ gives the 4th item. Note that for an even $N$ the middle item is the one just after the true centre. Example: for 10 items the middle is position $\frac{10+2}{2}=6$. If a search deletes the middle item and the items beyond it, the remaining list is renumbered from 1 before the rule is applied again.

Bin packing asks for the items to be placed into as few bins of a fixed capacity as possible. Every item must fit in a bin, and the total in each bin cannot exceed the capacity. The algorithms below give a good solution, not always the best one, so they are heuristic. A lower bound on the number of bins is $\left\lceil\frac{\text{total size of all items}}{\text{bin capacity}}\right\rceil,$ rounded up. For files of total size 73 MB on 20 MB sticks, $\frac{73}{20}=3.65$, so at least 4 sticks are needed. If an algorithm uses exactly the lower bound, the packing is optimal.

First-fit: take the items in the order given. Place each item in the first bin that has room, starting a new bin only when no earlier bin can take it. First-fit decreasing: first sort the items into decreasing order, then apply first-fit. It usually uses fewer bins. Full-bin: look for combinations of items that fill a bin exactly, pack these first, then pack the rest by first-fit. Example, capacity 20, items 9, 7, 11, 6, 5, 13, 12, 10: first-fit gives $\{9,7\}$, $\{11,6\}$, $\{5,13\}$, $\{12\}$, $\{10\}$, which is 5 bins. Sorting to 13, 12, 11, 10, 9, 7, 6, 5 gives $\{13,7\}$, $\{12,6\}$, $\{11,9\}$, $\{10,5\}$, which is 4 bins and meets the lower bound.

Show clearly how an algorithm has been applied: write the successive values, the item chosen and the resulting list or bins at each stage. For a text algorithm such as Euclid's, with $R$ the remainder of $A\div B$, then $A\leftarrow B$ and $B\leftarrow R$ until $R=0$: for $A=252$, $B=105$ the remainders are 42, 21 and 0, and the output is 21, the highest common factor. State the purpose of an algorithm only after tracing it, and quote the output with its context.