Algorithms, sorting and bin packing

Classifying decision problems

Decision problems fall into four kinds, and naming the kind determines what an algorithm has to deliver. An existence question asks whether a solution is there at all. A construction question asks for one, produced and written down. An enumeration question asks how many solutions there are. An optimisation question asks which of them is best, measured against something the question names, such as a distance, a cost or a number of bins.

An existence question can often be settled by a count that produces no solution at all: a network can be walked using each road once when it has no odd nodes or two of them, and those are counted without drawing a single route. An optimisation question is the expensive one, since a best answer has to beat the others as well as be found.

The kinds overlap, and a problem can be sorted into more than one of them. Asking for the fewest bins is optimisation, and answering it takes two halves: a packing, which is a construction, and a reason nothing does better, which is an existence claim turned round, since it says no packing into fewer bins is there to be found. The lower bound below is that second half: a packing that attains the lower bound is optimal, while one that does not leaves the question open.

Algorithms, tracing and pseudo-code

An algorithm is a finite sequence of precise instructions that solves a problem. A question that supplies one and asks for a trace wants a table with a column per variable and a row per pass, filled in mechanically. When asked to trace an algorithm, record every stated step, including the steps whose effect is already obvious.

Three properties make a method an algorithm. It has an input, the data it is handed, and an output, the answer it delivers. It is deterministic, so a second run on the same input takes the same steps in the same order and returns the same result, because no line leaves anything to the reader's judgement. And it is finite: it stops, and a set of instructions that could run for ever is not an algorithm at all.

Two devices do the stopping, and both are worth naming in a trace. A counter is a variable raised by one on each pass, so the working records how far the method has come and a question can ask for its final value. A stopping condition is the test that ends the loop. In the bubble sort below it is a pass that produces no swaps, so record that final pass as part of the trace.

Three further words describe how an algorithm works rather than what it computes. A greedy algorithm takes the best-looking option at each step and does not look ahead, which is what Prim, Kruskal, nearest neighbour and first fit all do. A heuristic is a method built to find a good answer quickly, with no promise that the answer is the best one, which is what the packing methods below are. A recursive algorithm calls itself on a smaller version of its own problem, which is what quick sort does to each sublist it makes.

A question may present an algorithm as a list of instructions in words, as a flow chart, or as pseudo-code: a numbered list of lines in the shape a program would take, built out of Input, Set, If and Output. No programming is asked for, and the trace table is the same in all three cases.

Two functions turn up inside the algorithms a decision paper sets. INT(x) is the integer part of x, so INT(7.9) = 7 and INT(3) = 3, and subtracting it from x leaves whatever sat after the decimal point. ABS(x) is the size of x with any minus sign removed, so ABS(−3.5) = 3.5 and ABS(4) = 4. Most calculators carry both. Between them they let an algorithm strip a number into digits and measure how far apart two numbers are.

Altering an algorithm is a question in its own right, and it usually turns on one line. Replace the 10 in lines 4 and 6 by 2 and the same loop takes 407 apart in base two instead, so C comes out as 9, the number of binary digits, and S as 6, the number of ones among them. Delete lines 4 and 5, the S = 0 from line 2 and the S from line 8, and what is left counts digits and nothing else.

Bubble, shuttle and quick sort

Bubble sort compares each neighbouring pair along the list and swaps them when they are out of order. One pass delivers the largest item to the end, so each pass is one shorter than the last, and the algorithm stops after a pass that makes no swaps. Record that final pass as part of the trace.

Shuttle sort builds the answer from the left instead. Take the items in turn, and move each one back through the part already sorted, swapping it with its left-hand neighbour while that neighbour is the larger and stopping the moment it is not. Pass 1 compares the first two items, pass 2 shuttles the third item back into place, and so on, so a list of n items takes n − 1 passes and the sorted part grows by one item each pass.

Describe the drawing

Four rows of five boxes, one row per pass. The first row is the list as it arrived, 5, 12, 3, 9, 1, since comparing the first two items finds them already in order. In each later row the item that has just been taken up is filled amber at the place it came to rest, and a coral arrow above the row marks every swap it made walking left. The boxes to the left of it are outlined in blue as the part now sorted, and that part grows by one box a pass until the last row reads 1, 3, 5, 9, 12. The counts down the right add to nine comparisons and seven swaps.

Quick sort picks a pivot and splits the list into those below it and those above it, keeping the original order within each part. The pivot is now fixed in place, and the method repeats on each sublist until every item has been a pivot. Which item serves as pivot is a convention rather than a rule, and the boards differ: this specification takes the middle item of each sublist, while others take the first value unless a question directs otherwise. Say which rule you are using, and hold to it in every sublist.

The order of an algorithm

Counting comparisons on one list settles which method was quicker on that list and nothing further. To compare two methods before either is run, count on a list of n items instead. Write T(n) for the largest number of operations the method can need on a list of that length, which is its worst case time complexity.

Take bubble sort. Its first pass makes n − 1 comparisons, its second n − 2, and so on down to 1, so a run that goes the whole way makes (n − 1) + (n − 2) + ... + 1 comparisons. That is the sum of the first n − 1 positive integers, and since the first m positive integers add to m(m + 1)/2, it comes to n(n − 1)/2, which at n = 5 gives 10, the number counted above. The worst case is the input that forces the whole of it: a list in reverse order, where each comparison swaps as well.

The best case is a list already in order. The stopping rule then ends the method after one pass of n − 1 comparisons and no swaps, so bubble sort is linear on a sorted list and quadratic on a reversed one. A typical case sits between: about half the pairs of a randomly ordered list are out of order, so around n(n − 1)/4 swaps is what an average list costs, which is quadratic again. The three are different questions, and a question will say which of them it wants.

Order is what is left once everything that stops mattering is thrown away. Suppose a method needs T(n) = 2n³ + 50n² + 300n + 1000 operations. The cubic term is 18 per cent of the total at n = 10 and 97.5 per cent at n = 1000. The dominant term, the one of highest power, is the part that survives, and its multiplier goes too, since doubling n multiplies any cubic term by 8 whatever sits in front of it. What is left is written O(n³).

Two methods labelled O(n²) and O(n³) can then be ranked without either being run, because the label is a statement about how the cost grows with the size of the problem rather than about one list. The powers wanted at this level are O(n^k) with k = 0, 1, 2, 3 or 4, which read constant, linear, quadratic, cubic and quartic, and dominance is used in the informal sense above rather than defined.

Three more orders sit outside that family, and where a formulae booklet prints the ranking it runs like this: O(1) is outgrown by O(log n), which is outgrown by O(n), then O(n log n), then O(n²), O(n³) and the higher powers, then O(aⁿ), the exponential orders, which outgrow every power once a is above 1, and last of all O(n!).

The last two rows are the reason large problems are handed to heuristics. At n = 10 the exponential row and the cubic row sit within 3 per cent of each other; at n = 20 the exponential row is 131 times the cubic one, and the factorial row is a number no machine will work through. That is why the travelling salesman problem is answered with bounds rather than by inspecting the tours.

Describe the drawing

Eight curves on one pair of axes, drawn against a vertical scale on which every gridline is a thousand times the one below it, so all eight fit for lists of up to twenty items. They leave the left-hand edge together and separate into a fan, and the name of each is written at the right-hand margin, reading downwards from n factorial through two to the n, the powers of n, n log n, n, log n and the constant. The exponential curve crosses the cubic one just short of n equal to ten, where the two costs are 1024 and 1000, and by twenty items it is 131 times the cubic and the factorial has left the page behind entirely.

Once the order is known, a run-time scales with it. A quadratic algorithm taking 0.5 seconds on a network of 20 nodes takes (100/20)² = 25 times as long on one of 100 nodes, which is 12.5 seconds. A cubic one taking 0.4 seconds on 50 nodes takes 4³ = 64 times as long on 200 nodes, which is 25.6 seconds. The orders needed for that scaling are stated in the lessons: Dijkstra is quadratic in the number of nodes, and Prim and Kruskal are cubic.

The two quick-sort pivot conventions build different recursion trees on the same five numbers, and the shape of the tree is where the count comes from: an even split costs less than a lopsided one.

Describe the drawing

Two recursion trees side by side, both starting from the list 5, 12, 3, 9, 1. Each box holds one sublist with its pivot underlined in amber, and the amber number beside the box is the comparisons that pivot costs. On the left the first value is taken each time and the tree splits evenly, four comparisons then one and one, six in all. On the right the middle item is taken, one sublist of three survives the first split, and the tree runs down one side for four, two and one, seven in all. Neither rule is the better one: on a list already in order the first value costs ten and the middle item six, and the middle item meets its own ten on 5, 3, 1, 2, 4.

Bin-packing algorithms and lower bounds

Bin packing puts items into bins of fixed size, and four methods are worth having. Next fit keeps one bin open: each item goes into it if there is room, and otherwise that bin is closed for good and a fresh one started. First fit takes the items in the order given and puts each into the first bin with room, going back to earlier bins to do it. That one difference, whether a bin may be reopened, costs next fit a whole extra bin on the ten items used below.

Describe the drawing

Two rows of open-topped bins of capacity ten, holding the same ten items in the same order. The upper row is next fit and needs six: the first bin takes the 4 and is then shut for good when the 8 arrives, so its gap of six is wasted, and five of the six bins are drawn grey to mark them closed. The lower row is first fit, which may return to any earlier bin and so fits the same items into five. Both are above the lower bound of four bins that the total of forty allows.

First fit decreasing sorts the items largest first, then packs by first fit. Full bin packing uses observation to spot groups of items that fill a bin exactly, packs those first, and finishes off whatever is left by first fit.

All four are heuristics, and they split in two on a second line. Next fit and first fit are online, deciding each item as it arrives and needing no sight of what is coming; first fit decreasing and full bin packing are offline, since one has to sort the list first and the other has to look it over. A question about items arriving one at a time on a conveyor is asking for an online method.

Next fit is the weakest of the four and the quickest, since it looks at one bin only. First fit decreasing is usually better than first fit and never much worse. Full bin is often better than both, but it needs a human eye and is hard to program.

The lower bound is the total of the items divided by the bin size, rounded up. Achieve it and the packing is certainly optimal and the question is finished. Miss it and the answer might still be optimal, but you would have to argue the point.