Algorithms

An algorithm is a step-by-step procedure for solving a class of problems. To count as an algorithm, the procedure must be:

1. Finite — has a defined ending.
2. Ordered — steps are performed in a specified sequence.
3. Unambiguous — each step has a single, clear interpretation.
4. Executable — each step can be performed in finite time.
5. Terminating — finishes after a finite number of steps (no infinite loops).

Two ways to express an algorithm in D1:

Pseudocode — structured English. Example:

INPUT N
SET A = 1
FOR k = 1 TO N
  A = A * k
NEXT k
OUTPUT A

Flowchart — diagrammatic. Standard shapes:

• Rounded rectangle: START / STOP.
• Parallelogram: INPUT / OUTPUT.
• Rectangle: process / assignment.
• Diamond: decision (yes/no branch).

Trace table. When asked to 'execute' or 'trace' an algorithm for a given input, build a table with one row per loop iteration and a column for each variable. Edexcel mark schemes split M and A marks across the rows — partial tables forfeit multiple marks.

Worked example. Trace the factorial pseudocode above with $N = 4$.

Output $A = 24 = 4!$.

Procedure. To sort a list into ascending order:

1. Compare the first two items. If left $>$ right, swap them.
2. Compare the next pair. Swap if needed.
3. Continue to the end of the list — this completes ONE PASS.
4. Repeat from the start of the list.
5. Stop after a complete pass during which NO SWAPS occurred.

After Pass 1 the largest item is at the right (it 'bubbles up' to the top). After Pass 2 the second-largest is in position. After at most $n - 1$ passes the list is sorted; Edexcel still expects the terminating no-swap pass.

Worked example. Sort $7, 3, 9, 4, 6$ ascending.

Pass 1:

Pass 2: $3, 7, 4, 6, 9$ → $3, 7, 4, 6, 9$ → $3, 4, 7, 6, 9$ → $3, 4, 6, 7, 9$ → $3, 4, 6, 7, 9$.

Pass 3: $3, 4, 6, 7, 9$ — NO SWAPS. Sort terminates.

Sorted: $3, 4, 6, 7, 9$.

Number of comparisons. Pass 1 makes $n - 1$ comparisons; Pass 2 makes $n - 2$ (the last position is already correct); and so on. Worst case: $\text{Comparisons} \le (n-1) + (n-2) + \ldots + 1 = \tfrac{1}{2}n(n-1).$

For $n = 5$, that's $10$ comparisons in the worst case.

Sorting descending. Reverse the comparison: swap when left $<$ right. The structure of the algorithm is unchanged.

Edexcel pivot rule. Use the MIDDLE element of the current sub-list. If the sub-list has even length, round the middle position UP (i.e. take the right of the two centre items).

Procedure.

1. Choose the pivot of the current (sub-)list.
2. Partition: items $\le$ pivot go to the left of the pivot in their ORIGINAL relative order; items $>$ pivot go to the right in their original relative order.
3. Box / underline the pivot to show it is now in its final sorted position.
4. Apply the same procedure to each sub-list on the left and the right.
5. Continue until every item is a pivot (i.e. all sub-lists have length $\le 1$).

Worked example. Sort $8, 3, 11, 5, 7, 2, 9$.

Sorted: $2, 3, 5, 7, 8, 9, 11$.

Key checks.

• Pivots NEVER move once placed.
• Items within each sub-list KEEP their original order.
• Edexcel mark schemes track pivots by row — always show each row of the list after a pivot is placed.

Comparison with bubble sort. Quick sort is much faster on long lists (average performance $O(n \log n)$ vs bubble sort's $O(n^{2})$), but bubble sort is simpler to implement and easier to trace by hand.

Problem. A list of items with positive weights must be packed into bins of fixed capacity. Find a packing using as few bins as possible.

Lower bound. No packing uses fewer than $\left\lceil \dfrac{\text{total weight}}{\text{bin capacity}} \right\rceil$ bins. A packing that achieves the lower bound is OPTIMAL.

First-fit (FF).

• Take items in the given order.
• Place each item into the FIRST bin (lowest-numbered) with enough remaining capacity.
• If no bin fits, open a new one.

Pros: fast; deterministic. Cons: order-dependent; often uses more bins than necessary.

First-fit decreasing (FFD).

• SORT items into decreasing order of weight.
• Apply first-fit to the sorted list.

Why it works: heavy items are placed when bins are empty; smaller items fill the leftover gaps.

Full-bin packing (FB).

• A HEURISTIC: visually identify items whose weights sum exactly to the bin capacity, and put them together.
• Pack the remaining items by first-fit (or FFD) on what's left.

Pros: often optimal when exact-fit combinations exist. Cons: requires inspection; not algorithmic in the strict sense.

Worked example. Items $6, 4, 7, 3, 5, 8, 2, 4, 6$ kg, bin capacity $10$ kg. Total $= 45$ kg. Lower bound $= \lceil 45/10 \rceil = 5$.

Worst case for FF. When small items come first and 'lock up' bins, FF can use up to $\tfrac{17}{10}$ times the optimal. FFD is usually much closer to optimal — a famous theoretical bound is $\tfrac{11}{9} \cdot \text{OPT} + 6/9$.

Edexcel D1 papers regularly include a flowchart or pseudocode that students must EXECUTE and identify. The standard question pattern:

• (a) Trace the algorithm for a given input. Build a trace table.
• (b) State the output, or identify what the algorithm computes.
• (c) Modify the algorithm — e.g. 'add a step so that ...' or 'what would the output be if you replaced $\le$ with $<$ in step 3?'.

Step-by-step approach.

1. Read the entire algorithm BEFORE filling in any values.
2. Identify all variables (loop counters, accumulators, flags).
3. Make a column in the trace table for each variable.
4. Start with the initialisation row.
5. Step through each instruction; update the corresponding column.
6. For loops, do one row per iteration.
7. For decisions (diamonds), record which branch is taken.

Worked example. Pseudocode:

INPUT N
SET S = 0
FOR k = 1 TO N
  IF k is odd THEN
    S = S + k
  END IF
NEXT k
OUTPUT S

Trace for $N = 5$:

Output $S = 9$. Algorithm computes the sum of odd integers from $1$ to $N$.

Identifying the purpose. Often the question ends 'state in words what the algorithm computes'. Common answers: factorial, sum, mean, maximum, GCD, primality test, sorting.