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.
• Every computer system is made of sub-systems, made of further sub-systems.

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.
• Also identify storage: data that must be kept, such as the price per hour.

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.
• 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.
• Cambridge exams use the pseudocode shown here; write precise conditions such as X > Y, not "X is greater than Y"
• This algorithm loops while the count is above 0. Each time round it doubles the result and counts down by 1.

DECLARE Count : INTEGER
DECLARE Result : INTEGER
Count ← 3
Result ← 1
WHILE Count > 0 DO
    Result ← Result * 2
    Count ← Count - 1
ENDWHILE
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.
• Also record any user prompts the algorithm outputs.

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.

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 is declared ARRAY[1:6], so Index runs from 1 to 5.
• 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.

DECLARE Items : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE Temp : INTEGER
DECLARE Swapped : BOOLEAN
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 5
        IF Items[Index] > Items[Index + 1]
          THEN
            Temp ← Items[Index]
            Items[Index] ← Items[Index + 1]
            Items[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
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.

How can a program average numbers if it doesn't know how many?

Totalling

• Totalling keeps a running total. Set the total to 0 before the loop.
• Inside the loop, add each new value to the total.
• Forgetting to set the total to 0 first is a common error.
• With marks 12, 7, 9 and 15, the total goes 0 → 12 → 19 → 28 → 43.

DECLARE Total : INTEGER
DECLARE Index : INTEGER
DECLARE Mark : INTEGER
Total ← 0
FOR Index ← 1 TO 4
    INPUT Mark
    Total ← Total + Mark
NEXT Index
OUTPUT Total

Counting and the average

• Counting adds 1 each time something happens. Set the count to 0 before the loop.
• If you do not know how many values are coming, loop until a value arrives that cannot be real data, such as −1 for a mark. This stop value is not added or counted.
• After the loop, average = total ÷ count. Check the count is above 0 first.

DECLARE Total : INTEGER
DECLARE Count : INTEGER
DECLARE Mark : INTEGER
Total ← 0
Count ← 0
INPUT Mark
WHILE Mark <> -1 DO
    Total ← Total + Mark
    Count ← Count + 1
    INPUT Mark
ENDWHILE
IF Count > 0
  THEN
    OUTPUT Total / Count
ENDIF

Maximum and minimum

• To find the maximum, set Max to the first value. Compare each value with Max and replace Max when a value is bigger.
• The minimum works the same way, replacing Min when a value is smaller.
• One loop can find the maximum, minimum and total; average = total ÷ number of values.
• For scores 18, 25, 21, 30, 16: maximum 30, minimum 16, average 22.

DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE Max : INTEGER
DECLARE Min : INTEGER
DECLARE Total : INTEGER
DECLARE Index : INTEGER
DECLARE Average : REAL
Max ← Score[1]
Min ← Score[1]
Total ← 0
FOR Index ← 1 TO 5
    IF Score[Index] > Max
      THEN
        Max ← Score[Index]
    ENDIF
    IF Score[Index] < Min
      THEN
        Min ← Score[Index]
    ENDIF
    Total ← Total + Score[Index]
NEXT Index
Average ← Total / 5
OUTPUT Max, Min, Average

Linear search

• A linear search checks each item in turn, from the first, until it finds the target or reaches the end.
• The data can be in any order.
• A Boolean flag, Found, stops the loop as soon as the item is found.

DECLARE Names : ARRAY[1:5] OF STRING
DECLARE Found : BOOLEAN
DECLARE Index : INTEGER
DECLARE Target : STRING
Found ← FALSE
Index ← 1
INPUT Target
WHILE (Found = FALSE) AND (Index <= 5) DO
    IF Names[Index] = Target
      THEN
        Found ← TRUE
      ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT Target, " found at position ", Index
  ELSE
    OUTPUT Target, " not found"
ENDIF

The program development life cycle

• Analysis: abstraction and decomposition of the problem; identify the problem and its requirements.
• Design: decomposition, structure diagrams, flowcharts and pseudocode.
• Coding: write the program code, with iterative testing of each part as it is written.
• Testing: test the finished program with test data.

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.

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 WHILE loop is a range check for 1 to 10.

DECLARE Score : INTEGER
OUTPUT "Score 1 to 10"
INPUT Score
WHILE Score < 1 OR Score > 10 DO
  OUTPUT "Must be 1 to 10"
  INPUT Score
ENDWHILE

Verification

• Verification checks that data was entered or copied accurately, so it matches the original.
• Double entry check: type the data twice; the computer compares the two and rejects a mismatch.
• Visual check: the user reads the data on screen 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.

It passed every test. So why did it fail for an 18-year-old?

Why test?

• Testing checks that a program works as intended and meets its requirements.
• It finds errors so they can be fixed before users meet them.
• A program can run without crashing and still give wrong results.
• Passing a few easy tests proves little: choose test data that could expose errors.

Normal, edge and wrong data

For a program that accepts whole numbers from 1 to 10:

• Normal data: sensible values that should be accepted, e.g. 5.
• Extreme data: the smallest and largest acceptable values, 1 and 10. Boundary data: each limit and the value just past it: 0 and 1, 10 and 11.
• Abnormal data: data that should be rejected, e.g. ten or 15.

Code that is easy to maintain

• Other people (and you, later) must be able to read and change code. This is maintainability.
• Meaningful identifiers: totalScore, not t.
• Comments explain what each part of the code does.
• Procedures and functions break code into named, reusable parts.

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.
• Decompose a problem into inputs, processes, outputs and storage, and show it with a structure diagram.
• 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.
• 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.
• Totalling: start at 0, add each value inside the loop. Counting: start at 0, add 1 each time.
• Average = total ÷ count, worked out after the loop.
• Max and min start at the first value; a linear search checks items in turn; the PDLC is analysis, design, coding, testing.
• 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 entry and visual checks.
• Choose test data of every kind: normal, at the edges of the range, and data that should be rejected (normal, extreme, boundary, abnormal).
• Meaningful names, comments, indentation and subprograms make code easy to maintain.