Decomposition

Breaking a large problem into smaller, more manageable sub-problems. Each sub-problem can be solved independently and combined.

• Easier to assign to different developers
• Each part easier to test in isolation
• Matches to modular programming

Divide and Conquer

A specific algorithmic strategy: divide the problem into sub-problems of the same type, conquer each recursively, combine results.

• Examples: merge sort, binary search, quicksort
• Usually gives O(log n) or O(n log n) complexity
• Much better than brute-force for large datasets

Operations

// Push — add to top
procedure push(stack, item)
  if top < maxSize-1 then
    top = top + 1
    stack[top] = item
  else
    print("Stack overflow")
  endif
endprocedure

// Pop — remove from top
function pop(stack)
  if top >= 0 then
    item = stack[top]
    top = top - 1
    return item
  else
    print("Stack underflow")
  endif
endfunction

// Peek — see top without removing
function peek(stack)
  return stack[top]
endfunction

// isEmpty
function isEmpty()
  return top == -1
endfunction

Key Points

• Top pointer starts at -1 (empty)
• Push: increment top, then insert
• Pop: read top, then decrement
• Overflow = push onto full stack
• Underflow = pop from empty stack
• Size = top + 1

Uses of Stacks

• Call stack (function calls in recursion)
• Undo functionality in editors
• Browser back button
• Expression evaluation

Complexity

// Enqueue — add to back
procedure enqueue(queue, item)
  if back < maxSize-1 then
    queue[back] = item
    back = back + 1
  else
    print("Queue full")
  endif
endprocedure

// Dequeue — remove from front
function dequeue(queue)
  if front != back then
    item = queue[front]
    front = front + 1
    return item
  else
    print("Queue empty")
  endif
endfunction

// isEmpty: front == back
// Size: back - front

Key Points

• Front and back both start at 0
• Empty when front == back
• Size = back − front
• A circular queue wraps the back pointer round to reuse freed space at the front

Uses of Queues

• CPU scheduling (process queues)
• Printer job queues
• Breadth-first search (uses a queue)
• Keyboard input buffer

Traversal

procedure traverse(head)
  current = head
  while current != null
    print(current.data)
    current = current.next
  endwhile
endprocedure

Advantages over arrays

• Dynamic size — no need to declare size in advance
• Efficient insertions/deletions (just update pointers)

Disadvantages

• No random access — must traverse from head: O(n)
• Extra memory for pointers
• Not cache-friendly

Complexity

Depth-First (Post-Order)

OCR spec specifically names post-order for depth-first. Visit left subtree → right subtree → root.

procedure postOrder(node)
  if node != null then
    postOrder(node.left)
    postOrder(node.right)
    print(node.data)
  endif
endprocedure

Breadth-First Traversal

Visits nodes level by level (top to bottom, left to right). Uses a queue.

procedure breadthFirst(root)
  queue.enqueue(root)
  while queue NOT empty
    node = queue.dequeue()
    print(node.data)
    if node.left != null
      queue.enqueue(node.left)
    endif
    if node.right != null
      queue.enqueue(node.right)
    endif
  endwhile
endprocedure

function bubbleSort(array)
  n = length(array)
  swapped = True
  while swapped
    swapped = False
    for i = 0 to n-2
      if array[i] > array[i+1] then
        temp = array[i]
        array[i] = array[i+1]
        array[i+1] = temp
        swapped = True
      endif
    next i
  endwhile
  return array
endfunction

Trace: [5, 3, 1, 4]

Key Points

• The swapped flag is an optimisation — stops early if no swaps in a pass (best case O(n))
• After pass k, the last k elements are guaranteed sorted
• Simple but slow — rarely used in practice

function insertionSort(array)
  n = length(array)
  for i = 1 to n-1
    key = array[i]
    j = i - 1
    while j >= 0 AND array[j] > key
      array[j+1] = array[j]
      j = j - 1
    endwhile
    array[j+1] = key
  next i
  return array
endfunction

Trace: [5, 3, 1, 4]

Key Points

• The sorted portion grows by one element each iteration
• Very efficient for nearly sorted data
• Note: the sorted elements are NOT necessarily the smallest i elements

function mergeSort(array)
  if length(array) <= 1 then
    return array
  endif
  mid = length(array) DIV 2
  left = mergeSort(array[0:mid])
  right = mergeSort(array[mid:])
  return merge(left, right)
endfunction

function merge(left, right)
  result = []
  while left != [] AND right != []
    if left[0] <= right[0] then
      result.append(left[0])
      left = left[1:]
    else
      result.append(right[0])
      right = right[1:]
    endif
  endwhile
  return result + left + right
endfunction

Trace: [5, 3, 1, 4]

Key Points

• Always O(n log n) — most consistent sort
• Requires O(n) extra space for the merging step
• The exact implementation of merge is not required — just how it works conceptually

function quickSort(array)
  if length(array) <= 1 then
    return array
  endif
  pivot = array[mid]
  left = [x for x in array
          if x < pivot]
  middle = [x for x in array
            if x == pivot]
  right = [x for x in array
           if x > pivot]
  return quickSort(left) +
         middle +
         quickSort(right)
endfunction

Trace: [5, 3, 1, 4, 2] — pivot = 3

Key Points

• Pivot choice matters — middle element is common in exams
• Once a pivot is placed, it never moves
• Worst case O(n²) when pivot is always smallest/largest
• O(log n) space (recursive call stack)

function linearSearch(array, target)
  for i = 0 to length(array)-1
    if array[i] == target then
      return i     // found at index i
    endif
  next i
  return -1        // not found
endfunction

Properties

• Complexity: O(n)
• Works on unsorted data
• Simple to implement
• Very inefficient for large datasets
• Best case: target is first element O(1)
• Worst case: target not in list — checks all n elements

function binarySearch(array, target)
  first = 0
  last = length(array) - 1
  while first <= last
    mid = (first + last) DIV 2
    if array[mid] == target then
      return mid
    elseif array[mid] < target then
      first = mid + 1
    else
      last = mid - 1
    endif
  endwhile
  return -1  // not found
endfunction

Trace: find 7 in [1,3,5,7,9,11]

Properties

How it works

vs Dijkstra's