Algorithms & Programs

Algorithm Definition

An algorithm must be:

• Finite — it must eventually stop
• Unambiguous — each step must be clearly defined with no room for interpretation
• Effective — each step must be achievable in a finite amount of time
• General — it must solve all instances of the problem, not just one specific case

Expressing Algorithms: Pseudo-code

Pseudo-code is a structured, language-independent way of writing algorithms. It uses natural language mixed with programming constructs and is independent of any specific syntax. The goal is clarity — anyone should be able to implement the algorithm in any language from the pseudo-code.

Common conventions:

SET total TO 0
INPUT value
WHILE value != -1
    SET total TO total + value
    INPUT value
END WHILE
OUTPUT total

Key keywords: SET, INPUT, OUTPUT, IF, THEN, ELSE, END IF, WHILE, END WHILE, FOR, END FOR, REPEAT, UNTIL, FUNCTION, PROCEDURE, RETURN, CALL.

Expressing Algorithms: Flowcharts

A flowchart is a visual representation of an algorithm using standard symbols:

Symbol	Shape	Purpose
Terminator	Oval	Start or End of the algorithm
Process	Rectangle	An action or computation
Input/Output	Parallelogram	Reading input or producing output
Decision	Diamond	A condition with Yes/No branches
Flow line	Arrow	Direction of flow

Flowcharts are useful for showing the flow of control, especially loops and branching, in a visual format that is easy to trace by hand.

---

Recursion

Base Case and Recursive Case

Every recursive function has two essential parts:

• Base case: The simplest instance of the problem that can be answered directly without further recursion. Without a base case, the recursion would continue forever (in practice, until the call stack overflows).
• Recursive case: The function calls itself with a modified argument that moves closer to the base case.

The Call Stack and Stack Frames

When a recursive function calls itself, each call creates a new stack frame. These frames accumulate on the stack until a base case is reached. Then, the frames are popped one by one as each call returns its result to the caller.

Key points about the call stack:

• The stack has a finite size. Too many recursive calls cause a stack overflow.
• Each stack frame stores the function’s local variables, parameters, and the return address (where to resume after the call returns).
• Frames are processed in LIFO (Last In, First Out) order.

Example: Factorial

The factorial of n is defined as:

• 0! = 1 (base case)
• n! = n x (n-1)! for n > 0 (recursive case)

def factorial(n):
    if n == 0:          # Base case
        return 1
    else:               # Recursive case
        return n * factorial(n - 1)

print(factorial(5))     # Output: 120

Function Factorial(n As Integer) As Long
    If n = 0 Then       ' Base case
        Return 1
    Else                 ' Recursive case
        Return n * Factorial(n - 1)
    End If
End Function

Sub Main()
    Console.WriteLine(Factorial(5))   ' Output: 120
End Sub

Tracing the call stack for factorial(4):

Call	Stack state (top to bottom)	Returns
factorial(4)	factorial(4)	4 * factorial(3)
factorial(3)	factorial(3), factorial(4)	3 * factorial(2)
factorial(2)	factorial(2), factorial(3), factorial(4)	2 * factorial(1)
factorial(1)	factorial(1), factorial(2), factorial(3), factorial(4)	1 * factorial(0)
factorial(0)	factorial(0), factorial(1), factorial(2), factorial(3), factorial(4)	1 (base case)

Then the stack unwinds: 1 * 1 = 1, then 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24.

Example: Fibonacci

The Fibonacci sequence is defined as:

• fib(0) = 0 (base case)
• fib(1) = 1 (base case)
• fib(n) = fib(n-1) + fib(n-2) for n > 1 (recursive case)

def fibonacci(n):
    if n == 0:              # Base case 1
        return 0
    elif n == 1:            # Base case 2
        return 1
    else:                   # Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

Function Fibonacci(n As Integer) As Long
    If n = 0 Then            ' Base case 1
        Return 0
    ElseIf n = 1 Then        ' Base case 2
        Return 1
    Else                      ' Recursive case
        Return Fibonacci(n - 1) + Fibonacci(n - 2)
    End If
End Function

Sub Main()
    For i As Integer = 0 To 9
        Console.Write(Fibonacci(i) & " ")
    Next
    ' Output: 0 1 1 2 3 5 8 13 21 34
End Sub

---

Elegance of Recursion vs Iteration

Comparison

Aspect	Recursion	Iteration
Code length	Often shorter and more readable	May require more code (loop, variables)
Mirrors definition	Directly reflects mathematical definitions	Must manually manage state
Memory usage	Uses call stack space (O(n) or more)	Typically O(1) extra space
Risk of overflow	Stack overflow for deep recursion	No stack overflow risk
Performance	Function call overhead per recursion	Generally faster due to no call overhead
Suitability	Tree traversals, divide-and-conquer, backtracking	Simple loops, accumulation

Factorial: Recursive vs Iterative

# Recursive -- elegant but uses O(n) stack space
def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative -- less elegant but O(1) extra space
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

' Recursive
Function FactorialRecursive(n As Integer) As Long
    If n = 0 Then Return 1
    Return n * FactorialRecursive(n - 1)
End Function

' Iterative
Function FactorialIterative(n As Integer) As Long
    Dim result As Long = 1
    For i As Integer = 2 To n
        result *= i
    Next
    Return result
End Function

When Recursion is Truly Elegant

Some problems are naturally recursive and become awkward or complex when written iteratively:

• Tree traversals – visiting every node in a binary tree is naturally expressed recursively.
• Divide-and-conquer algorithms – merge sort and quick sort split the problem into subproblems.
• Backtracking – problems like maze solving or the N-queens puzzle benefit from recursive exploration of possibilities.

For these problems, an iterative solution would require manually managing a stack data structure, which is essentially reimplementing what the call stack does automatically.

---

Merge Sort

Algorithm

1. Divide: If the list has more than one element, split it into two roughly equal halves.
2. Conquer: Recursively sort each half.
3. Merge: Combine the two sorted halves into one sorted list by comparing elements from the front of each half and appending the smaller one.

Worked Example

Sort the list: [38, 27, 43, 3, 9, 82, 10]

Splitting phase:

graph TD
    A["38, 27, 43, 3, 9, 82, 10"] --> B["38, 27, 43"]
    A --> C["3, 9, 82, 10"]
    B --> D["38"]
    B --> E["27, 43"]
    C --> F["3, 9"]
    C --> G["82, 10"]
    E --> H["27"]
    E --> I["43"]
    F --> J["3"]
    F --> K["9"]
    G --> L["82"]
    G --> M["10"]

Merging phase (bottom-up):

       [27] [43]  -->  [27, 43]
 [38] + [27, 43]  -->  [27, 38, 43]

       [3] [9]    -->  [3, 9]
       [82] [10]  -->  [10, 82]
 [3, 9] + [10, 82]  -->  [3, 9, 10, 82]

 [27, 38, 43] + [3, 9, 10, 82]  -->  [3, 9, 10, 27, 38, 43, 82]

Code

Merge sort can be written as a single recursive function. After the two recursive calls, the merge step uses two pointers: i for the left half and j for the right half.

Pseudo-code:

FUNCTION mergeSort(list)
    IF length(list) <= 1 THEN
        RETURN list                          // Base case
    END IF

    SET mid TO length(list) DIV 2
    SET left TO mergeSort(list[0 .. mid-1])  // Recursive call
    SET right TO mergeSort(list[mid .. end]) // Recursive call

    // Merge step
    SET result TO empty list
    SET i TO 0                               // Pointer for left
    SET j TO 0                               // Pointer for right
    WHILE i < length(left) AND j < length(right)
        IF left[i] <= right[j] THEN          // <= ensures stability
            APPEND left[i] TO result
            SET i TO i + 1
        ELSE
            APPEND right[j] TO result
            SET j TO j + 1
        END IF
    END WHILE

    // Append any remaining elements
    WHILE i < length(left)
        APPEND left[i] TO result
        SET i TO i + 1
    END WHILE
    WHILE j < length(right)
        APPEND right[j] TO result
        SET j TO j + 1
    END WHILE

    RETURN result
END FUNCTION

def merge_sort(arr):
    if len(arr) <= 1:              # Base case
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # Recursively sort left half
    right = merge_sort(arr[mid:])  # Recursively sort right half

    # Merge step
    result = []
    i = 0   # Pointer for left
    j = 0   # Pointer for right
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:    # <= ensures stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Append any remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))
# Output: [3, 9, 10, 27, 38, 43, 82]

Function MergeSort(arr As List(Of Integer)) As List(Of Integer)
    If arr.Count <= 1 Then       ' Base case
        Return arr
    End If

    Dim mid As Integer = arr.Count \ 2
    Dim left As List(Of Integer) = MergeSort(arr.GetRange(0, mid))
    Dim right As List(Of Integer) = MergeSort(arr.GetRange(mid, arr.Count - mid))

    ' Merge step
    Dim result As New List(Of Integer)
    Dim i As Integer = 0   ' Pointer for left
    Dim j As Integer = 0   ' Pointer for right

    While i < left.Count AndAlso j < right.Count
        If left(i) <= right(j) Then   ' <= ensures stability
            result.Add(left(i))
            i += 1
        Else
            result.Add(right(j))
            j += 1
        End If
    End While

    ' Append remaining elements
    While i < left.Count
        result.Add(left(i))
        i += 1
    End While
    While j < right.Count
        result.Add(right(j))
        j += 1
    End While

    Return result
End Function

Sub Main()
    Dim data As New List(Of Integer) From {38, 27, 43, 3, 9, 82, 10}
    Dim sorted As List(Of Integer) = MergeSort(data)
    Console.WriteLine(String.Join(", ", sorted))
    ' Output: 3, 9, 10, 27, 38, 43, 82
End Sub

Merge sort never swaps elements. It builds a new result list by repeatedly copying the smaller front item from left (pointer i) or right (pointer j). Compare this with quick sort, which sorts in place using swaps.

Characteristics of Merge Sort

Characteristic	Detail
Type	Divide and conquer
Time complexity (best)	O(n log n)
Time complexity (average)	O(n log n)
Time complexity (worst)	O(n log n)
Space complexity	O(n) – requires additional space for merging
Stable	Yes – equal elements maintain their original relative order
In-place	No – requires O(n) extra memory
Recursive	Yes

---

Quick Sort

Algorithm

1. Choose a pivot – commonly the first element, last element, middle element, or a random element.
2. Partition – rearrange elements so that all elements less than the pivot are to its left, and all elements greater are to its right. The pivot is now in its final sorted position.
3. Recurse – recursively apply quick sort to the left partition and the right partition.
4. Base case – a list with 0 or 1 elements is already sorted.

Pivot Selection

The choice of pivot affects performance:

Strategy	Description	Risk
First element	Simple but poor for already-sorted data	O(n^2) on sorted input
Last element	Simple but same risk as first	O(n^2) on sorted input
Middle element	Reasonable compromise	Less likely to hit worst case
Median-of-three	Median of first, middle, last	Good balance of simplicity and performance
Random	Choose a random element	Statistically avoids worst case

Worked Example

Sort the list: [7, 2, 1, 6, 8, 5, 3, 4] using the last element as the pivot (this matches the code below).

Pass 1: Pivot = 4, low = 0, high = 7, i starts at -1

j moves from left to right. Whenever list[j] <= pivot, add 1 to i and swap list[i] and list[j].

j	list[j]	<= 4?	i	Action	List after
0	7	No	-1	–	[7, 2, 1, 6, 8, 5, 3, 4]
1	2	Yes	0	Swap list[0] and list[1]	[2, 7, 1, 6, 8, 5, 3, 4]
2	1	Yes	1	Swap list[1] and list[2]	[2, 1, 7, 6, 8, 5, 3, 4]
3	6	No	1	–	[2, 1, 7, 6, 8, 5, 3, 4]
4	8	No	1	–	[2, 1, 7, 6, 8, 5, 3, 4]
5	5	No	1	–	[2, 1, 7, 6, 8, 5, 3, 4]
6	3	Yes	2	Swap list[2] and list[6]	[2, 1, 3, 6, 8, 5, 7, 4]

Finally, swap the pivot into position i + 1 = 3:

[2, 1, 3] [4] [8, 5, 7, 6]

4 is now in its final position (index 3).

Pass 2a: Sort left partition [2, 1, 3], pivot = 3

[2, 1] [3]

3 is in its final position.

Pass 2b: Sort right partition [8, 5, 7, 6], pivot = 6

[5] [6] [7, 8]

6 is in its final position.

Pass 3a: Sort [2, 1], pivot = 1

[1] [2]

Pass 3b: Sort [7, 8], pivot = 8

[7] [8]

Final sorted list: [1, 2, 3, 4, 5, 6, 7, 8]

Code

Quick sort can be written as a single recursive function that sorts the list in place. The partition step uses two pointers: j scans through the list, and i marks the end of the “less than or equal to pivot” section. Unlike merge sort, quick sort swaps elements.

Pseudo-code:

PROCEDURE quickSort(list, low, high)
    IF low < high THEN                       // Base case: 0 or 1 items -> do nothing
        // Partition step
        SET pivot TO list[high]              // Last element as pivot
        SET i TO low - 1
        FOR j FROM low TO high - 1
            IF list[j] <= pivot THEN
                SET i TO i + 1
                SWAP list[i] AND list[j]
            END IF
        END FOR
        SWAP list[i + 1] AND list[high]      // Place pivot in final position

        quickSort(list, low, i)              // Recursive call (left of pivot)
        quickSort(list, i + 2, high)         // Recursive call (right of pivot)
    END IF
END PROCEDURE

def quick_sort(arr, low, high):
    if low < high:                 # Base case: 0 or 1 items -> do nothing
        # Partition step
        pivot = arr[high]          # Last element as pivot
        i = low - 1                # End of the "<= pivot" section
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]        # Swap
        arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Place pivot

        quick_sort(arr, low, i)       # Recursively sort left of pivot
        quick_sort(arr, i + 2, high)  # Recursively sort right of pivot

data = [7, 2, 1, 6, 8, 5, 3, 4]
quick_sort(data, 0, len(data) - 1)
print(data)
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

Sub QuickSort(arr As List(Of Integer), low As Integer, high As Integer)
    If low < high Then             ' Base case: 0 or 1 items -> do nothing
        ' Partition step
        Dim pivot As Integer = arr(high)   ' Last element as pivot
        Dim i As Integer = low - 1         ' End of the "<= pivot" section
        Dim temp As Integer

        For j As Integer = low To high - 1
            If arr(j) <= pivot Then
                i += 1
                ' Swap arr(i) and arr(j)
                temp = arr(i)
                arr(i) = arr(j)
                arr(j) = temp
            End If
        Next

        ' Place pivot in final position
        temp = arr(i + 1)
        arr(i + 1) = arr(high)
        arr(high) = temp

        QuickSort(arr, low, i)         ' Recursively sort left of pivot
        QuickSort(arr, i + 2, high)    ' Recursively sort right of pivot
    End If
End Sub

Sub Main()
    Dim data As New List(Of Integer) From {7, 2, 1, 6, 8, 5, 3, 4}
    QuickSort(data, 0, data.Count - 1)
    Console.WriteLine(String.Join(", ", data))
    ' Output: 1, 2, 3, 4, 5, 6, 7, 8
End Sub

After the partition step, the pivot sits at index i + 1, so the recursive calls sort low .. i and i + 2 .. high. The pivot itself is never moved again.

Characteristics of Quick Sort

Characteristic	Detail
Type	Divide and conquer
Time complexity (best)	O(n log n)
Time complexity (average)	O(n log n)
Time complexity (worst)	O(n^2) – when pivot is always smallest or largest
Space complexity	O(log n) for the call stack (in-place version)
Stable	No – relative order of equal elements may change
In-place	Yes (in-place version) – does not require O(n) extra memory
Recursive	Yes

---

Comparing Sorting Algorithms

The following table compares the key sorting algorithms you need to know at A2 level:

Algorithm	Best Case	Average Case	Worst Case	Space	Stable	In-Place	Method
Bubble sort	O(n)	O(n^2)	O(n^2)	O(1)	Yes	Yes	Comparison / swapping
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)	Yes	Yes	Comparison / insertion
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No	Divide and conquer
Quick sort	O(n log n)	O(n log n)	O(n^2)	O(log n)	No	Yes	Divide and conquer

Key Points for Comparison

• Bubble sort and insertion sort are O(n^2) algorithms. They are simple but only practical for small datasets. Insertion sort is efficient on nearly-sorted data (O(n) best case).
• Merge sort guarantees O(n log n) in all cases but requires O(n) extra space. It is the best choice when consistent performance is needed and memory is not constrained.
• Quick sort is O(n log n) on average and typically the fastest in practice due to good cache locality. However, its O(n^2) worst case can be a problem. It is in-place (O(log n) stack space).
• For large datasets, merge sort and quick sort are preferred. For small or nearly-sorted datasets, insertion sort can be very efficient.

---

Searching Tree-Based Data Structures

BST Search Algorithm

To search for a value in a BST:

1. Start at the root.
2. If the current node is null, the value is not in the tree – return “not found”.
3. If the value equals the current node’s data, return the node – found.
4. If the value is less than the current node’s data, search the left subtree.
5. If the value is greater than the current node’s data, search the right subtree.

This is inherently recursive and mirrors binary search on a sorted array.

Worked Example

Given this BST:

         8
       /   \
      3     10
     / \      \
    1   6     14
       / \   /
      4   7 13

Search for 7:

• Start at 8. 7 < 8, go left.
• At 3. 7 > 3, go right.
• At 6. 7 > 6, go right.
• At 7. Found.

Visited 4 nodes out of 9. This is much faster than checking all elements.

Search for 5:

• Start at 8. 5 < 8, go left.
• At 3. 5 > 3, go right.
• At 6. 5 < 6, go left.
• At 4. 5 > 4, go right.
• Right child is null. Not found.

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def bst_search(root, target):
    """Search for a value in a BST. Returns the node if found, None otherwise."""
    if root is None:               # Base case: not found
        return None
    if target == root.data:        # Base case: found
        return root
    elif target < root.data:       # Recursive case: search left
        return bst_search(root.left, target)
    else:                          # Recursive case: search right
        return bst_search(root.right, target)

def bst_insert(root, data):
    """Insert a value into a BST."""
    if root is None:
        return Node(data)
    if data < root.data:
        root.left = bst_insert(root.left, data)
    elif data > root.data:
        root.right = bst_insert(root.right, data)
    return root

# Build the example tree
root = None
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = bst_insert(root, val)

# Search
result = bst_search(root, 7)
print("Found" if result else "Not found")  # Output: Found

result = bst_search(root, 5)
print("Found" if result else "Not found")  # Output: Not found

Class Node
    Public Data As Integer
    Public Left As Node
    Public Right As Node

    Sub New(data As Integer)
        Me.Data = data
        Me.Left = Nothing
        Me.Right = Nothing
    End Sub
End Class

Function BSTSearch(root As Node, target As Integer) As Node
    If root Is Nothing Then          ' Base case: not found
        Return Nothing
    End If
    If target = root.Data Then       ' Base case: found
        Return root
    ElseIf target < root.Data Then   ' Search left
        Return BSTSearch(root.Left, target)
    Else                              ' Search right
        Return BSTSearch(root.Right, target)
    End If
End Function

Function BSTInsert(root As Node, data As Integer) As Node
    If root Is Nothing Then
        Return New Node(data)
    End If
    If data < root.Data Then
        root.Left = BSTInsert(root.Left, data)
    ElseIf data > root.Data Then
        root.Right = BSTInsert(root.Right, data)
    End If
    Return root
End Function

Sub Main()
    Dim root As Node = Nothing
    For Each val As Integer In {8, 3, 10, 1, 6, 14, 4, 7, 13}
        root = BSTInsert(root, val)
    Next

    Dim result As Node = BSTSearch(root, 7)
    Console.WriteLine(If(result IsNot Nothing, "Found", "Not found"))  ' Output: Found

    result = BSTSearch(root, 5)
    Console.WriteLine(If(result IsNot Nothing, "Found", "Not found"))  ' Output: Not found
End Sub

BST Search Complexity

Case	Time Complexity	When it occurs
Best	O(1)	Target is at the root
Average	O(log n)	Tree is reasonably balanced
Worst	O(n)	Tree is completely unbalanced (degenerates to a linked list)

The average case O(log n) arises because a balanced BST has a height of approximately log2(n), and each comparison eliminates half the remaining nodes.

---

Big O Notation

Common Time Complexities

Big O	Name	Description	Example
O(1)	Constant	Time does not change with input size	Accessing an array element by index
O(log n)	Logarithmic	Time increases slowly; halving the problem each step	Binary search
O(n)	Linear	Time grows proportionally to input size	Linear search, traversing a list
O(n log n)	Linearithmic	Slightly worse than linear; typical of efficient sorts	Merge sort, quick sort (average)
O(n^2)	Quadratic	Time grows with the square of input size	Bubble sort, insertion sort (worst), nested loops
O(2^n)	Exponential	Time doubles with each additional input element	Naive recursive Fibonacci, brute-force subset enumeration

Growth Rate Comparison

For an input of size n, the approximate number of operations:

n	O(1)	O(log n)	O(n)	O(n log n)	O(n^2)	O(2^n)
1	1	0	1	0	1	2
10	1	3	10	33	100	1,024
100	1	7	100	664	10,000	1.27 x 10^30
1,000	1	10	1,000	9,966	1,000,000	too large
10,000	1	13	10,000	132,877	100,000,000	too large

This table makes it clear why O(2^n) algorithms are impractical for anything beyond very small inputs, and why O(n log n) sorting algorithms are vastly superior to O(n^2) ones for large datasets.

Graphical Description of Growth Rates

The shapes matter more than the numbers. O(1) and O(log n) stay almost flat, so they scale to any input. O(n) and O(n log n) rise steadily and remain usable. O(n²) and O(2ⁿ) leave the plot entirely — O(2ⁿ) before n reaches 7 — which is why they are impractical for anything but small inputs.

Space Complexity

Algorithm	Time Complexity	Space Complexity	Notes
Linear search	O(n)	O(1)	Only needs a loop variable
Binary search (iterative)	O(log n)	O(1)	Only needs low, high, mid variables
Binary search (recursive)	O(log n)	O(log n)	Call stack depth
Bubble sort	O(n^2)	O(1)	Sorts in place
Merge sort	O(n log n)	O(n)	Needs temporary arrays for merging
Quick sort (in-place)	O(n log n) avg	O(log n)	Call stack depth
BST search	O(log n) avg	O(log n) recursive / O(1) iterative	Depends on implementation

---

Validation and Verification

Validation

Technique	Description	Example
Range check	Ensures a value falls within an acceptable range	Age must be between 0 and 120
Type check	Ensures data is of the correct type	A salary field must contain a number
Length check	Ensures a string is within an acceptable length	A password must be 8–20 characters
Presence check	Ensures a required field is not left empty	Email address must not be blank
Format check	Ensures data matches a required pattern	A date must be in DD/MM/YYYY format
Check digit	A digit calculated from the other digits, used to detect data entry errors	Last digit of an ISBN or barcode

Verification

Technique	Description
Double entry	Data is entered twice by the same or different operator; the two entries are compared and any discrepancy is flagged
Proofreading	A human checks the entered data against the original source document
Batch total / hash total	A total is calculated from the source data before input; the same total is calculated after input and the two are compared to check all records were received correctly

Validation vs Verification

Aspect	Validation	Verification
What it checks	That data is reasonable and acceptable	That data matches its source
Who/what performs it	The program	A human or a comparison process
Example error caught	Age entered as 999	A digit mistyped during manual entry
Catches wrong data?	No — data can pass validation but still be wrong (e.g. the correct age for a different person)	No — data can match the source but the source itself may be wrong

---

Linear Search and Binary Search

Linear Search

A linear search checks each element of a list one by one from the beginning until the target is found or the end of the list is reached.

FUNCTION linearSearch(list, target)
    FOR i FROM 0 TO length(list) - 1
        IF list[i] = target THEN
            RETURN i
        END IF
    END FOR
    RETURN -1
END FUNCTION

Case	Complexity	When
Best	O(1)	Target is the first element
Average	O(n)	Target is in the middle
Worst	O(n)	Target is last or not present
Space	O(1)	No extra storage needed

When to use linear search: When the list is unsorted, very small, or when searching is only done occasionally (sorting to enable binary search would cost more than the search itself).

Binary Search

A binary search repeatedly halves the search space. It requires the list to be sorted.

FUNCTION binarySearch(list, target)
    SET low TO 0
    SET high TO length(list) - 1
    WHILE low <= high
        SET mid TO (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            SET low TO mid + 1
        ELSE
            SET high TO mid - 1
        END IF
    END WHILE
    RETURN -1
END FUNCTION

Worked example — search for 42 in [5, 12, 23, 37, 42, 56, 78]:

Step	low	high	mid	list[mid]	Action
1	0	6	3	37	42 > 37, set low = 4
2	4	6	5	56	42 < 56, set high = 4
3	4	4	4	42	Found at index 4

Case	Complexity	When
Best	O(1)	Target is the middle element
Average	O(log n)	Target found after several halvings
Worst	O(log n)	Target is last found or not present
Space	O(1)	Iterative version needs no extra space

Comparison: Linear vs Binary Search

Feature	Linear Search	Binary Search
Requires sorted data	No	Yes
Time complexity	O(n)	O(log n)
Space complexity	O(1)	O(1) iterative; O(log n) recursive
Best for	Small or unsorted lists	Large sorted lists
Overhead	None	Sorting cost if data not already sorted

---

Shortest-Path Algorithm (Dijkstra’s)

How It Works

1. Assign distance 0 to the source node and infinity (∞) to all other nodes.
2. Mark all nodes as unvisited. Create a set of all unvisited nodes.
3. For the current node, consider all its unvisited neighbours and calculate their tentative distances through the current node.
4. If the calculated distance is less than the currently recorded distance, update it.
5. Mark the current node as visited (it will not be checked again).
6. Select the unvisited node with the smallest tentative distance as the new current node.
7. Repeat from step 3 until all nodes are visited or the destination is reached.

Worked Example

The same trace, written out as the exam expects it:

Step	Current	A	B	C	D	E	F	Visited
Start	A	0	∞	∞	∞	∞	∞	{}
1	A	0	4	∞	2	∞	∞	{A}
2	D	0	4	∞	2	3	∞	{A,D}
3	E	0	4	∞	2	3	5	{A,D,E}
4	B	0	4	7	2	3	5	{A,D,E,B}
5	F	0	4	7	2	3	5	{A,D,E,B,F}
6	C	0	4	7	2	3	5	{A,D,E,B,F,C}

Shortest paths from A: A→B = 4, A→D = 2, A→D→E = 3, A→D→E→F = 5, A→B→C = 7.

Note that C is reached through B, not through E: A→B→C costs 4 + 3 = 7, whereas going round by A→D→E→B→C would cost 2 + 1 + 6 + 3 = 12. Dijkstra finds the 7 because B is settled at distance 4 before C is ever examined.

Big O Complexity

Implementation	Time Complexity
Simple (adjacency matrix)	O(V²) where V = number of vertices
With priority queue (min-heap)	O((V + E) log V) where E = number of edges

---

Sorting Algorithm Efficiency: Comparisons, Exchanges and Passes

The spec requires you to explain how four factors affect sorting efficiency:

Number of Comparisons

A comparison occurs every time two data items are examined to determine their relative order.

• Bubble sort (worst case): For n items, pass 1 makes n-1 comparisons, pass 2 makes n-2, etc. Total: n(n-1)/2 = O(n²)
• Merge sort: Always O(n log n) comparisons regardless of input order
• Quick sort: O(n log n) average; O(n²) worst case (poor pivot choice)

Number of Exchanges (Swaps)

An exchange occurs when two elements are swapped into their correct relative positions.

• Bubble sort: Up to n(n-1)/2 swaps in the worst case (reverse-sorted input)
• Merge sort: No swaps — elements are copied into a new array. Exchange cost replaced by memory allocation cost.
• Quick sort: O(n log n) average swaps; fewer swaps than bubble sort in practice
• Insertion sort: Each out-of-order element requires shifting, which acts like multiple exchanges

Number of Passes

A pass is one complete traversal of the data (or a significant portion of it).

• Bubble sort: Requires up to n-1 passes. Each pass guarantees one more element is in its final position.
• Merge sort: Requires log₂(n) levels of merging. At each level, all n elements are processed once.
• Quick sort: Requires O(log n) recursive levels on average; O(n) in the worst case.

Storage Space Required

Algorithm	Extra Space	Why
Bubble sort	O(1)	In-place; only a temporary swap variable
Insertion sort	O(1)	In-place
Merge sort	O(n)	Requires an auxiliary array the same size as the input
Quick sort	O(log n)	In-place for data; O(log n) stack space for recursion

Summary Table

Algorithm	Comparisons (worst)	Exchanges (worst)	Passes	Extra Space
Bubble sort	O(n²)	O(n²)	n-1	O(1)
Insertion sort	O(n²)	O(n²)	n-1	O(1)
Merge sort	O(n log n)	O(n log n) (copies)	log n levels	O(n)
Quick sort	O(n²) worst, O(n log n) avg	O(n log n) avg	log n avg	O(log n)

---

Logical Operators in Algorithms and Programs

As well as their use in hardware logic gates, AND, OR, NOT, NAND and NOR are used directly in programming for bitwise operations and Boolean conditions.

NAND and NOR in Conditions

In pseudocode and programs, NAND and NOR can be expressed using combinations of NOT, AND, OR:

• A NAND B is equivalent to NOT (A AND B)
• A NOR B is equivalent to NOT (A OR B)

# NAND: True unless both inputs are True
def nand(a, b):
    return not (a and b)

# NOR: True only when both inputs are False
def nor(a, b):
    return not (a or b)

print(nand(True, True))   # False
print(nand(True, False))  # True
print(nor(False, False))  # True
print(nor(True, False))   # False

Bitwise Logical Operations

Bitwise operators apply a logical operation to each corresponding pair of bits in two integers:

Operation	Symbol (Python)	Effect
AND	&	Bit is 1 only if both bits are 1
OR	\|	Bit is 1 if either bit is 1
XOR	^	Bit is 1 if bits differ
NOT	~	Inverts all bits
Left shift	<<	Shifts bits left (multiply by 2ⁿ)
Right shift	>>	Shifts bits right (divide by 2ⁿ)

Applications

Clearing a register (AND with a mask):

To clear specific bits, AND with a mask where the bits to clear are 0:

Register: 1101 1010
Mask:      1111 0000   (clear lower 4 bits)
Result:    1101 0000

Setting specific bits (OR with a mask):

Register: 1101 0000
Mask:      0000 1111   (set lower 4 bits)
Result:    1101 1111

Testing a bit (AND with a mask):

Register: 1101 1010
Mask:      0000 0100   (test bit 2)
Result:    0000 0000   (bit 2 is 0 — flag not set)

Encryption using XOR:

XOR is used in stream ciphers because XORing with the same key twice returns the original value:

Plaintext:  1010 1100
Key:        0110 1001
Ciphertext: 1100 0101   (XOR)
Ciphertext: 1100 0101
Key:        0110 1001
Plaintext:  1010 1100   (XOR again — decrypted)

---

Traversal of Data Structures

A traversal visits every element in a data structure exactly once. Different data structures have different standard traversal algorithms.

Stack Traversal

A stack follows LIFO (Last In, First Out). To traverse all elements, pop each one in turn:

PROCEDURE traverseStack(stack)
    WHILE stack is not empty
        item = POP(stack)
        PROCESS(item)
    END WHILE
END PROCEDURE

Note: traversing by popping destroys the stack. To preserve it, push items onto a second stack and restore afterwards.

Queue Traversal

A queue follows FIFO (First In, First Out). To traverse, dequeue each element:

PROCEDURE traverseQueue(queue)
    WHILE queue is not empty
        item = DEQUEUE(queue)
        PROCESS(item)
    END WHILE
END PROCEDURE

Linked List Traversal

Follow pointers from the head node to the end (null pointer):

PROCEDURE traverseList(head)
    SET current TO head
    WHILE current IS NOT null
        PROCESS(current.data)
        SET current TO current.next
    END WHILE
END PROCEDURE

Binary Tree Traversal

Three standard depth-first traversal orders:

In-order (Left → Root → Right) — for a BST, produces elements in sorted ascending order:

PROCEDURE inOrder(node)
    IF node IS NOT null THEN
        inOrder(node.left)
        PROCESS(node.data)
        inOrder(node.right)
    END IF
END PROCEDURE

Pre-order (Root → Left → Right) — visits root before children; used to copy or serialise a tree:

PROCEDURE preOrder(node)
    IF node IS NOT null THEN
        PROCESS(node.data)
        preOrder(node.left)
        preOrder(node.right)
    END IF
END PROCEDURE

Post-order (Left → Right → Root) — visits root after children; used to delete a tree safely, or to build an expression tree from postfix notation:

PROCEDURE postOrder(node)
    IF node IS NOT null THEN
        postOrder(node.left)
        postOrder(node.right)
        PROCESS(node.data)
    END IF
END PROCEDURE

Example — given this tree:

       5
      / \
     3   8
    / \   \
   1   4   9

Traversal	Output	Use
In-order	1, 3, 4, 5, 8, 9	Sorted output from BST
Pre-order	5, 3, 1, 4, 8, 9	Copy/serialise tree
Post-order	1, 4, 3, 9, 8, 5	Delete tree; evaluate expression

---

Data Compression

Why Compress Data?

• Reduces storage space required
• Reduces transmission time and bandwidth consumption
• Essential for streaming media and large file transfers

Measuring Compression Effectiveness

Measure	Formula	Description
Compression ratio	Original size ÷ Compressed size	Higher is better; 4:1 means the compressed file is 4× smaller
Saving percentage	((Original − Compressed) ÷ Original) × 100	The percentage by which the file size is reduced
Compression time	Time taken to compress the data	Relevant when data is compressed frequently
Decompression time	Time taken to restore the data	Relevant when data is accessed frequently

Example: A 2 MB file compressed to 500 KB:

• Compression ratio = 2000 ÷ 500 = 4:1
• Saving percentage = ((2000 − 500) ÷ 2000) × 100 = 75%

Run-Length Encoding (RLE)

RLE replaces consecutive repeated values with a count and the value. It is most effective when data contains long runs of the same value.

Example:

Original:   AAABBBBBCCDDDDDD
Encoded:    3A5B2C6D

Original: 16 characters → Compressed: 8 characters (50% saving)

RLE is highly effective for images with large areas of solid colour (e.g. simple graphics, fax documents) but ineffective for complex images or text.

Huffman Coding

Huffman coding assigns shorter bit patterns to more frequent characters and longer patterns to less frequent ones. It produces an optimal prefix-free code — no codeword is the prefix of another.

Process:

1. Count the frequency of each character
2. Build a Huffman tree: repeatedly combine the two nodes with the lowest frequency into a new node until one tree remains
3. Assign 0 to left branches and 1 to right branches
4. Read the code for each character by tracing the path from root to leaf

Example — encode “AABABCBA”:

Character	Frequency
A	4
B	3
C	1

Build tree:

1. Combine C(1) and B(3) → new node(4)
2. Combine new node(4) and A(4) → root(8)

Tree:

       root(8)
      /        \
   A(4)       node(4)
             /      \
           B(3)    C(1)

Codes: A=0, B=10, C=11

Original (ASCII 8 bits each)	8 chars × 8 bits = 64 bits
Huffman encoded	A=0(×4), B=10(×3), C=11(×1) = 4 + 6 + 2 = 12 bits
Compression ratio	64 ÷ 12 ≈ 5.3:1

Comparing Compression Algorithms

Feature	RLE	Huffman Coding
Type	Lossless	Lossless
Best for	Data with long runs of repeated values	Data with uneven character frequencies
Worst for	Random data with few/no repeated runs	Data where all characters occur with equal frequency
Compression time	Very fast (O(n))	Requires frequency analysis and tree construction
Decompression time	Very fast	Fast (traverse tree)

---

Testing

Selecting Test Data

Good testing requires selecting data that exercises different aspects of the algorithm. Three categories of test data are needed:

Category	Description	Purpose
Normal (valid)	Typical data the algorithm is expected to handle correctly	Confirms the algorithm works under normal conditions
Boundary (extreme)	Data at the edges of the valid range	Reveals off-by-one errors and edge case failures
Erroneous (invalid)	Data outside the valid range or of the wrong type	Confirms the algorithm handles bad input without crashing

Example — testing an algorithm that accepts ages 0–120:

Test Data	Category	Expected Result
25	Normal	Accepted
0	Boundary	Accepted (lower boundary)
120	Boundary	Accepted (upper boundary)
-1	Boundary/Erroneous	Rejected
121	Boundary/Erroneous	Rejected
“abc”	Erroneous	Rejected / error message

Dry-Running an Algorithm

A dry run (also called a trace) involves manually stepping through an algorithm with specific test data, recording the value of each variable at each step. It is used to:

• Verify that an algorithm produces the correct output
• Identify logical errors
• Understand what an unfamiliar algorithm does

A dry run is recorded in a trace table, which has one column per variable and one row per step.

Example — dry run of a search algorithm:

FUNCTION linearSearch(list, target)
    FOR i FROM 0 TO length(list) - 1
        IF list[i] = target THEN
            RETURN i
        END IF
    END FOR
    RETURN -1
END FUNCTION

Test data: list = [3, 7, 2, 9, 5], target = 9

Step	i	list[i]	list[i] = target?	Action
1	0	3	No	Continue
2	1	7	No	Continue
3	2	2	No	Continue
4	3	9	Yes	Return 3

Result: index 3 (correct).

Explaining the Purpose of an Algorithm

When asked to explain what an algorithm does, trace through it with a small example and describe:

1. What inputs it takes
2. What it does to those inputs (the logic of each major step)
3. What output it produces
4. Any special cases it handles (e.g. empty list, item not found)

Types of Testing

Testing can be classified by what is being tested and how much the tester knows about the internal code.

White-box vs Black-box Testing

Feature	White-box	Black-box
Tester’s knowledge	Full access to source code	No knowledge of internals
Based on	Code structure (paths, branches)	Specification / requirements
Detects	Logic errors, unreachable code	Missing functionality, incorrect outputs
Performed by	Developers	Testers / clients

Testing by Scope

Type	Description
Unit testing	Tests individual modules or functions in isolation. Checks that each unit produces the correct output for given inputs. Performed by developers.
Integration testing	Tests that multiple modules work correctly when combined. Checks that interfaces and data passing between modules are correct.
System testing	Tests the complete, integrated system against the requirements specification. Checks that the whole system functions as intended.
Acceptance testing	The client or end user tests the system to verify it meets their requirements. The final stage before sign-off and deployment.

Testing by Purpose

Type	Description
Functional testing	Verifies that each feature of the software works according to the specification. A type of black-box testing.
Performance testing	Measures how the system behaves under load — response times, throughput, resource usage. Includes stress testing (pushing beyond normal capacity) and load testing (simulating expected usage).
Regression testing	Re-runs previously passing tests after a change to ensure that the change has not broken existing functionality. Essential after every bug fix or new feature.

Alpha and Beta Testing

Stage	Description
Alpha testing	Performed by internal testers (developers and QA team) in a controlled environment before release. Identifies bugs before the software reaches real users.
Beta testing	Performed by a selected group of real end users in their own environment before the final release. Identifies issues that only arise in real-world conditions. Feedback is used to fix remaining problems before the public launch.