What an algorithm is; carrying out an algorithm given as written instructions, with a trace table

Following a flow chart and counting how many times a box is used

Bubble sort: passes, comparisons and swaps, and when to stop

Quick sort with the middle item of each sublist as the pivot, ascending or descending

Binary search in an ordered list, including an item that is not there

Bin packing: first fit, first-fit decreasing and full bins, and the lower bound

The order of an algorithm (linear, quadratic, cubic) and estimating run times

1. An algorithm is a finite sequence of precise instructions that solves a problem; in D1 you carry algorithms out accurately and show that you did, tracing them in a table with one column per variable and one row per change.

2. Bubble sort: compare neighbours left to right, swap if out of order; after pass k the last k items are fixed. Stop after a pass with no swaps.

3. Quick sort: the middle item of each sublist (right of centre if there is an even number) is the pivot; items that belong before it go to its left, the others to its right, in their original order. Repeat on every sublist.

4. Binary search: on an ordered list, compare with the item in position ⌈(first + last)/2⌉ and discard the half that cannot contain the target.

5. Bin packing: lower bound = total ÷ capacity, rounded up. First fit takes items in the given order; first-fit decreasing sorts them first; full bins looks for exact fills. A packing that meets the lower bound is optimal.

D1 algorithm questions never ask you to invent a sort. They ask you to carry one out pass by pass, keep track of comparisons and swaps, find the middle item correctly, pack bins in the right order and say how good the answer is. So the skill is accuracy plus a clear layout of working.

Every instruction must be unambiguous: two people following it get the same result. It must stop after a finite number of steps, and it usually takes an input and produces an output. Algorithms can be written as numbered instructions ("Step 3: if N < k, go to Step 7"), as a flow chart, or in a simple code-like form. You only follow them, never program them.

A trace table records the value of every variable each time it changes. Start a new row each time the algorithm goes round its loop, and write the output at the end.

When asked "what does the algorithm do?", look at your input–output pairs and describe the general result (for example "it finds the highest common factor of A and B"), not the particular numbers.

WORKED EXAMPLE · QUESTION

Step 1: Input a positive integer N. Step 2: Let k = 1 and c = 0. Step 3: If N < k, go to Step 7. Step 4: Replace N by N − k. Step 5: Replace c by c + 1 and k by k + 2. Step 6: Go to Step 3. Step 7: Output c.

(a) Carry out the algorithm with N = 40, showing the values in a table. (b) State what the algorithm finds. (c) How many times is Step 4 carried out when N = 150?

SOLUTION

(a) One row for the starting values, then one row per time round the loop:

At N = 4, k = 13 the test 4 < 13 is true, so the output is c = 6.

(b) The amounts subtracted are 1, 3, 5, 7, … and 1 + 3 + …+ (2c-1) = c². The algorithm counts how many odd numbers can be removed, so it finds the integer part of √N (√40 = 6.32…).

(c) Step 4 runs once for each odd number removed, and the output for 150 is the integer part of √150: 12² = 144 ≤ 150 < 169 = 13², so 12 times.

Follow the arrows, one box at a time. A "Let" box replaces the old value of a variable with the new one.

Boxes are usually numbered so a question can ask, for example, how many times box 4 is used.

INT(x) means the integer part of x: INT(37 ÷ 2) = 18.

A loop is an arrow that goes back up the chart; the decision box that controls it is the stopping condition. Check that it is eventually met.

WORKED EXAMPLE · QUESTION

Use the flow chart above. (a) Complete a trace table for the input A = 37, B = 23 and state the output. (b) Suggest what the algorithm calculates. (c) For the input A = 100, B = 7, how many times is box 4 used?

SOLUTION

(a) One row each time box 4 is reached, showing P after box 5:

At box 7, A = 0, so the output is P = 851. The last row shows the values after box 6 on the final pass; only P matters.

(b) 37 × 23 = 851, so the algorithm finds the product A × B.

(c) A is halved (rounding down) each time round: 100 → 50 → 25 → 12 → 6 → 3 → 1 → 0, so box 4 is used 7 times.

In each pass, compare the 1st and 2nd items, then the 2nd and 3rd, and so on, swapping any pair in the wrong order. Equal items are not swapped. For ascending order the largest item "bubbles" to the end in pass 1, so pass 2 can stop one place earlier: pass k makes n − k comparisons for a list of n items.

Stop after a pass with no swaps, or after n − 1 passes, whichever comes first. The pass with no swaps must be shown: it is how you know the list is sorted.

The most comparisons possible are (n-1) + (n-2) + …+ 1 = ½ n(n-1), when the list starts in reverse order.

For descending order, swap whenever the left item is smaller; then the smallest item moves to the end.

WORKED EXAMPLE · QUESTION

Use a bubble sort to arrange 27, 41, 19, 52, 34, 60, 45, 38 in ascending order. (a) Show the first pass in full. (b) Show the list after each later pass. (c) State the total number of comparisons and swaps.

SOLUTION

(a) Pass 1, one comparison at a time:

(b) Each pass is one comparison shorter. Pass 2: 19, 27, 34, 41, 45, 38, 52, 60. Pass 3: 19, 27, 34, 41, 38, 45, 52, 60. Pass 4: 19, 27, 34, 38, 41, 45, 52, 60. Pass 5: 19, 27, 34, 38, 41, 45, 52, 60 (no swaps: sort complete).

(c) Comparisons 7 + 6 + 5 + 4 + 3 = 25; swaps 4 + 4 + 1 + 1 + 0 = 10. The list was in order after pass 4, but the algorithm cannot know that until pass 5 finds nothing to swap.

Quick sort works by splitting rather than by neighbour swaps. Choose a pivot: the middle item of the list. With n items it is in position ⌈(n + 1)/2⌉, so for an even number you take the one just right of centre (the 6th of 10). This page uses that convention throughout; whichever you use, use it consistently.

Write the items that belong before the pivot to its left, in the order they appear, then the pivot, then the rest in the order they appear. The pivot is now in its final position.

Each later pass chooses a pivot in every sublist of two or more items. Show the list after each pass and mark the pivots (underline or circle them).

The sort ends when every item has been a pivot or is alone in its sublist.

For descending order, items larger than the pivot go to its left. For words, "before" means earlier in the alphabet.

WORKED EXAMPLE · QUESTION

Use a quick sort to arrange 48, 73, 15, 62, 56, 37, 81, 24, 90 in descending order. Show the result of each pass and identify the pivots.

SOLUTION

Pass 1 9 items, so the pivot is the 5th, 56. Larger items go left, in their original order: 73, 62, 81, 90, 56, 48, 15, 37, 24.

Pass 2 Two sublists of 4; each pivot is the 3rd item (right of centre): [73, 62, 81, 90] → pivot 81; [48, 15, 37, 24] → pivot 37. List: 90, 81, 73, 62, 56, 48, 37, 15, 24.

Pass 3 Remaining sublists [73, 62] and [15, 24]; the pivot of a two-item sublist is its 2nd item. List: 90, 81, 73, 62, 56, 48, 37, 24, 15 (pivots 62 and 24).

Every item is now a pivot or alone in a sublist, so the sort is complete after 3 passes.

Checking every item in turn is slow for a long list. A binary search halves the problem each time, but it only works on a list that is already in order (numerical or alphabetical); sort it first if it is not.

Number the positions 1 to n and track the first and last positions still in play. The middle position is ⌈(first + last)/2⌉ (round up).

Compare the target with the middle item. If they match, stop. If the target comes before it, the new last is middle − 1; if after, the new first is middle + 1. Either way the middle item and one half are discarded.

If the list runs out (first > last) the item is not in the list; say so.

Each iteration roughly halves what is left, so n items need at most ⌊log₂ n⌋ + 1 iterations: the smallest k with 2ᵏ > n.

WORKED EXAMPLE · QUESTION

The names Amir, Bea, Carlos, Dmitri, Elena, Femi, Grace, Hiro, Ines, Jonas, Leila, Mateo, Nadia, Oscar, Priya are in positions 1 to 15. Use a binary search to (a) find Leila, (b) search for Kofi. Show each iteration.

SOLUTION

(a) ⌈(1 + 15)/2⌉ = 8, Hiro: Leila is after Hiro, so the list becomes 9–15. ⌈(9 + 15)/2⌉ = 12, Mateo: Leila is before Mateo, so 9–11. ⌈(9 + 11)/2⌉ = 10, Jonas: after, so 11–11. ⌈(11 + 11)/2⌉ = 11, Leila: found in position 11 after 4 iterations.

(b) Kofi is compared with the same names: Hiro (after) → Mateo (before) → Jonas (after) → Leila: Kofi is before Leila, so last = 10 < first = 11. The list is empty, so Kofi is not in the list.

Items of known sizes go into identical bins of fixed capacity, using as few bins as possible. "Bins" can be lorries, CDs, time slots, lengths of timber: anything with a capacity.

The lower bound is not always reachable. Three items of size 11 in bins of 20 have a lower bound of ⌈33/20⌉ = 2, but no two fit together, so 3 bins are needed.

WORKED EXAMPLE · QUESTION

Parcels of mass (kg) 7, 4, 12, 9, 3, 8, 6, 11, 5, 10 are loaded onto trolleys, each carrying at most 20 kg. (a) Find a lower bound for the number of trolleys. (b) Use first fit. (c) Use first-fit decreasing. (d) Explain whether (c) is optimal.

SOLUTION

(a) Total 75; 75 ÷ 20 = 3.75, so 4 trolleys.

(b) Items in the given order, each into the first trolley with room: T1: 7, 4, 9 · T2: 12, 3, 5 · T3: 8, 6 · T4: 11 · T5: 10, so 5 trolleys. The 9 goes into trolley 1 (7 + 4 + 9 = 20), not trolley 3: always check from the first bin.

(c) Sorted: 12, 11, 10, 9, 8, 7, 6, 5, 4, 3. T1: 12, 8 · T2: 11, 9 · T3: 10, 7, 3 · T4: 6, 5, 4, so 4 trolleys.

(d) 4 trolleys = the lower bound, so the solution is optimal.

The size of a problem is the number of items, n. The order of an algorithm describes how the amount of work (and so the run time) grows with n.

Linear (order n): doubling n doubles the time, for example adding up a list.

Quadratic (order n²): doubling n multiplies the time by 4: bubble sort, first fit and first-fit decreasing.

Cubic (order n³): doubling n multiplies the time by 8.

A binary search grows only like log₂ n: each extra iteration doubles the list it can handle. 1000 items need at most 10 iterations; a million at most 20.

To estimate a time for an algorithm of order nᵏ: t₂ ≈t₁ ×(n₂ ÷n₁)ᵏ. A bubble sort taking 2.4 s for 300 items takes about 2.4 × 4² = 38.4 s for 1200 items. These are estimates for large n; the exact count depends on the particular list (a sorted list needs only one bubble-sort pass).

WORKED EXAMPLE · QUESTION

A radio station has ten segments of lengths (minutes) 5, 15, 13, 14, 5, 10, 6, 17, 19, 16 to put into 30-minute slots; a segment cannot be split. (a) Find a lower bound for the number of slots. (b) Use first-fit decreasing. (c) Use full bins to find an allocation using the fewest slots, and explain why it is optimal. (d) First-fit decreasing has quadratic order; a program applies it to 250 items in 0.9 seconds. Estimate the time for 1000 items.

SOLUTION

(a) 120 ÷ 30 = 4, so 4 slots.

(b) Sorted: 19, 17, 16, 15, 14, 13, 10, 6, 5, 5. S1: 19, 10 · S2: 17, 13 · S3: 16, 14 · S4: 15, 6, 5 · S5: 5, so 5 slots.

(c) Combinations totalling exactly 30: 19 + 6 + 5 · 17 + 13 · 16 + 14 · 15 + 10 + 5, so 4 slots, equal to the lower bound, so optimal.

The total is exactly 4 × 30, so an optimal allocation must fill every slot, which is why full bins works so well here.

(d) n is multiplied by 4: 0.9 × (1000 ÷ 250)² = 0.9 × 16 = 14.4 seconds.

D1.2 Graphs, minimum spanning trees and Dijkstra

Kruskal's algorithm starts by sorting the arcs by weight (a sorting job), and Prim's and Dijkstra's algorithms are traced step by step exactly like the flow charts here.

Critical path analysis (D1)

The lower bound for the number of workers, ⌈total activity time ÷ critical time⌉, is the bin-packing lower bound in disguise, and allocating activities to workers is a packing problem.

P2 and P3

The binary search's ⌊log₂ n⌋ + 1 iterations come from solving 2ᵏ > n with logarithms (P2); iterative methods for equations in P3 are algorithms with a stopping condition, traced in a table just like worked example 1.

1. What is the largest number of comparisons a bubble sort can make on a list of 12 items, and how many passes can it need?

2. What is the largest number of iterations a binary search can need for an ordered list of 50 items?

3. Items of sizes 8, 7, 6, 5 and 4 are packed into bins of capacity 10. Show that the lower bound is 3 but that 4 bins are needed.

4. A sublist in a quick sort has 10 items. Which item is the pivot?

5. An algorithm of cubic order takes 5 seconds for 20 items. Estimate the time for 60 items.

6. Use first fit to pack 9, 6, 5, 8, 2, 4 into bins of capacity 12, and state whether the result is optimal.

1. 11 + 10 + … + 1 = ½ × 12 × 11 = 66 comparisons, in at most 11 passes.

2. 2⁵ = 32 ≤ 50 < 64 = 2⁶, so at most 6 iterations.

3. Total 30, 30 ÷ 10 = 3. But 8 and 7 cannot share a bin with any other item (the smallest is 4), so each needs its own bin, and 6, 5 and 4 (total 15) need two more: 4 in all.

4. The 6th item, ⌈(10 + 1)/2⌉ = 6: the one just right of centre.

5. 5 × (60 ÷ 20)³ = 5 × 27 = 135 seconds.

6. Bin 1: 9, 2 · Bin 2: 6, 5 · Bin 3: 8, 4. Total 34, lower bound ⌈34/12⌉ = 3, so 3 bins is optimal.