Why does the Tube map ignore real distances, yet still work?

Breaking a problem down

• Decomposition means breaking a problem into smaller sub-problems, each doing one identifiable task.
• Each sub-problem can be broken down again until it is simple to solve.
• Parts can be solved and tested separately, even by different people.
• "Plan a Tube journey" splits into: find the nearest station, choose the route, work out the time.

Leaving detail out

• Abstraction is removing unnecessary detail from a problem to focus on what matters.
• Harry Beck's 1933 Tube map keeps the lines, the order of stations and where they connect.
• It drops true distances and the real shape of the tunnels: travellers do not need them.
• A program does the same: it models the real world with only the details the task needs.

Inputs, processes and outputs

• To analyse a problem, identify its inputs (data going in), processes (what is done to the data) and outputs (results).
• Car park ticket machine: inputs are the hours wanted and the coins; the process works out the cost and change; outputs are the ticket and the change.

Structure diagrams

• A structure diagram shows how a problem is decomposed, from the top down.
• The top box is the whole problem. Each level below splits a box into its sub-problems.
• Lines link each box to the sub-problems it is made of.
• Boxes at the bottom are small enough to become a subroutine or a few lines of code.

Algorithms and algorithmic thinking

• An algorithm is a sequence of steps that can be followed to complete a task.
• The same algorithm can be written as a flowchart, as pseudocode or as program code.
• Algorithmic thinking is working out the steps that solve a problem, and their order, so the solution can be reused for similar problems.
• Decomposition, abstraction and algorithms together are the core of computational thinking.

How can you find a bug without running the program?

Flowchart symbols

• A flowchart shows an algorithm's steps and the order they happen in.

Pseudocode and code

• Pseudocode writes an algorithm as structured statements, not tied to one programming language.
• OCR exam questions use the OCR Exam Reference Language shown here
• This algorithm loops while the count is above 0. Each time round it doubles the result and counts down by 1.

count = 3
result = 1
while count > 0
    result = result * 2
    count = count - 1
endwhile
print(result)

Trace tables

• A dry run follows an algorithm by hand. A trace table records it: one column per variable, plus Output.
• Add a row when a value changes. For screen 3, count goes 3, 2, 1, 0 and result goes 1, 2, 4, 8.
• The pattern shows the purpose: it works out 2 to the power of the starting count.

Errors in algorithms

• A syntax error breaks the language's rules, e.g. a missing endif. The code will not run.
• A logic error: the code runs but gives a wrong result, e.g. > where ≥ was needed.
• To fix a logic error, dry-run with test data, find where the trace goes wrong, correct it and retest.

How can 20 checks find one name among a million?

Linear search

• A linear search checks each item in turn, from the first, until it finds the target or reaches the end.
• The list can be in any order.
• Finding 15 in [27, 8, 63, 15, 44, 3, 70] takes 4 checks.
• At worst (target last, or missing) it checks every item.

found = False
i = 0
while i < 7 AND found == False    // items holds 7 values: index 0 to 6
    if items[i] == target then
        found = True
    else
        i = i + 1
    endif
endwhile
if found == True then
    print(i)
else
    print("Not found")
endif

Binary search

• A binary search only works on a sorted list.
• Check the middle item. If it is the target, stop.
• If the target is bigger, discard the middle item and all before it. If smaller, discard it and all after it.
• Repeat on what is left until the target is found or nothing is left.
• Each check halves the list: a divide and conquer algorithm.

Binary search in code

• first and last mark the part of the list still being searched.
• The middle position is (first + last) DIV 2, using whole-number division.
• With an even number of items this picks the lower of the two middle items.
• Some textbooks take the higher middle item. Use one rule throughout, or the rule a question gives.
• The loop ends when the target is found or first passes last.

first = 0
last = 14    // items holds 15 values: index 0 to 14
found = False
while first <= last AND found == False
    mid = (first + last) DIV 2
    if items[mid] == target then
        found = True
    elseif items[mid] < target then
        first = mid + 1
    else
        last = mid - 1
    endif
endwhile

Comparing the two searches

• Binary search is far more time-efficient on large sorted lists.
• Linear search suits small or unsorted lists. Sorting a list first takes time too.

Why is it called a bubble sort?

One pass

• A bubble sort compares each adjacent pair of items, starting at the front of the list.
• If the pair is in the wrong order, swap them. Then move along one place and compare the next pair.
• One trip through every pair is a pass.
• After pass 1 of [5, 2, 8, 1, 4], the list is [2, 5, 1, 4, 8].

Passes until sorted

• Keep making passes. Each pass carries the largest unsorted item to its final place.
• Stop after a pass that makes no swaps: the list must be sorted.
• [5, 2, 8, 1, 4] needs 3 passes with swaps, then a 4th pass with none to confirm it.
• A list of n items needs at most n − 1 passes that make swaps.

Bubble sort in code

• The inner loop is one pass: it compares item i with item i + 1 and swaps them if needed.
• the array items holds 6 values at indexes 0 to 5, so i runs from 0 to 4.
• A swap needs a temporary variable, temp, to hold one value.
• swapped records whether the pass changed anything. The outer loop repeats until a pass makes no swaps.

do
    swapped = False
    for i = 0 to 4
        if items[i] > items[i + 1] then
            temp = items[i]
            items[i] = items[i + 1]
            items[i + 1] = temp
            swapped = True
        endif
    next i
until swapped == False

Strengths and weaknesses

• Simple to understand and to code.
• Sorts in place: it needs almost no extra memory.
• Quick on a nearly sorted list: a sorted list needs just one pass.
• Slow on large lists: with 1,000 items, each pass makes 999 comparisons, and it may need 999 passes with swaps.

Why does a fast sort start by chopping a list into pieces?

Split until single items

• A merge sort first splits the list into two halves, then splits each half, and so on.
• Splitting stops when every list holds one item. A list of one item is already sorted.
• 8 items take 3 rounds of splitting: 8 → 4 + 4 → four lists of 2 → eight lists of 1.
• Breaking a problem into smaller problems like this is divide and conquer.

Merge sorted lists

• Now merge pairs of sorted lists into bigger sorted lists, until one list is left.
• To merge, compare the first items of both lists and move the smaller to the new list. Repeat.
• When one list is empty, copy the rest of the other across with no more comparisons.
• Merging [2, 4, 6, 9] with [1, 3, 7, 8] takes 7 comparisons (see diagram).

Insertion sort

• An insertion sort builds a sorted part at the start of the list, one item at a time.
• Take the next item. Shift each larger item in the sorted part one place right, then insert the item in the gap.
• n items need n − 1 passes: the first item starts as the sorted part.
• The diagram shows each pass on a list of 6 items.

for i = 1 to 5    // items holds 6 values: index 0 to 5
    current = items[i]
    pos = i
    while pos > 0 AND items[pos - 1] > current
        items[pos] = items[pos - 1]
        pos = pos - 1
    endwhile
    items[pos] = current
next i

Comparing sorts

• Insertion sort is simple, sorts in place and is quick on nearly sorted lists, but slow on large unsorted ones.

Big ideas

• Decomposition breaks a problem into sub-problems that can be solved separately.
• Abstraction removes unnecessary detail so a model keeps only what the task needs.
• An algorithm is a sequence of steps; start by identifying the inputs, processes and outputs.
• Flowcharts, pseudocode and program code are three ways to write the same algorithm.
• A trace table records each variable during a dry run; it reveals the output, the purpose and any logic error.
• Syntax errors stop code running; logic errors give wrong results.
• Linear search checks items one by one; it works on unsorted data but can need a check for every item.
• Binary search needs sorted data; it checks the middle and halves the list each time, so it needs far fewer checks.
• A bubble sort compares adjacent pairs and swaps any in the wrong order; one run through the list is a pass.
• After each pass, the largest unsorted item is in place; stop when a pass makes no swaps.
• It is simple and needs little memory, but it is slow for large lists.
• Merge sort splits the list down to single items, then merges sorted lists back together: divide and conquer.
• Merge sort is much faster on large lists but needs extra memory; bubble sort is simpler and sorts in place.
• Insertion sort inserts each item into a growing sorted part at the start of the list.