Questions on algorithms, sorting and bin packing

Question 1

Define an algorithm, and explain what is meant by its order.

Accepted Answer

A finite sequence of precise instructions that solves a problem and always terminates. Its order says how the number of operations grows with the size n of the problem. An order n² algorithm takes four times as long on a list twice as long. B1 for the definition, B1 for the order. A complete definition names precision and termination; a vague 'a set of steps' gives neither.

Question 2

Apply bubble sort to 5, 12, 3, 9, 1, writing the list after each pass.

Accepted Answer

Pass 1 compares 5 with 12, then 12 with 3, 9 and 1, so the 12 is carried to the end: 5, 3, 9, 1, 12. Pass 2: 3, 5, 1, 9, 12. Pass 3: 3, 1, 5, 9, 12. Pass 4: 1, 3, 5, 9, 12. Each pass leaves one more item fixed at the right-hand end, so after four passes on five items nothing remains to compare and the list is sorted. M1 for a correct first pass, A1 A1 for the later passes. Write the whole list after every pass: the intermediate lists are the answer here, not the sorted result alone.

Question 3

Sort each of these two problems into one of the four kinds existence, construction, enumeration and optimisation. (i) Can nine parcels of sizes 3, 6, 4, 8, 5, 7, 2, 9 and 1 be packed into four bins of size 10? (ii) What is the fewest bins of size 10 that will hold those nine parcels?

Accepted Answer

(i) is an existence problem: its answer is yes or no, together with a reason. (ii) is an optimisation problem: its answer is a number, supported by a packing that achieves it and an argument that nothing does better. B1 for existence, B1 for optimisation. The other two kinds sit alongside these. A construction problem would ask for a packing into four bins to be exhibited, and an enumeration problem would ask how many such packings there are. Say what the answer would look like as well as naming the kind, since an optimisation problem carries a construction inside it and the two are told apart by what has to be produced.

Question 4

An algorithm is written as: Line 1: let p = 250 and q = 37. Line 2: let d = INT(p ÷ q). Line 3: let r = p − q × d. Line 4: if r = 0, print q and stop; otherwise let p = q, let q = r and go to line 2. Trace the algorithm and write down what it prints.

Accepted Answer

INT takes the whole-number part, so line 2 discards the fractional part of the division and line 3 leaves the remainder.
Pass 1: 250 ÷ 37 = 6.756…, so d = 6 and r = 250 − 222 = 28; not zero, so p = 37 and q = 28.
Pass 2: d = 1, r = 37 − 28 = 9; p = 28, q = 9.
Pass 3: d = 3, r = 28 − 27 = 1; p = 9, q = 1.
Pass 4: d = 9, r = 0, so the algorithm prints 1 and stops.
M1 for a correct first pass, A1 for the four rows of the trace, A1 for the output 1. The value printed is the highest common factor of the two starting numbers, and 250 = 2 × 5³ shares no factor with the prime 37. Record every variable at every pass in a trace table: the four numbers on one line are what shows the algorithm was followed.

Question 5

Apply quick sort to 5, 12, 3, 9, 1, taking the middle item as pivot each time and taking the right-hand of two middle items. Show every stage.

Accepted Answer

The middle item of the whole list is 3, so it is the first pivot. Items smaller than it go to the left in their existing order and larger ones to the right, giving 1 | 3 | 5, 12, 9.
The middle item of 5, 12, 9 is 12, giving 5, 9 | 12 | with nothing to its right. Of 5, 9 the right-hand middle is 9, giving 5 | 9. The sublist 1 is a single item and is already in place.
Final order 1, 3, 5, 9, 12, in three pivot steps against bubble sort's four passes. M1 for the first pivot and split, A1 for the resulting sublists, M1 for the second round of pivots, A1 for the sublists there, A1 for the final order. Show each pivot and preserve the order of the items within each sublist.

Question 6

Pack the items 3, 6, 4, 8, 5, 7, 2, 9, 1 into bins of size 10 by first fit, and state the lower bound.

Accepted Answer

The total is 45, so the lower bound is 45/10 = 4.5, rounded up to 5 bins.
First fit fills bin 1 with 3 and 6, opens bin 2 for the 4 and later adds the 5, opens bin 3 for the 8 and later adds the 2, and gives the 7 and the 9 a bin each. The 1 goes back into bin 1. Packing (3, 6, 1), (4, 5), (8, 2), (7), (9), so 5 bins. M1 A1 for the lower bound, M1 A1 for the packing. That equals the lower bound, so this packing is optimal and no further work is needed.

Question 7

Explain why first fit decreasing usually beats first fit, and why neither is guaranteed to be optimal.

Accepted Answer

Placing the large items first leaves the small ones to fill the gaps they create, whereas first fit can commit a bin to small items and then have no room for a large one. Neither looks ahead, so both can be beaten by a packing that sacrifices an early fit for a better later one; finding the optimum in general is a much harder problem. B1 for placing the large items first, B1 for the way first fit can block a bin, B1 for neither algorithm looking ahead.

Question 8

Apply bubble sort to 27, 15, 41, 9, 33, 12, 38, 20, writing the list after each pass. Find the total number of comparisons and the total number of swaps the sort makes, and write down the greatest number of comparisons a bubble sort of eight items could ever need.

Accepted Answer

Pass 1 carries the largest item to the right-hand end: 15, 27, 9, 33, 12, 38, 20, 41, using 7 comparisons and 6 swaps. Pass 2 gives 15, 9, 27, 12, 33, 20, 38, 41 in 6 comparisons and 3 swaps. Pass 3 gives 9, 15, 12, 27, 20, 33, 38, 41 in 5 comparisons and 3 swaps. Pass 4 gives 9, 12, 15, 20, 27, 33, 38, 41 in 4 comparisons and 2 swaps. Pass 5 makes 3 comparisons and no swaps at all, which is the signal that the list is in order, and the sort stops there.
Totals: 25 comparisons and 14 swaps.
The worst case on eight items is a full pass of 7 comparisons, then 6, and so on down to 1, giving 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28, which is 8 × 7 ÷ 2. For n items that is n(n − 1)/2 comparisons, whose dominant term is n²/2, so bubble sort is of order n².
M1 for a correct first pass, A1 for the remaining passes, B1 for stopping after a pass that makes no swap, A1 for 25 comparisons, A1 for 14 swaps, B1 for 28.
Count the comparisons pass by pass, not at the end. Each pass compares adjacent pairs in the unsorted part only, so the counts fall 7, 6, 5, 4, and a count of 8 in every pass counts positions rather than pairs. The final pass counts as well: its 3 comparisons are what prove the list is sorted, and leaving them out gives 22 instead of 25.

Question 9

In the worst case an algorithm performs 2n³ + 15n² + 40n operations on a list of n items. Write down its order, use the order alone to estimate how many times longer it takes on 500 items than on 100, and compare that estimate with the exact ratio of the two counts.

Accepted Answer

The dominant term is 2n³, so the algorithm is of order n³: the multiplier 2 and the lower-order terms are dropped. B1 for the order.
Five times as many items multiplies the work by 5³ = 125. M1 for cubing the ratio of the sizes, A1 for 125.
Exactly, the counts are 2 154 000 and 253 770 000, whose ratio is 117.8 to 1 decimal place, a little below the estimate. B1 for the exact ratio with a comment.
The order is a statement about large n. At n = 100 the 15n² term is still worth 150 000 against the cubic term's 2 000 000, so it inflates the smaller count more than the larger one and pulls the true ratio below 125. Cube the ratio of the sizes rather than the sizes themselves.

Question 10

Eight items of sizes 5, 8, 2, 7, 4, 6, 3, 9 are to be packed into bins of size 15. Find a lower bound for the number of bins, apply next fit to the items in the order given, then apply first fit decreasing, and say whether either packing is optimal.

Accepted Answer

The sizes total 5 + 8 + 2 + 7 + 4 + 6 + 3 + 9 = 44, and 44 ÷ 15 = 2.93, so at least 3 bins are needed. M1 for the total over the bin size, A1 for 3.
Next fit keeps only the current bin open. Bin 1 takes 5, 8 and 2, filling it exactly; the 7 opens bin 2 and the 4 joins it; the 6 will not fit, so bin 3 takes the 6 and the 3; the 9 will not fit either, so bin 4 takes it alone. Packing (5, 8, 2), (7, 4), (6, 3), (9): 4 bins. M1 for a correct next fit packing.
First fit decreasing works on 9, 8, 7, 6, 5, 4, 3, 2. The 9 opens bin 1. The 8 will not fit beside it, so it opens bin 2, and the 7 will not fit with the 9 but does fit with the 8, filling bin 2. The 6 then fills bin 1. The 5 opens bin 3 and the 4, 3 and 2 follow it there, totalling 14. Packing (9, 6), (8, 7), (5, 4, 3, 2): 3 bins. A1.
Three matches the lower bound, so the first fit decreasing packing is optimal and next fit's fourth bin was avoidable. B1.
Next fit closed bin 2 with 4 units to spare and bin 3 with 6, and never went back to fill them. That is what never looking back gives up.

Question 11

The items 6, 1, 6, 1, 6, 1, 7, 7, 7 are to be packed into bins of size 10. Apply first fit and state the lower bound. Then prove that no packing can use five bins.

Accepted Answer

First fit: the 6 opens bin 1 and the 1 joins it; the second 6 opens bin 2 and its 1 goes back into bin 1; the third 6 opens bin 3 and its 1 again goes into bin 1. The bins so far are (6, 1, 1, 1), (6), (6), and no bin has room for a 7, so each 7 opens a bin of its own: 6 bins.
The total is 42, so the lower bound is 42/10 = 4.2, rounded up to 5 bins.
To show five is impossible, look at the six items of size 6 or more. Any two of them total at least 12, which exceeds the bin size, so no bin can hold two of them. Six such items therefore need six separate bins, and 6 is optimal.
M1 A1 for the first fit packing, B1 for six bins, M1 A1 for the lower bound, M1 A1 for the impossibility argument.
Falling short of the lower bound proves nothing on its own.

Question 12

Nine items of sizes 7, 13, 5, 10, 12, 8, 8, 2, 15 are to be packed into bins of size 20. Find a lower bound for the number of bins needed, and apply the next fit algorithm to the items in the order given.

Accepted Answer

The sizes total 7 + 13 + 5 + 10 + 12 + 8 + 8 + 2 + 15 = 80, and 80 ÷ 20 = 4, so at least 4 bins are needed.
Next fit keeps only the current bin open. Bin 1 takes the 7 and then the 13, which fills it exactly. The 5 will not fit, so bin 1 is closed for good and bin 2 takes the 5 and the 10. The 12 will not fit in bin 2, so bin 3 opens and the first 8 joins it, filling it. The second 8 opens bin 4 and the 2 joins it. The 15 will not fit, so it opens bin 5. Packing (7, 13), (5, 10), (12, 8), (8, 2), (15), so 5 bins.
M1 for the total of 80, A1 for the lower bound of 4, M1 for the next fit method, A1 for the packing, B1 for five bins.
Next fit never looks back, so the 5 left in bin 2 and the 10 left in bin 4 can never be used again. That is what makes it the quickest of the four algorithms to apply and the weakest of the four in result.

Question 13

For the same nine items and bins of size 20, apply first fit, then first fit decreasing, and write down the packing that full bin packing gives. State whether any of these algorithms is guaranteed to give the smallest possible number of bins, justifying your answer.

Accepted Answer

First fit puts 7 and 13 in bin 1, filling it. The 5 opens bin 2 and the 10 joins it. The 12 opens bin 3 and the first 8 joins it, filling it. The second 8 fits in none of bins 1 to 3, so it opens bin 4. The 2 goes back into bin 2, which still had 5 to spare. The 15 fits nowhere and opens bin 5. Packing (7, 13), (5, 10, 2), (12, 8), (8), (15), so 5 bins.
First fit decreasing works on 15, 13, 12, 10, 8, 8, 7, 5, 2. Those four largest items open four bins; the first 8 joins the 12, the second 8 joins the 10, the 7 joins the 13, the 5 joins the 15 and the 2 joins the 10 and 8. Packing (15, 5), (13, 7), (12, 8), (10, 8, 2), so 4 bins.
Full bin packing looks for subsets totalling exactly 20 before packing anything, and finds the same four: 15 + 5 = 20, 13 + 7 = 20, 12 + 8 = 20 and 10 + 8 + 2 = 20.
Four bins equals the lower bound, so this packing is optimal and nothing can beat it. That does not make the algorithm reliable: none of the four is guaranteed optimal. Each places items one at a time with no view of what is still to come, and on other data first fit decreasing also finishes above the lower bound.
M1 for first fit, A1 for its packing in five bins, M1 for first fit decreasing, A1 for its four bins, B1 for the full bin packing, B1 for four matching the lower bound, B1 for no algorithm being guaranteed optimal.

Question 14

An algorithm is written as: Line 1: let x = 1. Line 2: let y = (x + 7 ÷ x) ÷ 2. Line 3: if ABS(y − x) < 0.001, print y correct to 4 decimal places and stop. Line 4: let x = y and go to line 2. Trace the algorithm, stating what it prints, and say what it would have to be changed to for it to serve a different purpose.

Accepted Answer

ABS takes the size of a number without its sign, so line 3 measures how far the new value has moved from the old one, whichever way it moved.
x = 1: y = (1 + 7)/2 = 4, and ABS(4 − 1) = 3, too big.
x = 4: y = (4 + 1.75)/2 = 2.875, and ABS = 1.125.
x = 2.875: y = 2.654891…, and ABS = 0.220….
x = 2.654891…: y = 2.645767…, and ABS = 0.009124…, still too big.
x = 2.645767…: y = 2.645751…, and ABS = 0.0000157… < 0.001, so the algorithm prints 2.6458 and stops.
M1 for a correct first pass, A1 for the second and third values of y, A1 for the fourth and fifth, A1 for the test failing four times and passing on the fifth, B1 for the printed 2.6458. Replacing the 7 in line 2 by any positive number a makes the algorithm print √a, and replacing the 0.001 by a smaller tolerance makes it run longer and print a closer value. B1 for an alteration with what it achieves.
√7 = 2.6457513…, so the printed value is right in all four decimal places. The test in line 3 compares two successive values with each other, not either of them with √7, so the tolerance controls how far the algorithm travels and not directly how accurate the answer is.

Question 15

Apply shuttle sort to 8, 3, 6, 1, 5, writing the list after each pass and counting the comparisons and swaps the whole sort makes. Bubble sort on the same list makes 10 comparisons and 7 swaps; comment on the two counts.

Accepted Answer

Shuttle sort takes each item in turn and walks it back down the sorted part until it meets something smaller, then stops.
Pass 1: the 3 passes the 8, giving 3, 8, 6, 1, 5, in 1 comparison and 1 swap.
Pass 2: the 6 passes the 8 and stops at the 3, giving 3, 6, 8, 1, 5, in 2 comparisons and 1 swap.
Pass 3: the 1 travels the whole way, giving 1, 3, 6, 8, 5, in 3 comparisons and 3 swaps.
Pass 4: the 5 passes the 8 and the 6 and stops at the 3, giving 1, 3, 5, 6, 8, in 3 comparisons and 2 swaps.
Totals: 9 comparisons and 7 swaps.
M1 for a correct first pass, A1 for the four lists, A1 for 9 comparisons, A1 for 7 swaps, B1 for the comparison with bubble sort.
The two sorts make the same 7 swaps, because a swap is an inversion undone and this list holds 7 of them however they are removed. Shuttle sort makes one comparison fewer, because a pass stops as soon as the travelling item meets a smaller one while a bubble pass runs to the end of the unsorted part whatever it finds. Both are of order n², so the saving is in the constant rather than in the order.