Computational Thinking and Problem-solving

Paper 3 and Paper 4 test whether you can choose and write the right algorithm, say how efficient it is, and use the standard data structures. This chapter extends chapters 9 to 11 with the A Level algorithms. Paper 4 expects you to be able to turn them into working code in a language of your choice.

19.1 Algorithms

Searching

Linear search (chapter 10) checks each item in turn, from the start, until it finds the target or reaches the end. It works on unsorted data. For n items it makes up to n comparisons.

Binary search works only on a sorted list. It repeatedly halves the part of the list that could contain the target:

1. Look at the middle item.
2. If it equals the target, stop: it is found.
3. If the target is smaller, repeat with the lower half; if larger, repeat with the upper half.
4. If no items are left, the target is not in the list.

Low ← 1
High ← 100
Found ← FALSE
WHILE Low <= High AND Found = FALSE
    Mid ← (Low + High) DIV 2
    IF List[Mid] = Target THEN
        Found ← TRUE
    ELSE
        IF List[Mid] < Target THEN
            Low ← Mid + 1
        ELSE
            High ← Mid - 1
        ENDIF
    ENDIF
ENDWHILE

Example: find 23 in 3 8 12 17 23 29 35 41 (positions 1 to 8). Mid = 4 (17): 23 > 17, so Low = 5. Mid = (5+8) DIV 2 = 6 (29): 23 < 29, so High = 5. Mid = 5 (23): found, after 3 comparisons rather than 5.

Tap to enlarge

A binary search for 23 in the sorted list 3, 8, 12, 17, 23, 29, 35, 41 shown in three steps: the middle item 17 is smaller than 23 so the lower half is ruled out, the middle item 29 is larger so the upper part is ruled out, and the middle item 23 is found

Close

Sorting

Bubble sort (chapter 10): repeatedly compare adjacent items and swap them if out of order; after each pass the largest remaining item is in its final place. Stop when a pass makes no swaps. It is easy to write but slow for big lists: $n$ items may need about $n^2$ comparisons. It is a good method for a list that is nearly sorted, since the flag ends it after few passes.

Insertion sort builds a sorted list one item at a time: take the next item, and insert it into the correct place in the already-sorted part, shifting larger items one place to the right to make room.

FOR Index ← 2 TO 10
    Item ← List[Index]
    Position ← Index - 1
    WHILE Position >= 1 AND List[Position] > Item
        List[Position + 1] ← List[Position]      // shift right
        Position ← Position - 1
    ENDWHILE
    List[Position + 1] ← Item                   // insert in the gap
NEXT Index

Trace of 5 2 9 1 : start with 5 sorted; insert 2 → 2 5; insert 9 → 2 5 9; insert 1 → shift 9, 5, 2 → 1 2 5 9.

Insertion sort does not need extra memory, works well for small or almost sorted lists, and can sort a list as the data arrives; like bubble sort it is slow ($\approx n^2$) for large lists.

Abstract data types (ADT)

An ADT (chapter 10) is a collection of data and a set of operations on it, whose implementation is hidden. At A Level you must also know about:

Binary tree. A tree is a hierarchy of nodes; a binary tree has at most two children per node (a left and a right child). The first node is the root; a node with no children is a leaf. In a binary search tree the left subtree holds values smaller than the node and the right subtree values larger, so a value can be found by going left or right at each node (like a binary search).

It can be stored in arrays: one array for the data, and two arrays for the left pointer and right pointer, with -1 (null) for no child.

Tap to enlarge

A binary search tree with root 50, children 30 and 70, 30 having children 20 and 40 and 70 having left child 60, with the in-order, pre-order and post-order traversals listed; the in-order traversal gives the values in ascending order

Close

Traversal visits every node: in-order (left, node, right) gives a binary search tree's values in ascending order (30, 50, 60, 70 above); pre-order (node, left, right) copies a tree; post-order (left, right, node) is used to delete a tree or to evaluate an expression tree.

Inserting a value into a binary search tree: start at the root; compare with the node; go left if smaller, right if larger; when an empty position is reached, put the new node there.

Dictionary. A dictionary stores key-value pairs and allows a value to be looked up by its key (a word and its meaning, a name and a phone number). The keys are unique. It is often implemented using hashing (chapter 13) so look-up is very fast.

Implementing one ADT from another. One ADT can be built using another as its storage:

• A stack can be implemented with an array (and a top pointer) or with a linked list (push and pop at the start of the list).
• A queue can be implemented with an array and two pointers, or with a linked list (add at the end, remove from the front).
• A binary tree can be built from a linked list-like structure of nodes, or from arrays of data and pointers (above).
• A dictionary can use an array with hashing, or a binary tree ordered by key.

The user of the ADT only sees the operations (push, pop, enqueue and so on), so the underlying structure can be changed without affecting the program that uses it.

Algorithms for the abstract data types

The algorithms use the array implementations of chapter 10: Data and Pointer arrays with a StartPointer and a FreePointer for a linked list, and LeftPointer, Data, RightPointer and a RootPointer for a binary tree. -1 means no pointer.

Find an item in a linked list (follow the pointers):

Current ← StartPointer
Found ← FALSE
WHILE Current <> -1 AND Found = FALSE
    IF Data[Current] = SearchItem THEN
        Found ← TRUE
    ELSE
        Current ← Pointer[Current]
    ENDIF
ENDWHILE

Insert an item into a linked list (after the node at position Previous; -1 means at the start):

IF FreePointer = -1 THEN
    OUTPUT "The list is full"
ELSE
    NewNode ← FreePointer
    FreePointer ← Pointer[FreePointer]        // take a node from the free list
    Data[NewNode] ← NewItem
    IF Previous = -1 THEN
        Pointer[NewNode] ← StartPointer
        StartPointer ← NewNode
    ELSE
        Pointer[NewNode] ← Pointer[Previous]
        Pointer[Previous] ← NewNode
    ENDIF
ENDIF

Delete a node from a linked list (the node at Current, with Previous the node before it):

IF Previous = -1 THEN
    StartPointer ← Pointer[Current]
ELSE
    Pointer[Previous] ← Pointer[Current]
ENDIF
Pointer[Current] ← FreePointer                     // return the node to the free list
FreePointer ← Current

Remove an item from a queue (a circular queue, chapter 10):

IF NumberOfItems = 0 THEN
    OUTPUT "The queue is empty"
ELSE
    Item ← Queue[FrontPointer]
    FrontPointer ← FrontPointer + 1
    IF FrontPointer > MaxSize THEN FrontPointer ← 1 ENDIF
    NumberOfItems ← NumberOfItems - 1
ENDIF

Adding to and removing from a stack are Push and Pop in chapter 10.

Find an item in a binary search tree (go left if smaller, right if larger):

Current ← RootPointer
Found ← FALSE
WHILE Current <> -1 AND Found = FALSE
    IF Data[Current] = SearchItem THEN
        Found ← TRUE
    ELSE
        IF SearchItem < Data[Current] THEN
            Current ← LeftPointer[Current]
        ELSE
            Current ← RightPointer[Current]
        ENDIF
    ENDIF
ENDWHILE

Insert an item into a binary search tree (NewNode is a free position already holding the item, with both pointers -1):

IF RootPointer = -1 THEN
    RootPointer ← NewNode
ELSE
    Current ← RootPointer
    Placed ← FALSE
    WHILE Placed = FALSE
        IF Data[NewNode] < Data[Current] THEN
            IF LeftPointer[Current] = -1 THEN
                LeftPointer[Current] ← NewNode
                Placed ← TRUE
            ELSE
                Current ← LeftPointer[Current]
            ENDIF
        ELSE
            IF RightPointer[Current] = -1 THEN
                RightPointer[Current] ← NewNode
                Placed ← TRUE
            ELSE
                Current ← RightPointer[Current]
            ENDIF
        ENDIF
    ENDWHILE
ENDIF

A graph is an ADT too. It is a set of nodes (vertices) joined by edges, which may be directed and weighted (chapter 18). Its operations are adding a node, adding an edge, and finding the nodes joined to a given node. It can be stored as an adjacency matrix or an adjacency list, and it is the right structure when the data is a network of connections: road maps, social networks, computer networks and the moves in a game.

Comparing algorithms

Different algorithms that do the same task can be compared by:

• Time taken to complete it (how the running time grows with the amount of data), and
• Memory used (extra space needed).

Big O notation describes how the time or space grows as the input size $n$ grows, ignoring constants and smaller terms. It gives the worst-case behaviour.

19.2 Recursion

Recursion is when a subroutine calls itself. A recursive definition needs two things:

• a base case: a condition for which the answer is known and the subroutine does not call itself again, so the recursion stops;
• a general (recursive) case: the subroutine calls itself with a simpler version of the problem (closer to the base case).

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    IF N = 0 THEN
        RETURN 1                      // base case
    ELSE
        RETURN N * Factorial(N - 1)   // general case
    ENDIF
ENDFUNCTION

Tracing Factorial(3): the function calls itself with 3, 2, 1, 0, winding up the calls; at 0 it returns 1 (the base case), then the calls unwind: Factorial(1) returns 1 × 1 = 1; Factorial(2) returns 2 × 1 = 2; Factorial(3) returns 3 × 2 = 6.

Factorial(3) = 3 * Factorial(2)
                     = 2 * Factorial(1)
                           = 1 * Factorial(0)
                                 = 1

Tap to enlarge

The recursive function Factorial(3): on the left the calls wind up as stack frames for Factorial(3), (2), (1) and (0), where the base case returns 1; on the right the results are returned in reverse order, 1, 1, 2 and finally 6

Close

Another example, the Fibonacci sequence, where each term is the sum of the previous two:

FUNCTION Fib(N : INTEGER) RETURNS INTEGER
    IF N <= 1 THEN
        RETURN N
    ELSE
        RETURN Fib(N - 1) + Fib(N - 2)
    ENDIF
ENDFUNCTION

What the compiler has to do

A computer has no instruction for recursion, so a compiler (or interpreter) uses a stack to make it work. On each call it pushes a stack frame holding the return address, the parameters and the local variables of that call, so that each call has its own copy. When a call finishes, the frame is popped, the result is passed back, and execution resumes at the saved return address. This is why a very deep recursion can run out of stack space.

Recursion or iteration?

Any recursive solution can be written using a loop and a stack, and vice versa.