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.
• Also identify initialisation: values set before processing starts, such as the amount paid starting at 0.

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.
• Pearson exam questions use its pseudocode command set, 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 TO 3
SET result TO 1
WHILE count > 0 DO
  SET result TO result * 2
  SET count TO count - 1
END WHILE
SEND result TO DISPLAY

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 TO FALSE
SET i TO 0
WHILE i < LENGTH(items) AND found = FALSE DO
  IF items[i] = target THEN
    SET found TO TRUE
  ELSE
    SET i TO i + 1
  END IF
END WHILE
IF found = TRUE THEN
  SEND i TO DISPLAY
ELSE
  SEND 'Not found' TO DISPLAY
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 TO 0
SET last TO LENGTH(items) - 1
SET found TO FALSE
WHILE first <= last AND found = FALSE DO
  SET mid TO (first + last) DIV 2
  IF items[mid] = target THEN
    SET found TO TRUE
  ELSE
    IF items[mid] < target THEN
      SET first TO mid + 1
    ELSE
      SET last TO mid - 1
    END IF
  END IF
END WHILE

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.
• Efficiency here is measured by the number of compares each search makes.

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 TO FALSE
  FOR i FROM 0 TO 4 DO
    IF items[i] > items[i + 1] THEN
      SET temp TO items[i]
      SET items[i] TO items[i + 1]
      SET items[i + 1] TO temp
      SET swapped TO TRUE
    END IF
  END FOR
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

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.
• Choosing the more efficient algorithm matters most when the data set is large.
• 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.