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.

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.
• 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.
• Eduqas also uses a small circle as a connector to join parts of a flowchart.

Pseudocode and code

• Pseudocode writes an algorithm as structured statements, not tied to one programming language.
• Eduqas uses the pseudo-code conventions in its specification, shown here
• This algorithm loops while the count is above 0. Each time round it doubles the result and counts down by 1.

set count = 3
set result = 1
while count > 0
    set result = result * 2
    set count = count - 1
repeat
output 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 end if. 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.

set found = FALSE
set i = 0
while i < 7 AND found = FALSE    /** items holds 7 values: index 0 to 6 */
    if items[i] = target
        set found = TRUE
    else
        set i = i + 1
    end if
repeat
if found = TRUE
    output i
else
    output "Not found"
end if

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.

set first = 0
set last = 14    /** items holds 15 values: index 0 to 14 */
set found = FALSE
while first <= last AND found = FALSE
    set mid = (first + last) DIV 2
    if items[mid] = target
        set found = TRUE
    else
        if items[mid] < target
            set first = mid + 1
        else
            set last = mid - 1
        end if
    end if
repeat

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.

repeat
    set swapped = FALSE
    for i = 0 to 4
        if items[i] > items[i + 1]
            set temp = items[i]
            set items[i] = items[i + 1]
            set items[i + 1] = temp
            set swapped = TRUE
        end if
    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).

Comparing sorts

You typed 41, not 14, for your age. Why did the form accept it?

What validation does

• Validation is an automatic check that input is sensible and follows rules before the program uses it.
• Invalid data is rejected, and the user is told why and asked again.
• It stops bad data causing crashes or wrong results later.
• Validation cannot tell whether data is correct: a mistyped value that still follows the rules gets through.

Types of validation check

• Type check: the data is the right data type, e.g. a whole number.
• Format check: the data matches a set pattern, e.g. a date as DD/MM/YYYY.
• Check digit: the last digit of a code such as an ISBN or barcode, calculated from the other digits. On entry it is recalculated; a mismatch shows a mistyped digit.
• Lookup table: the value must be in a list of allowed values, e.g. Mon to Sun.

Writing a validation routine

• Ask for input, test it, and keep asking until it passes.
• A loop does this: the user cannot move on with invalid data.
• This repeat ... until loop is a range check for 1 to 10.

repeat
  output "Score 1 to 10"
  input score
until score >= 1 AND score <= 10

Verification

• Verification checks that data was entered or copied accurately, so it matches the original.
• Double keying (double entry): type the data twice; the computer compares the two and rejects a mismatch.
• Proofreading: a person reads the data back and compares it with the original.
• Validation asks "is it sensible?"; verification asks "is it what was meant?". Typing 41 for 14 passes validation; comparing it with the original could catch it.

Authentication

• Authentication confirms the identity of a user before they get access, e.g. with a username and password.
• The program compares what is typed with the stored details.

input username
input password
if username = "sam01" AND password = "Tr33house"
  output "Access granted"
else
  output "Access denied"
end if

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.
• Abstraction and decomposition are the first steps of a systematic approach to a programming task.
• 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.
• Validation automatically checks input is sensible, e.g. range, length and presence checks, and rejects data that breaks the rules; it cannot check data is correct.
• Verification checks data matches the original: double keying and proofreading.
• Authentication confirms who a user is, e.g. by matching a username and password.