Algorithms

What you'll learn

• How to analyse a problem and design a correct algorithm for it.
• How to compare algorithms using execution time, space and Big-O notation.
• How common data structures affect algorithm design.
• How standard searches, sorts and shortest-path algorithms work.

From problem to algorithm

An algorithm is not just “some code”. Before coding, you need to understand the situation: what data goes in, what result must come out, and what restrictions apply.

Useful questions:

• What are the inputs and outputs?
• How large could the input be? We usually call this input size $n$.
• Is the data already sorted?
• Are duplicates allowed?
• Is the data stored in an array, linked list, tree or graph?
• Are there memory limits?
• What are the awkward edge cases, such as an empty list or a missing value?

A precondition is something assumed to be true before the algorithm starts, such as “the list is sorted”. A postcondition is something that should be true when it finishes, such as “the returned index contains the target value”.

Measuring efficiency

An algorithm must be correct, but for large inputs it also needs to be efficient.

Execution time means how long the algorithm takes, usually estimated by counting key operations. Space means how much memory the algorithm needs, including extra arrays, queues, stacks or recursion.

Important classes for OCR H446:

• $O(1)$ — constant time: does not grow with input size, such as reading the top item of a stack.
• $O(\log n)$ — logarithmic time: grows very slowly, such as binary search.
• $O(n)$ — linear time: grows in proportion to input size, such as linear search.
• $O(n^k)$ — polynomial time: includes $O(n^2)$ and $O(n^3)$, often caused by nested loops.
• $O(2^n)$ — exponential time: doubles rapidly as input size grows, such as trying every subset.
• $O(n\log n)$ — common for efficient comparison sorts such as merge sort and average-case quick sort.

Methods for determining efficiency include:

• Counting operations, especially loop repetitions.
• Dry running with a trace table on small inputs.
• Benchmarking, where you time real executions, although this depends on hardware, language and test data.
• Asymptotic analysis, where you simplify the growth rate using Big-O notation.

Data structures and their algorithms

Stacks

A stack is a last-in, first-out structure, often written LIFO. The newest item is removed first.

Typical operations:

• Push: add an item to the top.
• Pop: remove and return the top item.
• Peek: read the top item without removing it.

Stacks are useful for recursion, undo features, expression evaluation and depth-first search.

Queues

A queue is a first-in, first-out structure, often written FIFO. The oldest item is removed first.

Typical operations:

• Enqueue: add an item to the rear.
• Dequeue: remove and return the front item.

Queues are useful for printer queues, simulations and breadth-first traversal of trees or graphs.

Linked lists

A linked list is made from nodes. Each node stores data and a pointer or reference to the next node. The first node is reached using the head pointer.

To search a linked list, start at the head and follow links until the item is found or the end is reached. This is usually $O(n)$.

Insertion and deletion can be efficient once you already have the correct position, because you change pointers rather than shifting many array elements.

Trees and traversal

A tree is a hierarchical data structure made from nodes connected by edges. The top node is the root. A node with no children is a leaf. In a binary tree, each node has at most two children.

Two important tree traversal algorithms are:

• Depth-first post-order traversal: visit the children first, then the node itself.
• Breadth-first traversal: visit level by level, usually using a queue.

OCR-style pseudocode for post-order traversal:

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

Standard searching algorithms

Linear search

Linear search checks each item in order until it finds the target or reaches the end.

It works on unsorted data and linked lists, but its worst-case time is $O(n)$.

function linearSearch(items[], n, target)
    for i = 0 to n - 1
        if items[i] == target then
            return i
        endif
    next i
    return -1
endfunction

Binary search

Binary search repeatedly checks the middle item and discards half of the remaining data.

It requires sorted data and efficient access to the middle item, so it is usually used with arrays. Its time is $O(\log n)$.

function binarySearch(items[], n, target)
    low = 0
    high = n - 1
    while low <= high
        mid = (low + high) DIV 2
        if items[mid] == target then
            return mid
        elseif target < items[mid] then
            high = mid - 1
        else
            low = mid + 1
        endif
    endwhile
    return -1
endfunction

Standard sorting algorithms

A sorting algorithm puts data into order, such as ascending numerical order or alphabetical order.

An in-place sort uses only a small amount of extra memory. A stable sort keeps equal items in their original relative order.

• Bubble sort repeatedly compares adjacent items and swaps them if they are in the wrong order. It is simple but usually slow: $O(n^2)$.
• Insertion sort builds a sorted section at the start of the list and inserts each new item into the correct place. It is good for small or nearly sorted data, but worst-case time is $O(n^2)$.
• Merge sort splits the data into halves, recursively sorts them, then merges the sorted halves. It is $O(n\log n)$ and stable, but needs extra memory.
• Quick sort chooses a pivot, partitions the data around it, then recursively sorts the partitions. It is often fast, with average time $O(n\log n)$, but worst-case time $O(n^2)$ if pivots are badly chosen.

Shortest path algorithms

A graph is a set of nodes, called vertices, connected by edges. In a weighted graph, each edge has a cost, distance or time.

Dijkstra’s shortest path algorithm

Dijkstra’s algorithm finds the shortest path from a start node to other nodes in a graph with non-negative edge weights.

Main idea:

1. Give the start node distance 0 and all other nodes infinity.
2. Repeatedly choose the unvisited node with the smallest tentative distance.
3. Update neighbouring distances if a shorter route has been found.
4. Stop when the target is visited or all reachable nodes are processed.

A* algorithm

A* also finds a shortest path, but it uses a heuristic, which is an estimate of the remaining cost to the goal.

It chooses the node with the smallest value of:

$$f(n)=g(n)+h(n)$$

where $g(n)$ is the known cost from the start and $h(n)$ is the estimated cost to the goal.

A* is especially useful in route finding and games because a good heuristic can direct the search towards the target instead of exploring equally in all directions.

Comparing algorithm suitability

When comparing algorithms, discuss both time and space, and link your answer to the task and data set.

For example:

• Use binary search only when the data is sorted and random access is efficient.
• Use linear search when the data is unsorted or stored as a linked list.
• Use insertion sort for small or nearly sorted data.
• Use merge sort when stable, predictable $O(n\log n)$ sorting is needed and extra memory is available.
• Use Dijkstra for shortest paths with non-negative weights.
• Use A* when you have a useful heuristic to guide the search.