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.

Pseudocode and code

• Pseudocode writes an algorithm as structured statements, not tied to one programming language.
• Pearson calls informal written steps "pseudocode"; exam programs use Python, 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
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 colon. The code will not run.
• A logic error: the code runs but gives a wrong result, e.g. > where ≥ was needed.
• A runtime error happens while the code runs, e.g. dividing by zero, and can crash it.
• 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 < len(items) and found == False:
    if items[i] == target:
        found = True
    else:
        i = i + 1
if found == True:
    print(i)
else:
    print("Not found")

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) // 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 = len(items) - 1
found = False
while first <= last and found == False:
    mid = (first + last) // 2
    if items[mid] == target:
        found = True
    elif items[mid] < target:
        first = mid + 1
    else:
        last = mid - 1

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.

swapped = True
while swapped == True:
    swapped = False
    for i in range(0, 5):
        if items[i] > items[i + 1]:
            temp = items[i]
            items[i] = items[i + 1]
            items[i + 1] = temp
            swapped = True

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.
• Pearson judges efficiency by compares, passes through a loop and memory used.

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

• Pearson measures efficiency by compares, passes through a loop and memory used.

"Tea or coffee?" Would a computer's OR let you have both?

1 or 0, and NOT

• A Boolean value has only two states: 1 (TRUE) or 0 (FALSE).
• A truth table lists every possible combination of inputs with the output for each.
• NOT has one input and reverses it: NOT 0 = 1, NOT 1 = 0.
• Write it as NOT A.

AND

• AND has two inputs. The output is 1 only when both inputs are 1.
• If either input is 0, the output is 0.
• Write it as A AND B.

OR

• OR has two inputs. The output is 1 when at least one input is 1.
• The output is 0 only when both inputs are 0.
• This is wider than everyday "or", which often means "one or the other, not both".
• Write it as A OR B.

Three sensors, one alarm: how many cases must you test?

Combining operators

• One logic statement (expression) can use several operators, e.g. (A AND B) OR NOT C.
• Work out brackets first.
• NOT applies only to the input or bracket just after it.
• Example: (1 AND 0) OR (1 AND 1) = 0 OR 1 = 1

Every combination of three inputs

• Each input can be 0 or 1, so each new input doubles the number of rows.
• 1 input: 2 rows. 2 inputs: 4 rows. 3 inputs: 8 rows.
• Fill the input columns by counting up in binary from 000 to 111. Then no row is missed or repeated.
• Exam questions use up to three inputs.

Working columns

• For a long statement, add a column for each part.
• Example: P = (A AND B) OR NOT C.
• Column 4: A AND B. Column 5: NOT C. Column 6: P = column 4 OR column 5.
• Working columns are optional, but they stop you mixing up steps.

From a problem to a logic statement

• Give each condition a letter (1 = true, 0 = false).
• "and" → AND; "or" / "either" → OR; "not" / "is off" → NOT.
• Use brackets to group conditions that go together.
• Example: the alarm X sounds if the door is open (D) and the system is armed (S), or if the panic button (P) is pressed.
• X = (D AND S) OR P

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.
• Runtime errors happen while the code runs, e.g. dividing by zero.
• 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.
• Every input and output is 1 (TRUE) or 0 (FALSE). A truth table lists every combination of inputs.
• AND: 1 only if both inputs are 1. OR: 1 if at least one input is 1. NOT: reverses its one input.
• Work out brackets first; NOT applies only to what comes straight after it.
• 3 inputs give 8 rows: count in binary from 000 to 111, and add working columns for each part.
• Turn a problem into a statement by giving each condition a letter and mapping "and", "or", "not".