Module 01: What is computation?

You have four books on a shelf and want to know where The Hobbit is. You could look along the shelf, read each title and stop when you find it. That simple activity contains the ingredients of computation: information, a precise question, a sequence of steps and a result.

Computation transforms information according to rules. The information can describe numbers, text, pictures, movements or relationships. A computer performs those rules using a physical machine; a person can carry out the same small computation with pencil and paper. Computer science studies how to represent problems, construct and analyse procedures, organise systems and understand what computation can and cannot achieve.

Programming is one way to express a procedure so a machine can execute it. Computer science also asks whether the procedure answers the right question, whether it always finishes, how much work it requires and how it fits into a larger system. These questions remain relevant when the programming language changes.

Notice the decisions already made: order matters, matching is exact, duplicates are possible, and missing books have an explicit result. “Find a book” did not specify any of those. Much of good computing begins with resolving such ambiguities.

A problem specification states the required relationship between inputs and outputs. An algorithm is a procedure for achieving it. A program implements a procedure in a language with defined execution rules. There can be many algorithms for one problem and many programs implementing one algorithm.

The assumptions are preconditions: what must hold before the procedure runs. The promised output and unchanged input are postconditions: what must hold after it returns. Together they make a contract. Later modules will use contracts for data structures, network protocols and database transactions.

A library user might expect “dune” to match “Dune”. That would require a new matching rule, for example case-insensitive comparison. Do not quietly change the meaning while claiming the original contract still holds.

Linear search checks items in their given order. In pseudocode, which expresses the steps without depending on a particular programming language:

FOR each position i, from first to last:
    IF title at i equals target:
        RETURN i
RETURN -1

The final return happens only after all items have been examined. The return inside the loop ends the entire search immediately. That immediate stop gives us the first matching index even when a title occurs twice.

The procedure has state: the information needed to describe where it is in its execution. Here the changing state is the current position and, when we measure work, the number of comparisons. A trace records that state step by step.

The fourth title is never inspected in this run. Predict a trace before running code: doing so forces you to distinguish what you expect from what the program actually does.

Try three experiments. Search for Dune and explain why index 3 is never reached. Search for Solaris and count the comparisons. Select the empty catalogue and explain why returning -1 requires no title comparisons. The demonstration shows the final “list exhausted” step separately; that step is not a title comparison.

Examples show particular executions. An argument about the procedure covers every input satisfying the contract. We will develop formal proofs later; a short reasoning pattern is enough here.

Correctness: what stays true?

Just before we inspect position i, none of the earlier positions contains the target. This is a loop invariant, a statement preserved as the loop advances. It is initially true because there are no earlier positions at index 0. If the current title does not match, adding that title to the inspected prefix preserves the statement. If it matches, the invariant tells us that no earlier match exists, so returning i satisfies the contract. If the list is exhausted, every title was unequal, so returning -1 satisfies the contract.

Termination: what makes progress?

For a list with n entries, each unsuccessful iteration advances one position. The number of uninspected entries decreases by one and cannot decrease forever below zero. A match ends the search even sooner. A finite list that remains unchanged therefore guarantees termination.

Cost: count a defined operation

Choose one title-equality check as the operation to count. For a nonempty list, a first-position match costs one comparison. A last-position match or an absent target costs n comparisons. An empty list costs zero comparisons. Doubling the number of entries doubles the worst-case comparison count.

This count is a model, not elapsed time. Comparing two long strings may require examining many characters; a title comparison is not necessarily constant-time when title length varies. The computer, implementation and data also affect seconds on a clock. Module 05 develops these distinctions and introduces Big O. Here, specify the operation and count it accurately.

An abstraction exposes the properties needed for a task while hiding other details. Treating the catalogue as an ordered list lets us reason about positions without knowing how a particular machine stores strings. Treating search as a function lets another part of a program use the result without repeating the search steps.

An abstraction must retain what matters. If we replace the ordered list with a collection that has no meaningful order, “first index” loses its meaning. If we keep only titles and discard authors, we cannot answer an author query without adding information.

When you run a script, the CPU does not directly understand a book title or the English phrase “find the first match”. A language implementation and machine instructions connect that meaning to physical operations. You can learn to reason about the search before learning all those mechanisms.

The same separation helps with faults. A requirement might ask for the wrong matching rule; the algorithm might skip index 0; the program might place return -1 inside the loop; the environment might fail to open a file. Identify the responsibility that failed before changing the code.

Use Python 3.11 or later, a text editor and a terminal. The labs use only Python's standard features; no packages or datasets are needed. Download each script below or copy its code into a file with the same name. In a terminal opened in that folder, run python lab1_trace.py. On Windows, py -3 lab1_trace.py is another option. On systems where Python is named python3, use that command.

A quoted value such as "Dune" is a string; square brackets hold a list. for repeats the indented block. enumerate supplies an index and an item. if selects a block when a condition is true. == compares values; = assigns a value to a name. Indentation is part of Python's syntax. The labs introduce only the notation needed here; Module 03 teaches programming systematically.

Goal: connect pseudocode, state and actual execution. Time: 30 minutes. First predict which lines will print. Then run the script and compare your prediction with the captured output.

Download lab1_trace.py

"""Module 01, Lab 1: trace a search, one comparison at a time."""

books = ["Dune", "Foundation", "The Hobbit", "Dune"]
target = "The Hobbit"
found = -1

for index, title in enumerate(books):
    print(f"inspect {index}: {title}")
    if title == target:
        found = index
        break

print(f"result: {found}")

inspect 0: Dune
inspect 1: Foundation
inspect 2: The Hobbit
result: 2

found = -1 sets the absent result before searching. break exits the loop after a match; the final print still runs. The f before a quoted string lets the print include values inside braces.

1. Change the target to Dune, then Solaris. Write the predicted traces before running.
2. Set books = []. Explain why the loop body does not run.
3. Remove break and search for Dune. Why does the result become 3? Which part of the contract fails?
4. Restore the original code. Explain the difference between “exit this loop” and “return from this function”.

Goal: test empty, missing, boundary and duplicate cases. Time: 35 minutes. A def block defines a function. A return supplies its result and ends that call. assert stops the script if its condition is false. Run normally, without Python's -O option, which disables assertions.

Download lab2_contract.py

"""Module 01, Lab 2: make a contract executable with examples."""


def find_first(items, target):
    """Return the first matching index, or -1 if target is absent."""
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1


cases = [
    ([], "Dune", -1),
    (["Dune"], "Dune", 0),
    (["Dune"], "Solaris", -1),
    (["Dune", "Solaris"], "Solaris", 1),
    (["Dune", "Solaris", "Dune"], "Dune", 0),
]

for items, target, expected in cases:
    actual = find_first(items, target)
    assert actual == expected, (items, target, expected, actual)
    print(f"{items!r}, {target!r} -> {actual}")

print("5 cases passed")

[], 'Dune' -> -1
['Dune'], 'Dune' -> 0
['Dune'], 'Solaris' -> -1
['Dune', 'Solaris'], 'Solaris' -> 1
['Dune', 'Solaris', 'Dune'], 'Dune' -> 0
5 cases passed

1. Explain why the five cases exercise different parts of the contract.
2. Add (["Dune"], "dune", -1) to confirm exact, case-sensitive matching.
3. Move return -1 inside the loop, immediately after the if block. Predict which checks will fail or which result will change, then run.
4. Repair the function. Add a check that the input list is unchanged after a call.

Goal: distinguish input size from work in a particular run. Time: 35 minutes. This script returns a pair: result and comparison count. range(size) produces integers from zero up to, but excluding, size; list collects them. The same equality-search procedure applies to numbers. += 1 increases a counter by one.

Download lab3_cost.py

"""Module 01, Lab 3: count comparisons instead of timing the computer."""


def search_with_cost(items, target):
    comparisons = 0
    for index, item in enumerate(items):
        comparisons += 1
        if item == target:
            return index, comparisons
    return -1, comparisons


for size in [0, 1, 4, 8, 16]:
    items = list(range(size))
    missing_index, missing_cost = search_with_cost(items, -1)
    first_index, first_cost = search_with_cost(items, 0)
    print(f"n={size:2}: absent={missing_cost:2}, first={first_cost:2}")
    assert missing_index == -1 and missing_cost == size
    assert first_index == (0 if size else -1)
    assert first_cost == (1 if size else 0)

n= 0: absent= 0, first= 0
n= 1: absent= 1, first= 1
n= 4: absent= 4, first= 1
n= 8: absent= 8, first= 1
n=16: absent=16, first= 1

1. Predict both counts for a list of length 32.
2. Add a last-position target using size - 1. For size 0, the target remains absent.
3. Search for the middle position of a 16-entry list: target 8. Why are there nine comparisons?
4. State the best and worst comparison counts for a nonempty list. Explain why elapsed time alone would not establish those formulas.

Try each question before opening its solution. ★ means a direct application; ★★ combines ideas; ★★★ asks you to change the contract or construct an argument.

def find_first_ascii_ignore_case(items, target):
    for index, item in enumerate(items):
        if item.lower() == target.lower():
            return index
    return -1

assert find_first_ascii_ignore_case(["Dune"], "dune") == 0
assert find_first_ascii_ignore_case([], "dune") == -1

Choose an answer to see feedback. The score counts answered questions; reset to try again. If scripts are disabled, open the answer key below.

Read the official Python introduction to lists and the sections on for statements, range, break and defining functions. Focus on the constructs used in the labs; you can skip the other control-flow features for now.

Write down why an empty list causes zero loop iterations, why range excludes its endpoint and what return does. Then explain how those language rules support our search algorithm. The distinction between a language rule and a problem requirement is the purpose of this reading.

You can now turn a vague search request into a contract, trace a procedure, explain its first-match property, show why it terminates and count its comparisons. You have also located that computation within the layers of a running computer.

Close the page and reproduce the pseudocode from memory. Trace an empty list, a duplicate match and an absent title. Explain which assumption makes the termination argument work. If one explanation is uncertain, revisit that section before checking off your last session.

The next module is Representing information: how bits encode integers and text, and why some numbers cannot be represented exactly. The course overview links to all 14 modules.