Advanced algorithms and recursion

Linear search and binary search

A linear search starts at the first item and compares each item with the search value in turn, stopping when it finds a match or reaches the end of the list. It is the only option when the data is in no particular order, and it is perfectly adequate for a short list. Its weakness is that the work grows in step with the data: for 1 000 items the worst case is 1 000 comparisons and the average is about 500.

A binary search works only on data that is already sorted. It looks at the middle item: if that is the search value the search is over, if the search value is larger then it cannot be in the lower half, and if it is smaller it cannot be in the upper half, so half of the remaining data is discarded at every comparison. Searching 1 000 items this way takes at most 10 comparisons and searching 1 000 000 items takes at most 20, because each comparison halves what is left.

Three conditions must be met before a binary search can be used. The data must be sorted into the order used by the comparisons; it must be held in a structure where the middle item can be reached directly, such as an array or a list with an index, because a linked list can only be walked from one end; and the items must be comparable, so that a decision can be made about which half to keep.

A binary search also assumes that the data does not change while it is running. Inserting or deleting an item moves the positions of the middle items, so the halving no longer works; this is why a binary search is used on a static sorted array, or on a sorted file that is read into an array first.

• Linear search: set Found <- FALSE and Index <- 1; while Index <= NumberOfItems and Found = FALSE, compare DataArray[Index] with SearchValue and add 1 to Index; then report the position if Found, otherwise report that the value is not in the list.
• Binary search: set First <- 1 and Last <- NumberOfItems; while First <= Last and Found = FALSE, set Middle <- (First + Last) DIV 2; if DataArray[Middle] equals SearchValue stop, if it is less than SearchValue set First <- Middle + 1, otherwise set Last <- Middle - 1.
• Conditions for a binary search: the data must be sorted, the middle item must be directly accessible (an array rather than a linked list), and the items must be comparable so that a half can be discarded.
• Performance: for n items a linear search needs up to n comparisons and a binary search up to log2(n) + 1; doubling the data adds one comparison to a binary search but doubles the work of a linear search.
• Both algorithms must cope with the value not being present: a linear search ends when the index passes the last item, a binary search ends when Last becomes smaller than First.
• A linear search is still the right choice for a short list, for unsorted data, or where the data changes so often that keeping it sorted would cost more than the search saves.

Bubble sort and insertion sort

A bubble sort makes repeated passes through the array, comparing each item with the one after it and swapping the pair if they are in the wrong order. After the first pass the largest item has bubbled to the last position, after the second the second largest is in place, so each pass can be one comparison shorter. With n items it needs at most n - 1 passes, which is why its worst case is about n(n - 1)/2 comparisons, or O(n^2).

A swap flag makes the bubble sort stop as soon as a pass makes no swaps, because no swaps means the data is in order. That one addition takes the best case from n - 1 passes down to a single pass of n - 1 comparisons, so an already sorted array is handled in O(n).

An insertion sort takes the items one at a time from position 2 onwards, holds the current item, shifts every larger item in the sorted part one place to the right, and drops the current item into the gap. The left-hand part of the array is always a sorted list, and each new item is inserted into its correct place in that list, which is why the sort is called insertion.

The two behave differently on the same data. An insertion sort does the minimum of movement when the data is already nearly in order, because each item travels only a short way, and it is the faster of the two on small arrays and on data that arrives almost sorted. A bubble sort moves an item only one place per pass, so on data in reverse order it does the largest number of swaps of any of the simple sorts, while an insertion sort also does its maximum work but with one move per shift instead of three assignments per swap.

• Bubble sort: for Pass <- 1 TO NumberOfItems - 1, set Swap <- FALSE; for Index <- 1 TO NumberOfItems - Pass, compare DataArray[Index] with DataArray[Index + 1] and swap them if they are out of order, setting Swap <- TRUE; if Swap is still FALSE after the pass, stop.
• Swap: Temp <- DataArray[j]; DataArray[j] <- DataArray[j + 1]; DataArray[j + 1] <- Temp.
• Insertion sort: for Index <- 2 TO NumberOfItems, set Current <- DataArray[Index] and Position <- Index - 1; while Position >= 1 and DataArray[Position] > Current, move DataArray[Position] to Position + 1 and subtract 1 from Position; then store Current at Position + 1.
• Both algorithms work in place: they rearrange the original array and need only one or two extra variables, so their space complexity is O(1).
• Best case for both is data that is already sorted: O(n), the bubble sort because of the swap flag and the insertion sort because each item needs one comparison and no shifts.
• Worst case for both is data in reverse order: O(n^2).

Abstract data types: stacks and queues

An abstract data type (ADT) is a description of a data structure in terms of the data it holds and the operations that can be performed on it, without saying how those operations are implemented. A programmer using a stack needs to know what push and pop do, not whether the data is held in an array, in a linked list or on disk. That separation is the point: the implementation can be changed, or written by somebody else, without any of the code that uses the ADT being rewritten.

A stack is a last in, first out (LIFO) structure: the item most recently pushed is the first one popped. Its operations are push (add to the top), pop (remove and return the top item), peek (look at the top item without removing it), and tests for empty and full. A stack is the right structure whenever the most recent thing is the next thing needed - reversing a list, checking that brackets are nested correctly, or the undo history of an editor.

A queue is a first in, first out (FIFO) structure: items join at the rear and leave from the front. Its operations are enqueue (add at the rear), dequeue (remove and return the item at the front), and tests for empty and full. A queue is the right structure whenever things must be handled in the order they arrived - jobs sent to a printer, keystrokes in a buffer, or processes waiting for the processor.

Both can be implemented from a one-dimensional array plus integer variables that mark the positions, or from a linked list. With an array, a stack needs a Top pointer that starts at 0 and is incremented on push and decremented on pop; a queue needs Front and Rear pointers. A plain array queue wastes the spaces at the front as items are dequeued, so the pointers are wrapped round with MOD to make a circular queue, and a count of the number of items held is the simplest way to tell a full queue from an empty one.

• Push(Item): if Top = MaxSize then report overflow, otherwise add 1 to Top and store Item at Stack[Top].
• Pop: if Top = 0 then report underflow, otherwise read Stack[Top], subtract 1 from Top, and return the item that was read.
• Enqueue(Item): if the queue is full then report overflow, otherwise move Rear on one place (Rear <- Rear MOD MaxSize + 1) and store Item at Queue[Rear].
• Dequeue: if the queue is empty then report underflow, otherwise read Queue[Front], move Front on one place (Front <- Front MOD MaxSize + 1), and return the item.
• Circular queue: Front and Rear wrap round to 1 after the last position, so the spaces freed at the front are reused instead of being lost.
• Underflow and overflow checks are part of the algorithm, not an optional extra: a pop from an empty stack is a run-time error, and the check is a mark in its own right.
• Stack from a linked list: push is an insert at the head and pop is a removal of the head node - the same LIFO behaviour with no fixed size.

Linked lists, binary trees and dictionaries

A linked list stores each item in a node with a pointer to the next node, and a separate head pointer marks the first node. Nothing is stored in consecutive positions, so an item can be inserted or deleted by changing pointers instead of shifting every item after it. The price is that there is no direct access to the nth item: a search must follow the pointers from the head, which makes it O(n).

In an exam the linked list is usually held in two parallel arrays, one for the data and one for the next pointer, with a null pointer such as -1 marking the end of the list and a free list of unused nodes. Following the pointers is the whole of a linked list algorithm: search, insert and delete all reduce to deciding which pointer is changed.

A binary tree is made of nodes that each hold an item and two pointers, to a left child and a right child, with a root pointer to the first node. In a binary search tree every item in the left subtree is smaller than the node and every item in the right subtree is larger, so one comparison at each node discards a whole subtree. A search and an insert follow the same path: compare with the current node, go left if the new item is smaller, go right if it is larger, and stop when the item is found or the pointer is null.

A dictionary is an ADT that stores pairs of a key and a value, and looks a value up by its key rather than by its position, such as a table of student IDs and names. It can be implemented from two parallel arrays (one of keys and one of values), from a list of records searched linearly, or from a binary tree keyed on the key.

An ADT can be built from another ADT, not only from a built-in type, and the syllabus asks for exactly that. A stack can be made from a linked list by inserting and removing at the head; a queue from a linked list by inserting at the tail and removing from the head; a binary tree from a linked list whose nodes hold two pointers; and a dictionary from a binary tree or from a sorted array searched with a binary search. The operations offered to the user stay the same - only the code underneath them changes.

• Search a linked list: start at the head pointer, compare the data in each node, follow the next pointer, and stop when the item is found or the pointer is -1.
• Insert into a linked list: take a node from the free list, store the item, set its pointer to the node it must come before, and set the previous node's pointer to the new node.
• Delete from a linked list: set the previous node's pointer to the deleted node's pointer, then return the freed node to the free list.
• Search a binary tree: compare the search value with the current node, go left if it is smaller and right if it is larger, and repeat until it is found or a null pointer is reached.
• Insert into a binary tree: follow the same comparison path until a null pointer is found, then attach the new node at that point.
• Stack from a linked list: push = insert at the head, pop = remove the head node. Queue from a linked list: enqueue = insert at the tail, dequeue = remove the head node.
• Dictionary operations: add a key and value, find the value for a key, delete a key, and report a missing key - the position of a pair is never used by the program that uses the dictionary.

Graphs as an abstract data type

A graph is a set of vertices (nodes) together with a set of edges (arcs) that join pairs of vertices. It is an ADT because what matters is the set of relationships it records and the operations on them, not the way those relationships happen to be stored in memory.

Edges may be undirected, meaning the relationship works both ways, as with two towns joined by a road, or directed, meaning it works one way only, as with a one-way street or the statement that one task must be finished before another. They may be weighted, carrying a number such as a distance, a cost or a time, or unweighted. A vertex's degree is the number of edges that meet it, and a path is a sequence of edges leading from one vertex to another.

A graph is stored either as an adjacency matrix, a two-dimensional array in which a cell records whether an edge exists and with what weight, or as an adjacency list, in which each vertex keeps a list of the vertices it is joined to. A matrix answers the question 'is there an edge between these two vertices' immediately but uses n x n cells even when there are very few edges; an adjacency list uses memory in proportion to the number of edges but can need a search of a list to answer the same question.

A graph is chosen when the problem is about connections between items rather than about the items in a sequence: a road network for a route planner, a set of flights between airports, a network of friendships, or the tasks in a project and which of them must be completed before which. Storing the same information in an array or a table either loses the connections or repeats them so heavily that a question such as 'what is the shortest route from here to there' becomes very hard to ask. The graph is also the structure that graph searches such as Dijkstra's algorithm and A* need, which is why it returns in the artificial intelligence topic.

• Vertex (node): an object in the graph. Edge (arc): a link between two vertices.
• Undirected / directed: the link works both ways / the link works one way only.
• Weighted / unweighted: each edge carries a value such as a distance, cost or time / the edges carry no value.
• Adjacency matrix: an n x n two-dimensional array; O(1) to test one pair, but O(n^2) memory even when the graph is sparse.
• Adjacency list: one list of neighbours for each vertex; memory in proportion to the number of edges, but testing one particular edge may need a search of a list.
• Justifying a graph: name the vertices, name the edges, say whether the edges are directed or weighted, and say which question the graph makes easy to answer.
• No code is required for a graph structure at this level - you are asked to describe and justify it, not to implement it.

Comparing algorithms with Big O notation

Two algorithms can perform the same task and still be very different in the resources they need. The syllabus criteria are the time taken to complete the task and the memory used, and Big O notation is how those are specified without depending on one computer, one compiler or one particular set of data.

Big O describes how the work or the memory grows as the number of data items, n, grows. Constants and lower-order terms are dropped, because they do not change the shape of the growth: an algorithm that makes 3n + 5 comparisons is O(n). The figure usually quoted is the worst case, because that is the case that has to be planned for, though a best case may be quoted when the question is about data that is already in a favourable order.

The classes worth knowing are small in number. O(1) constant: the work does not depend on n, as in reading Array[5]. O(log n) logarithmic: one more step of work each time n doubles, as in a binary search. O(n) linear: the work grows in step with n, as in a linear search. O(n log n) means a logarithmically growing number of levels with O(n) work at each level. O(n^2) quadratic: the work grows with the square of n, which is what a loop inside a loop produces, as in a bubble or insertion sort.

Space complexity is counted in the same way. Bubble sort and insertion sort rearrange the array in place and need only a few extra variables, so their space complexity is O(1); a sort that copies the whole array into a second array would need O(n). A binary search implemented with a loop needs O(1) space, but a recursive version needs O(log n) stack frames, and a recursive algorithm of depth n needs O(n) space for the stack even when it holds no data structure at all.

Big O does not tell you which algorithm is faster on a particular small set of data, because it ignores constants: an O(n^2) insertion sort with a small constant can beat an O(n log n) algorithm on twenty items, which is why real libraries fall back to a simple sort for small sections. What Big O does tell you is which algorithm wins as n becomes large, and that is the comparison an exam question is asking for.

• Criteria for comparing algorithms: the time taken to complete the task and the memory used - say which one your comparison is about.
• O(1) constant: array access by index, push and pop on a stack stored in an array.
• O(log n) logarithmic: binary search - each comparison halves the remaining items.
• O(n) linear: linear search, or one pass through an array.
• O(n^2) quadratic: bubble sort and insertion sort, because of the loop inside a loop.
• Space: bubble sort and insertion sort are O(1) extra memory; a recursive routine costs one stack frame per level.
• Drop the constants and the lower-order terms: 3n + 100 is O(n), 2n^2 + 5n is O(n^2). Write the class, not the formula.

Recursion: the essential features

Recursion is a technique in which a procedure or function calls itself to solve a smaller version of the same problem. The problem is reduced at every call until it reaches a version simple enough to answer directly, and the answers are then combined on the way back out.

Every correct recursive routine has two parts. The base case is the stopping condition: a test that returns a result without making another call, such as 'if n = 1 then return 1'. The general case, also called the recursive case, does one step of the work and then calls the routine again with a smaller or simpler argument, for example 'return n * Factorial(n - 1)'. Without a base case the routine never stops; without a call that moves towards the base case it never reaches it.

In a programming language recursion is expressed by calling the routine by its own name inside its own body, passing changed arguments, and using the returned value. The base case is written as an IF statement that returns before the recursive call can be reached. A function that returns a value, such as Factorial or a search of a tree, and a procedure that produces output or changes a structure, such as printing a folder tree or drawing a fractal, can both be recursive.

Nothing special is needed in the language for this: a call is a call, whether it is to another routine or to the routine that is already running. Each call gets its own copy of the parameters and local variables, which is why the n in Factorial(4) and the n in Factorial(3) do not interfere with one another.

• Base case: the condition that stops the recursion and returns a value directly, without another call.
• General case: the step that performs part of the work and calls the routine again on a smaller version of the problem.
• Progress: every call must move the argument closer to the base case, usually by subtracting 1 or by halving it.
• Own copy of variables: each call has its own parameters and local variables, held in its own stack frame.
• Factorial(n): IF n = 1 THEN RETURN 1 ELSE RETURN n * Factorial(n - 1) ENDIF - one base case, one general case, one step towards the base.
• Recursion and iteration are interchangeable: any recursive algorithm can be rewritten with a loop and an explicit stack, and any loop can be written recursively. Recursion is chosen for clarity, not because it can do something a loop cannot.

Tracing recursion, the call stack and unwinding

When a recursive call is made, the computer must remember where to come back to. Each call gets a stack frame, also called an activation record, holding its parameters, its local variables and the return address, and the frames pile up as the calls go deeper. This is the stack that the syllabus means by the use of stacks and unwinding.

Unwinding is what happens as the calls return. The innermost call reaches the base case and returns its value, its frame is popped, the value is handed back to the call below, that call completes its own step and returns, and so on back to the original call. A trace of Factorial(4) shows the descent 4 -> 3 -> 2 -> 1 and then the unwind 1 -> 2 -> 6 -> 24.

A trace table for a recursive routine needs a column for each parameter and one row per call, with the returns filled in from the bottom upwards, because a return value cannot be known until the call beneath it has returned. The commonest tracing error is to work down the table writing returns as you go, which produces a wrong answer even when the logic of the routine is right.

The compiler needs no special instruction for recursion, but it must generate the code that makes it work. At each call it saves the return address and the current values on the stack, passes the new arguments, jumps to the start of the routine, and on return restores the saved values and continues after the call. Because each call consumes memory, the depth of the recursion is limited by the size of the stack: a routine that never reaches its base case, or one that is simply too deep, exhausts the stack - a stack overflow.

Recursion is beneficial when the problem is defined in terms of itself, because the code then matches the definition and is short and easy to check: searching or traversing a tree, walking a folder and its subfolders, the Towers of Hanoi puzzle, and algorithms that split the data in half and solve each half. It is a poor choice when the recursion is deep, because a list of 100 000 items handled one item per call will overflow the stack, and a very poor choice when the same subproblem is recalculated many times, as in the naive recursive calculation of Fibonacci numbers, where the number of calls grows exponentially.

• Benefit: short, readable code for problems that are naturally recursive, such as trees, nested structures and divide and conquer.
• Benefit: no separate data structure is needed to remember what to do next - the call stack holds it.
• Cost: every call uses memory for a stack frame and time for the call and the return.
• Cost: deep recursion can overflow the stack, so the depth is limited by the stack size rather than by the problem.
• Cost: recursion is harder to trace and debug, and a missing or unreachable base case ends in a crash rather than an obvious wrong answer.
• Cost: a naive recursive solution can recalculate the same subproblem many times, making it far slower than the loop version.
• Tracing: list the calls downwards to the base case, then substitute the returns upwards - the return value of each call depends on the one beneath it.