Decision Maths: Algorithms, Sorting and Bin Packing
An algorithm in decision mathematics is a finite, precisely defined sequence of instructions that, when followed exactly, is guaranteed to solve a problem (or a class of problems) in a fixed number of steps. It covers algorithms for sorting a list into order (bubble sort, quick sort), locating a value in an already-sorted list (binary search), and packing items of different sizes into the smallest number of equal-capacity bins (bin-packing algorithms such as first-fit and first-fit decreasing). Exam questions mark the method, that is correctly tracing every pass or comparison, not just the final answer.
Before you start
No specific prerequisites - this is a good place to start.
Method
- Understand an algorithm as a finite, precise sequence of instructions, and trace one by hand, recording the state of the list after every pass or comparison in a table or list.
- Bubble sort: pass left to right comparing each pair of adjacent items, swapping if they are in the wrong order; each pass needs one fewer comparison than the last, since the largest unsorted item is guaranteed to reach its final position each time.
- Quick sort: choose a pivot (the first item of each sublist, by the usual exam convention), partition the remaining items into a sublist of items less than the pivot and a sublist of items greater than the pivot, then apply quick sort recursively to each sublist until every sublist has at most one item.
- Binary search: on an already-sorted list, compare the target value with the middle item; discard the half of the list that cannot contain the target, and repeat on the remaining half until the target is found or the list is empty.
- Bin-packing lower bound: divide the total weight (or size) of all the items by the bin capacity, and round the result up to the next whole number.
- First-fit: taking the items in the order given, place each item into the first bin (checked in order 1, 2, 3, ...) that has enough remaining capacity for it.
- First-fit decreasing: sort the items into decreasing order of size first, then apply first-fit to the sorted list; this typically uses fewer bins than plain first-fit.
- Compare the number of bins used by a packing to the lower bound to judge how good the packing is; a packing that matches the lower bound is optimal.
Worked example
The list 25, 11, 33, 4, 18, 7 is to be sorted into ascending order using quick sort, choosing the first item of each sublist as the pivot. Carry out the full sort, showing the sublists produced at each stage.
- First pivot = 25 (the first item). Comparing each remaining item (11, 33, 4, 18, 7) to 25: those less than 25 form the sublist [11, 4, 18, 7] in their original order, and those greater form the sublist [33]. This gives [11, 4, 18, 7] | 25 | [33].
- The sublist [33] has one item, so it needs no further sorting. Apply quick sort to [11, 4, 18, 7]: pivot = 11. The remaining items 4, 18, 7 split into [4, 7] (less than 11) and [18] (greater than 11), giving [4, 7] | 11 | [18].
- [18] has one item, so it is done. Apply quick sort to [4, 7]: pivot = 4. The remaining item 7 is greater than 4, so the less-than sublist is empty and the greater-than sublist is [7], giving 4 | [7].
- Every sublist now has at most one item, so sorting is complete. Reading the sublists in order gives 4, 7, 11, 18, 25, 33.
- Final answer: sorted list is 4, 7, 11, 18, 25, 33.
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1A list contains the numbers 8, 3, 15, 6. Perform one pass of a bubble sort (left to right, comparing adjacent pairs) and state the resulting list.Show answer
Answer: 3, 8, 6, 15 (compare 8,3: swap; compare 8,15: no swap; compare 15,6: swap).
Q2Find the lower bound for the number of bins needed to pack items of weight 5, 7, 3, 6, 4, 8 kg into bins of capacity 12 kg.Show answer
Answer: 3 bins (total weight = 33 kg; 33/12 = 2.75, rounded up to 3).
Q3Use first-fit to pack the items 9, 4, 6, 3, 7 (bin capacity 10) in the order given, stating the contents of each bin.Show answer
Answer: Bin 1 = {9}, Bin 2 = {4, 6}, Bin 3 = {3, 7}; 3 bins used (4 does not fit with 9, but 6 fills bin 2 exactly; 3 does not fit bin 1 or bin 2, but 7 fills bin 3 exactly).
Q4State one advantage of first-fit decreasing over plain first-fit for bin packing.Show answer
Answer: Sorting into decreasing order before applying first-fit places the larger items first, while there is still plenty of space to fit them, which tends to use fewer bins and gives a packing closer to the lower bound.
Q5A sorted list has 200 items. Using binary search, what is the maximum number of comparisons needed to locate a target value (or determine it is absent)?Show answer
Answer: 8 comparisons (the smallest k with 2^k >= 200 is k=8, since 2^7=128 < 200 <= 2^8=256).
Q6The list 12, 45, 7, 89, 34, 2, 67 is to be sorted using quick sort with the first item of each sublist chosen as the pivot. State the two sublists produced after the first pass.Show answer
Answer: [7, 2] | 12 | [45, 89, 34, 67] (7 and 2 are less than 12; 45, 89, 34, 67 are greater than 12).
Q7Explain what is meant by an 'algorithm' in decision mathematics.Show answer
Answer: A finite, precisely defined sequence of instructions (steps) that, when followed, is guaranteed to produce a solution to a problem, or to a class of problems, in a finite number of steps.
Exam-style questions
Written in the style of a A Level Further Maths exam paper, with a full mark scheme.
The numbers 38, 15, 62, 9, 41, 27, 6 are to be sorted into ascending order using a bubble sort, where each pass needs one fewer comparison than the previous pass. (a) Perform a full bubble sort on this list, showing the list produced after each pass. (b) State how many passes were needed.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
The following items have weights 9, 5, 8, 4, 7, 3, 6 kg and are to be packed into bins of capacity 15 kg. (a) Find the lower bound for the number of bins required. (b) Apply first-fit decreasing to pack the items, stating clearly the contents of each bin.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
The list 4, 19, 2, 27, 11, 8, 33, 15 is to be sorted into ascending order using quick sort, choosing the first item of each sublist as the pivot. Carry out the first two levels of recursion (i.e. find the pivot and sublists at each of the first two stages), showing your sublists clearly at each stage.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 5 available
See real A Level Further Maths past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the decision maths: algorithms, sorting and bin packing worksheet pack - 11 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on decision maths: algorithms, sorting and bin packing, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.