9. Algorithm design

Abstraction is the process of creating a simplified model that represents the essential features of a problem, by removing unnecessary detail.

Everyday example: a metro map shows stations, lines and the order of stops, but not real distances, streets or buildings — the details a traveller does not need.

• Makes the problem simpler to understand and solve.
• Lets the programmer focus on what matters.
• Less data to store and process, so the program is smaller and faster to write and run.
• Reduces the chance of errors and makes the solution easier to design and test.
• The model can often be reused for similar problems.

Scenario: a school library wants a program to lend books to students.

The model becomes: a book record, a student record and a loan linking them with dates. Everything else is left out. For a different purpose (e.g. a bookshop selling books) the essential features would change — price and stock become essential — so always decide relative to the given context.

Decomposition is the process of breaking down a problem into smaller, more manageable sub-problems. Each sub-problem can be broken down again until each part is simple enough to solve directly — often as its own procedure or function.

• Each sub-problem is easier to understand and solve.
• Different programmers can work on different parts at the same time, so the project is finished sooner.
• Each part can be tested on its own, so errors are found and fixed more easily.
• Parts can be reused in other programs (e.g. a "validate date" function).
• The program is easier to maintain: a change affects one part only.

Scenario: a program records a class's test marks and reports the average and the highest mark.

1. Input marks — ask for each student's name and mark; validate the mark (0–100).
2. Store marks — keep names and marks in two lists.
3. Process — total the marks, count them, calculate the average, find the highest.
4. Output — display the average to 1 decimal place and the top student's name.

Each numbered step can become a function:

def get_mark():
    mark = int(input("Mark: "))
    while mark < 0 or mark > 100:
        mark = int(input("0 to 100 only: "))
    return mark

def average(marks):
    return round(sum(marks) / len(marks), 1)

A box may contain several statements, and a decision box may combine a process and a decision (e.g. "count ← count + 1, count = 10?"). Every decision exit must be labelled Yes/No.

To design an algorithm for a context: decompose it (inputs, processes, outputs, storage), choose the constructs (selection? which loop?), then write it as a flowchart or Python.

Amending means changing a working algorithm to do something extra — e.g. change a fixed loop of 10 to ask how many, add validation, or also output the lowest value.

# Original: total of 5 numbers
total = 0
for count in range(5):
    total = total + int(input())
print(total)

# Amended: user chooses how many, and the average is also output
how_many = int(input("How many? "))
total = 0
for count in range(how_many):
    total = total + int(input())
print(total, total / how_many)

Read the code, trace it with sample data, then state what it does in terms of the problem, broken into its parts:

• Inputs — what it asks for.
• Processes — what it calculates or decides.
• Outputs — what it displays.
• Storage — what it keeps (variables, lists, files).

e.g. "It inputs numbers until −1 is entered, totals and counts them, and outputs the total and how many were entered." Avoid line-by-line translation ("it sets total to 0…").

A trace table records the value of every variable, and every input and output, each time it changes, as you dry-run the algorithm line by line.

count = 0
total = 0
number = int(input())
while number != -1:
    total = total + number
    count = count + 1
    number = int(input())
print(total, count)

Input data: 4, 7, 2, −1

Rules: a new row when a value changes; leave a cell blank if nothing changes; outputs exactly as printed.

Typical faults planted in exam algorithms: wrong operator (< instead of <=), wrong starting value (highest = 0 when values may be negative), counter not incremented, total reset inside the loop, wrong loop range, wrong variable output.

# Should output the sum of 1 to 5 (15) but prints 10
total = 0
for count in range(1, 5):     # error: stops at 4
    total = total + count
print(total)

Correction: for count in range(1, 6):. In the exam, give the line with the error and the corrected line in full.

Checks each item in turn from the start until the target is found or the end of the list is reached. Works on unsorted data.

numbers = [14, 3, 27, 8, 19]
target = 8
found = False
position = -1
index = 0
while index < len(numbers) and not found:
    if numbers[index] == target:
        found = True
        position = index
    index = index + 1
if found:
    print(target, "found at index", position)
else:
    print(target, "not found")

Output: 8 found at index 3 (after 4 comparisons).

Steps: start at the first item → compare with the target → if equal, stop (found) → otherwise move to the next item → if the end is reached, report not found.

Works only on sorted data. Repeatedly checks the middle item and discards the half that cannot contain the target.

Steps: set low = first index, high = last index → mid = (low + high) // 2 → if the middle item is the target, stop → if the target is larger, low = mid + 1; if smaller, high = mid − 1 → repeat until found or low > high (not found).

numbers = [3, 8, 15, 21, 30, 42, 57]
target = 42
low = 0
high = len(numbers) - 1
found = False
while low <= high and not found:
    mid = (low + high) // 2
    print("low", low, "high", high, "mid", mid, "value", numbers[mid])
    if numbers[mid] == target:
        found = True
    elif numbers[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print("Found" if found else "Not found")

Output: low 0 high 6 mid 3 value 21, low 4 high 6 mid 5 value 42, Found — two comparisons, where a linear search would need six.

Goes through the list comparing adjacent pairs and swapping them if they are in the wrong order. After each pass the largest remaining value has "bubbled" to its place at the end. Stops when a pass makes no swaps.

numbers = [5, 1, 4, 2, 8]
n = len(numbers)
swapped = True
passes = 0
while swapped:
    swapped = False
    for i in range(n - 1 - passes):
        if numbers[i] > numbers[i + 1]:
            temp = numbers[i]
            numbers[i] = numbers[i + 1]
            numbers[i + 1] = temp
            swapped = True
    passes = passes + 1
    print("After pass", passes, numbers)

A temporary variable is needed for the swap so a value is not overwritten.

Builds a sorted part at the front. Takes the next item and inserts it into the correct place in the sorted part, shifting larger items one place right.

items = [23, 4, 42, 8, 15, 16]
for i in range(1, len(items)):
    current = items[i]
    j = i - 1
    while j >= 0 and items[j] > current:
        items[j + 1] = items[j]
        j = j - 1
    items[j + 1] = current
    print("After inserting", current, items)

A divide and conquer sort:

1. Split the list in half, and keep splitting until every sub-list has one item (a list of one is already sorted).
2. Merge pairs of sub-lists: compare the front items of both, move the smaller into the new list, repeat until both are empty.
3. Keep merging until there is one sorted list.

Example: 38, 27, 43, 3, 9, 82, 10, 5

You must be able to show and describe merge sort; you are not asked to write it in Python.

Insertion sort, like bubble sort, is simple and sorts in place; it is quick on small or nearly sorted lists.