Algorithms (Edexcel IAL Math D1)

Edexcel International A-Level Mathematics· WDM11 2018 Specification Issue 3· 25 min read

1. 1. Fundamentals of Algorithms & Middle Item Rule★★☆☆☆⏱ 5 min

✓ Calculator OK

An algorithm is a finite sequence of step-by-step instructions to complete a task. You will be required to implement algorithms provided as text or flowcharts, and apply the middle-item rule for pivot selection in sorting and search algorithms.

📘 Definition

Middle Item Rule

To find the position of the middle item in a list of N items: If N is odd, position = $⌈ \frac{1}{2} (N + 1)⌉$ . If N is even, position = $\frac{1}{2} (N + 2)$ .

Example:

For a list of 6 items: N=6 even, position = 4th item. For 5 items: N=5 odd, position = 3rd item.

📐 Worked Example

Find the position of the middle item for a list of N=7 items and N=8 items.

1
For N=7 (odd): Apply the odd N formula
$\left\lceil \frac{7+1}{2} \right\rceil = 4$
2
Middle item for N=7 is at position 4
3
For N=8 (even): Apply the even N formula
$\frac{8+2}{2} = 5$
4
Middle item for N=8 is at position 5

Exam tip:

Always write the middle position first before selecting the value from the list to avoid losing marks for incorrect pivot selection.

2. 2. Bubble Sort Algorithm★★☆☆☆⏱ 5 min

✓ Calculator OK

Bubble sort works by repeatedly passing through a list, comparing adjacent pairs of items and swapping them if they are in the wrong order, until the list is sorted. You must show every pass and every swap in your working to gain full marks.

📘 Definition

Bubble Sort

Sorting algorithm that compares adjacent items, swaps misordered pairs, and repeats until no swaps are made in a full pass.

Example:

Sorting [3,1,4,2] into ascending order requires 3 full passes.

📐 Worked Example

Sort the list [7, 2, 9, 1, 5] into ascending order using bubble sort, showing all passes.

1
Pass 1: Compare adjacent pairs, swap if out of order: 7↔2 swap, 7&9 no swap, 9↔1 swap, 9↔5 swap → end of pass 1: [2,7,1,5,9] (last item sorted)
2
Pass 2: Check first 4 items: 2&7 no swap,7↔1 swap,7↔5 swap → end of pass 2: [2,1,5,7,9] (last 2 items sorted)
3
Pass 3: Check first 3 items: 2↔1 swap, 2&5 no swap → end of pass 3: [1,2,5,7,9] (last 3 items sorted)
4
Pass 4: Check first 2 items: 1&2 no swap, no swaps in full pass → list sorted
5
Final sorted list: [1,2,5,7,9]

Exam tip:

After each pass, the next highest unsorted item 'bubbles' to its correct position, so you can reduce the number of comparisons per pass by 1 each time to save time.

3. 3. Quick Sort Algorithm (Middle Item Pivot)★★★☆☆⏱ 5 min

✓ Calculator OK

Quick sort is a divide-and-conquer sorting algorithm that uses a pivot element to split the list into sublists of items less than the pivot and items greater than the pivot, then recursively sorts each sublist. You must use the middle item rule to select the pivot for every sublist.

📘 Definition

Quick Sort

Divide-and-conquer sorting algorithm that selects a pivot, rearranges the list so items less than pivot are left, items greater are right, then repeats for each sublist until all items are sorted.

Example:

Pivot selection for a sublist of 4 items uses the 3rd item as per the middle item rule.

📐 Worked Example

Sort the list [6, 3, 8, 1, 9, 2] into ascending order using quick sort, selecting pivots using the middle item rule.

1
Original list N=6 even: pivot position = 4th item = 1. Split: items <1 = [], pivot = [1], items >1 = [6,3,8,9,2]
2
Sort right sublist [6,3,8,9,2], N=5 odd: pivot position = 3rd item =8. Split: items <8 = [6,3,2], pivot = [8], items>8 = [9]
3
Sort [6,3,2], N=3 odd: pivot position = 2nd item =3. Split: items <3 = [2], pivot = [3], items>3 = [6]
4
Combine all sorted components: [] + [1] + [2,3,6] + [8] + [9] = [1,2,3,6,8,9]

Exam tip:

Always label each pivot clearly and show every sublist split to gain full method marks, even if you can see the sorted list immediately.

4. 4. Bin Packing Algorithms★★★☆☆⏱ 5 min

✓ Calculator OK

Bin packing aims to pack items of given sizes into the minimum number of fixed-capacity bins. You need to know three methods: first-fit, first-fit decreasing, and full-bin packing.

📘 Definition

Bin Packing Methods

First-fit: Place each item in the first bin it fits into, in the given order. 2. First-fit decreasing: Sort items in descending order first, then apply first-fit. 3. Full-bin: Combine items to fill as many full bins as possible first, then pack remaining items with first-fit.

Example:

Full-bin packing gives the optimal (minimum) number of bins where possible, while first-fit is an approximate heuristic.

📐 Worked Example

Pack items of sizes 6, 3, 5, 7, 2, 4 into bins of capacity 10, using (a) first-fit, (b) first-fit decreasing, (c) full-bin packing.

1
(a) First-fit: Process items in given order. Result: Bin1(6,3), Bin2(5,2), Bin3(7), Bin4(4) → 4 bins used
2
(b) First-fit decreasing: Sort items descending first: [7,6,5,4,3,2]. Apply first-fit: Bin1(7,3), Bin2(6,4), Bin3(5,2) → 3 bins used
3
(c) Full-bin packing: Identify full bins first: 7+3=10, 6+4=10. Remaining items 5,2 fit in Bin3 → 3 bins used

Exam tip:

Explicitly show the sorted item list for first-fit decreasing, and all full bin combinations for full-bin packing to get full marks.

5. 5. Binary Search Algorithm★★☆☆☆⏱ 3 min

✓ Calculator OK

Binary search is used to find a target item in an ORDERED list only, by repeatedly comparing the target to the middle item of the current sublist, eliminating half the list each time until the target is found or confirmed absent.

📘 Definition

Binary Search

Efficient search algorithm for ordered lists that uses the middle item to eliminate half the search space with each comparison, until the target is located or determined missing.

📐 Worked Example

Use binary search to find the target value 10 in the ordered list [1,2,4,5,7,9,10,12]. Show all steps.

1
Original list N=8 even: middle position = 5th item =7. 10>7, eliminate left half, search right sublist [9,10,12]
2
Sublist N=3 odd: middle position = 2nd item =10. Middle item equals target, found at position 7 in original list

Exam tip:

Binary search only works on pre-ordered lists. If you are given an unordered list, sort it first before applying binary search, and state that you have done so.

6. Common Pitfalls

Wrong move:

Using the wrong formula for middle item position (e.g., N/2 for even N)

Why:

Edexcel explicitly requires the specified middle item rule, so incorrect pivot selection loses all method marks for quick sort and binary search.

Correct move:

Memorise: odd N → $⌈ \frac{1}{2} (N + 1)⌉$ , even N → $\frac{1}{2} (N + 2)$ . Write the position down before selecting the pivot value.

Wrong move:

Skipping passes or swaps in bubble sort, only showing the final sorted list

Why:

Marks are awarded for each correct intermediate pass, so missing steps lead to lost method marks even if the final list is correct.

Correct move:

Write down every comparison and swap made in each pass, and label each pass clearly.

Wrong move:

Using first-fit directly without sorting items for first-fit decreasing bin packing

Why:

First-fit decreasing requires items to be sorted in descending order first, skipping this step means you are using the wrong method.

Correct move:

Always explicitly sort items into descending order before applying first-fit for the first-fit decreasing method, and show the sorted list.

Wrong move:

Applying binary search to an unordered list

Why:

Binary search only works on sorted lists, using it on unordered data will give incorrect results and no marks.

Correct move:

Check the list is ordered first; if not, sort it before beginning binary search, and state this step.

Wrong move:

Assuming first-fit bin packing gives the optimal number of bins

Why:

First-fit is a heuristic, not an optimal algorithm, so it often uses more bins than necessary.

Correct move:

State that full-bin packing gives the optimal solution where possible, and first-fit/first-fit decreasing are approximate methods.

7. Quick Reference Cheatsheet

Algorithm	Key Steps	Exam Requirement
Middle Item Rule	Odd N: $⌈ \frac{1}{2} (N + 1)⌉$ , Even N: $\frac{1}{2} (N + 2)$	Calculate position before selecting value
Bubble Sort	Compare adjacent pairs, swap misordered, repeat until no swaps	Show every pass and all swaps
Quick Sort	Select middle pivot, split into < pivot / > pivot sublists, repeat	Label all pivots and sublist splits
First-fit Bin Packing	Place each item in first available bin it fits	Process items in given order
First-fit Decreasing Bin Packing	Sort items descending, then apply first-fit	Show sorted item list first
Full-bin Bin Packing	Fill as many full bins as possible first, pack remaining with first-fit	Show all full bin combinations
Binary Search	Compare target to middle of ordered list, eliminate half, repeat	Only use on ordered lists, show all comparisons

8. Frequently Asked

Do I need to show every step of sorting algorithms?

Yes, Edexcel awards marks for each correct pass/comparison, so you must write every intermediate step clearly, even if you know the final sorted list immediately.

Which pivot rule do I use for quick sort?

You must use the middle-item rule: for a list of N items, position = $⌈ \frac{1}{2} (N + 1)⌉$ if N is odd, and $\frac{1}{2} (N + 2)$ if N is even. Always state the position before selecting the pivot value.

Going deeper

What's Next

Now that you have mastered core D1 algorithms, you are ready to move on to graphs and networks, the next foundational topic in Edexcel IAL Decision Maths 1. Practice applying these algorithms to past paper questions to build speed and accuracy, as algorithm questions make up ~15% of the D1 IAS paper. Make sure you always show full working for every step, as Edexcel awards most marks for method rather than final answers. You should also practice interpreting algorithm flowcharts, a common exam question format that builds directly on the content covered here.