CSSE1001 — Full Course Notes

Week 1

Python as a Calculator

See csse1001 for course logistics — this note covers Lecture 1B’s technical content.

Today’s outline

• The Python REPL
• Syntax vs. semantics
• Arithmetic expressions, order of operations, and associativity
• Variables
• Worked exam questions

Learning objectives

1. Python expressions have syntax and semantics.
2. Python can evaluate arithmetic expressions, but this requires an order of operations and rules for associativity.

The Python REPL

A REPL (read-evaluate-print loop) is an interactive environment: it reads input, evaluates it, prints the result, then loops.

>>> 2*3
6
>>>

The >>> prompt is only shown in the interactive REPL — it isn’t included when writing Python instructions into files.

Syntax vs. semantics

A programming language like Python has both:

• Syntax — defines what it means to be a valid program.
• Semantics — defines what a valid program actually does.

2 + 3 is syntactically correct Python and evaluates to 5. Prefix notation like + 2 3 (valid in Lisp) is not valid Python syntax:

>>> + 2 3
    + 2 3
      ^
SyntaxError: invalid syntax

Python’s language rules must be followed precisely for a program to run.

Arithmetic expressions

See python-operator-precedence-and-associativity for the full syntax/semantics rules for brackets, negation/affirmation, and the arithmetic operators (+ - * / // % **), the order-of-operations table, associativity (including why ** is right-associative), integer division, and the ^ xor gotcha.

Worked exam questions

Q: What does 2 ** 3 % 5 - 1 evaluate to? ((2 ** 3) % 5) - 1 = (8 % 5) - 1 = 3 - 1 = 2

Q: What value gets assigned to x in x = 35 * 2 % 5 ** 2? (35 * 2) % (5 ** 2) = 70 % 25 = 20 — 60% of the class answered correctly.

Variables

Values can be named — these names are called variables. Assigning a value to a variable doesn’t print anything in the REPL:

>>> width = 2
>>> height = 3
>>> area = width * height
>>> 4 * area
24

min and max

>>> max(1, 2)
2
>>> min(1, 2)
1
>>> max(5, 1, -2, 3, 2*7)
14

Exercise: second largest of three numbers

Given three distinct numbers a, b, c, write an expression for the second largest:

>>> a, b, c = -9, 19, 3
>>> a + b + c - max(a, b, c) - min(a, b, c)
3
>>> min( max(a, b), max(a, c), max(b, c) )
3
>>> max( min(a, b), min(a, c), min(b, c) )
3

Next lecture

1. 2025-08-04-python-memory-model — Python memory model.
2. 2025-08-04-primitive-data — Primitive data types.

Week 2

Primitive Data

See csse1001 for course logistics — this note covers Lecture 2B’s technical content.

Today’s outline

• Primitive data types built into Python
• Booleans, integers, strings, and tuples
• Converting between types

Learning objectives

1. There are more built-in types besides integers that can form expressions.
2. These types are immutable.
3. We can convert between types, albeit imperfectly.

Primitive data

The types “built-in” to Python by default are called primitive data: booleans, integers, floats (not covered in this lecture), strings, and tuples.

See python-primitive-data-types for the full definitions, operators, and worked examples for each of these types — comparison operators and truthy/falsy values for booleans; unbounded-precision and conversion for integers; concatenation, comparison, indexing/slicing, and immutability for strings; and construction, indexing/slicing, immutability, and packing/unpacking for tuples.

Summary

We have booleans, integers, strings, and tuples. Strings and tuples are indexed and can be sliced. We can convert between the types (imperfectly).

Next lecture

1. 2025-08-11-functions — Functions.
2. 2025-08-11-sequence-selection-and-iteration — If-statements (selection).

Python Memory Model

See csse1001 for course logistics — this note covers Lecture 2A’s technical content.

Today’s outline

• Memory as a sequence of bits
• Variables as named memory locations
• Sequencing: why the order of instructions matters

Learning objectives

1. Memory is a sequence of bits that we can toggle.
2. We can (and should) store values in named memory locations called variables.
3. The order of instructions matters.

How much can a byte hold?

Computer memory is a very long series of on/off switches (bits, short for binary digit). Eight consecutive bits form a byte, and 4 or 8 bytes form a word (depending on machine architecture).

In general, \(n\) bits can store \(2^n\) distinct things:

• 1 bit: \(2^1 = 2\) things (off, on)
• 2 bits: \(2^2 = 4\) things (off-off, on-off, off-on, on-on)
• 3 bits: \(2^3 = 8\) things
• 4 bits: \(2^4 = 16\) things

Variables and memory

See python-variables-and-memory-model for how Python interprets memory as typed objects, how id() reveals an object’s address, and the rules for assigning, retrieving, naming, and reassigning variables.

Sequencing: order matters

The same instructions executed in a different order will (usually) produce a different outcome.

Python Tutor 1 — note we cannot swap these two lines: x = x + 1 on its own throws a NameError, since x has no value yet.

>>> x = 1
>>> x = x + 1

Python Tutor 2:

>>> x = 1
>>> x = x + 1
>>> x = 2*x
>>> x
4

Python Tutor 3 — last two lines swapped:

>>> x = 1
>>> x = 2*x
>>> x = x + 1
>>> x
3

Python Tutor 4:

>>> x = 2
>>> y = 3
>>> y = x
>>> x = y
>>> x
2
>>> y
2

Python Tutor 5 — middle two lines swapped:

>>> x = 2
>>> y = 3
>>> x = y
>>> y = x
>>> x
3
>>> y
3

Summary

We can manipulate memory using Python and refer to that memory with variables. The order in which we do this manipulation matters — the same sequence of instructions done in a different order will (usually) result in a different outcome.

Next lecture

2025-08-04-primitive-data — immutable objects (the things we put in memory that cannot be changed).

Week 3

Functions

See csse1001 for course logistics — this note covers Lecture 3A’s technical content.

Today’s outline

• What a function is and how to define one
• The return statement, and how it differs from print
• Improving functions with type hints and docstrings

Learning objectives

1. User-defined functions bundle code together and are the building blocks of more sophisticated programs.
2. return hands back a value and exits a function; it is not the same as print.
3. Functions can be documented with type hints and docstrings.

What is a function?

We have already used functions — * and max, for example — each of which takes input and returns output. User-defined functions let us name and reuse our own bundles of code, just like a mathematical function such as \(f(x) = x^2+x+1\):

>>> def f(x):
...     return x**2 + x + 1
>>> f(3)
13

See python-functions for the full syntax rules (indentation, multiple parameters, the return statement, return vs. print, type hints, and docstrings) — used throughout the rest of this note.

Building up Heron’s formula

Exercise. The area of a triangle with side lengths \(a, b, c\) is \(\sqrt{s(s-a)(s-b)(s-c)}\) where \(s = \tfrac{1}{2}(a+b+c)\) (Heron’s formula). What is the area of the triangle with sides 3, 4, and 5?

As a calculator, we’d have to type this out in full, and it would be tedious to repeat for other side lengths:

>>> (0.5*(3+4+5)
...  *(0.5*(3+4+5)-3)
...  *(0.5*(3+4+5)-4)
...  *(0.5*(3+4+5)-5))**0.5
6.0

Using names and sequencing (see 2025-08-04-python-memory-model) avoids repeating the same sub-expression:

>>> a, b, c = 3, 4, 5
>>> s = (a + b + c)/2
>>> (s*(s-a)*(s-b)*(s-c))**0.5
6.0

Wrapping it in a function makes it reusable for any triangle:

>>> def heron(a, b, c):
...     s = (a + b + c)/2
...     return (s*(s-a)*(s-b)*(s-c))**0.5
>>> heron(3, 4, 5)
6.0

Improving the function

Adding type hints and a docstring (see python-functions):

>>> def triangle_area(a: float, b: float, c: float) -> float:
...     """
...     Return the area of the triangle with sides length <a>,
...     <b>, and <c>.
...     Preconditions: <a>, <b>, <c> are all nonzero positive.
...     >>> triangle_area(3, 4, 5)
...     6.0
...     """
...     s = (a+b+c)/2
...     return (s*(s-a)*(s-b)*(s-c))**0.5
>>> triangle_area(2.2, 3.3, 4.4)
3.5147323866832307

See python-pep8-style-guide for the naming, spacing, and line-length conventions expected of functions like this.

return vs. print: quick check

>>> def example(x):
...     print(1*x)
...     return 3*x
...     print(2*x)   # never runs -- return already exited the function
>>> a = example(1)
1
>>> a
3

>>> def foo(x):
...     if x > 0:
...         print("Positive")
...     if x > 10**5:
...         print("Large positive")
>>> ans = foo(10**6)
Positive
Large positive
>>> type(ans)
<class 'NoneType'>

foo above never hits a return, so it defaults to returning None even though it printed something. Contrast with a version that returns instead:

>>> def bar(x):
...     if x > 0:
...         return "Positive"
...     if x > 10**5:
...         return "Large positive"
>>> ans = bar(10**6)
>>> ans
'Positive'

bar exits at the very first return it reaches, so "Large positive" is never returned even though x > 10**5 is also true.

Exercise: the middle number

Write a function that takes three integers and returns the number that is not the largest or the smallest:

def middle_number(x: int, y: int, z: int) -> int:
    """
    Return the number that is not the largest or smallest
    among the three inputs.
    Precondition: the numbers are distinct.
    >>> middle_number(3, 1, 2)
    2
    >>> middle_number(2, 3, 1)
    2
    """
    return (x + y + z) - min(x, y, z) - max(x, y, z)

Summary

Blocks of code can be grouped into functions. Functions take zero or more inputs and hand back a single value designated by return.

Next lecture

2025-08-11-sequence-selection-and-iteration — selection.

Sequence, Selection, and Iteration

See csse1001 for course logistics — this note covers Lecture 3B’s technical content.

Today’s outline

Despite the title, this lecture is entirely about selection (controlling program flow) — sequencing was already covered in 2025-08-04-python-memory-model, and iteration is the topic of the next lecture.

Learning objectives

1. Predicates and the logical operators and, or, not let us build up complex conditions.
2. The if statement (and its elif/else variants) lets us skip or select blocks of code based on a condition.
3. If-statements can often be refactored into simpler, equivalent forms.

Selection

See python-boolean-logic for the full reference on booleans, predicates, and/or/not, precedence, short-circuiting, and truthiness, and python-if-statements for the full reference on if/elif/else, the common elif-ordering bug, and simplifying if-statements.

Exercises

Bracket for False. Bracket the expression below so that it evaluates to False. How many different bracketings can you find?

False and False or True and False or False or True

Add a single not. Add a single not to the same expression so that it evaluates to False.

Both exercises are posed but left unsolved in the source material — flagged here rather than guessed at.

Refactoring exercise. Refactor the following code:

def foo(x, y):
    if x > 100 and y > 0:
        if y > 100 and x > 0:
            return "A"
        elif y > 100 or x > 0:
            return "A"
        else:
            return "B"
    elif y <= 0 or x <= 0:
        if x == y:
            return "A"
        if x <= y and x >= y:
            return "B"
        if y < x and x < y:
            return "C"
        else:
            return "A"
    else:
        if x <= 100 and y > 0:
            return "A"
        if x > 100 or y <= 0:
            return "B"
        else:
            return "D"

No worked solution is given in the source for this exercise either — left as an exercise rather than invented here.

Summary

Blocks of code can be skipped using if statements. This control flow depends on the evaluation of predicate (boolean-valued) statements.

Next lecture

2025-08-18-while-loops — iteration.

Week 4

Non-Primitive Data

See csse1001 for course logistics — this note covers Lecture 4B’s technical content.

Today’s outline

• Lists: mutable ordered collections
• Dictionaries: hash tables

Learning objectives

1. Lists are mutable ordered collections; tuples (python-primitive-data-types) are immutable ordered collections.
2. A dictionary maps keys to values via a hash function, and is unordered and mutable.

Lists

See python-lists for the full reference on lists: creation, mutability, comparison, membership, append/extend, aliasing, copying (shallow/deep), passing to functions, slicing, nested lists/matrices, type hints, and unpacking into function arguments.

Exercise: counting occurrences

def count(xs: list[int], ys: list[int]) -> int:
    """ Return the number of times members of ys are in xs.
    >>> count([1, 2], [1, 2, 3, 4])
    2
    >>> count([1, 2], [1, 2, 2, 2, 3, 1, 4])
    5
    """

A while-loop solution:

def count(xs: list[int], ys: list[int]) -> int:
    ans, k = 0, 0
    while k < len(ys):
        y = ys[k]
        k += 1
        if y in xs:
            ans += 1
    return ans

A for-loop is more natural for this problem:

def count(xs: list[int], ys: list[int]) -> int:
    ans = 0
    for y in ys:
        if y in xs:
            ans += 1
    return ans

There is also a one-line solution:

def count(xs: list[int], ys: list[int]) -> int:
    return sum(y in xs for y in ys)

Exercise: rotating a list

We say the list [0, 1, 2, 3, 4, 5] rotated by 2 is [2, 3, 4, 5, 0, 1]. Write a function def rotate(xs: list, k: int) -> list that rotates a list by k.

No worked solution is given in the source for this exercise — left as an open exercise rather than invented here.

Question: Caesar cipher

Write code for encrypting and decrypting messages using the Caesar cipher, with function headers:

def encrypt_caeser(plaintext: str, shift: int) -> str:

def decrypt_caeser(ciphertext: str, shift: int) -> str:

Left unsolved in the source — the lecture moves directly on to dictionaries afterwards. A working caesar_cipher implementation (a single shift parameter instead of separate encrypt/decrypt functions) appears later, in Lecture 5C — see week-five-exercises.

Dictionaries

Here is a deliberately vague question: write a function that returns the character frequency of a string, ignoring case — e.g. the character frequency of "hello world" would encode that there is one h, three ls, and so on.

What are some viable representations?

Two lists (characters paired positionally with their counts):

[['h', 'e', 'l', 'o', ' ', 'w', 'r', 'd'],
 [ 1,   1,   3,   2,   1,   1,   1,   1 ]]

One-to-one encoding (a count for every letter of the alphabet, in order):

# a b c d e f g h i j k l m n o p q r s t u v w x y z
 [0,0,0,1,1,0,0,1,0,0,0,3,0,0,2,0,0,1,0,0,0,0,1,0,0,0]

Hash functions

In both representations we provided a way to map a key (a character) to a value (a count) — this mapping is called a hash function:

\[\texttt{str} \to \texttt{int}, \quad \texttt{h} \mapsto 1, \; \texttt{e} \mapsto 1, \; \texttt{l} \mapsto 3, \; \ldots\]

The hash function for the two-list encoding looks up the key’s position in the first list, then indexes the second list at that position:

def hash_1(key: str) -> int:
    """Two list encoding."""
    xs = ['h', 'e', 'l', 'o', ' ', 'w', 'r', 'd']
    ys = [1, 1, 3, 2, 1, 1, 1, 1]
    k = xs.index(key)   # position of key in xs
    return ys[k]

The hash function for the one-to-one encoding computes the key’s position in the alphabet directly, via ord:

def hash_2(key: str) -> int:
    """One-to-one encoding."""
    xs = [0,0,0,1,1,0,0,1,0,0,0,3,0,0,2,0,0,1,0,0,0,0,1,0,0,0]
    pos_in_alpha = ord(key) - ord('a')   # position of key in alphabet
    return xs[pos_in_alpha]

Generally, we can index a collection by any type of key given some hash function that maps keys to values. Python has a “magic” hash function that indexes anything appropriately — implemented as the dict type. See python-dictionaries for the full reference on dictionaries: creation, indexing, keys/values/items, clear/copy (and its shallow-copy gotcha), get, and the requirement that keys be immutable.

The “hello world” character frequency, encoded as a dictionary:

>>> char_to_freq = {
...     'd': 1, 'o': 1, ' ': 1, 'r': 1,
...     'w': 1, 'e': 1, 'l': 3, 'h': 1
... }

Summary

Lists are mutable ordered collections; dictionaries store key-value pairings, found quickly via a “magically” fast hash function.

Next lecture

For-loops and list comprehensions.

While-Loops

See csse1001 for course logistics — this note covers Lecture 4A’s technical content.

Today’s outline

• Why we need to repeat code, possibly indefinitely
• The while-loop
• Simulating a do-while, and reading user input

Learning objectives

1. Loops are a control structure for repeating code.
2. A while-loop repeats code while a condition holds.
3. input() reads from the keyboard; random.randint generates random integers.

Motivation

There are (at least) two scenarios where repeating code, possibly indefinitely, is necessary:

1. prompting the user for valid input, and
2. playing a random game (e.g. guessing dice rolls).

See python-while-loops for the full reference on loops, while-loops, break, augmented assignment operators (+=, *=, /=, %=), simulating a do-while, input(), and random.randint.

Accumulator pattern

>>> x = 0
>>> while x < 10:
...     x = x + 1
>>> x
10

Using an augmented assignment operator (see python-while-loops) makes the accumulation more concise:

>>> x = 0
>>> while x < 10:
...     x += 1
>>> x
10

There is usually a key-stroke (typically ctrl+c) that terminates a runaway loop (e.g. while True: print(x); x += 1) — it is a good idea to learn what it is in your IDE.

Exercise: guess the number

Write a function foo(target: int) -> int that prompts the user to input a number until the user guesses some (secret) target. For each guess the function should print Too high, Too low, or That's it! depending on the guess, and return the number of guesses required.

def foo(target: int) -> int:
    number_of_guesses = 0
    while True:
        guess = int(input("Guess: "))
        number_of_guesses += 1
        if guess > target:
            print("Too high")
        elif guess < target:
            print("Too low")
        else:
            print("That's it!")
            return number_of_guesses

Exercise: guess the dice roll

Write a function bar() -> None that prompts the user to predict the result of a six-sided dice roll, repeating the prompt until the user predicts correctly:

from random import randint

def bar() -> None:
    """
    Prompt user to predict the result of a six sided
    dice roll until the guess is correct.
    """
    while True:
        guess = int(input("Guess in [1..6]: "))
        roll = randint(1, 6)
        if roll == guess:
            break
    return

Further exercises

The source poses these without a worked solution — left here as open exercises rather than guessed at:

• Write a function that prints the result of a six-sided dice roll until a six is rolled, and returns the number of rolls required.
• Write a function that accumulates the result of dice rolls until some threshold is met/passed, and returns the number of rolls required.
• Develop functions for adding and multiplying positive integers together, restricting yourself to exactly two arithmetic operations — succ (adding one) and pred (subtracting one). The source only gives the two building blocks:

def succ(x: int) -> int:
    return x+1

def pred(x: int) -> int:
    return x-1

(The add/multiply functions built from succ/pred are not solved in the source.)

Summary

The while-loop is a control structure for repeating code a possibly infinite number of times.

Next lecture

2025-08-18-non-primitive-data — lists and dictionaries.

Week 5

Comprehensions

See csse1001 for course logistics — this note covers Lecture 5B’s technical content. See python-comprehensions for the full reference on comprehension syntax.

Today’s outline

• List comprehensions
• Dictionary comprehensions
• Nested comprehensions
• Filtering
• all and any

List comprehension

Mathematics builds sets and sums this way:

\[ \{k^2 : k \in \{0, 1, 2, 3\}\} = \{0, 1, 4, 9\} \qquad \sum_{k \in \{0,1,2,3\}} k^2 = 0^2+1^2+2^2+3^2 \]

Python mirrors this directly:

>>> [k**2 for k in range(4)]
[0, 1, 4, 9]
>>> sum(k**2 for k in range(4))
14

Dictionary comprehension

>>> {x: f"value is {x}" for x in range(3)}
{0: 'value is 0', 1: 'value is 1', 2: 'value is 2'}

>>> {x: 0 for x in "ABC"}   # useful for assigning default values
{'A': 0, 'B': 0, 'C': 0}

>>> cs = "hello world"
>>> {x: cs.count(x) for x in cs}
{'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Nested comprehensions

Multiple for clauses can appear in one comprehension — order matters:

>>> [(a, x) for a in "ABC" for x in range(2)]
[('A', 0), ('A', 1), ('B', 0), ('B', 1), ('C', 0), ('C', 1)]

>>> [(a, x) for x in range(2) for a in "ABC"]
[('A', 0), ('B', 0), ('C', 0), ('A', 1), ('B', 1), ('C', 1)]

Implementing [(a, x) for a in "ABC" for x in range(2)] with a for-loop:

>>> xs = []
>>> for a in "ABC":
...     for x in range(2):
...         xs.append((a, x))

Exercise: disassemble a string

def disassemble(cs: str) -> list[str]:
    """ Returns a list of characters comprising <cs>, maintaining order.
    >>> disassemble("")
    []
    >>> disassemble("abcdef")
    ['a', 'b', 'c', 'd', 'e', 'f']
    """

With a for-loop:

>>> def disassemble(xs: str) -> list[str]:
...     ans = []
...     for x in xs:
...         ans.append(x)
...     return ans

With a list comprehension:

The companion source file defines disassemble with the comprehension return first, followed by an equivalent for-loop version left in the function body below it. That second block is unreachable dead code (the return above it always exits first) and is omitted here.

NoteWorking

return [c for c in cs]

Exercise: more capitals than lower-case

Check if a string has (strictly) more capitals than lower-case letters, ignoring all other characters:

def more_capitals(cs: str) -> bool:
    """
    >>> more_capitals("aAbBcCdD")
    False
    >>> more_capitals("CSSE 1001")
    True
    >>> more_capitals("")
    False
    """

A useful “hack”: the integer value of True and False is 1 and 0 respectively, so sum(...) over a sequence of booleans counts how many are True:

>>> True + True + False
2

The lecture slide’s solution has a typo — it compares against 'a' <= c <= 'a' (matching only the literal character 'a') instead of 'a' <= c <= 'z' (matching any lower-case letter). The companion source file has it correct; the exercise below uses the corrected bound.

NoteWorking

return (sum('A' <= c <= 'Z' for c in cs)
        > sum('a' <= c <= 'z' for c in cs))

Exercise: all

Check if every element of a list is truthy:

def all(xs: list) -> bool:
    """
    >>> all([1, 2, 3])
    True
    >>> all(["a", "", "c"])
    False
    >>> all([])
    True
    """

NoteWorking

return len(xs) == sum(bool(x) for x in xs)

Exercise: any

Check if any element of a list is truthy:

def any(xs: list) -> bool:
    """
    >>> any([0, 0, 0])
    False
    >>> any(["a", "", "c"])
    True
    >>> any([])
    False
    """

NoteWorking

return sum(bool(x) for x in xs) > 0

all and any are both included in base Python already (no import needed):

>>> xs = "HELLO WORLD"
>>> all('A' <= x <= 'Z' for x in xs)   # is every letter a capital?
False    # (space is not a capital)
>>> any('A' <= x <= 'Z' for x in xs)   # is any letter a capital?
True

Filtering

Comprehension elements may be filtered with a trailing if. E.g. the numbers less than 100 divisible by both 3 and 7:

>>> [x for x in range(101) if not (x % 3) and not (x % 7)]
[0, 21, 42, 63, 84]

The general pattern

[x for x in xs if P(x)]
[x for x in xs for y in ys if P(x, y)]
[x for x in xs for y in ys for z in zs if P(x, y, z)]
...

where P is some predicate.

Summary

Comprehensions are a rapid way of forming lists and dictionaries that would otherwise require an accumulator for-loop.

Next: week-five-exercises — practice exercises from Lecture 5C.

For-Loops

See csse1001 for course logistics — this note covers Lecture 5A’s technical content. See python-for-loops for the full reference on for-loop syntax, ranges, and enumerate.

Today’s outline

• For-loops: definition and syntax
• Iterating over strings, lists, and dictionaries
• The accumulator pattern
• range and enumerate

Definitions

Loop — a control structure that repeats code that belongs to it.

For-loop — a control structure that, given a group, repeats code for every member of that group, in order.

for <name> in <iterator>:
    <code>

String iteration (character by character)

A for-loop iterates through a string’s characters, in order:

>>> for x in "abcd":
...     print(x)
a
b
c
d
>>> x
'd'

Note the looping name (x) retains its final value after the loop exits.

Nesting for-loops

>>> (digits, alphas) = ("012", "xy")
>>> for d in digits:
...     for a in alphas:
...         print(d + a)
0x
0y
1x
1y
2x
2y

Python disallows empty for-loop bodies — use pass (the empty instruction, which has no effect) as a placeholder:

>>> for d in digits:
...     for a in alphas:
...         pass
...     print(d + a)
0y
1y
2y

Again, the names used to iterate through an iterator retain their values after the for-loop exits — by the time the outer loop’s print runs, the inner loop has already finished, leaving a at its last value ('y') each time.

The accumulator pattern

Recall an accumulator is a variable a loop uses to build up an aggregate value:

>>> acc = ""
>>> for x in "abcd":
...     acc = acc + x
...     print(acc)
a
ab
abc
abcd

Building it in reverse order just by swapping the order of concatenation:

>>> acc = ""
>>> for x in "abcd":
...     acc = x + acc
...     print(acc)
a
ba
cba
dcba

For-loops vs. while-loops

Can every for-loop be rewritten with only while-loops? Yes:

>>> for x in xs:
...     ...   # do something with x

is code-equivalent to:

>>> k = 0
>>> while k < len(xs):
...     ...   # do something with xs[k]
...     k += 1

Can every while-loop be rewritten with only for-loops? No — consider how many times you’d need to repeat asking a user for correct input (not known in advance).

Technical caveat: a for-loop can be tricked into looping forever in Python, by giving it an iterator that never exhausts. And if you dig deep enough, Python itself used a while-loop to build that iterator in the first place.

Exercise: removing characters

def remove(c: str, cs: str) -> str:
    """ Return the string with all instances of c removed from cs.
    Precondition: len(c) == 1
    >>> remove('b', "bluey")
    'luey'
    >>> remove('b', "Bluey")
    'Bluey'
    >>> remove('b', "chilli")
    'chilli'
    >>> remove('b', "")
    ''
    """

The lecture slide’s worked solution has a variable-naming slip — it reuses c as the loop variable (shadowing the parameter) and references an undefined x:

acc = ""
for c in cs:
    if not c == x:
        acc += c
return acc

The corrected version below (matching the companion source file) uses a different name for the loop variable.

Fill in the blank to complete remove:

NoteWorking

acc = ""
for x in cs:
    if x != c:
        acc += x
return acc

List looping (index by index)

A for-loop also iterates directly through a list’s elements:

>>> xs = ['a', 2, 'c', 4, 'e']
>>> for x in xs:
...     print(x)
a
2
c
4
e

Exercise: unique elements

def make_unique(xs: list[int]) -> list[int]:
    """ Returns the UNIQUE elements of xs.
    >>> make_unique([1, 2, 3, 4])
    [1, 2, 3, 4]
    >>> make_unique([1, 2, 2, 2, 3, 1, 4, -3])
    [1, 2, 3, 4, -3]
    """

NoteWorking

acc = []
for x in xs:
    if x not in acc:
        acc.append(x)
return acc

This is an out-of-place computation — the original list xs is not modified. An in-place change would instead modify xs directly; those are covered later, in the object-oriented part of the course.

Ranges (iterating through numbers)

range builds an iterator of numbers, with the general form range([start], stop[, step]) (square brackets denote optional arguments) — similar to list slicing:

>>> range(10)
range(0, 10)
>>> type(range(10))
<class 'range'>
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(2, 7))
[2, 3, 4, 5, 6]
>>> list(range(2, 7, 3))
[2, 5]
>>> list(range(2, 7, -1))
[]
>>> list(range(7, 2, -1))
[7, 6, 5, 4, 3]

range is commonly used to walk through a list by index:

>>> xs = [11, 22, 33, 44]
>>> for k in range(len(xs)):
...     ...   # code involving xs[k]

Enumerate (iterating with index)

enumerate simplifies the index-and-value pattern above. Roughly:

enumerate([x0, ..., xn]) == [(0, x0), ..., (n, xn)]

(this isn’t the full story — enumerate actually returns an iterable, not a list — but the pairs it produces work the same way):

>>> xs = [1, 2, 3, 4]
>>> for k, xk in enumerate(xs):
...     ...   # code involving k and xk == xs[k]

Each (k, xk) pair is an immutable tuple:

>>> for k, x in enumerate(["Scientia", "ac", "Labore"]):
...     print(k, x)
0 Scientia
1 ac
2 Labore

(“Scientia ac Labore” is UQ’s motto — “by means of knowledge and hard work”.)

Dictionary looping (key by key)

A for-loop iterates through a dictionary’s keys:

>>> h = {"red": 1, "blue": 2, "green": 3}
>>> for key in h:
...     print(key)
red
blue
green
>>> for key in h:
...     print(h[key])
1
2
3

Exercise: character index

Write a function that returns the character frequency of a string:

def char_index(xs: str) -> dict[str, list[int]]:
    """ Return a dictionary mapping the characters (length one
    substrings) of <xs> to the list of indices at which they occur.
    >>> char_index("")
    {}
    >>> char_index("aaAbbB")
    {'a': [0, 1], 'A': [2], 'b': [3, 4], 'B': [5]}
    """

The companion source file’s signature annotates the return type as dict[str, int], but both the doctest and the actual behaviour return dict[str, list[int]] — a list of indices per character, not a single count. The annotation above has been corrected to match.

NoteWorking

acc = {}
for k, x in enumerate(xs):
    if x in acc:
        acc[x].append(k)
    else:
        acc[x] = [k]
return acc

Summary

For-loops let us iterate through anything iterable. Strictly speaking they’re not necessary (a while-loop, or copy-pasting code k times, can always do the same job) but they’re used often enough to merit their own dedicated syntax.

Next: 2025-08-25-comprehensions (Lecture 5B) — a rapid way of building lists and dictionaries that would otherwise need an accumulator for-loop.

Week 5 Exercises — For-Loop Practice

Practice exercises for week 5 (Lecture 5C, “For Loop Practice”), following on from 2025-08-25-for-loops and 2025-08-25-comprehensions. See python-for-loops and python-comprehensions for the reference material needed to solve these.

On the HTML site, fill in each blank with your answer, then click Run Code to check it. In the PDF, the Working callout is shown as a static answer key instead (interactive checking needs a browser).

Q1 — Capitalize a string

def capitalize(cs: str) -> str:
    """ Capitalize every alphabet letter of a string.
    >>> capitalize("boom goes the dynamite!")
    'BOOM GOES THE DYNAMITE!'
    >>> capitalize("123")
    '123'
    """

NoteWorking

acc += chr(ord('A') + ord(c) - ord('a'))

Shifting a lower-case letter up to its capital by the fixed gap between 'A' and 'a' in the character encoding.

Q2 — Matrix transpose

def transpose(xss: list[list[int]]) -> list[list[int]]:
    """ Return the transpose of xss (rows and columns swapped).
    Precondition: xss is square, i.e. len(xss) == len(xss[0]) == ...
    >>> transpose([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
    [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
    >>> transpose([[1]])
    [[1]]
    """

NoteWorking

row = [xs[k] for xs in xss]

Row k of the transpose is column k of the original — the k-th element of every row xs in xss.

Q3 — Caesar cipher

A Caesar cipher shifts each letter a fixed number of places down the alphabet (wrapping around) to encrypt; shifting by the negative amount decrypts it again.

def caesar_cipher(cs: str, shift: int) -> str:
    """ Return a string where each character of <cs> has been shifted
    by <shift> according to the Caesar cipher.
    >>> caesar_cipher("HELLO", 3)
    'KHOOR'
    >>> caesar_cipher("KHOOR", -3)
    'HELLO'
    >>> caesar_cipher("abc xyz", 2)
    'cde zab'
    >>> caesar_cipher("cde zab", -2)
    'abc xyz'
    """

This resolves the Caesar cipher exercise posed (and left unsolved) back in 2025-08-18-non-primitive-data — same idea, a single shift parameter instead of separate encrypt/decrypt functions.

NoteWorking

acc += chr((ord(c) - ord('a') + shift) % 26 + ord('a'))

% 26 wraps the shift around the alphabet in both directions (including for negative shifts, since Python’s % always returns a non-negative result for a positive divisor).

Q4 — Combine two dictionaries

def combine(d1: dict[int, list[int]], d2: dict[int, list[int]]) -> dict[int, int]:
    """ Return the dictionary where each key is a key that is in both
    d1 and d2. The value for each key is the sum of all the integers
    associated with that key in d1 and d2.
    >>> combine({1: [2], 4: [5, 6]}, {4: [8]})
    {4: 19}
    """

NoteWorking

acc[key] = sum(d1[key]) + sum(d2[key])

Q5 — Reverse lookup

def reverse_lookup(d: dict, item) -> list:
    """ Returns all keys of <d> such that d[key] == item.
    Precondition: the items of <d> are immutable.
    >>> reverse_lookup({1: 'bluey', 19: 'chilli', -31: 'bluey'}, 'bluey')
    [1, -31]
    >>> reverse_lookup({1: 'bluey', 19: 'chilli', -31: 'bluey'}, 'muffin')
    []
    """

NoteWorking

if d[k] == item:

Q6 — Invert a dictionary

def invert(d: dict) -> dict:
    """ Return the inverted version of d (values become keys, mapping
    to a list of the original keys that shared that value).
    >>> invert({1: 10, 2: 10})
    {10: [1, 2]}
    """

NoteWorking

acc[val] = [key]

Week 6

File IO

See csse1001 for course logistics — this note covers Lecture 6B’s technical content. See python-file-io for the full reference on file modes and reading/writing patterns.

Today’s outline

• Memory hierarchy and why files
• Opening, reading, and closing files
• Exercises: counting empty lines, reading numbers, finding the highest-rated band, reading a Sudoku board
• Writing and appending to files

Memory hierarchy

Type	Order	2016 MacBook Pro	Persistence
CPU Cache L2	KB	256KB	Requires power
CPU Cache L3	MB	8MB	Requires power
Random Access Memory	GB	16GB	Requires power
Disk	GB/TB	256GB	Persistent
Cloud	PB	Functionally infinite	Persistent

Why files?

When Python launches, it’s allocated space in RAM, which can fill up — a problem for memory-intensive problems (analyzing tweets, payroll, scientific computing). We may also want to save our data with persistence. Either way, we need to instruct Python to use the disk, one level up the hierarchy.

Opening a file

file = open("file.dat", "<mode>")

Mode	Description
r	read
w	write
a	append (write at end of file)

See also os.getcwd() and os.chdir() (a file assumed to be in the same directory as the running script).

Reading a file

Given hello.txt containing:

What a
wonderful
hello world.

>>> file = open("hello.txt", "r")
>>> file.readline()
'What a\n'
>>> file.readline()
'wonderful\n'
>>> file.readline()
'hello world.'      # note: no trailing newline (last line of the file)
>>> file.readline()
''                  # empty string once exhausted, returned indefinitely

A for-loop iterates line by line:

>>> file = open("hello.txt", "r")
>>> for line in file:
...     print(line)
What a

wonderful

hello world.

>>>

(The extra blank lines above come from print’s own newline stacking on top of each line’s own trailing \n.)

The file-pointer is exhausted after one pass

>>> for line in file:
...     print(line)
>>>

Nothing prints — the file-pointer already reached the end of the file during the loop above. We need to reopen the file (or seek back to the start) to read it again:

>>> file = open("hello.txt", "r")
>>> for line in file:
...     line
'What a\n'
'wonderful\n'
'hello world.'

Closing files

Files left open are vulnerable to side-effects — you may find data missing, or extra bytes, if you neglect to close after use:

>>> file = open("hello.txt", "r")
>>> for line in file:
...     line
>>> file.close()

The with construct closes the file for you automatically, even if the code block crashes:

with open("hello.txt", "r") as file:
    for line in file:
        print(line)

Exercise: counting empty lines

def num_empty_lines(path: str) -> int:
    """ Count the number of empty lines (those that only contain \n)
    in the file at <path>.
    """

def num_empty_lines(path: str) -> int:
    ans = 0
    with open(path, "r") as the_file:
        for line in the_file:
            if line == "\n":
                ans += 1
    return ans

A second version takes a file pointer directly, rather than a path — note the different parameter type (the caller is now responsible for opening the file):

from typing import TextIO

def num_empty_lines(file_pointer: TextIO) -> int:
    ans = 0
    for line in file_pointer:
        if line == "\n":
            ans += 1
    return ans

fp = open("filename.txt")
num_empty_lines(fp)

Reading numbers from a file

Given numbers.dat containing one number per line (1 through 6), reading always gives back strings — cast to the appropriate type when needed:

>>> with open("numbers.dat", "r") as file:
...     ans = []
...     for line in file:
...         ans.append(int(line))
>>> ans
[1, 2, 3, 4, 5, 6]

Exercise: the highest-rated band

Given a CSV file bands.txt with a header row (Band,Rating,Plays), find the highest-rated band:

def highest_rated(path: str) -> str:
    """ Return the highest-rated band in the file at <path>.
    Precondition: the file has a header row.
    """
    current_most_popular_band = ""
    current_highest_rating = -float('inf')   # guarantees the first row updates it

    with open(path, "r") as file:
        file.readline()   # skip the header
        for line in file:
            band, rating, _ = line.split(',')   # don't name values you won't use
            rating = int(rating)
            if rating > current_highest_rating:
                current_highest_rating = rating
                current_most_popular_band = band

    return current_most_popular_band

The lecture slide names this function higest_rated (missing a t) — corrected to highest_rated above. The companion source file has a differently-named most_played function with the same shape of code, but it unpacks the third CSV column (Plays) instead of the second (Rating) — so despite its docstring claiming to return “the highest rated band”, it actually returns the band with the most plays. Reproduced here as highest_rated (ranking by rating, matching the slide and this section’s title) rather than perpetuating that docstring/behaviour mismatch.

Exercise: an arbitrary attribute

Extend the previous answer to take an arbitrary file with a header of attributes (e.g. name,grade,age) and a function def most(path: str, attribute: str) -> str that finds the maximum of that attribute.

No worked solution is given in the source for this exercise — left as an open exercise rather than invented here. (The companion source file also includes a least_rated_band function that is an intentional joke stub — return "Drake" with the comment # This is a joke — rather than a real implementation.)

Exercise: reading a Sudoku board

Given a partially-filled Sudoku board as a text file (| separates 3x3 blocks column-wise, a row of - separates them row-wise, and spaces mark empty cells):

685|13 | 47
7  |   | 1 
 1 |764| 5 
-----------
9  | 7 |5 4
8 1|  9| 72
4 3|  6|   
-----------
   |427|39 
 4 |9  | 68
1 7|   |4  

def read_board(path: str) -> list[list[int | None]]:
    """ Return a board representation for the Sudoku board in the
    file at <path>. None denotes an empty position.
    """

Character-by-character version:

def read_board_v1(path: str) -> list[list[int | None]]:
    with open(path, "r") as the_file:
        board = []
        for line in the_file:
            row = []
            if "-" in line:
                continue   # skip horizontal dividers
            for x in line:
                if x.isdigit():
                    row.append(int(x))
                if x == " ":
                    row.append(None)
            board.append(row)
    return board

Equivalent using a list comprehension (filtering out | characters, rather than simply not appending on them):

def read_board_v2(path: str) -> list[list[int | None]]:
    with open(path, "r") as the_file:
        board = []
        for line in the_file:
            if "-" in line:
                continue   # skip horizontal divider
            row = [int(x) if x.isdigit() else None for x in line if x != '|']
            board.append(row)
    return board

Exercise: has the Sudoku been won?

def has_won(board: list[list[int]]) -> bool:
    """ Return True when the Sudoku board is solved (contains the
    digits 1 through 9 in each row, column, and 3x3 grid).
    """

No worked solution is given in the source for this exercise — left as an open exercise rather than invented here.

Writing to files

>>> with open("numbers.dat", "w") as file:
...     file.write("Hello World.\n")            # write a single string
...     file.writelines(["Hello\n", "World\n"])  # write a list of strings

Careful! Opening a file for write ("w") creates the file if it doesn’t exist, or overwrites it if it does.

Appending to files

Appending opens a file without overwriting, instead adding to the end (creating the file if it doesn’t exist):

>>> with open("numbers.dat", "a") as file:
...     file.write("Hello World.\n")

Summary

We can read strings from files and write strings to files. A file-pointer moves forward every time a line is read — to read a line (or the whole file) twice, the file must be reopened.

Next: 2025-09-01-testing (Lecture 6C).

String Methods

See csse1001 for course logistics — this note covers Lecture 6A’s technical content. See python-string-methods for the full reference on the string methods covered here.

Today’s outline

• Built-in string methods and help()
• Method invocation syntax
• Exercises: title, center
• Splitting and joining strings
• Sanitizing data with strip

Why learn string methods?

During file processing (next lecture) we’ll be working extensively with strings. We’re already able to replicate the functionality of any string method with our current tools — but it’s worth striving to implement any string method you use at least once.

Built-in string methods

Python’s str type has a myriad of built-in methods. Review them via help(str):

>>> help(str)
...
| capitalize(self, /)
|     Return a capitalized version of the string.
|
| casefold(self, /)
|     Return a version of the string suitable for
|     caseless comparisons.

(Type Enter to scroll, q to quit help.)

Methods

Strings are objects — we’ll eventually learn what that means fully. Objects have methods, which are like functions but invoked differently. We don’t say:

>>> capitalize("hello")
NameError: name 'capitalize' is not defined

but rather:

>>> "hello".capitalize()   # note the ()
'Hello'

For information on a particular method:

>>> help(str.find)
find(...)
    S.find(sub[, start[, end]]) -> int

    Return the lowest index in S where substring sub is found,
    such that sub is contained within S[start:end]. Optional
    arguments start and end are interpreted as with slice notation.

    Return -1 on failure.

Interpreting help

Square brackets in a signature like find(sub[, start[, end]]) indicate an optional parameter — and this rule recurses (an optional parameter can itself have optional parameters). The valid ways to call find are:

"team".find("I")
"team".find("I", 1)
"team".find("I", 1, -1)

whereas find(1, -1) is not allowed, since sub is required.

>>> "hello world".find("world", 6)
6
>>> "hello hello".find("hello")
0
>>> "hello hello".find("hello", 1)
6
>>> "hello hello".find("hello", 1, 3)
-1

Exercise: title case

Convert a string of text into title format:

def title_case(cs: str) -> str:
    """ Convert cs to title case.
    >>> title_case("a tale of two cities")
    'A Tale Of Two Cities'
    """

This can be accomplished by invoking the appropriate string method correctly:

>>> cs = "a tale of two cities"
>>> cs.title()
'A Tale Of Two Cities'
>>> "a tale of two cities".title()
'A Tale Of Two Cities'

Exercise: centering text

Write a function that, given a word and an integer width, centers the word in a sequence of xs:

def foo(word: str, width: int) -> str:
    """
    >>> foo('spam', 10)
    'xxxspamxxx'
    >>> foo('101', 20)
    'xxxxxxxx101xxxxxxxxx'
    >>> foo('UQQU', 30)
    'xxxxxxxxxxxxxUQQUxxxxxxxxxxxxx'
    """

>>> help(str.center)
center(self, width, fillchar=' ', /)
    Return a centered string of length width.

    Padding is done using the specified fill character
    (default is a space).

>>> 'spam'.center(10, 'x')
'xxxspamxxx'
>>> '101'.center(20, 'x')
'xxxxxxxx101xxxxxxxxx'

Splitting strings

>>> "a b c".split()          # default: split at whitespace
['a', 'b', 'c']
>>> "axbxc".split()
['axbxc']
>>> "axbxc".split('x')
['a', 'b', 'c']
>>> "axbxc".split('bx')
['ax', 'c']
>>> "a, b, c".split(',')     # useful for CSV processing
['a', ' b', ' c']
>>> "a, b, c".split(', ')    # removes leading/trailing spaces
['a', 'b', 'c']

Joining strings

>>> ",".join(["A", "B", "C"])
'A,B,C'
>>> "".join(["A", "B", "C"])
'ABC'
>>> ", ".join(["A", "B", "C"])
'A, B, C'
>>> "xxx".join(["A", "B", "C"])
'AxxxBxxxC'

Sanitizing data

>>> help(str.strip)
strip(self, chars=None, /)
    Return a copy of the string with leading and trailing
    whitespace removed.

    If chars is given and not None, remove characters in
    chars instead.

>>> "   123   \n".strip()   # a newline is considered whitespace
'123'

Summary

Sometimes datatypes come with extra functionality by way of methods. In particular, there are many string methods that will aid with text processing.

Next: 2025-09-01-file-io (Lecture 6B).

Testing

See csse1001 for course logistics — this note covers Lecture 6C’s technical content, which concludes the module on imperative programming. See python-testing for the full reference on doctest and assertions.

Today’s outline

• Docstring (value) testing with doctest.testmod()
• Writing good doctests, and common whitespace/equality pitfalls
• Testing unordered types, and multi-line docstrings
• Black-box testing
• doctest.testfile()
• Assertions
• Practice exercises

Docstring testing

We’ve been diligently including doctests in our docstrings, e.g.:

def factorial(k: int) -> int:
    """Returns k! where k! = k*(k-1)! and 0! = 1.
    Assumes k > 0
    >>> factorial(3)
    6
    >>> factorial(0)
    1
    """

doctest.testmod() actually runs these tests, rather than just documenting intended usage.

Catching mistakes

def factorial(k: int) -> int:
    """
    >>> factorial(3)
    6
    >>> factorial(0)
    1
    """
    ans = 1
    for ell in range(k):
        ans *= ell     # bug: multiplies by ell, not k - ell
    return ans

>>> import doctest
>>> doctest.testmod(verbose=True)
**********************************************************************
File "__main__", line 5, in __main__.factorial
Failed example:
    factorial(3)
Expected:
    6
Got:
    0
**********************************************************************
1 items had failures:
   1 of 2 in __main__.factorial
***Test Failed*** 1 failures.
TestResults(failed=1, attempted=2)

The corrected version:

def factorial(k: int) -> int:
    ans = 1
    for ell in range(k):
        ans *= k - ell
    return ans

>>> doctest.testmod()
TestResults(failed=0, attempted=2)

Writing good doctests

A comprehensive doctest suite should:

1. Test typical cases and edge cases.
2. Test the zero of the data type — e.g. 0, [], "".
3. Test the singleton of the data type — e.g. 1, [1], "a".
4. Test for correctness, not violations of the function’s contract (precondition).
5. Avoid redundant tests.

Whitespace pitfalls

Doctest compares printed output exactly, character for character — not equality of values. Both of the following would fail:

def identity(x):
    """
    >>> identity([])
    [ ]
    >>> identity([1, 2, 3])
    [1, 2, 3]
    """

(an extra space inside [ ] doesn’t match Python’s actual [] output)

def identity(x):
    """
    >>> identity([])
    []
    >>> identity([1, 2, 3])
    [1,2,3]
    """

(a trailing space is fine here, but [1,2,3] doesn’t match Python’s own printed form, [1, 2, 3] — Python always prints a space after each comma in a collection literal)

String testing vs. equality testing

>>> identity(1.0)
1

fails because doctest compares the printed string 1.0 against the expected string 1 — they don’t match, even though 1.0 == 1 is True as values. Expected output must match exactly what Python would print.

Black-box testing

Suppose we’re given a function whose code is hidden — how do we gain confidence in its correctness through testing alone?

def pow(x: int, y: int) -> float:
    """ Returns x**y. Precondition: y >= 0. """
    return x*pow(x, y-1) if y else 1

def pow(x: int, y: int) -> int:
    """
    >>> pow(0, 0)      # zero
    1
    >>> pow(1, 0)      # unit and zero
    1
    >>> pow(0, 1)      # zero and unit
    0
    >>> pow(3, 1)      # typical and unit
    3
    >>> pow(1, 3)      # unit and typical
    1
    >>> pow(6, 10)     # typical
    60466176
    """

Exercise: ourmax

def ourmax(x: int, y: int) -> int:
    """ Return the larger of x and y. """

No worked solution is given in the source for this exercise — left as an open exercise (write the doctests, then implement) rather than invented here.

Testing sets

Only sets containing numbers print in sorted order — string-keyed sets print in an implementation-defined order:

>>> {3, 2, 1}
{1, 2, 3}
>>> {2, 1, 3}
{1, 2, 3}
>>> {"a", "b", "c"}
{'c', 'b', 'a'}
>>> {"b", "c", "a"}
{'c', 'b', 'a'}

Testing unordered types

Since string-testing an unordered type’s printed representation is unreliable, compare against a literal value with == instead:

def identity(x):
    """
    >>> {3, 1, 2} == identity({1, 2, 3})
    True
    >>> {1: "A", 2: "B"} == identity({1: "A", 2: "B"})
    True
    """

Multi-line docstrings

Setting up intermediate values across multiple >>> lines within one doctest is allowed:

def identity(x: int) -> int:
    """
    >>> a = 2
    >>> b = 1
    >>> identity(a + b)
    3
    """

Exercise: poly_min

def poly_min(a: int, b: int, c: int) -> float:
    """ Return the (approximate) minimum value of
    f(x) = a*x**2 + b*x + c
    for x any float.
    """

Float testing is complicated by the fact that float arithmetic is inexact — we usually only insist on answers being close enough, rather than equal, using a tolerance:

def poly_min(a: int, b: int, c: int) -> float:
    """
    >>> tolerance = 10**-3
    >>> abs(poly_min(1, 0, 0) - 0) < tolerance
    True
    >>> abs(poly_min(3, -5, 10) - 7.916666666666666) < tolerance
    True
    """

No worked implementation is given in the source for this exercise — only the doctests demonstrating the tolerance-based comparison technique.

Testing outside the module: doctest.testfile

Docstring examples inside a function aren’t meant to fully test a module — they explain usage to users. A full test suite belongs outside the functions, in its own file:

# testing.txt
sandbox.py should be in the same directory as this file
and contain fact. This entire file will be treated as
a docstring. For instance, this paragraph is considered
a comment despite not having quotes around it.
>>> from sandbox import fact
>>> fact(3)
6
>>> fact(0)
1

>>> doctest.testfile("testing.txt", verbose=True)
...
1 items passed all tests:
   3 tests in testing.txt
3 tests in 1 items.
3 passed and 0 failed.
Test passed.
TestResults(failed=0, attempted=3)

Assertions

An assertion is a truth claim that Python enforces at runtime. Programming with assertions helps catch problems early, by preventing (what are supposed to be) impossible situations from silently propagating — a failed assertion raises an AssertionError and stops the program.

def fact(x: int) -> int:
    ans = 1
    for k in range(x):
        ans *= k
    assert ans > 0   # all factorials are positive/non-zero
    return ans

>>> fact(3)
AssertionError

(This deliberately reuses the earlier buggy pattern — multiplying by the loop variable itself, which starts at 0 — to demonstrate the assertion catching the bug.)

>>> fact(3)
Traceback (most recent call last):
  File "<python-input-0>", line 1, in <module>
    fact(3)
  File "/Users/pvrbik/Desktop/sandbox.py", line 7, in fact
    assert ans > 0
AssertionError

assert False can also mark a line that’s assumed to be unreachable — e.g. after an exhaustive if/else that’s supposed to cover every case:

def maximum(x: int, y: int) -> int:
    if x > y:
        return x
    else:
        return y

    assert False   # (supposed to be) unreachable

Practice exercises

The following all ask: write doctests for the given signature, then implement it.

def indices(cs: str, subcs: str) -> list[int]:
    """ Return the indices in cs at which non-overlapping copies of
    subcs start. subcs is non-empty.
    >>> indices("A Coool pool look", "oo")
    [3, 9, 14]
    """

def insert_after(xs: list[int], a: int, b: int) -> list[int]:
    """ Insert <a> after each occurrence of <b> in list <xs>. """

def increment_count(hash: dict[str, int], key: str) -> None:
    """ Increment the value associated with key in hash in-place.
    If key is not a key in hash, add key with value 1.
    """
    if key in hash:
        hash[key] += 1
    else:
        hash[key] = 1
    return None

def average_grade(grades: list[list[object]]) -> float:
    """ Return the average grade for all the students in grades,
    where the inner lists contain a student ID and a grade.
    >>> grades = [['998765', 70], ['111234', 90], ['444567', 83]]
    >>> average_grade(grades)
    81.0
    """

def choose_chars(xs: str, ys: str, mask: str) -> str:
    """ Return a string where index i is xs[i] if mask[i] is '0'
    and ys[i] if mask[i] is '1'.
    Precondition:
        1. xs, ys, and mask are all of the same length.
        2. mask consists only of characters '0' and '1'.
    """

No worked solutions are given in the source for indices, insert_after, average_grade, or choose_chars — left as open exercises rather than invented here. increment_count’s implementation is given in the source; only its doctests are left as the open exercise.

Summary

We can verify our docstring examples using doctest. Tests should have sufficient coverage and not be redundant. Testing cannot guarantee a function works in general — it gives confidence that it’s working, and helps prevent coding mistakes.

This concludes the module on imperative programming.

Next: exceptions and an introduction to object-oriented programming.

Week 7

Exceptions

See csse1001 for course logistics — this note covers Lecture 7A’s technical content. See python-exceptions for the full reference on try/except and raising errors.

Today’s outline

• Syntax errors vs. run-time errors (exceptions)
• Common built-in exception types
• try/except, else, finally
• Catching specific vs. all exceptions
• Exercise: robust input reading
• Raising exceptions

Syntax errors vs. exceptions

When Python parses a file, it returns a syntax error if the contents don’t correspond to valid Python code. Code that passes parsing transitions to run-time, where errors (exceptions) can occur — these differ from syntax errors because they can’t be detected until they trigger.

Run-time errors are bad because they abort execution of the program, and all intermediate work is lost (unless saved to a file).

Common run-time exceptions

Exception	Description
AssertionError	an assertion fails
IOError	file does not exist
IndexError	index out of range
KeyError	key in dict does not exist
NameError	variable does not exist
TypeError	unexpected type is given to a function
ValueError	correct type, but inappropriate value
ZeroDivisionError	division by zero attempted

>>> xs = [1, 2, 3]
>>> xs[4]
IndexError: list index out of range

>>> xs = {'a': 1}
>>> xs['b']
KeyError: 'b'

>>> "two" + 2
TypeError: can only concatenate str (not "int") to str
>>> 2 + "two"
TypeError: unsupported operand type(s) for +: 'int' and 'str'

Note that int(xs: str) -> int’s type contract means int("ten") shouldn’t raise a type error, because "ten" is indeed a string — it’s the value that’s wrong:

>>> int("ten")
ValueError: invalid literal for int() with base 10: 'ten'

Try/except

try:
    <code>   # this code may throw an error
except ExceptionName:
    <code>   # this code is run when the error is of kind ExceptionName

(Also called try-catch in other languages, e.g. C++.) Typically used in user-facing layers of software and/or when accessing/interacting with external resources (files, databases, API calls, network calls, etc).

>>> x = 0
>>> 1/x               # without try-except
ZeroDivisionError: division by zero

>>> x = 0
>>> try:
...     1/x
... except ZeroDivisionError:
...     print("Please don't divide by zero...")
Please don't divide by zero

It doesn’t halt execution.

Catching specific vs. all exceptions

We can catch any exception without specifying the error type, but this can lead to undiscovered issues — it’s bad practice to ignore all errors, so it’s better to catch specific error types:

>>> x = 0
>>> try:
...     print(y)
...     1/x
... except:
...     print("You did something fishy...")

We can also catch among a list of exceptions:

>>> try:
...     print(y)     # this throws a name error
...     1/x
... except NameError:
...     print("You're using an undefined name...")
... except ZeroDivisionError:
...     print("You divided by zero...")

Exercise: robust input reading

Write a function def io_double() -> int: which takes no inputs, but prompts the user for a number and doubles it.

A first attempt:

>>> def io_double() -> int:
...     str_x = input("Number please: ")
...     int_x = int(str_x)
...     return 2*int_x

>>> io_double()
Number please: 2
4
>>> io_double()
Number please: two
...
ValueError: invalid literal for int() with base 10: 'two'

Wrapping the casting in a try/except inside a while True: loop lets the user retry until they succeed:

>>> def io_double() -> int:
...     while True:
...         str_x = input("Number please: ")
...         try:
...             int_x = int(str_x)
...             return 2*int_x   # unreachable if the line above errors
...         except ValueError:
...             print("That wasn't a number! Try again...")

>>> io_double()
Number please: two
That wasn't a number! Try again...
Number please: 3
6

General try/except framework

try:
    <code>
except ExceptionName_0:
    <code>
except ExceptionName_1:
    <code>
    ...
except ExceptionName_k:
    <code>

Python requires that specific exceptions appear before general ones:

try:
    <code>
except ZeroDivisionError:
    <code>
except:
    <code>

else and finally

try:
    <code>       # run the code under try
except:
    <code>       # execute the code under except, when there is an exception
else:
    <code>       # no exceptions? run the code under else, after try
finally:
    <code>       # always run this code

try:
    x = int(input("Type a number: "))
    y = 1/x
    # note that if an exception is raised on a line of code here,
    # the following lines don't execute -- keep try blocks as short
    # as possible (don't put everything here!)
except ZeroDivisionError:
    print("Cannot enter zero")
except ValueError:
    print("Must type in a number")
else:
    print(y)
finally:
    print("this block gets always executed")

Raising

To raise an error (rather than catch it):

>>> def safe_div(x: int, y: int) -> float:
...     """ Return 1 / (x-y). """
...     if x == y:
...         raise ZeroDivisionError   # halt execution as soon as zero division
...     return 1/(x-y)

>>> safe_div(1, 1)
ZeroDivisionError

def get_applicant_age() -> int:
    age = int(input("Enter your age: "))
    if age < 15:
        raise ValueError(f"Age must be >= 15 to apply for a license -- currently it's {age}")
    else:
        return age

try:
    get_applicant_age()
except ValueError:
    print("do something - don't issue license, etc")

Two exception-handling philosophies

LBYL (Look Before You Leap):

if b == 0:
    result = None
    print("zero division!")
else:
    result = a/b

EAFP (Easier to Ask for Forgiveness than Permission):

try:
    result = a/b
except ZeroDivisionError:
    result = None
    print("zero division!")

Summary

We can catch errors that are thrown at run-time with the try/except control structure. We should only use a try/except when absolutely necessary.

Next: 2025-09-09-scope (Lecture 7B).

Introduction to Object-Oriented Programming

See csse1001 for course logistics — this note covers Lecture 7C’s technical content. See python-classes-and-objects for the full reference on classes, instantiation, and encapsulation.

Today’s outline

• Programming paradigms: imperative vs. declarative
• Objects, classes, and self
• Instantiation, attributes, equality, and aliasing
• Methods
• Private variables, getters, and setters

Programming paradigms

Imperative programming — the programmer says how to do something, by:

1. Procedural — grouping instructions into functions.
2. Object-oriented — grouping instructions into objects that combine data (state, attributes) and behaviour (methods).

(Imperative, the adjective, means giving an authoritative command.)

Declarative programming — the programmer says what they want, through:

1. Functional — a series of function applications.
2. Logic — a question about a system of facts and rules.
3. Mathematical — optimization.

Object-oriented programming

The fundamental building block of object-oriented programming is the class (or object). The design principle is to solve a problem by creating objects that interact with one another.

An object is a collection of fields/attributes (data comprising the object’s state) along with methods (class-scoped functions) that can act on the object itself. An object can reference and change its own state, and has a notion of self.

Real-world analogues:

Class	Attributes	Methods
Dog	breed, size, age, colour	eat(), bark(), sleep(), fetch()
Student	name, age, grades, major	take_exam(), enroll(), attend_class()
Smartphone	brand, battery_level, is_on, storage	turn_on(), turn_off(), make_call(), install_app()

Convention: class names in Python are in CamelCaps — ClassNamesAreLikeThis.

I: Structure (holding named attributes)

class Point():
    def __init__(self):
        self.x = 0
        self.y = 0

>>> p = Point()          # 'instantiation' of the Point object
>>> p
<__main__.Point object at 0x10a9e0dd8>
>>> type(p)
<class '__main__.Point'>
>>> p.x
0
>>> p.y
0

Attributes of an instance are accessed with . — these are called instance variables.

What is self?

Think of the class definition as a blueprint with placeholders. self has an x, self has a y, and so on — these are the placeholders. When you create an instance of the class (e.g. p), self becomes the actual object you’re working with, and each placeholder becomes a real attribute stored in that object. You can create many instances from the same blueprint, each with its own unique values.

>>> p = Point()
>>> p.x = 2
>>> p.y = 3
>>> p.x
2
>>> p.y
3

Initializing with input

class Point():
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

>>> p = Point(2, 3)   # creates a Point and passes 2, 3 to __init__
>>> p.x
2
>>> p.y
3

Careful! Don’t pass an argument for self — Python supplies it automatically.

Equality

>>> p = Point(2, 3)
>>> q = Point(2, 3)
>>> p == q
False

Two separately-constructed objects with identical attribute values are not == by default — equality (as opposed to identity) needs to be defined explicitly (covered in a later lecture on magic methods).

Aliasing

>>> p = Point(2, 3)
>>> q = p            # q is an alias for the same object as p
>>> q.x = 1
>>> p.x
1
>>> p == q
True

Because q and p are aliases pointing to the same object, mutating q also changes what p sees, and (since it’s literally the same object) p == q is True here.

II: Methods (object-scoped functions)

class Person():
    def __init__(self, name: str) -> None:
        self.name = name

    def foo(self) -> str:            # methods must take self as the first argument
        return f"My name is {self.name}."

>>> p = Person("Slim Shady")
>>> p.foo()
'My name is Slim Shady.'

>>> foo()
NameError: name 'foo' is not defined

A method must be accessed via the object using dot notation: <object_variable>.<method>(<parameters>).

>>> p = Person("What")
>>> q = Person("Who")
>>> r = Person(f"{2*'chka'} Slim Shady")
>>> p.foo()
'My name is What.'
>>> q.foo()
'My name is Who.'
>>> r.foo()
'My name is chka chka Slim Shady.'

Each instance keeps its own independent state.

Exercise: a Counter object

Often our objects will be analogous to things that exist in the real world. Create an object called Counter that simulates the functionality of a hand-tally counter.

class Counter():
    def __init__(self) -> None:
        self._value = 0            # a 'private' variable

    def get_value(self) -> int:    # a 'getter'
        return self._value

    def click(self) -> None:
        self._value = self._value + 1

    def reset(self) -> None:
        self._value = 0

>>> x = Counter()
>>> x.get_value()
0
>>> x.click()
>>> x.click()
>>> x.click()
>>> x.get_value()
3
>>> x.reset()
>>> x.get_value()
0

Separate instances track their own count independently:

>>> x = Counter()
>>> y = Counter()
>>> x.click()
>>> y.click()
>>> x.click()
>>> x.get_value()
2
>>> x.click()
>>> y.get_value()
1

Private variables

The leading underscore on _value in Counter signals that this name is private — programmers should never manipulate it directly from outside the object.

Warning: nothing actually prevents a user from accessing a private variable in Python:

>>> x = Counter()
>>> x.click()
>>> x._value = -10
>>> x.click()
>>> x.get_value()
-9

Accessing private variables directly is bad practice.

Setters

It’s good practice to use a method — a setter — for changing an object’s private variables at the user level, so that invalid values can be rejected:

class Counter():
    def __init__(self) -> None:
        self._value = 0

    def set_value(self, x: int) -> None:   # a 'setter'
        if x < 0:
            raise ValueError
        self._value = x

Classic getters and setters

class Person():
    def __init__(self, name):
        self._name = name   # leading underscore = "internal use"

    def get_name(self):
        return self._name

    def set_name(self, value):
        if not value:
            raise ValueError("Name cannot be empty")
        self._name = value

p = Person("Alice")
print(p.get_name())
p.set_name("Sara")
print(p.get_name())

Pythonic getters and setters

Python’s @property decorator lets a getter/setter pair be used with plain attribute-access syntax, rather than explicit get_/set_ method calls:

class Person():
    def __init__(self, name):
        self._name = name

    @property
    def name(self):             # getter
        return self._name

    @name.setter
    def name(self, value):      # setter
        if not value:
            raise ValueError("Name cannot be empty")
        self._name = value

p = Person("Alice")
print(p.name)         # looks like attribute access (calls the getter)
p.name = "Sara"        # looks like assignment (calls the setter)
print(p.name)

Summary

OOP helps organise code using classes and objects.

• Class: a blueprint for creating objects.
• Object: an instance of a class.
• Encapsulation: keep data safe inside classes using attributes and methods.

Next: magic methods.

Scope

See csse1001 for course logistics — this note covers Lecture 7B’s technical content. See python-scope for the full reference on global/local scope and the LEGB rule.

Today’s outline

• Definition of scope
• Global variables and constants
• Local variables and shadowing
• The global keyword
• The LEGB name-resolution rule

Definition: scope

The scope of a variable is the region of the code where the variable’s name is recognized (i.e. the variable is accessible/visible).

>>> x = 2
>>> y = 3
>>> def foo():
...     return x
>>> def bar():
...     return foo()*y
>>> foo()
2
>>> bar()
6

(x and y are global variables, available to all functions.)

Global variables

A global variable (or simply “global”) is defined outside of any function (at the module level) and can be accessed by all functions in the module. Anything declared outside a function is globally accessible provided there is no local variable with the same name. A variable declared globally is said to have global scope.

Avoid global variables if possible — they can make code difficult to maintain.

Constants

By convention, constants are defined in SNAKE_CASE_CAPS:

PI = 3.14159
NUMBER_OF_DAYS_IN_WEEK = 7
GRID_SIZE = 5

Warning: unlike in other languages, the value of a “constant” is not protected and can be changed at run-time:

>>> PI = 3.14159
>>> PI = 3
>>> PI
3

Local variables shadow globals

>>> x = 2
>>> def foo():
...     x = 7   # local variable
...     return
>>> foo()
>>> x
2

Despite having the same name, the x inside foo() is assumed local — its scope is foo(). Assigning to x inside the function creates a brand-new local variable rather than touching the global one.

The global keyword

We can specify that a function should use a name as a global (rather than create a local shadow). It’s good practice to declare your globals when you use one:

>>> x = 2
>>> def foo():
...     global x
...     x = 7
...     return
>>> foo()
>>> x
7

If a function only ever creates a local variable (no global declaration), that name doesn’t exist outside the function:

>>> def foo():
...     x = 2
...     return x
>>> foo()
2
>>> x
NameError: name 'x' is not defined

A common gotcha: UnboundLocalError

>>> x = 2
>>> def foo():
...     x = x + 2    # local x, referenced before assignment
...     return
>>> foo()
UnboundLocalError: local variable 'x' referenced before assignment

As soon as foo assigns to x anywhere in its body, Python treats x as local throughout the whole function — so the right-hand side x + 2 tries to read a local x that doesn’t have a value yet. Declaring global x first fixes this, since x then refers to the module-level variable throughout:

>>> x = 2
>>> def foo():
...     global x
...     x = x + 2
...     return
>>> foo()
>>> x
4
>>> foo()
>>> x
6

Shadowing

>>> x = 5
>>> def foo(x):
...     return x
>>> foo(7)
7
>>> x
5

Despite having the same name, there are two x’s: one with global scope, and another local to foo (its parameter). The parameter shadows the global variable, making it temporarily invisible inside foo.

A function can’t declare a name as both a parameter and global at the same time:

>>> x = 5
>>> def foo(x):
...     global x
...     return
SyntaxError: name 'x' is parameter and global

Mixing globals and locals

>>> x = 5
>>> def foo(y):
...     return x*y
>>> foo(7)
35
>>> foo(x)
25

Globals and locals can be freely used together in the same expression.

Python’s LEGB rule for resolving names

When Python looks up a name, it searches (in order):

1. Local — the current function.
2. Enclosing — outer function(s), for nested functions.
3. Global — top-level script/module global variables.
4. Built-in — Python’s built-in names.

If the name isn’t found at any level, Python raises an error.

Exercise: an invocation counter

Write a function foo that returns the number of times it has been called:

>>> foo()
1
>>> foo()
2
>>> foo()
3

count = 0
def foo():
    """ prints the number of times foo() has been called """
    global count
    count += 1
    print(count)

The task asks for a function that returns the count, but the source’s implementation only prints it (returning None implicitly) — this happens to produce identical output in the REPL shown above, since a None return isn’t echoed, but the two aren’t the same thing. Reproduced here exactly as given, with the discrepancy flagged rather than silently “fixed” into a return count.

Summary

The places in your program that can access a name is called the scope of that name. The global scope is for things like constants, whereas names declared in functions get locally scoped to that function.

Next: 2025-09-09-object-oriented-programming (Lecture 7C).

Week 8

Dunder (Magic) Methods

See csse1001 for course logistics — this note covers Lecture 8A’s technical content. See python-dunder-methods for the full reference on __init__, __str__, __repr__, and operator overloading.

Today’s outline

• Recap: class vs. object
• Underscores: anonymous variables, private variables, and dunder names
• Magic methods: __init__, __str__, __repr__, __eq__, __add__, __sub__
• Overloadable operator tables (binary, unary, comparison)
• Instance variables vs. class variables

Class vs. object

Aspect	Class	Object
Meaning	Blueprint/template for creating objects	Instance of a class with real data
Represents	General concept or idea	Concrete entity based on a class
Defined by	class keyword	Instantiating a class
Example	class Animal:	my_animal = Animal()
Memory usage	No direct memory for data	Allocates memory for attributes
Purpose	Describes structure and behaviour	Performs actions and stores data
Analogy	House blueprint	Actual built house

Underscores

Python overloads the underscore with several distinct meanings (not an exhaustive list):

1. As anonymous variables, e.g. for _ in [1, 2, 3]: or x, _, z = (1, 2, 3).
2. For giving special meaning to functions and names:
   • _private variables — a leading single underscore (convention only).
   • __names__ — reserved for Python’s magic/dunder methods, like __init__().

III: Magic (overloading built-in functions)

We can create a new type, Fraction, with:

• Data attributes: numerator, denominator.
• Methods: arithmetic operations (add, eq, sub) to work with +, ==, -; and a print-friendly representation.

Initialiser

Runs when the object is instantiated (created):

class Fraction():
    def __init__(self, numer: int, denom: int) -> None:
        self._numer = numer
        self._denom = denom

String representation (__str__)

Says what to display when printing the object:

>>> p = Fraction(2, 3)
>>> print(p)
<__main__.Fraction object at 0x7f95c625e9d0>

Without a __str__, printing an object just shows its default memory-address representation. Defining one fixes this:

>>> class Fraction():
...     def __str__(self) -> str:
...         return f"A fraction: {self._numer} / {self._denom}"   # must return a string
>>> p = Fraction(2, 3)
>>> print(p)
A fraction: 2 / 3

Representation (__repr__)

The representation of an object is what Python displays for it in the console, and should be enough information to re-instantiate the object:

>>> class Fraction():
...     def __repr__(self) -> str:
...         return f"{self._numer} / {self._denom}"
>>> p = Fraction(2, 3)
>>> p
2 / 3

This is equivalent to calling print(repr(p)) or directly invoking print(p.__repr__()) — but we don’t manually invoke these methods; Python does.

__repr__ vs. __str__

• __repr__ is meant to be used by the programmer:

  • Unambiguous — it should clearly describe the object.

  • Meant for debugging, logging, and development, not end-users.

  • Its output should, if possible, be a valid Python expression that could recreate the object when passed to eval():

    >>> u
    Vector2D(x=2, y=3)
    >>> print(u)
    2D Vector: (2, 3) --- length: 3.605551275463989
    >>> u_copy = eval(repr(u))
    >>> u_copy
    Vector2D(x=2, y=3)

• __str__ is meant for pretty prints (a user-friendly string, printed for the user).

Equality (__eq__)

We can specify that objects are equal for reasons other than sharing a memory location:

>>> class Fraction():
...     def __eq__(self, other) -> bool:   # note the use of 'other'
...         a, b = self._numer, self._denom
...         c, d = other._numer, other._denom
...         return a*d == b*c
>>> p = Fraction(4, 6)
>>> q = Fraction(2, 3)
>>> p == q
True

Addition (__add__)

Instructs Python on how to add two objects together:

>>> from __future__ import annotations   # for the class' own type hint
>>> class Fraction():
...     def __add__(self, other) -> Fraction:
...         a, b = self._numer, self._denom
...         c, d = other._numer, other._denom
...         return Fraction(a*d + c*b, b*d)
>>> p = Fraction(2, 3)
>>> q = Fraction(1, 2)
>>> p + q
7 / 6

Subtraction (__neg__, __sub__)

>>> from __future__ import annotations
>>> class Fraction():
...     def __neg__(self) -> Fraction:
...         return Fraction(-self._numer, self._denom)
...     def __sub__(self, other) -> Fraction:
...         return self + -other
>>> p = Fraction(2, 3)
>>> q = Fraction(1, 2)
>>> p - q
1 / 6

Overloadable operators

Binary operator	Magic method
+	__add__
-	__sub__
*	__mul__
**	__pow__
//	__floordiv__
/	__truediv__

Unary operator	Magic method
-	__neg__
abs	__abs__
~	__invert__

Comparison	Magic method
<	__lt__
<=	__le__
==	__eq__
!=	__ne__
>	__gt__
>=	__ge__

Instance vs. class variables

Recall the class we wrote for counting clicks:

class Clicker():
    def __init__(self) -> None:
        self._clicks = 0   # each instance has its own

    def click(self) -> None:
        self._clicks += 1

Can we calculate the number of clicks across all counters? We can use a class variable:

class Clicker():
    _all_clicks = 0   # every instance has access to this

    def __init__(self) -> None:
        self._clicks = 0

    def click(self) -> None:
        self._clicks += 1        # access instance variable
        Clicker._all_clicks += 1  # access class variable

>>> c = Clicker(); d = Clicker(); e = Clicker()   # semi-colons can be used instead of newlines
>>> c.click(); c.click(); c.click();
>>> d.click(); d.click();
>>> e.click()

>>> (c._clicks, d._clicks, e._clicks)   # bad practice (accessing privates directly)
(3, 2, 1)

>>> (c._all_clicks, d._all_clicks, e._all_clicks)
(6, 6, 6)

>>> Clicker._all_clicks   # you don't even need an instance
6

The exercise on the previous slide asked for a class called Clicker, but the companion Clicker.py file actually defines a class called Counter instead (matching the earlier Lecture 7C Counter exercise, plus extra set_count/print_counter methods) — the naming doesn’t match the exercise prompt. The file’s final two lines, d = Counter("second counter"), also don’t work: Counter.__init__ only takes self, so passing an extra argument raises TypeError: Counter.__init__() takes 1 positional argument but 2 were given. This looks like leftover exploratory code rather than a demonstrated feature.

Summary

Classes (or objects) are like functions that maintain their state even after returning. Classes have attributes and methods, and provide a public interface — through setters and getters — for manipulating values considered private to the object.

Exercises

Task (Vectors). Notice that + concatenates lists:

>>> [1, 2, 3] + [4, 5, 6]
[1, 2, 3, 4, 5, 6]

Implement a Vector class so that we can do:

>>> x = Vector(1, 2)
>>> y = Vector(3, 4)
>>> x + y
<4, 6>
>>> -x
<-1, -2>

Starter code (unsolved in the source):

class Vector():
    def __init__(self, x: int, y: int):
        self._x, self._y = x, y

    def __add__(self, other):
        ...

    def __neg__(self):
        ...

    def __repr__(self):
        ...

Extension: try creating a Vector class that handles an arbitrary dimension. If two vectors of different sizes are added, __add__ should raise a ValueError.

The companion magic.py file contains a separate, fully-worked Vector2D class (2D-only, not the arbitrary-dimension extension) with __init__, length(), __repr__, __str__, __eq__, __add__, and __len__ — useful as a worked reference for this style of task, even though it doesn’t solve the exercise as stated (it’s fixed at two dimensions and doesn’t raise on mismatched sizes). See python-dunder-methods for the full listing.

Task (Currency). Create a class for working with the currencies AUD, EUR, and JPY. Implement the __repr__, __gt__, and __add__ magic methods — you’ll need the dollar/euro/yen symbols, and to do currency conversions when adding different currencies together. Use: 1 AUD is 0.62 EUR; 1 AUD is 79.7 JPY.

Starter code (unsolved in the source):

class Currency():
    def __init__(self, value: float, currency: str) -> None:
        """ <currency> is one of 'AUD', 'EUR', 'JPY'. """
        self.value = value
        self.currency = currency

    def __repr__(self) -> str:
        ...

    def __add__(self, other) -> object:
        ...

    def __gt__(self, other) -> bool:
        ...

Task (Greeter). A fully worked example, using a class variable as a shared lookup table:

class Greeter():
    _lang_to_hello = {
        "FR": "Bonjour",
        "AU": "G'Day",
        "DE": "Hallo",
        "CN": "Ni Hao"
    }

    def __init__(self, country: str) -> None:
        self._country = country

    def greet(self) -> str:
        return Greeter._lang_to_hello[self._country]

>>> a = Greeter("FR"); b = Greeter("AU")
>>> c = Greeter("DE"); d = Greeter("CN")
>>> a.greet()
'Bonjour'
>>> b.greet()
"G'Day"
>>> c.greet()
'Hallo'
>>> d.greet()
'Ni Hao'

Next: 2025-09-16-representation-invariants (Lecture 8B).

Representation Invariants

See csse1001 for course logistics — this note covers Lecture 8B’s technical content. See python-representation-invariants for the full reference on writing and enforcing invariants.

Today’s outline

• What representation invariants are, and why they matter
• Documenting invariants in docstrings
• Enforcing invariants with assert and a _check_invariants() helper
• Encapsulation and avoiding exposed mutable state
• Worked example: DroneFlight

What are representation invariants?

Representation invariants are conditions or properties that must remain true about the internal state of an object throughout its lifetime (usually enforced during development).

Why do they matter?

• Discover and prevent bugs and inconsistent behaviour.
• Simplify the implementation of methods (you can assume a valid starting state).
• Make code more maintainable and robust.
• Help detect errors early.
• Serve as documentation for developers.

Examples

• A stack’s size must never be negative.
• A list’s length must equal the number of elements it contains.
• All elements in a set must be unique.
• A fraction’s denominator cannot be zero.
• A date must follow calendar rules (e.g. no 30 Feb).
• For free/basic X (Twitter) accounts, the standard limit is 280 characters per tweet.

Writing representation invariants

Clearly state invariants in docstrings, underneath a class’s attributes:

class Fraction():
    """Represents a mathematical fraction.

    Representation Invariants:
    - denominator != 0
    - if fraction is zero, it is represented as 0/1
    - if fraction is negative, numerator is negative
    """

Enforcing representation invariants

Assertions

Directly check conditions in the initialiser and setter methods, using an assert statement to raise an AssertionError if an assumption isn’t met:

assert <statement that should be true>, "Error message if not True"

• Assertions can be disabled in production when running Python with optimization (python -O).
• Assertions are meant to find bugs (e.g. invalid states) during development.

class Fraction():
    def __init__(self, numer: int, denom: int) -> None:
        assert denom != 0, "Denominator cannot be zero."
        assert isinstance(numer, int), "Numerator must be an integer."
        assert isinstance(denom, int), "Denominator must be an integer."

        # Ensure denominator is positive
        if denom < 0:
            numer, denom = -numer, -denom
        self._numer = numer
        self._denom = denom

        # Special case for zero
        if self._numer == 0:
            assert self._denom == 1, "Zero must be 0/1"

Private attributes and encapsulation

• Use private (_variable) names to discourage direct access.
• Provide public methods that maintain the invariants.
• Never expose mutable objects directly:

class Team():
    def __init__(self):
        self._members = []   # internal mutable state

    # classic getter (dangerous!)
    # BAD!
    def get_members(self):
        return self._members

    # instead, return a copy
    # GOOD!
    # def get_members(self):
    #     return list(self._members)  # caller can't modify internal state directly

t = Team()
members = t.get_members()   # gets the actual list inside the class
members.append("Alice")      # modifies it directly!

print(t.get_members())        # ['Alice'] <-- internal state was changed externally

Helper methods

Define a private method (e.g. _check_invariants()) that validates the object’s state, and call it after any state changes:

\[\text{state change} \to \texttt{\_check\_invariants()} \to \text{valid}\]

When to call _check_invariants():

• At the end of __init__.
• At the end of methods that modify object state.
• At the beginning of methods that rely on invariants being true.

class Fraction():
    def __init__(self, numer: int, denom: int) -> None:
        self._numer = numer
        self._denom = denom
        self._check_invariants()

    def _check_invariants(self) -> None:
        """Verify that representation invariants hold."""
        assert isinstance(self._numer, int), "Numerator must be an integer."
        assert isinstance(self._denom, int), "Denominator must be an integer."
        assert self._denom != 0, "Denominator cannot be zero."
        assert self._denom > 0, "Denominator must be positive."
        if self._numer == 0:
            assert self._denom == 1, "Zero must be 0/1"

Best practices

• Document invariants in docstrings.
• Centralise invariant checking in a single method.
• Do not expose methods that could violate invariants.
• Create comprehensive test cases focusing on edge cases.
• Python’s type hints can express some invariants.
• Balance strictness with practicality.

Exercise: DroneFlight

You have joined a start-up that records quick test flights for hobby drones. Write a minimal DroneFlight class that always keeps its state valid by enforcing these representation invariants:

• Drone ID — exactly six alphanumeric characters (e.g. "A1B2C3").
• Altitude — must stay within 0 m–120 m, the CASA (Civil Aviation Safety Authority) legal ceiling for recreational drones.
• Battery — an integer percentage in the range 0–100.

Solution

class DroneFlight:
    """
    Model a quick test-flight for a small hobby drone.

    Attributes:
    _id (str) : 6-character alphanumeric flight identifier.
    _altitude (float): Current altitude in metres above launch point.
    _battery (int): Remaining battery charge as a percentage (0-100).

    Representation invariants:
    - _id is a 6-character alphanumeric string
    - 0 <= _altitude <= 120
    - 0 <= _battery <= 100
    """

    _ID_LEN = 6         # one place to change if the rule changes
    _MAX_ALT = 120.0    # metres (CASA limit)

    def __init__(self, flight_id: str) -> None:
        self._id = flight_id
        self._altitude = 0.0
        self._battery = 100
        self._check_invariants()

    def _check_invariants(self) -> None:
        assert (
            isinstance(self._id, str)
            and self._id.isalnum()
            and len(self._id) == self._ID_LEN
        ), "ID must be a 6-character alphanumeric string."
        assert 0.0 <= self._altitude <= self._MAX_ALT, "Altitude out of range."
        assert 0 <= self._battery <= 100, "Battery out of range."

    # Getter and setter methods
    def get_flight_id(self) -> str:
        """Return the immutable flight identifier."""
        return self._id

    def get_altitude(self) -> float:
        """Return current altitude in metres."""
        return self._altitude

    def get_battery(self) -> int:
        """Return remaining battery charge (percentage)."""
        return self._battery

    def set_altitude(self, value: float) -> None:
        """Set altitude, clamping to legal ceiling."""
        if not isinstance(value, (int, float)):
            raise TypeError("Altitude must be a number.")
        if not 0.0 <= value <= self._MAX_ALT:
            raise ValueError(f"Altitude must be 0-{self._MAX_ALT} m.")
        self._altitude = float(value)
        self._check_invariants()

    def __repr__(self) -> str:
        return (f"DroneFlight({self._id}, "
                f"alt={self._altitude:.1f} m, bat={self._battery} %)")

    def ascend(self, metres: float) -> None:
        """Climb *metres* metres (cannot exceed the legal ceiling)."""
        if metres < 0:
            raise ValueError("ascend() expects a non-negative distance.")
        self.set_altitude(min(self._altitude + metres, self._MAX_ALT))

    def land(self) -> None:
        """Land the drone and consume 5 % battery."""
        self.set_altitude(0.0)
        self._battery = max(self._battery - 5, 0)
        self._check_invariants()

>>> d = DroneFlight("ABC123")
>>> d.ascend(50)
>>> print(d)
DroneFlight(ABC123, alt=50.0 m, bat=100 %)

>>> d.altitude = 200
Caught: Altitude must be 0-120 m.

>>> DroneFlight("BAD!")
Caught: ID must be a 6-character alphanumeric string.

>>> d.land()
DroneFlight(ABC123, alt=0.0 m, bat=95 %)

The d.altitude = 200 line is presented as raising a “Caught” error, but as written this class only defines set_altitude() as an ordinary method — it has no @property/@altitude.setter. Plain attribute assignment like d.altitude = 200 doesn’t call set_altitude() at all; it silently creates a brand-new, unrelated altitude attribute (alongside the real _altitude) and raises nothing. To actually trigger the validation shown, the demo would need d.set_altitude(200) wrapped in a try/except (TypeError, ValueError) as e: print("Caught:", e). The companion drone.py script does contain the bare d.altitude = 200 line with no such wrapper, confirming it wouldn’t actually raise in practice. The second demo line (constructing DroneFlight("BAD!")) is legitimate, though — __init__ really does call _check_invariants(), so an invalid ID genuinely raises an AssertionError there (assuming it’s likewise wrapped in a try/except AssertionError).

Summary

• Representation invariants define the valid states of an object.
• They help catch bugs early and document assumptions (mostly during development time).
• We can use _check_invariants() to verify invariants, and call it after state changes.
• Good invariants are specific, testable conditions.

Next: composition and inheritance (Week 9).

Week 9

Composition

See csse1001 for course logistics — this note covers Lecture 9A’s technical content. See python-composition for the full reference on has-a relationships.

Today’s outline

• The DRY principle, and two ways to reuse classes: composition and inheritance
• Composition (“has-a” relationships)
• Worked example: DroneFlight composed of Battery, Camera, and Motor
• Hot-swapping composed objects

Recap

A quick recap table of last lecture’s dunder methods:

Category	Key methods	What they enable
Lifecycle	__init__	Control object initialisation
String rep	__repr__, __str__	Unambiguous & user-friendly text
Numeric ops	__add__, __sub__, __mul__, …	Custom arithmetic (1/2 + 1/3, v1 * v2)
Comparisons	__eq__, __lt__, __gt__, …	Sorting, ==, <

And representation invariants:

What?	Why?	How?
Conditions that must hold for an object’s private state at all times (e.g. \(0 \leq \text{altitude} \leq 120\), ID is 6 digits).	Prevents invalid states; simplifies reasoning & testing (assume invariants true); catches bugs early with clear, localised checks.	Set valid values in __init__; centralise assertions in a private helper like _check_invariants().

How to reuse code?

DRY (don’t repeat yourself) principle: in general, duplication and copy/paste are bad —

• Increased risk of bugs.
• Maintenance overhead.
• Poor readability.
• Code bloat.
• Signals that a common abstraction/refactoring is needed.

Today: how to reuse classes in a new class? Via composition or inheritance.

Composition

We can use objects built from other classes (implemented by us or others) as attributes of our new class/object. This isn’t new — we’ve already used integers, strings, lists, etc. as attributes for our classes; we can do this with other (more complex) classes as well. For example, if we are implementing a Robot class, we can use an object from a Battery class (already implemented by us or others) as one of its attributes.

Modularity:

• A Student has a String (e.g. to store the student’s name).
• A Robot has a Sensor, Motor, etc.

Has-a relationship

When an object (say Car) includes another object inside itself as an attribute (say Engine), this forms a has-a relationship — we call this class composition:

>>> class Car():
...     def __init__(self, engine: Engine) -> None:
...         self._engine = engine   # Car has-a engine

engine = Engine()
car = Car(engine)
car.engine.start()
car.engine.stop()
print(car.engine.power)

Which is clearer: “is-a” or “has-a”?

Recall the DroneFlight representation-invariants exercise from last lecture (Drone ID, altitude, battery). Which one sounds clearer: “A Drone is a Camera” or “A Drone has a Camera”? A drone “has a” camera, “has a” motor, and “has a” battery — composition is the natural fit here, not inheritance.

Worked example: DroneFlight

class Battery:
    def __init__(self, capacity: int = 100) -> None:
        if capacity < 0:
            raise ValueError("Capacity must be non-negative.")
        self._level = capacity   # percentage

    def use_power(self, amount: int) -> None:
        if amount < 0:
            raise ValueError("Power usage must be non-negative.")
        self._level -= amount
        if self._level < 0:
            self._level = 0
        print(f"Power used: {amount}%. Remaining: {self._level}%.")

    def get_level(self) -> int:
        """Return remaining battery charge (percentage)."""
        return self._level


class Camera:
    def __init__(self, resolution: str = "12MP") -> None:
        self._resolution = resolution

    def take_photo(self) -> None:
        print(f"Photo taken at {self._resolution} resolution.")


class Motor:
    def __init__(self, power_rating: float = 100.0) -> None:
        self._power_rating = power_rating   # Watts
        self._is_running = False

    def start(self) -> None:
        self._is_running = True
        print("Motor started.")

    def stop(self) -> None:
        self._is_running = False
        print("Motor stopped.")

class DroneFlight:
    _ID_LEN = 6
    _MAX_ALT = 120.0   # metres (CASA limit)

    def __init__(self, flight_id: str, battery: Battery,
                 camera: Camera, motor: Motor) -> None:
        self._id = flight_id
        self._altitude = 0.0
        self._battery = battery   # Drone has-a Battery
        self._camera = camera     # Drone has-a Camera
        self._motor = motor       # Drone has-a Motor
        self._check_invariants()

    def get_flight_id(self) -> str:
        """Return the immutable flight identifier."""
        return self._id

    def get_altitude(self) -> float:
        """Return current altitude in metres."""
        return self._altitude

    def get_battery(self) -> int:
        """Return remaining battery charge (percentage)."""
        return self._battery.get_level()   # don't call use_power(0) here! just show the level

    def __str__(self) -> str:
        return (f"DroneFlight({self._id}, alt={self._altitude:.1f} m, "
                f"bat={self.get_battery()}%)")

    def ascend(self, metres: float) -> None:
        """Climb *metres* metres (cannot exceed the legal ceiling)."""
        if metres < 0:
            raise ValueError("ascend() expects a positive distance.")
        self.set_altitude(min(self._altitude + metres, self._MAX_ALT))
        self._check_invariants()

    def land(self) -> None:
        """Land the drone and consume 5% battery."""
        self.set_altitude(0.0)
        self._battery.use_power(5)
        if self._motor.is_running():
            self._motor.stop()
        self._check_invariants()

    def take_photo(self) -> None:
        if self._battery.get_level() < 5:
            print("Not enough battery to take photo.")
            return
        self._camera.take_photo()
        self._battery.use_power(5)

>>> b = Battery(); c = Camera(); m = Motor()
>>> d = DroneFlight("SAD564", b, c, m)
>>> d.ascend(80); d.take_photo()
Photo taken at 12 MP resolution.
Power used: 5%. Remaining: 95%
>>> d.land()
Power used: 5%. Remaining: 90%
>>> print(d)
DroneFlight(SAD564, alt=0.0 m, bat=90 %)

get_battery() delegates straight to self._battery.get_level() rather than self._battery.use_power(0) — the comment on the slide (“Don’t call use_power(0) here! Just show the level.”) is a reminder that even a “zero-amount” power use would still print a spurious “Power used: 0%…” message and is conceptually the wrong operation for a getter to perform. A getter should just report state, not have side effects.

Hot-swapping

Because a composed attribute is just an object reference, it can be swapped out for another compatible object at any time:

class ThermalCamera:
    def __init__(self, resolution: str = "12MP"):
        self.resolution = resolution

    def take_photo(self):
        print("Thermal image saved.")

>>> b = Battery(); c = Camera(); m = Motor()
>>> d = DroneFlight("SAD564", b, c, m)
>>> d.take_photo()
Photo taken at 12 MP resolution.
Power used: 5%. Remaining: 95%
>>> d.camera = ThermalCamera()
>>> d.take_photo()

ThermalCamera doesn’t inherit from Camera at all — it just happens to provide a take_photo() method with a compatible signature, so it works as a drop-in replacement. This is an example of duck typing: Python doesn’t check that the new object is “officially” a Camera, only that it supports the operations actually used on it.

The companion composition.py file demonstrates a more defensive hot-swap via a dedicated swap_engine() method on its Car/Engine example, which stops the currently-running engine before swapping it out — a small improvement over directly reassigning an attribute mid-flight, since a direct reassignment (like d.camera = ThermalCamera() above) doesn’t get a chance to clean up the object it’s replacing. See python-composition for the full listing.

Summary

Build by pieces: snap self-contained objects together to create a richer whole.

• Modular: each component handles one clear task.
• Reusable: same parts work in new contexts; no code rewrite.
• Readable: data flow is explicit and easy to trace.
• Few side effects: isolated state keeps surprises and bugs low.

Next: 2025-09-23-inheritance (Lecture 9B).

Inheritance

See csse1001 for course logistics — this note covers Lecture 9B’s technical content. See python-inheritance for the full reference on subclassing, super(), and polymorphism.

Today’s outline

• Inheritance and “is-a” relationships
• Terminology: subclass/superclass, child/parent, extends
• Inheriting, introducing, and overriding methods
• super() and extending methods
• Polymorphism

Inheritance

Inheritance is another way of reusing code in classes. By inheriting from a class, we can create specialized (sub)classes while reusing attributes/methods from the original class. Key idea: building a hierarchy of classes.

        Robot
   /      |       \
DeliveryRobot  CleanerRobot  HumanoidRobot

This is an “is-a” relationship: a DeliveryRobot is a Robot. DeliveryRobot, CleanerRobot, and HumanoidRobot all specialize the base class (Robot):

• They inherit the attributes and methods of the base class.
• They can override the attributes/methods of the base class (e.g. a move() method might have different implementations).
• They can have new (unique) attributes/methods or implementations.

More examples of “is-a” hierarchies:

• Employee → Programmer, Manager, Admin
• Animal → Cat, Dog, Fox; and Dog → ServiceDog
• Person → Professor, Student; and Student → UndergradStudent, GradStudent

Terminology

Given class Student(Person): — all of the following mean the same thing, and can be used interchangeably:

• The Student class inherits from the Person class.
• The Student class is a subclass of the Person class.
• The Student class is a child class of the Person class.
• The Person class is a superclass of the Student class.
• The Person class is a parent class of the Student class.
• (less often) The Student class extends the Person class.

Reusing code via inheritance

Without inheritance, two robot classes end up duplicating __init__ and charge:

# BAD -- duplicating code, violating the DRY principle
class CleaningRobot:
    def __init__(self, name: str, batt_level: int):
        self.name = name
        self.batt_level = batt_level

    def charge(self):
        self.batt_level = 100
        print(f"{self.name} is fully charged!")

    def clean(self):
        print(f"{self.name} is cleaning the floor.")

class DeliveryRobot:
    def __init__(self, name: str, batt_level: int, load_capacity: int):
        self.name = name
        self.batt_level = batt_level
        self.load_capacity = load_capacity

    def charge(self):
        self.batt_level = 100
        print(f"{self.name} is fully charged!")

    def deliver(self):
        print(f"{self.name} is delivering a package up to {self.load_capacity}kg.")

Instead, extract the common behaviour into a base class, and inherit specialized robots from it:

class Robot:
    def __init__(self, name: str, batt_level: int):
        self.name = name
        self.batt_level = batt_level

    def charge(self):
        self.batt_level = 100
        print(f"{self.name} is fully charged!")


class CleaningRobot(Robot):
    def clean(self):
        print(f"{self.name} is cleaning the floor.")

The syntax class Child(Parent): means the child class inherits from the parent class.

>>> cleaner = CleaningRobot("Roomba", 80)   # calls Robot's (base class') __init__
>>> cleaner.charge()   # CleaningRobot inherited charge() from the base class
Roomba is fully charged!
>>> print(cleaner.name)   # CleaningRobot inherited attributes from the base class
Roomba

Introducing new methods

A child class can define methods that don’t exist on the base class at all — clean() only exists on CleaningRobot objects, not on plain Robot objects.

Overriding methods

We can override a method by simply declaring one of the same name in the child class:

class FastChargingRobot(Robot):
    def charge(self):   # overriding the charge method from the base class
        self.batt_level = 100
        print(f"{self.name} is fully charged in record time!")

Calling charge() on a FastChargingRobot object calls this overridden method, not Robot’s.

Extending methods with super()

super() specifies that we want to use the method from the superclass, rather than the child class — useful for extending (rather than fully replacing) inherited behaviour:

class DeliveryRobot(Robot):
    def __init__(self, name: str, batt_level: int, load_capacity: int):
        # super().__init__(...) calls the __init__ method from the parent (base) class
        super().__init__(name, batt_level)
        self.load_capacity = load_capacity

    def deliver(self):
        print(f"{self.name} is delivering a package up to {self.load_capacity}kg.")

>>> deliverer = DeliveryRobot("DHLBot", 80, 10)
>>> deliverer.charge()
DHLBot is fully charged!
>>> deliverer.deliver()
DHLBot is delivering a package up to 10kg.

Polymorphism

The word polymorphism means “to take on many forms”. In computer science, an interface that works over different underlying data-types is called polymorphic.

len() is polymorphic — it works across many different types:

>>> len({'a': 1, 'b': 2, 'c': 3})
3
>>> len("Drop Bear")
9
>>> len([1, 2, 3, 4])
4

Classes that share a common interface (e.g. all inheriting a charge() method) are polymorphic too — the same call produces different behaviour depending on the actual object’s class:

robots = [
    CleaningRobot("Roomba", 40),
    DeliveryRobot("DHL-Bot", 20, 15),
    FastChargingRobot("FlashBot", 5)
]

for r in robots:
    r.charge()   # different behaviors depending on r's charge() method

Exercise

Implement the SurveyDrone and DeliveryDrone classes, inheriting from DroneFlight:

>>> class DroneFlight:
...     pass   # implemented before (see [[2025-09-23-composition]])
>>> class SurveyDrone(DroneFlight):
...     pass   # implement SurveyDrone
>>> class DeliveryDrone(DroneFlight):
...     pass   # implement DeliveryDrone

Left unsolved in the source — just stubs.

Summary

We can create classes that inherit from other classes. By doing so, the subclass automatically receives all attributes and methods implemented in the superclass. The subclass can have additional methods and attributes, while overriding inherited methods and calling methods from its superclass.

Use inheritance only when there’s a clear “is-a” relationship.

Next: Unified Modelling Language (Week 10).

Week 10

Advanced Inheritance

See csse1001 for course logistics — this note covers Lecture 10B’s technical content. See python-inheritance for the full reference, now extended with abstract base classes and MRO.

Today’s outline

• A useful trick for Assignment 2: type(c).__name__
• Abstract base classes
• Method Resolution Order (MRO), and Python’s inheritance models
• The diamond problem, and C3 linearisation
• super() and MRO

A useful trick for A2: getting the class name of an object

class Car():
    pass

c = Car()
print(type(c))          # <class '__main__.Car'>
print(type(c).__name__)  # 'Car' -- e.g. can be used in __repr__

type(c).__name__ returns the class name as a plain string — handy inside a __repr__ (see python-dunder-methods) so it stays correct even if the class is renamed or subclassed.

Abstract base classes

It is common to have an abstract base class that doesn’t have concrete methods/attributes, but enforces contracts in its children classes. You’re not meant to instantiate objects from these abstract classes directly.

Example: an abstract Shape class has an area() method without a concrete implementation. Every (concrete) child class of Shape must provide a concrete implementation of area(). Abstract base classes can sometimes have concrete implementations for some of their methods too (especially if those are meant to be used as-is by child classes).

import math

# Abstract class -- defines the interfaces (child classes must implement these methods)
class Shape:
    def area(self) -> float:
        raise NotImplementedError("Subclasses must implement area()")

    def perimeter(self) -> float:
        raise NotImplementedError("Subclasses must implement perimeter()")

class Circle(Shape):
    def __init__(self, r: float):
        self.r = r
    def area(self) -> float:
        return math.pi * self.r * self.r
    def perimeter(self) -> float:
        return 2 * math.pi * self.r

class Rectangle(Shape):
    def __init__(self, w: float, h: float):
        self.w, self.h = w, h
    def area(self) -> float:
        return self.w * self.h
    def perimeter(self) -> float:
        return 2 * (self.w + self.h)


s = Shape()   # BAD -- you're not meant to create an object from this abstract base class
s.area()      # ERROR

Shape() itself doesn’t raise an error here — it’s still just a regular class. The error only happens on s.area(), which raises NotImplementedError. This is a plain-Python convention, not an enforced restriction: nothing actually stops you from instantiating Shape, only from usefully calling its unimplemented methods.

Optional: enforcing this properly with abc

Using the standard-library abc module does enforce this at instantiation time:

from abc import ABC, abstractmethod

class Shape(ABC):
    @abstractmethod
    def area(self) -> float:
        ...
    @abstractmethod
    def perimeter(self) -> float:
        ...
    # (optional) concrete helper: allowed in an abstract class
    def describe(self) -> str:
        return f"{self.__class__.__name__}"

With this version, Shape() itself raises TypeError: Can't instantiate abstract class Shape with abstract methods area, perimeter — the abstract methods are enforced immediately, rather than only failing later when called.

Advanced inheritance

If a class inherits from two parents, and both parents have a method with the same name, which one does Python use?

Method Resolution Order (MRO)

MRO stands for Method Resolution Order — it defines the order in which Python looks through classes to find a method or attribute when it’s called on an object. It determines which method gets called when there are multiple implementations, and is stored in cls.__mro__.

Python supports several inheritance models:

Single inheritance

A class inherits from a single parent class:

>>> class A(object):   # 'object' is the universal class
...     def __init__(self, x):
...         self.x = x
...     def f(self):
...         return self.x
...     def g(self):
...         return 2 * self.x
...     def fg(self):
...         return self.f() - self.g()

>>> a = A(3)
>>> a.x
3
>>> a.f()
3
>>> a.g()
6
>>> a.fg()
-3

>>> class B(A):
...     def g(self):   # override
...         return self.x ** 2

>>> b = B(7)
>>> b.x
7
>>> b.f()   # inherited from A
7
>>> b.g()   # overridden
49
>>> b.fg()  # inherited from A, but uses B's overridden g()
-42

Multilevel inheritance

A class inherits from a child class, which in turn inherits from another parent class — forming a linear parent → child → grandchild chain:

>>> class C(B):
...     def __init__(self, x, y):   # extends B's (and A's) __init__
...         super().__init__(x)
...         self.y = y
...     def fg(self):                # extends B's (and A's) fg
...         return super().fg() * self.y

>>> c = C(3, 5)
>>> c.x
3
>>> c.y
5
>>> c.f()    # inherited from B, from A
3
>>> c.g()    # inherited from B (overridden there)
9
>>> c.fg()   # extends B's fg: (3 - 9) * 5
-30

For multilevel inheritance, the MRO is simple — it just follows the chain from child to parent to grandparent, etc.

Hierarchical inheritance

Multiple child classes inherit from a single parent class:

>>> class D(A):
...     def f(self):   # override
...         return -2 * self.g()

>>> d = D(3)
>>> d.x
3
>>> d.f()   # overridden: -2 * g()
-12
>>> d.g()   # inherited from A
6
>>> d.fg()  # inherited from A, uses D's overridden f()
-18

The combined UML diagram for A, B, C, D above:

        A
      /   \
     B     D
     |
     C

Multiple inheritance

A class inherits from multiple parent classes:

>>> class E(B, D):   # inherit from B and D
...     pass

  B   D
   \ /
    E

The diamond problem

• E inherits from both B and D.
• B and D both inherit from A.
• Which version of A’s methods should E use?

      A
     / \
    B   D
     \ /
      E

Python resolves this with MRO C3 linearisation:

• Child classes are checked before parents.
• Parents are checked in the order they are listed in the class definition.
• If a class appears multiple times in the MRO, only the last occurrence is kept.

>>> E.mro()
[<class '__main__.E'>, <class '__main__.B'>,
 <class '__main__.D'>, <class '__main__.A'>,
 <class 'object'>]

>>> for cls in E.__mro__:
...     print(cls.__name__)
E
B
D
A
object

>>> e = E(3)
>>> e.x
3
>>> e.f()    # E has none; B has none of its own; D's f() is used
-18
>>> e.g()    # B's overridden g() is used (B comes before D in the MRO)
9
>>> e.fg()   # A's fg(): self.f() - self.g() = -18 - 9
-27

Even though B doesn’t define its own f(), and D doesn’t define its own g(), Python resolves each name independently by walking the MRO — e.f() finds D’s f() (since B has none of its own), while e.g() finds B’s g() (since B comes before D in the MRO).

A larger example, showing the general C3 rule (child before parents, parents in listed order, keep only the last occurrence of a repeated class):

>>> class A: pass
>>> class B: pass
>>> class C(A): pass
>>> class D(A, B): pass
>>> class E(C, D, B): pass
>>> print([cls.__name__ for cls in E.__mro__])
['E', 'C', 'D', 'A', 'B', 'object']

super() and MRO

The super() function follows the MRO, not just the immediate parent listed in the class definition:

class A:
    def ping(self):
        print("A")

class B(A):
    def ping(self):
        print("B")
        super().ping()

class C(A):
    def ping(self):
        print("C")
        super().ping()

class D(B, C):
    def ping(self):
        print("D")
        super().ping()

>>> D().ping()
D
B
C
A

D’s MRO is [D, B, C, A, object]. When B.ping() calls super().ping(), it doesn’t jump straight to A (B’s statically-declared parent) — it calls the next class in the actual runtime MRO of the instance, which is C. This is what makes cooperative multiple inheritance work: each class’s super() call advances one step through the shared MRO, regardless of what its own declared parent is.

If a class in the chain doesn’t call super() at all, the chain of calls simply stops there — the MRO itself is unaffected (it’s purely a function of the inheritance structure), but fewer ping() implementations actually get executed. For example, if B.ping() omits its super().ping() call, D().ping() only prints D and B — C and A are never reached, even though they’re still part of D’s MRO.

Summary

When a class inherits from multiple parents, it’s possible for more than one parent to define the same method or attribute. To avoid confusion and ensure consistency, Python uses a rule called Method Resolution Order (MRO) to determine the order in which classes are searched. MRO follows a well-defined path based on class hierarchy and inheritance order, ensuring that each method or attribute is found in a predictable and logical way. This is especially important in complex inheritance situations like the diamond pattern.

Next: design patterns and MVC (Week 11).

Unified Modelling Language (UML)

See csse1001 for course logistics — this note covers Lecture 10A’s technical content. See uml for the full reference on UML diagram notation.

Today’s outline

• Recap: inheritance vs. composition
• UML class diagrams: attributes, methods, and visibility
• Relationship diagrams: inheritance, association, multiplicity, composition, aggregation
• A larger, real-world example

Recap: inheritance vs. composition

Feature	Inheritance	Composition
Relationship	“Is-a”	“Has-a”
Flexibility	Less flexible (changes in parent affect children)	More flexible (components can be changed)
Reusability	Extends base class functionality	Contains objects that provide functionality
Example	Dog is a Animal	Drone has a Camera

Unified Modelling Language (UML)

A UML diagram is the standard way of illustrating relationships among classes — e.g. for our Animal class:

        Animal
   /      |      \
 Cat     Dog     Fox

UML class diagram

A class diagram is a type of UML diagram that shows:

• Classes and their attributes/methods.
• Relationships (e.g. inheritance, composition, association).
• It’s great for object-oriented design.

A class box has 3 parts, plus a visibility marker for each attribute/method:

• Top section: class name (e.g. Animal).
• Middle section: attributes (e.g. name: str).
• Bottom section: methods (e.g. speak(): str).
• Visibility: - (private), + (public), # (protected).

ClassName
-----------------------
-privateAttribute
+publicAttribute
#protectedAttribute
-----------------------
+method()
-privateMethod()

Animal
-----------------------
#name: str
#age: int
-----------------------
+info(): str

UML inheritance diagram

Each subclass inherits from Animal and overrides speak(). Inheritance is drawn as a solid line with a hollow arrowhead pointing from the subclass to the superclass:

                Animal
            -----------------
            #name: str
            #age: int
            -----------------
            +info()
                 ^
                 | (inheritance)
     -----------------------------
     |           |               |
    Cat         Dog             Fox
  --------   -----------    ------------------
             -breed: str    -nationality: str
  --------   -----------    ------------------
  +speak()   +speak()       +speak()
                             +info()

UML association diagram

Association — drawn as a plain solid line — represents one class using or knowing about another, without owning it. For example, a Cat can drink(Milk):

Animal            Milk
  ^          ----------------
  |          -expiration: str
Cat          ----------------
--------     +is_fresh(int): bool
+speak()
+drink(Milk)  ------ (association: "drinks") ------> Milk

UML multiplicity

Multiplicity shows how many objects are involved in a relationship:

Multiplicity	Meaning
0..1	Zero to one
n	Specific number
0..*	Zero to many
1..*	One to many
m..n	Specific number range

For example, an Animal can be associated with 1..* Vets, and a Vet is associated with 1..* Animals:

Animal  1..* ------ Associated ------ 1..*  Vet

UML composition diagram

Composition (“has a” relationship, filled diamond): here the “part” cannot exist independently of the “whole”. For example, an Animal has exactly one Heart:

Animal  ◆──1────────1──  Heart

UML aggregation diagram

Aggregation (hollow diamond) is a weaker form of composition: here the “part” can exist independently of the “whole”. For example, an Owner has zero or more Animals (pets), but an Animal can exist without an Owner:

Owner  ◇──────0..*──  Animal

Exercise

Try modelling a UML diagram for the DroneFlight class (from 2025-09-23-composition) and its child DeliveryDrone class (from 2025-09-23-inheritance’s exercise) — left unsolved in the source.

A larger example

Real systems combine all of these relationships. A simplified tank-battle game architecture might look like:

WTView <╌╌1╌╌1╌╌ WTController
                       ╎ 1
                       ╎
                       v 1
Battlefield <╌╌1╌╌1╌╌ WTModel ╌╌1╌╌N╌╌> Tank
     ^                                    ^
     | 1                                  |
     N                          ----------------------
     |                          |                     |
    Tile                     Player                Enemy
  /  |  \                                             ^
Floor Wall Rock                                  ------------
                                                  |          |
                                                Guard      Patrol

The dashed arrows here represent dependencies between the controller, model, and view — this is the classic Model-View-Controller (MVC) pattern, which we’ll cover properly next week.

Summary

UML is a visual language used to design and describe software systems. In object-oriented programming, class diagrams are one of the most-used UML tools. They help represent the structure of a system by showing classes, their attributes and methods, and the relationships between them — such as inheritance, association, aggregation, and composition. Using UML before writing code makes it easier to plan, communicate, and maintain software designs effectively.

Next: 2025-10-07-advanced-inheritance (Lecture 10B).

Week 11

Model View Controller

See csse1001 for course logistics — this note covers Lecture 11A’s technical content. See [mvc] for the full reference on the Model-View-Controller pattern.

Advanced inheritance (recap)

A quick recap table from the end of last week, tying MRO complexity to each inheritance model (see python-inheritance for the full detail):

Inheritance type	MRO complexity
Single	Simple linear order
Multilevel	Chain-like resolution
Multiple	C3 linearization
Hybrid (e.g. diamond)	C3 linearization

A few extra facts about MRO worth reinforcing:

• Every class has an MRO, computed the moment the class is defined (not when it’s first used) — inspect it with ClassName.mro() or ClassName.__mro__.
• The MRO is built by the C3 linearization algorithm and depends entirely on the inheritance structure.
• If two base classes define the same attribute/method, whichever appears earlier in the MRO wins.
• Inside a method of an object of type MyClass, every super() call — whether it’s in MyClass itself or in one of its parents/grandparents — refers to the next class after the current one on MyClass’s MRO (not the next class up from wherever the method happens to be defined).

MVC

The Model-View-Controller (MVC) pattern separates an application into three interconnected components:

• Model: stores the data and business rules of the application; responsible for every state change.
• View: some (usually visual) representation of the data, without altering it.
• Controller: an interface that receives user input (commands), tells the Model what to do, then selects a View to present the result.

Anatomy of MVC

Layer	Core question	Owns	MUST NOT
Model	What is the data?	Data & rules	print, parse args, call input()
View	How is info shown?	Formatting & rendering	change state, validate data
Controller	What happens next?	Workflow & commands	store raw data, format output

The Model knows nothing about the outside world — no printing, no argument parsing, no reading input. It’s pure data and logic.

MVC flow

1. User issues a command.
2. Controller parses input and calls the appropriate Model method.
3. Model mutates state and returns domain data.
4. Controller selects a View and passes the data.
5. View formats the data and pushes it to stdout.
6. Control returns to the main loop, waiting for the next user action.

Why MVC?

• Modularity — swap in new models, views, or controllers without breaking the application.
• Testability — each component can be tested in isolation.
• Separation of concerns — each component has a distinct responsibility.

Exercise: a minimal todo list manager

Implement a minimal todo list manager with the MVC design pattern:

• Task + TodoList → Model (domain)
• TodoView → View (presentation only)
• TodoApp + run-loop → Controller (input parsing & orchestration)

Model

class Task:
    def __init__(self, title: str) -> None:
        self._title = title
        self._done = False

class TodoList:
    def __init__(self) -> None:
        self._tasks = []

    def add(self, title: str) -> Task:
        task = Task(title)
        self._tasks.append(task)
        return task

    def all(self) -> list[Task]:
        return list(self._tasks)

View

class TodoView:
    def show_task(self, task: Task) -> None:
        mark: str = "/" if task._done else "X"
        print(f"[{mark}] {task._title}")

    def show_list(self, tasks: list[Task]) -> None:
        print("\n My Tasks\n--------")
        for t in tasks:
            self.show_task(t)

Controller

class TodoApp:
    def __init__(self, todo: TodoList, view: TodoView) -> None:
        self._todo = todo
        self._view = view

    def handle(self, command: str) -> None:
        parts = command.strip().split(maxsplit=1)
        if not parts:
            return
        cmd: str = parts[0]
        if cmd == "add" and len(parts) == 2:
            self._todo.add(parts[1])
            print("Task added!")
        elif cmd == "list":
            self._view.show_list(self._todo.all())
        else:
            print("Commands: add <title>, list, quit")

Run loop

app = TodoApp(TodoList(), TodoView())
while True:
    user_cmd: str = input("$")
    if user_cmd.strip() in ("quit", "exit"):
        break
    app.handle(user_cmd)

$add Work on A2
Task added!
$add buy groceries
Task added!
$list

 My Tasks
--------
[X] Work on A2
[X] buy groceries

Tracing through add Buy groceries against the MVC flow above:

1. User issues add Buy groceries.
2. Controller (TodoApp.handle) parses the input and calls TodoList.add.
3. Model (TodoList) mutates state and returns a Task.
4. Controller selects a View method (show_task, or show_list for list) and passes the data.
5. View formats the data and pushes it to stdout.
6. Control returns to the main loop, waiting for the next command.

Every [X] in the output above is correct, if a little misleading at first glance — X just means “not done” here (mark = "/" if task._done else "X"), and nothing in this exercise ever sets _done = True. It’s not a bug, just an unused feature stub left for extension.

Worked example: a larger system

game.py (a small pygame grid-world) is a good example of these same ideas showing up in a messier, more realistic setting:

• Model: Grid, Cell, Robot, and the Enemy hierarchy hold all the state and rules — cell rewards, slipperiness, robot/enemy position, and score.
• Enemy is itself an abstract base class in the unenforced style from python-inheritance: act() just raises NotImplementedError, and the two concrete subclasses RandomEnemy and ChaserEnemy each provide their own act() — RandomEnemy picks a random legal direction, ChaserEnemy greedily moves toward whichever direction minimises squared distance to the robot.
• View + Controller: Game owns both of these — draw()/_draw_grid()/_draw_hud()/_draw_actor() render the current state (View), while handle_events() reads keyboard input and directly drives the Model (self.robot.move(...), self.enemy.act(...), self.enemy.check_collision(...)) (Controller).

This is a useful contrast with the todo list example above: real GUI/game loops very often merge View and Controller into one class for pragmatic reasons (rendering and input handling are both tied to the same per-frame loop), even though the stricter three-way split is what’s taught here. The important invariant that is preserved is the one in the “MUST NOT” table: the Model (Grid, Cell, Robot, Enemy) never calls print or input(), and knows nothing about pygame at all.

One subtlety in handle_events(): on every keypress the order is always robot moves, then the enemy acts, then collision is checked — so it’s possible for the robot to step onto the enemy’s old square and the enemy to then step away in that same tick, without a collision ever being registered. Not necessarily a bug, but worth noticing if the game feels like it “should” have caught you.

Summary

• MVC is a pattern, typically used in web/GUI applications.
• Separation of concerns makes code more organised.
• It’s easier to test, maintain, and extend code built this way.
• It provides a solid foundation for future enhancements.
• Numerous variants of MVC exist.

Next: further design patterns (Lecture 11B).

Week 12

Recursion

See csse1001 for course logistics — this note covers Lecture 12A’s technical content. See python-recursion for the full reference on recursion.

What is recursion?

A function that calls itself is a recursive function. This can feel circular — we’re using the function to define the function — but it’s logically sound, and is essentially an implementation/realization of mathematical induction.

The lecture note explicitly says: you will not be tested on (nor need to really understand) induction — it’s just motivation, and there are only one or two questions (of forty) on recursion on the exam. Allocate study time accordingly.

Recursion as induction

The Principle of Mathematical Induction (PMI): for any predicate \(P : \mathbb{N} \to \{\text{True}, \text{False}\}\),

\[(P(0) \text{ and } (P(n) \implies P(\text{succ}(n)))) \implies \forall m \in \mathbb{N}, P(m)\]

In prose: if the proposition is true for zero, and if it being true for \(n\) implies it’s true for the successor of \(n\), then it’s true in general.

Worked example: any \(2^n \times 2^n\) board can be tiled with “corner-tiles” (L-shaped trominoes) so that exactly one square is left uncovered.

• Base case (\(n=0\)): a \(1 \times 1\) board can be “covered” with zero tiles (the one square is the uncovered one).
• Induction hypothesis: assume a \(2^n \times 2^n\) board can be tiled this way.
• Induction step: a \(2^{n+1} \times 2^{n+1}\) board splits into four \(2^n \times 2^n\) quadrants. Tile three of the quadrants fully (using one corner-tile in the centre to cover the three inner corners), and tile the fourth quadrant using the induction hypothesis — its single uncovered square becomes the uncovered square for the whole board.

Recursion ingredients

Every recursion must have at least one of each:

• Base case: a case defined outright (if base_case: return constant).
• Recursive step: a line where the function calls itself on “smaller” input.

Factorial: the canonical example

\[n! = \begin{cases} 1 & n = 0 \\ n \times (n-1)! & \text{otherwise} \end{cases}\]

def fact(n: int) -> int:
    if not n:           # Pythonic zero check
        return 1        # base case
    return n * fact(n-1)   # inductive case / recursion

>>> fact(0)
1
>>> fact(3)
6
>>> fact(-1)
RecursionError: maximum recursion depth exceeded

fact(-1) never reaches the base case — n just keeps getting more negative — so it “bottoms out” once Python’s recursion limit is hit.

Winding and unwinding

Evaluating fact(4):

factorial(4)
← 4 × factorial(3)
← 4 × (3 × factorial(2))
← 4 × (3 × (2 × factorial(1)))
← 4 × (3 × (2 × (1 × factorial(0))))

This build-up is the winding phase — each recursive call pushes a new activation record onto the call stack (last in, first out). Once the base case is hit, unwinding begins, resolving each pending multiplication from the inside out: 1×1 → 2×1 → 3×2 → 4×6 → 24.

Stack overflow

Python only allows finitely many recursive calls (default limit: 1000). Exceeding it doesn’t necessarily mean you’re bottoming out (as with fact(-1)) — sometimes an algorithm legitimately needs a deeper stack than Python’s default:

>>> import sys
>>> sys.setrecursionlimit(1500)   # default is 1000

Finding base cases

To handle non-obvious base cases, consider an example that makes a single recursive call, and ask what the base case must be for that example to work. For instance, \(2^k = 2 \cdot 2^{k-1}\) — what does “\(2\) multiplied \(0\) times” mean? Since \(2^1 = 2 \cdot 2^0\) and \(2^1 = 2\), it must be that \(2^0 = 1\).

Recursive functions over lists/strings usually use the empty list/string as their base case:

Type	Base case
list	[]
str	'' (empty string)

Advice: ask yourself how you’d solve the problem if you could already solve it on smaller examples. When in doubt, pick base cases so that the singleton case (the second-smallest case) works correctly.

Worked exercises

Palindrome check

The obvious, non-recursive answer:

def is_palindrome(cs: str) -> bool:
    return cs == cs[::-1]

Avoiding a full reversal:

def is_palindrome(cs: str) -> bool:
    for k in range(len(cs)//2):
        if cs[k] != cs[-k-1]:
            return False
    return True

With recursion:

def is_palindrome(cs: str) -> bool:
    if not cs:                                    # base case
        return True
    return cs[0] == cs[-1] and is_palindrome(cs[1:-1])   # recursion

Sentence palindrome (ignoring spacing, casing, punctuation)

def sentence_palindrome(cs: str) -> bool:
    if not cs:
        return True
    if not cs[0].isalpha():
        return sentence_palindrome(cs[1:])
    if not cs[-1].isalpha():
        return sentence_palindrome(cs[:-1])
    return cs[0].lower() == cs[-1].lower() and sentence_palindrome(cs[1:-1])

>>> sentence_palindrome("Al lets Della call Ed 'Stella'.")
True
>>> sentence_palindrome("Yo, banana boy!")
True

Flatten a list

def flatten(xs: list) -> list:
    if not xs:
        return xs                                   # base case
    if type(xs[0]) is int:
        return xs[0:1] + flatten(xs[1:])             # recursion
    return flatten(xs[0]) + flatten(xs[1:])          # recursion

>>> flatten([1, [2], [[3,4]], [[5], [6,7,8], 9]])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Monotonically increasing

def increasing(xs: list[int]) -> bool:
    if len(xs) <= 1:                                # base case
        return True
    return xs[0] < xs[1] and increasing(xs[1:])     # recursion

Sum of digits

def sum_of_digits(n: int) -> int:
    if not n:
        return 0
    return (n % 10) + sum_of_digits(n // 10)

Sublist sum (tree recursion)

Determine if any sublist of xs sums to a target value:

def sublist_sum(xs: list[int], target: int) -> bool:
    if not xs:
        return not target        # true only for target == 0
    return sublist_sum(xs[1:], target-xs[0]) \
        or sublist_sum(xs[1:], target)

>>> xs = [3, 5, 6, -3, 1, 2]
>>> sublist_sum(xs, 9)
True     # [3, 5, 1]
>>> sublist_sum(xs, -1)
True     # [-3, 2]

Every call to sublist_sum here triggers two further recursive calls (include xs[0] in the target sum, or don’t) — this branches into a tree of recursive calls, rather than the single linear chain seen in fact or is_palindrome.

Counting grid paths

How many distinct paths are there from the origin to (x, y), moving only in the positive \(x\) or \(y\) direction?

def num_paths(x_cord: int, y_cord: int) -> int:
    if (x_cord, y_cord) == (0, 0):
        return 1
    if x_cord < 0 or y_cord < 0:
        return 0
    return num_paths(x_cord-1, y_cord) + num_paths(x_cord, y_cord-1)

Towers of Hanoi

Move num_disks disks (labelled \(1 \ldots n\), biggest to smallest) from from_peg to to_peg (pegs labelled 0, 1, 2), moving one disk at a time and never placing a bigger disk on a smaller one:

def hanoi(num_disks: int, from_peg: int, to_peg: int) -> list[tuple[int, int]]:
    if not num_disks:
        return []

    off_peg = 3 - from_peg - to_peg

    return (hanoi(num_disks-1, from_peg, off_peg)
            + [(num_disks, to_peg)]
            + hanoi(num_disks-1, off_peg, to_peg))

>>> hanoi(2, 0, 2)
[(1, 1), (2, 2), (1, 2)]

The recursive idea: to move \(n\) disks from from_peg to to_peg, first move the top \(n-1\) disks out of the way (to the spare off_peg), move the single bottom disk directly, then move those \(n-1\) disks from the spare peg onto their final destination.

See towers-of-hanoi for a formal induction proof that this always works, plus a fully validated 4-disc move trace.

Tiling exercise (unsolved)

The lecture also poses tiling a \(2^n \times 2^n\) board with distinct numbered tiles (rather than just proving a tiling exists, as in the induction example above), leaving 0 for the uncovered square:

>>> tile(2)
[[0, 2, 3, 3],
 [2, 2, 1, 3],
 [4, 1, 1, 5],
 [4, 4, 5, 5]]

No solution was given in the lecture materials — left here as an open exercise (a natural recursive approach mirrors the induction proof: solve the smaller board, then place three tiles to cover the other three quadrants).

Longest common subsequence

def lcs(xs: str, ys: str) -> str:
    if not xs or not ys:
        return ""
    if xs[0] == ys[0]:
        return xs[0] + lcs(xs[1:], ys[1:])
    return max(lcs(xs[1:], ys), lcs(xs, ys[1:]), key=len)

>>> lcs("cbfbcdeb", "cbebcee")
'cbbce'

Dynamic programming

Branching recursion (like sublist_sum) can be slow because the same subproblems get recomputed many times. Dynamic programming caches previous results to avoid this — most effective when there are many overlapping subproblems, like the naive Fibonacci function:

def fib(n: int) -> int:
    if n < 2:
        return 1
    return fib(n-1) + fib(n-2)

With caching:

fib_cache = {0: 1, 1: 1}          # base cases go here
def fib(n: int) -> int:
    global fib_cache
    if n in fib_cache:
        return fib_cache[n]
    fib_cache[n] = fib(n-1) + fib(n-2)
    return fib_cache[n]

Summary

• Recursion is a function calling itself, with a base case and a recursive step.
• It’s the programming realization of mathematical induction.
• Evaluation has a winding phase (building up calls) and an unwinding phase (resolving them).
• Common base cases: 0 for numbers, []/'' for lists/strings.
• Some recursions branch into a tree of calls rather than a single chain — caching (dynamic programming) can make these tractable.

Next: functional programming and complexity (Week 13).

Towers of Hanoi (Induction & Recursion, Supplementary)

Supplementary material reinforcing 2025-10-20-recursion and python-recursion — a formal induction proof that the Towers of Hanoi puzzle is always solvable, plus a fully validated worked trace. (Sourced from a guest set of slides that used its own “Lecture 4A” numbering — treated here as extra practice material rather than a separate CSSE1001 lecture.)

The puzzle

Given a tower of \(n\) discs (each a different size) stacked on one of several poles, move the entire stack to another pole, one disc at a time, never placing a bigger disc on top of a smaller one.

Proving it’s always solvable

Let \(P(n)\) be the proposition “a stack of \(n\) discs can be moved to an arbitrary pole under the rules above.”

• Base case \(P(0)\): vacuously true — there’s nothing to move.
• Inductive step: assume \(P(n-1)\) (a stack of \(n-1\) discs can always be moved to an arbitrary pole). Then, for a stack of \(n\) discs:
  1. Move the top \(n-1\) discs onto the spare pole (possible by the inductive hypothesis).
  2. Move the remaining (largest) disc onto the target pole directly.
  3. Move the \(n-1\) discs from the spare pole onto the target pole, on top of the largest disc (again possible by the inductive hypothesis).
  This gives a valid sequence of moves for \(n\) discs, so \(P(n)\) holds.
• Conclusion: by the Principle of Mathematical Induction, \(P(n)\) holds for all \(n\).

This is exactly the recursive structure of the hanoi function in 2025-10-20-recursion: the inductive hypothesis is the recursive call.

Validated example: 4 discs

Moving 4 discs from peg 0 to peg 2 (moves written as (disc, destination_peg)):

(1,1) (2,2) (1,2) (3,1) (1,0) (2,1) (1,1)
(4,2)
(1,2) (2,0) (1,0) (3,2) (1,1) (2,2) (1,2)

That’s \(2^4 - 1 = 15\) moves, split as 7 moves to clear discs 1–3 onto the spare peg, 1 move for disc 4, then 7 moves to bring discs 1–3 back on top — matching the proof’s structure exactly. This trace is exactly what hanoi(4, 0, 2) from 2025-10-20-recursion produces:

>>> hanoi(4, 0, 2)
[(1, 1), (2, 2), (1, 2), (3, 1), (1, 0), (2, 1), (1, 1),
 (4, 2),
 (1, 2), (2, 0), (1, 0), (3, 2), (1, 1), (2, 2), (1, 2)]

Exercise stub

The source slides left the implementation as an exercise:

def hanoi(n: int, from_peg: int, target_peg: int) -> list[tuple[int, int]]:
    """Return the sequence of moves to shift n discs from from_peg to
    target_peg, obeying the Towers of Hanoi rules."""
    ...

See 2025-10-20-recursion for a complete implementation (using the third, “off”, peg as scratch space).

Related: [[2026-07-27-welcome-and-intro-problems|MATH1061’s welcome & intro problems]] previews the same puzzle (and the \(2^n - 1\) minimum move count) as motivation for MATH1061’s own later induction/recursion content — a nice example of the same idea showing up in two different courses.

Reference material

Model-View-Controller (MVC)

Model-View-Controller (MVC) is a design pattern that separates an application into three interconnected components, each with a single, distinct responsibility.

The three components

Layer	Core question	Owns	MUST NOT
Model	What is the data?	Data & business rules	print, parse args, call input()
View	How is info shown?	Formatting & rendering	change state, validate data
Controller	What happens next?	Workflow & commands	store raw data, format output

The Model knows nothing about the outside world — it never prints, reads input, or otherwise interacts with the user directly. It’s pure data and logic.

Flow of control

1. User issues a command.
2. Controller parses the input and calls the appropriate Model method.
3. Model mutates its own state and returns domain data.
4. Controller selects a View and passes it the data.
5. View formats the data and presents it (e.g. prints to stdout).
6. Control returns to the main loop, waiting for the next user action.

Why use it?

• Modularity — swap in a new model, view, or controller without breaking the rest of the application.
• Testability — each component can be tested in isolation (the Model especially, since it has no I/O).
• Separation of concerns — each component has exactly one job.

Minimal skeleton

class Model:
    def __init__(self):
        self._state = ...

    def do_something(self, ...):
        # mutate self._state, return domain data
        ...

class View:
    def show(self, data):
        # format `data` and present it -- no mutation, no logic
        ...

class Controller:
    def __init__(self, model, view):
        self._model = model
        self._view = view

    def handle(self, command):
        # parse `command`, call the right Model method,
        # then pass its result to the View
        ...

In practice

Strict three-way separation is common in textbook examples (e.g. a todo list manager: Task/TodoList as Model, TodoView as View, TodoApp as Controller), but real GUI and game applications very often merge View and Controller into a single class — rendering and input handling both naturally live inside the same per-frame/per-event loop. The property that’s still worth preserving even then is the Model’s isolation: whatever owns rendering and input, the Model itself should stay free of print/input()/UI-framework calls.

See python-inheritance for abstract base classes and MRO, and python-composition for is-a vs has-a — both are commonly combined with MVC (e.g. an abstract Enemy base class within a game’s Model layer).

Python Boolean Logic

The basic operands of logic are True, False, or, and, and not.

Boolean domain and predicates

Let \(\mathbb{B}\) denote the boolean domain, \(\mathbb{B} = \{\texttt{True}, \texttt{False}\}\). Any function that maps into \(\mathbb{B}\) (i.e. one that evaluates to True or False) is called a predicate — e.g. \(> : \mathbb{Z} \times \mathbb{Z} \to \mathbb{B}\) (“greater than”).

>>> type(True), type(False)
(<class 'bool'>, <class 'bool'>)
>>> 7 > 3
True
>>> 7 >= 7 + 1        # addition happens first
False
>>> (7 >= 7) + 1
2
>>> int(True), int(False)
(1, 0)

and, or, not

and (\(\mathbb{B} \times \mathbb{B} \to \mathbb{B}\)) is true only when both inputs are true:

and	True	False
True	True	False
False	False	False

or (\(\mathbb{B} \times \mathbb{B} \to \mathbb{B}\)) is true when at least one input is true (false only when both are false):

or	True	False
True	True	True
False	True	False

>>> 3 > 7 or 7 > 3
True
>>> 3 > 7 and 7 > 3
False
>>> 0 < 3 and 3 < 8
True
>>> 0 < 3 < 8          # shorthand for the above
True

True or False and False is ambiguous without a precedence rule, since \((\texttt{True or False}) \texttt{ and False} = \texttt{False}\) but \(\texttt{True or (False and False)} = \texttt{True}\). Python resolves this with and having higher precedence than or (so the expression above evaluates to True, as if bracketed True or (False and False)).

not is the negation of a logical statement (not True == False, not False == True) and is evaluated first, before and/or:

>>> a, b = 6, 7
>>> not (a == 6 and b != 5)
False
>>> not a == 6 and b != 5   # not happens before and
False

Avoid double negations (e.g. not (a != 6 or not b != 5)) — they’re valid but hard to read.

Short circuits (lazy evaluation)

or stops as soon as it finds a truthy value; and stops as soon as it finds a falsy value — the remaining operand is never evaluated:

>>> True or 1/0
True
>>> False or 1/0
ZeroDivisionError: division by zero
>>> True or non_existent_variable
True   # Python never bothers looking up non_existent_variable
>>> True and 1/0
ZeroDivisionError: division by zero
>>> False and 1/0
False

Truthiness

Any object can be converted to a boolean with bool. Truthy values evaluate to True (non-zero numbers, non-empty strings/tuples/lists); falsy values evaluate to False (zero, the empty string, the empty tuple/list):

>>> bool(1), bool(-10), bool("Hello"), bool([1, 2, 3])
(True, True, True, True)
>>> bool(0), bool(""), bool([])
(False, False, False)

What and/or actually return

and and or don’t always return True/False — and returns its first falsy input (or its last input, if none are falsy), and or returns its first truthy input (or its last input, if none are truthy):

>>> 0 or 2
2
>>> 0 and 2
0
>>> () or (1,) or (1, 2)
(1,)
>>> (1, 2) or (1,) or ()
(1, 2)
>>> () and (1,) and (1, 2)
()
>>> (1, 2) and (1,) and ()
()

Python Classes and Objects

An object bundles data (attributes, comprising its state) with methods (functions that act on that data) — the object has a notion of self.

Defining a class

class ClassName():
    def __init__(self, ...):
        self.attribute = ...

    def some_method(self, ...):
        return ...

• Class names use CamelCaps by convention.
• __init__ is the initializer, run automatically when an instance is created.
• Every method’s first parameter is self — Python supplies it automatically; never pass an argument for it explicitly.

Instantiation and attributes

>>> p = ClassName(...)      # creates an instance, passing args to __init__
>>> p.attribute              # dot notation accesses instance variables

Equality vs. aliasing

• Two separately-constructed instances with identical attributes are not == by default (equality compares identity unless a class defines otherwise).
• Assigning q = p makes q an alias for the same object as p — mutating one is visible through the other, and p == q holds because they’re literally the same object.

Private variables, getters, and setters

A leading underscore (self._value) signals that an attribute is intended for internal use only — a convention, not an enforced restriction; nothing stops external code from reading or writing it directly (which is bad practice).

Prefer exposing controlled access via methods:

def get_value(self) -> int:            # getter
    return self._value

def set_value(self, x: int) -> None:   # setter
    if x < 0:
        raise ValueError
    self._value = x

Python’s @property/@<name>.setter decorators let a getter/setter pair be used with ordinary attribute syntax (obj.name / obj.name = value) instead of explicit method calls.

Encapsulation

Encapsulation means keeping an object’s data safe inside the class, exposed only through its attributes and methods.

Python Composition

Composition is a way of building a class out of other objects: an object of one class holds an object of another class as one of its attributes. This forms a has-a relationship (e.g. a Car has-a Engine) — as opposed to inheritance’s is-a relationship (e.g. a SportsCar is-a Car).

Basic pattern

class Car():
    def __init__(self, engine: Engine) -> None:
        self._engine = engine   # Car has-a engine

    def start(self):
        self._engine.start()

The outer object (Car) doesn’t need to know how the inner object (Engine) works internally — it just calls the inner object’s public methods. This keeps each class focused on a single responsibility.

Worked example: Car/Engine

class Engine:
    def __init__(self, horsepower, fuel_type="gasoline"):
        self.horsepower = horsepower
        self.fuel_type = fuel_type
        self.running = False

    def start(self):
        if not self.running:
            self.running = True
            print(f"{self.fuel_type.capitalize()} engine with {self.horsepower} HP started.")
        else:
            print("Engine is already running.")

    def stop(self):
        if self.running:
            self.running = False
            print("Engine stopped.")
        else:
            print("Engine is already off.")


class Car:
    def __init__(self, make, model, engine: Engine):
        self.make = make
        self.model = model
        self.engine = engine

    def start(self):
        print(f"Starting the {self.make} {self.model}...")
        self.engine.start()

    def stop(self):
        print(f"Stopping the {self.make} {self.model}...")
        self.engine.stop()

    def swap_engine(self, new_engine: Engine):
        if self.engine.running:
            print("Stopping current engine before swap...")
            self.engine.stop()
        print(f"Swapping engine in {self.make} {self.model}...")
        self.engine = new_engine
        print("New engine installed!")

>>> small_engine = Engine(150, "gasoline")
>>> car = Car("Toyota", "Corolla", small_engine)
>>> car.start()
Starting the Toyota Corolla...
Gasoline engine with 150 HP started.

>>> big_engine = Engine(300, "diesel")
>>> car.swap_engine(big_engine)   # safely stops the old engine first, if running

Composition vs. inheritance

• Use composition (“has-a”) when an object is made up of other objects, or uses another object to do part of its job.
• Use inheritance (“is-a”) when a new class is a more specific version of an existing class.

Composition tends to be more flexible: a composed attribute can be freely swapped for any object supporting the same interface (see duck typing), without needing any shared base class.

Python Comprehensions

A comprehension is a concise way to build a list or dictionary directly from an iterable, without writing an explicit accumulator for-loop.

List comprehension

>>> [k**2 for k in range(4)]
[0, 1, 4, 9]

Equivalent to:

>>> acc = []
>>> for k in range(4):
...     acc.append(k**2)

sum(... for ...) (a generator expression, without the surrounding []) computes a running total directly, without building the intermediate list:

>>> sum(k**2 for k in range(4))
14

Dictionary comprehension

>>> {x: x**2 for x in range(4)}
{0: 0, 1: 1, 2: 4, 3: 9}

Useful for assigning default values across a set of keys:

>>> {x: 0 for x in "ABC"}
{'A': 0, 'B': 0, 'C': 0}

Nested comprehensions

Multiple for clauses can appear in one comprehension. The order of the for clauses matters — it matches the order they’d be nested as for-loops:

>>> [(a, x) for a in "AB" for x in range(2)]
[('A', 0), ('A', 1), ('B', 0), ('B', 1)]

>>> [(a, x) for x in range(2) for a in "AB"]
[('A', 0), ('B', 0), ('A', 1), ('B', 1)]

Filtering

A trailing if filters which elements are included:

>>> [x for x in range(101) if not (x % 3) and not (x % 7)]
[0, 21, 42, 63, 84]

The general pattern

[x for x in xs if P(x)]
[x for x in xs for y in ys if P(x, y)]
[x for x in xs for y in ys for z in zs if P(x, y, z)]
...

where P is some predicate.

True/False as 1/0

Python’s bool is a subtype of int, so True/False behave as 1/0 in arithmetic — a common idiom for counting how many elements of an iterable satisfy some condition:

>>> True + True + False
2
>>> sum(x > 0 for x in [-1, 2, 3, -4])
2

all and any

Python’s built-in all(xs)/any(xs) check whether every/some element of xs is truthy:

>>> all(['A' <= x <= 'Z' for x in "HELLO WORLD"])
False
>>> any(['A' <= x <= 'Z' for x in "HELLO WORLD"])
True

Careful: redefining a function named all or any in your own code shadows these built-ins for the rest of that scope — see 2025-08-25-comprehensions’s exercises, which do exactly this (as an exercise in reimplementing them) as a worked example.

See python-for-loops for the equivalent for-loop/accumulator forms these shortcut.

Python Dictionaries

A dictionary is a data structure that stores (key, value) pairs. Python uses a “magic” hash function to find a key among the stored pairs quickly (see 2025-08-18-non-primitive-data for how a hash function generalizes indexing-by-position to indexing-by-any-key). Dictionaries are not ordered (keys can be of mixed type) and are mutable.

Hash tables are a candidate for the most important/useful data structure in computer science.

Creating and indexing

>>> h = {
...     "red": ["apple", "firetrucks", "cars"],
...     "yellow": ["banana", "cars"],
...     "blue": ["sky", "cars"]
... }
>>> h["blue"]
['sky', 'cars']
>>> h["green"]
KeyError: 'green'
>>> h["green"] = ["leaves"]   # fine -- we're assigning, not retrieving

keys, values, items

>>> h.keys()
dict_keys(['red', 'yellow', 'blue'])
>>> h.values()
dict_values([['apple', 'firetrucks', 'cars'], ['banana', 'cars'], ['sky', 'cars']])
>>> h.items()
dict_items([('red', ['apple', 'firetrucks', 'cars']), ('yellow', ['banana', 'cars']), ('blue', ['sky', 'cars'])])

clear and copy

>>> f = h.copy()
>>> h.clear()
>>> h["blue"]
KeyError: 'blue'
>>> f["blue"]
['sky', 'cars']

Like list’s .copy() (see python-lists), dict’s .copy() is only a shallow copy — mutable values are still shared:

>>> f = h.copy()
>>> h["blue"].append("windex")
>>> h["blue"]
['sky', 'cars', 'windex']
>>> f["blue"]
['sky', 'cars', 'windex']   # shallow copy -- same underlying list

get

.get(key) is a safer alternative to h[key] — it returns None instead of raising KeyError if the key is missing:

>>> h.get("red")
['apple', 'firetrucks', 'cars']
>>> h["green"]
KeyError: 'green'
>>> h.get("green")
None

Without a method, the same “avoid a KeyError” pattern can be written explicitly:

>>> if key in table:
...     table[key] += 1
... else:
...     table[key] = 0

Warning: keys must be immutable

The keys of a dictionary must be an immutable type (see python-primitive-data-types and python-lists):

>>> d = dict()
>>> d[[1, 2, 3]] = 1
TypeError: unhashable type: 'list'
>>> d[(1, 2, 3)] = 1   # tuples are immutable -- fine
>>> d[dict()] = 1
TypeError: unhashable type: 'dict'

Python Dunder (Magic) Methods

Dunder (“double underscore”) or magic methods are special methods, named __like_this__, that Python calls automatically to implement built-in behaviour for a type — instantiation, printing, equality, arithmetic operators, and more. You don’t call them directly; Python invokes them on your behalf when the corresponding syntax/built-in is used.

Common dunder methods

Method	Called by	Purpose
__init__(self, ...)	ClassName(...)	Initializes a new instance.
__str__(self)	print(obj), str(obj)	User-friendly display string.
__repr__(self)	the REPL, repr(obj)	Unambiguous, developer-facing string — ideally a valid Python expression that recreates the object via eval().
__eq__(self, other)	obj == other	Custom equality (instead of identity).
__add__(self, other)	obj + other	Addition.
__sub__(self, other)	obj - other	Subtraction.
__neg__(self)	-obj	Unary negation.
__len__(self)	len(obj)	Length.

__repr__ vs. __str__

• __repr__ is for the programmer: unambiguous, meant for debugging/logging, ideally eval(repr(obj)) reconstructs an equal object.
• __str__ is for the user: a friendly, readable string, used by print().
• If only __repr__ is defined, print() falls back to it. If neither is defined, printing an object shows its default <... object at 0x...> representation.

Overloadable operators

Binary	Method	Unary	Method	Comparison	Method
+	__add__	-	__neg__	<	__lt__
-	__sub__	abs	__abs__	<=	__le__
*	__mul__	~	__invert__	==	__eq__
**	__pow__			!=	__ne__
//	__floordiv__			>	__gt__
/	__truediv__			>=	__ge__

Instance variables vs. class variables

An instance variable (self.x = ...) belongs to one specific object — each instance has its own copy. A class variable (declared directly in the class body) is shared by all instances of the class, and can be accessed either via an instance (obj.class_var) or via the class itself (ClassName.class_var), without needing any instance at all.

class Clicker():
    _all_clicks = 0   # class variable -- shared by every instance

    def __init__(self) -> None:
        self._clicks = 0   # instance variable -- unique per object

    def click(self) -> None:
        self._clicks += 1
        Clicker._all_clicks += 1

Worked example: Vector2D

A fuller worked example combining several dunder methods together:

import math

class Vector2D():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def length(self):
        return math.sqrt(self.x**2 + self.y**2)

    def __repr__(self):
        return f"Vector2D(x={self.x}, y={self.y})"

    def __str__(self):
        return f"2D Vector: ({self.x}, {self.y}) --- length: {self.length()}"

    def __eq__(self, other):
        return isinstance(other, Vector2D) and self.x == other.x and self.y == other.y

    def __add__(self, other):
        if not isinstance(other, Vector2D):
            return NotImplemented
        return Vector2D(self.x + other.x, self.y + other.y)

    def __len__(self):
        return 2

>>> u = Vector2D(2, 3)
>>> v = Vector2D(4, 5)
>>> print(u + v)
2D Vector: (6, 8) --- length: 10.0
>>> print(u)          # calls __str__
2D Vector: (2, 3) --- length: 3.605551275463989
>>> repr(u)            # calls __repr__
'Vector2D(x=2, y=3)'
>>> u == v              # calls __eq__
False
>>> len(u)               # calls __len__
2

Returning NotImplemented (rather than raising or returning False) from a method like __add__ is the standard way to signal “I don’t know how to combine these two types” — it lets Python fall back to the other object’s reflected method, or raise a clean TypeError if nothing handles it.

Python Exceptions

An exception is a run-time error — unlike a syntax error, it can’t be detected until the offending line actually executes. Left uncaught, it aborts the program.

Common built-in exceptions

Exception	Raised when…
AssertionError	an assert fails
IOError	a file does not exist
IndexError	a sequence index is out of range
KeyError	a dict key does not exist
NameError	a variable/name does not exist
TypeError	an unexpected type is given to a function/operator
ValueError	correct type, but an inappropriate value
ZeroDivisionError	division by zero

Catching exceptions

try:
    <code that may raise>
except SomeError:
    <handle SomeError>
except AnotherError:
    <handle AnotherError>
else:
    <runs only if no exception occurred>
finally:
    <always runs>

• Specific exceptions must be listed before a bare except: — Python enforces this ordering.
• A bare except: catches any exception, but hides genuine bugs — prefer catching specific exception types.
• Keep try blocks short: once an exception is raised inside one, the rest of the block is skipped.

Raising exceptions

raise SomeError                  # bare
raise SomeError("message")       # with an explanatory message

LBYL vs. EAFP

Two equally valid philosophies for guarding against errors:

• LBYL (Look Before You Leap) — check the condition with an if before attempting the risky operation.
• EAFP (Easier to Ask for Forgiveness than Permission) — attempt the operation inside a try, and handle the resulting exception if it fails.

Python File IO

Opening a file

file = open("path", "<mode>")

Mode	Description
r	read
w	write (creates or overwrites)
a	append (creates or adds to the end)

Reading

file.readline() returns one line (including its trailing \n, except possibly the last line of the file), then '' forever once exhausted. A for-loop iterates line by line and is the idiomatic way to consume a whole file:

with open("path", "r") as file:
    for line in file:
        ...

Reading always gives back strings — cast (int(...), float(...), …) as needed.

A file-pointer only moves forward: once a for loop (or repeated readline() calls) has consumed a file, iterating again yields nothing further, unless the file is reopened (or the pointer is seeked back to the start).

Closing

file.close() releases the file; forgetting to close leaves it vulnerable to side effects (missing or extra data). with open(...) as file: closes it automatically — even if the block raises an exception — so it’s preferred over manual open/close.

Writing and appending

with open("path", "w") as file:
    file.write("a single string\n")
    file.writelines(["one string\n", "per element\n"])

"w" overwrites any existing file; "a" instead appends to the end without touching existing content.

Python For-Loops

A for-loop is a loop that repeats code for every member of a group (an iterator), in order:

for <name> in <iterator>:
    <code>

Iterating over strings, lists, and dictionaries

A for-loop iterates a string’s characters, a list’s elements, or a dictionary’s keys (in each case, in order):

>>> for x in "abcd":
...     print(x)
a
b
c
d

>>> for x in ['a', 2, 'c']:
...     print(x)
a
2
c

>>> for key in {"red": 1, "blue": 2}:
...     print(key)
red
blue

The looping name retains its final value after the loop exits.

Nested for-loops

Python disallows empty loop bodies — use pass (the empty instruction, which has no effect) as a placeholder when a loop body needs no code yet:

>>> for d in "01":
...     for a in "xy":
...         pass
...     print(d + a)
0y
1y

Accumulator pattern

An accumulator is a variable a loop uses to build up an aggregate value across iterations:

>>> acc = ""
>>> for x in "abcd":
...     acc = acc + x
>>> acc
'abcd'

range

range([start], stop[, step]) builds an iterator of numbers (square brackets denote optional arguments), similar to list slicing:

>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(2, 7))
[2, 3, 4, 5, 6]
>>> list(range(2, 7, 3))
[2, 5]
>>> list(range(7, 2, -1))
[7, 6, 5, 4, 3]

Commonly used to walk through a list by index: for k in range(len(xs)):.

enumerate

enumerate(xs) pairs each element of xs with its index, roughly enumerate([x0, ..., xn]) == [(0, x0), ..., (n, xn)] (it actually returns an iterable of tuples, not a list):

>>> for k, x in enumerate(["a", "b", "c"]):
...     print(k, x)
0 a
1 b
2 c

For-loops vs. while-loops

Every for-loop can be rewritten with only a while-loop:

>>> for x in xs:
...     ...

>>> k = 0
>>> while k < len(xs):
...     x = xs[k]
...     ...
...     k += 1

The reverse isn’t always true — a while-loop whose number of repetitions isn’t known in advance (e.g. repeatedly prompting a user until they enter valid input) can’t be rewritten as a for-loop.

Out-of-place vs. in-place

Building a new accumulator (e.g. a fresh list) without touching the original input is an out-of-place computation. An in-place change instead mutates the input directly — covered with lists and the object-oriented part of the course.

See python-comprehensions for a more concise way to write many accumulator-style for-loops.

Python Functions

User-defined functions bundle lines of code together so they can be reused, abstracting away complexity. Like mathematical functions, they take input and return output (we’ve already used built-in functions this way, e.g. * and max).

Defining a function

A mathematical function such as \(f(x) = x^2 + x + 1\) is written in Python as:

>>> def f(x):
...     return x**2 + x + 1
>>> f(3)
13

Functions can take multiple parameters, and calls can be nested inside other expressions:

>>> def f(x, y):
...     return x*y
>>> f(-f(5, 2) + 12, f(2, 3))
12

Indentation

Four spaces of indentation are significant in Python — they associate a line of code with the control structure above it (here, the function body with its def). Inconsistent indentation raises IndentationError: unexpected indent.

The return statement

return is a reserved word (not a function) that hands a value back to the caller and immediately exits the function — any code after the first return a call actually reaches (including further prints or returns) never runs.

If a function has no return statement, Python presumes a return None as its last line.

return versus print

print displays something as a side effect but returns None. This looks similar to return but behaves very differently once the result is used in further computation:

>>> def f(x, y):
...     print(x+y)
>>> a = f(2, 3)
5
>>> b = f(3, 4)
7
>>> a + b
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

>>> def f(x, y):
...     return x + y
>>> a = f(2, 3)
>>> b = f(3, 4)
>>> a + b
12

return is a reserved word, not a function — we write return x + y, not return(x + y) (the latter happens to still work, since the brackets are just a redundant grouping, but it’s misleading).

Type hints

Type hints annotate the expected type of each parameter and the return value, e.g. mapping to \(\text{triangle\_area}: \mathbb{R} \times \mathbb{R} \times \mathbb{R} \to \mathbb{R}\):

>>> def triangle_area(a: float, b: float, c: float) -> float:
...     s = (a+b+c)/2
...     return (s*(s-a)*(s-b)*(s-c))**0.5

Type hints are not enforced — they exist purely as documentation to make code more readable, and Python will not stop you calling a function with the “wrong” types.

Docstrings

A docstring ("""...""" immediately under the def line) documents what a function does and its preconditions, and gives example calls (written like REPL input/output) that double as tests:

>>> def triangle_area(a: float, b: float, c: float) -> float:
...     """
...     Return the area of the triangle with sides length <a>,
...     <b>, and <c>.
...     Preconditions: <a>, <b>, <c> are all nonzero positive.
...     >>> triangle_area(3, 4, 5)
...     6.0
...     """
...     s = (a+b+c)/2
...     return (s*(s-a)*(s-b)*(s-c))**0.5

General template

def function_name(arg0: type, arg1: type, ...) -> type:
    """
    Short description of the function for documentation.
    Preconditions (if any).
    >>> function_name(x, y, ...)
    expected output
    """
    ...
    function body
    ...
    return

See python-pep8-style-guide for the naming, spacing, and line-length conventions used when writing functions like this.

Python If Statements

Given a condition \(C\) (a predicate — see python-boolean-logic), an if-statement is a control structure that executes a block of code when \(C\) is True and skips it otherwise.

If-then

if <cond>:
    <code executed when cond == True>

Only the indented code runs when the condition holds; execution otherwise skips straight past it. Because of truthiness, the condition doesn’t need to literally be True/False:

>>> x = 0
>>> if x:
...     x = x + 1
>>> x
0
>>> x = 1
>>> if x:
...     x = x + 1
>>> x
2

Warning. A variable only assigned inside an if-block does not exist if the condition was false:

>>> if False:
...     ans = 0
>>> ans
NameError: name 'ans' is not defined

If-then-else

if <cond>:
    <code>
else:
    <code>

if-else picks between exactly one of two instruction sets — unlike two separate ifs, the condition is only checked once and the two branches can never both run.

Elif chains

if <cond0>:
    <code>
elif <cond1>:
    <code>
    ...
elif <condN>:
    <code>

Each elif condition is only checked if every condition above it was False — so later branches can safely assume the earlier conditions failed.

Common bug. Because later elifs implicitly assume the earlier ones were false, checking overlapping ranges in the wrong order silently picks the wrong branch:

>>> age = 60
>>> if age >= 18:
...     beverage = "cheap beer"
... elif age >= 30:
...     beverage = "standard beer"
... elif age >= 50:
...     beverage = "expensive beer"
>>> beverage
'cheap beer'   # not what was intended!

Two ways to fix it — bound each range explicitly:

>>> if 18 <= age < 30:
...     beverage = "cheap beer"
... elif 30 <= age < 50:
...     beverage = "standard beer"
... elif 50 <= age:
...     beverage = "expensive beer"

or check from highest to lowest, relying on the guarantee each elif gives about ranges already ruled out:

>>> if age >= 50:
...     beverage = "expensive beer"
... elif age >= 30:      # guaranteed age < 50
...     beverage = "standard beer"
... elif age >= 18:      # guaranteed age < 50 and age < 30
...     beverage = "cheap beer"

If-elif-else

if <cond0>:
    <code>
elif <cond1>:
    <code>
    ...
else:
    <code>

else is a catch-all — it runs whenever none of the preceding if/elif conditions were True (avoiding a NameError from a variable never getting assigned).

Factoring and refactoring

Factoring means breaking a complex problem into parts that are easier to conceive, understand, program, and maintain. Refactoring is the process of restructuring existing code — changing the factoring — without changing its behaviour.

Simplifying if-statements

Nested ifs can often collapse into a single anded condition:

if x > 1:                        if x > 1 and y > 2 and z > 3:
    if y > 2:             ==>        print("hello")
        if z > 3:
            print("hello")

An if/else that only assigns/returns True/False can be replaced by the condition itself:

def foo(x):                      def foo(x):
    if x > 0:             ==>        return x > 0
        return True
    else:
        return False

if x > 0:                        y = x > 0
    y = True          ==>
else:
    y = False

Comparing directly to True/False is redundant:

if x > y == True:    ==>    if x > y:
if x > y == False:   ==>    if not x > y:

Equivalence of elif vs. nested if. An elif condition can safely assume the earlier condition was false, so elif x <= 0 and x % 2 == 0 is equivalent to just elif x % 2 == 0 (given a preceding if x > 0). This is not true for a second, independent if — if x <= 0 and x % 2 == 0 is not equivalent to a bare if x % 2 == 0 placed after if x > 0, since the second if doesn’t know the first one already ran (e.g. with x = 2, the elif form prints only A, but the two-independent-ifs form prints both A and B).

Common errors

or/and do not distribute over a list of bare values — x == 1 or 2 or 3 always evaluates truthy (2 and 3 are truthy on their own, regardless of x). The comparison needs to be repeated instead: x == 1 or x == 2 or x == 3 (later refactored to x in [1, 2, 3]).

if x: pass else: <code> is just a roundabout way of writing if not x: <code>.

Python Inheritance

Inheritance lets a class (the subclass/child class) reuse the attributes and methods of another class (the superclass/parent class), while adding new behaviour or overriding existing behaviour. It models an “is-a” relationship (a DeliveryRobot is a Robot) — contrast with python-composition’s “has-a” relationship.

Syntax

class Parent():
    # parent class' implementation

class Child(Parent):
    # child class' implementation -- inherits everything from Parent

A subclass automatically gets all of its parent’s attributes and methods. It can:

• Add new methods/attributes that only it has.
• Override an inherited method by redefining it with the same name.
• Extend an inherited method using super(), rather than fully replacing it.

super()

super().method(...) calls the parent class’ version of a method — most commonly used inside an overridden __init__ to reuse the parent’s initialization logic before adding subclass-specific setup:

class DeliveryRobot(Robot):
    def __init__(self, name: str, batt_level: int, load_capacity: int):
        super().__init__(name, batt_level)   # reuse Robot's __init__
        self.load_capacity = load_capacity

Terminology cheat-sheet

Given class Student(Person):

Term	Refers to
subclass / child class	Student
superclass / parent class	Person
“Student inherits from / extends Person”	the relationship between them

Polymorphism

Polymorphism (“many forms”) describes an interface that works across different underlying types. Built-ins like len() are polymorphic (works on strings, lists, dicts, …). Classes that share a method name (whether via a common superclass or just by convention) are also polymorphic: the same call, e.g. r.charge(), produces different behaviour depending on which actual class r is an instance of.

When to use inheritance

Only when there’s a genuine “is-a” relationship between the two classes. If the relationship is really “has-a” (one object contains or uses another), prefer python-composition instead.

Abstract base classes

An abstract base class doesn’t provide concrete implementations for some/all of its methods — it just defines the interface that every concrete subclass must implement. You’re not meant to instantiate the abstract class directly.

The simplest (unenforced) version just raises an error from each method that subclasses must override:

class Shape:
    def area(self) -> float:
        raise NotImplementedError("Subclasses must implement area()")

This only fails when the unimplemented method is actually called — Shape() itself still succeeds. The standard-library abc module enforces this properly, raising TypeError at the point of instantiation:

from abc import ABC, abstractmethod

class Shape(ABC):
    @abstractmethod
    def area(self) -> float:
        ...

    # concrete helpers are still allowed alongside abstract methods
    def describe(self) -> str:
        return f"{self.__class__.__name__}"

With ABC, Shape() raises immediately: TypeError: Can't instantiate abstract class Shape with abstract methods area.

Method Resolution Order (MRO)

When a class inherits from multiple parents (or a chain of parents) that define the same method/attribute name, Python needs a deterministic rule for which one wins. That rule is the Method Resolution Order (MRO) — the order Python searches through classes to resolve a name on an object. It’s stored on the class as cls.__mro__ (or cls.mro()).

Python’s inheritance models

• Single inheritance: class B(A): — one parent.
• Multilevel inheritance: class C(B): (where B itself inherits from A) — a linear chain; the MRO just follows the chain upward.
• Hierarchical inheritance: multiple children (B, D, …) inherit from the same parent A.
• Multiple inheritance: class E(B, D): — a class inherits from more than one parent directly.

The diamond problem and C3 linearisation

If E(B, D) and both B and D inherit from A, which version of A’s methods should E use? Python resolves this with C3 linearisation:

• Child classes are checked before parents.
• Parents are checked in the order they’re listed in the class definition.
• If a class would appear more than once, only its last occurrence is kept.

>>> class E(B, D): pass
>>> [cls.__name__ for cls in E.__mro__]
['E', 'B', 'D', 'A', 'object']

Each attribute/method name is resolved independently by walking this list and taking the first class that defines it — so two different method calls on the same object can effectively “come from” two different classes in the hierarchy.

super() follows the MRO

super() doesn’t call the immediate parent named in the class statement — it calls the next class after the current one in the instance’s actual MRO. This is what makes cooperative multiple inheritance work: as long as every class in the chain calls super(), a single call can ripple through every class in the MRO exactly once, in order.

class A:
    def ping(self): print("A")
class B(A):
    def ping(self): print("B"); super().ping()
class C(A):
    def ping(self): print("C"); super().ping()
class D(B, C):
    def ping(self): print("D"); super().ping()

>>> D().ping()
D
B
C
A

If any class in the chain omits its super() call, the chain simply stops there for that call — the MRO itself doesn’t change (it’s purely a function of the class hierarchy), but fewer methods actually get executed.

Python Lists

A list is a mutable ordered collection of elements — elements are not necessarily all the same type. Square brackets [] create a list in Python.

>>> xs = [1, "apple"]
>>> type(xs)
<class 'list'>
>>> xs[0]
1
>>> xs[0] = 2*xs[1]
>>> xs[0]
'appleapple'

Comparison

Lists compare point-wise from position zero:

>>> [1, 2, 3] < [4, 5, 6]
True
>>> [7, 2, 3] < [4, 5, 6]
False
>>> [] < [1]
True

Membership

>>> 1 in [1, 2, 3]
True
>>> 0 in [1, 2, 3]
False
>>> [1] in [1, 2, 3]
False

Adding elements: append vs. concatenation

xs.append(y) mutates xs in place, adding y as a single new element (even if y is itself a list):

>>> xs = [0, 1, 2]
>>> xs.append(3)
>>> xs
[0, 1, 2, 3]
>>> xs.append([4, 5])
>>> xs
[0, 1, 2, 3, [4, 5]]

xs + [y] instead creates a new list, which must be reassigned back to xs to have an effect:

>>> xs = [0, 1, 2]
>>> xs = xs + [3]
>>> xs
[0, 1, 2, 3]

xs.extend(ys) mutates xs in place, appending every element of ys:

>>> xs = [1, 2, 3]
>>> xs.extend([4, 5])
>>> xs
[1, 2, 3, 4, 5]

Aliasing

Assigning one list variable to another does not copy it — both names refer to the same list object:

>>> xs = [1, 2, 3]
>>> ys = xs
>>> ys[-1] = 9
>>> ys
[1, 2, 9]
>>> xs
[1, 2, 9]

Whether an operation preserves this aliasing relationship depends on whether it mutates the list in place or creates a new one:

>>> xs = [1, 2, 3]
>>> ys = xs           # ys is an alias of xs
>>> xs.append(4)      # mutates in place
>>> ys
[1, 2, 3, 4]
>>> xs += [5]         # also mutates in place
>>> ys
[1, 2, 3, 4, 5]
>>> xs = xs + [6]     # creates a NEW list, only rebinds xs
>>> ys
[1, 2, 3, 4, 5]        # aliasing relationship broken!

.copy() breaks the alias for a flat list:

>>> xs = [1, 2, 3]
>>> ys = xs.copy()
>>> ys[-1] = 9
>>> xs
[1, 2, 3]
>>> ys
[1, 2, 9]

Passing lists to functions

Lists are passed to functions by reference, so mutating a parameter inside a function mutates the caller’s list too:

>>> def foo(ys):
...     ys[0] = -100
>>> xs = [1, 2, 3]
>>> foo(xs)
>>> xs
[-100, 2, 3]

Nested lists and matrices

A list can contain another list as an element, e.g. representing a matrix as a list-of-lists:

\[\mathbb{A} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \equiv \texttt{[[1, 2, 3], [4, 5, 6], [7, 8, 9]]}\]

>>> ass = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> ass[-1]
[7, 8, 9]
>>> ass[1:3]
[[4, 5, 6], [7, 8, 9]]
>>> ass[1][-1]
6
>>> ass[1, -1]
TypeError: list indices must be integers or slices, not tuple

Deep copying

.copy() only performs a shallow copy — nested mutable elements (like inner lists) are still shared between the original and the copy:

>>> ass = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> bss = ass.copy()
>>> bss[0][0] = 0
>>> bss
[[0, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> ass
[[0, 2, 3], [4, 5, 6], [7, 8, 9]]   # ass was changed too!

A true independent copy of nested structures needs a deep copy, which isn’t built into list — see copy.deepcopy.

Slicing

>>> xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> xs[3:6]
[3, 4, 5]
>>> xs[::2]
[0, 2, 4, 6, 8]
>>> xs[7:2:-2]
[7, 5, 3]

Type hints

Type-hinting the elements of a list (e.g. list[int]) is a feature new in Python 3.9 and greater.

Unpacking into function arguments

A list can be “unbracketed” into positional arguments with *:

>>> def f(x, y, z):
...     return x + y + z
>>> xs = [1, 2, 3]
>>> f(xs)
TypeError: f() missing 2 required positional arguments: 'y' and 'z'
>>> f(*xs)
6

Python Operator Precedence and Associativity

Syntax vs. semantics

Each rule below has two parts:

• Syntax — what makes the expression a valid Python program.
• Semantics — what the expression evaluates to.

Constants and brackets

• A constant (e.g. 2) is the most basic expression.
• If x is a valid expression then (x) is also a valid expression — bracketed expressions get evaluated first. Whitespace inside brackets is ignored, and brackets can nest arbitrarily (((2))).
• An unmatched closing bracket (2)) is a SyntaxError.

Negation and affirmation

• If x is a valid expression then +x and -x are valid expressions.
• +x is equivalent to multiplying x by 1; -x is equivalent to multiplying x by -1.
• These can be chained (--3 is 3, +-+-+-3 is -3), but a trailing operator with nothing after it (3+) is a SyntaxError.

Arithmetic operators

If x and y are valid expressions, then all of the following are valid expressions, evaluated according to the rules of math:

Operator	Meaning
x + y	Addition
x - y	Subtraction
x * y	Multiplication
x / y	Division
x // y	Integer (floor) division
x % y	Remainder
x ** y	Exponentiation

Order of operations

From highest to lowest precedence:

Operator	Description
()	Parenthesis
**	Exponents
-x, +x	Negation, Affirmation
*, /, //, %	Multiplication, Division, Integer Division, Remainder
+, -	Addition, Subtraction

*, /, //, and % share a precedence level, as do + and - — see Associativity below for how ties between operators of equal precedence get resolved.

Associativity

An order of operations alone doesn’t remove all ambiguity — e.g. 1 - 2 + 3 needs a rule for whether it means (1 - 2) + 3 or 1 - (2 + 3). Python evaluates 1 - 2 + 3 as (1 - 2) + 3 = 2, so +/- are left-associative.

Operators of equal precedence are left-associative in general, except exponentiation (**), which is right-associative:

• 3 * 1 // 2 = (3 * 1) // 2 = 1 (left-associative *///)
• 2 ** 1 ** 0 = 2 ** (1 ** 0) = 2 (right-associative **, not (2 ** 1) ** 0 = 1)

In general, if # and @ are operators of equal precedence, a # b @ c = (a # b) @ c (left-associative case).

Division and floats

• / always returns a float, even when the division is exact (4 / 2 is 2.0, not 2) — type(2) is int, type(2.0) is float.
• 1 / 3 gives an approximate result (0.3333333333333333) since floats have finite precision.
• 1 / 0 raises ZeroDivisionError; 1 / float('inf') is 0.0.

Exponentiation edge cases

• 2 ** 3 is 8 (int); 2 ** 3.0 is 8.0 (float) — a float exponent/base produces a float result.
• 2 ** -1 is 0.5.
• 2 ** 0 and 0 ** 0 are both 1.

Warning: ^ is not exponentiation

The caret ^ is Python’s bit-wise xor operator, not exponentiation — e.g. 2 ^ 3 is 1 and 4 ^ 1 is 5. Using ^ where you meant ** does not raise an error, so this mistake can silently produce wrong results.

Integer division (the division algorithm)

For positive integers x and y, there is a unique quotient q and remainder r (with 0 <= r < y) satisfying x = q * y + r — “grade school” division. E.g. for x = 17, y = 3: 17 = 5 * 3 + 2, so 17 // 3 is 5 (the quotient) and 17 % 3 is 2 (the remainder), and 3 * (17 // 3) + (17 % 3) == 17.

The division algorithm can be computed directly (repeated subtraction) or recursively:

def remainder(x: int, y: int) -> int:
    ans = x
    while ans >= y:
        ans = ans - y
    return ans

def remainder(x: int, y: int) -> int:
    return x if x < y else remainder(x - y, y)

Both give remainder(17, 7) == 3.

Python PEP8 Style Guide

A PEP (Python Enhancement Proposal) is a design document describing conventions for how to style code. This course follows Google’s PEP, a variant of PEP8.

Variable and function names

Names must start with a letter (not a digit) and can otherwise only contain letters, digits, and underscores (_). Names should be lowercase, with words separated by underscores for readability:

Yes	No
descriptive_variable_name	DescriptiveVariableName

Spacing

Put single spaces around binary operators; don’t pad the inside of brackets:

Yes	No
i = i + 1	i=i+1
hypot2 = x*x + y*y	hypot2 = x * x + y * y
c = (a+b) * (a-b)	c = (a + b) * (a - b)

Breaking long lines

All lines should be strictly less than 80 characters wide. Wrap a long expression in a redundant enclosing bracket so it can be split across multiple lines (otherwise pressing enter would evaluate the expression early):

>>> income = (gross_wages
...           + taxable_interest
...           + (dividends - qualified_dividends)
...           - ira_deduction
...           - student_loan_interest)

Comments

Anything following a # is ignored by Python. Comments (and docstrings, see python-functions) should explain why something not obvious was done, not simply restate what the code already shows:

x = x + 1   # Not helpful: Increment x
x = x + 1   # Helpful: Compensate for border

Python Primitive Data Types

The types “built-in” to Python by default are called primitive data: booleans, integers, floats (not covered here), strings, and tuples.

Booleans

The boolean type comprehensively provides the values True and False (type(True) and type(False) are both bool).

Comparison operators

All comparison operators have equal precedence and are left-associative; when mixed with arithmetic, comparison is evaluated last.

Operator	Description
==	Equal
!=	Not equal
<, <=	Less than, less than or equal
>, >=	Greater than, greater than or equal

>>> 3 + 2 > 1 + 3   # arithmetic first
True
>>> 3+2 > 1+3       # better to group like this
True
>>> 3 + (2>1) + 3   # True has int value 1
7

Logical connectors

Functions that return booleans are called predicates. More sophisticated predicates can be built with the logical connectors and, or, and not (covered in detail in the if-statement lecture).

bool — truthy / falsy

Any object can be converted to a boolean with bool. Data that converts to True is truthy; data that converts to False is falsy — usually the falsy element is whatever acts as zero for the type, and everything else is truthy.

>>> bool(0)
False
>>> bool(1)
True

Integers

An integer is a number without a fractional part — zero, positive, or negative. Integers are unbounded in Python, so we can work with arbitrarily large integers without overflow (which is unusual amongst languages):

>>> 2 ** 256 - 1
115792089237316195423570985008687907853269984665640564039457584007913129639935

Booleans convert to integers with int (True behaves as 1, False as 0):

>>> int(True)
1
>>> int(False)
0
>>> True + False
1
>>> True * False
0

Strings

A string is (with some exceptions) anything enclosed by single- or double-quotes — an ordered collection of the characters (e.g. unicode/ascii) the computer allows.

>>> "hello world"
'hello world'
>>> type("hello world")
<class 'str'>
>>> hello world   # note the lack of quotes
SyntaxError: invalid syntax
>>> hello         # note the lack of quotes
NameError: name 'hello' is not defined

str conversion and formatting

>>> str(1)
'1'
>>> str(True)
'True'

Formatted strings (f"...") substitute variables into a string:

>>> x = 1
>>> y = "two"
>>> f"x is {x} y is {y}"
'x is 1 y is two'
>>> print(f"x is {x} y is {y}")
x is 1 y is two
>>> f"{x}"   # alternative to str
'1'

Concatenation and scalar multiplication

Adding strings creates a new string; multiplying a string by a positive integer repeats it:

>>> "hello" + "world"
'helloworld'
>>> space = " "
>>> "hello" + space + "world"
'hello world'
>>> 3 * "Hello World!"
'Hello World!Hello World!Hello World!'

Comparing strings

Strings compare lexicographically by character order (ord/chr give a character’s order and the character at an order):

>>> "a" < "b"
True
>>> ord("a"), ord("b")
(97, 98)
>>> chr(97)
'a'
>>> "A" < "a"
True
>>> "Z" < "a"
True

A shorter string is less than an extension of itself, but otherwise comparison proceeds character-by-character:

>>> "a" < "aa"
True
>>> "b" < "aa"
False
>>> "aba" < "ab"
False
>>> "aZ" < "aa"
True

The lecture previews an exercise (string_less_than(cs, ds), restricted to comparing integer character codes) that it explicitly defers (“we will return to this”) without giving a worked solution — flagged here rather than invented.

Escape characters

\n (new line) and \t (tab) are escape characters — a string can be stored differently than it is printed:

>>> print("hello\nworld")
hello
world
>>> print("hello\tworld")
hello   world

Tabs display as a fixed amount of horizontal space, but exactly how much depends on the program displaying them.

Numbers versus strings

+ does not silently convert between int and str — mixing them raises a TypeError:

>>> "3" + "7"
'37'
>>> 3 + "7"
TypeError: unsupported operand type(s) for +: 'int' and 'str'
>>> str(3) + "7"
'37'
>>> 3 + int("7")
10

int()/float() only work on strings that are actually numbers expressed as digits:

>>> int("3.14")
ValueError: invalid literal for int() with base 10: '3.14'
>>> float("123.456")
123.456
>>> int("seven")
ValueError: invalid literal for int() with base 10: 'seven'

Length and inclusion

>>> len("hello")
5
>>> cs = "world"
>>> len(cs+"world") == len(cs) + len("world")
True
>>> "h" in "hello world"
True
>>> "ow" in "hello world"
False

Indexing and slicing

Strings are ordered, so characters are numbered from zero and accessed with square brackets. Negative indices count from the end:

>>> cs = "hello world"
>>> cs[0]
'h'
>>> cs[-1]
'd'
>>> cs[len(cs)]
IndexError: string index out of range

A slice cs[start:stop:step] grabs the start-inclusive, stop-exclusive characters, stepping by step (default 1); omitted endpoints default to the whole string in that direction, and a negative step reverses direction:

>>> cs = "0123456789"
>>> cs[1:4]
'123'
>>> cs[:-1]
'012345678'
>>> cs[::2]
'02468'
>>> cs[::-1]
'9876543210'

Immutability

Strings are immutable — they cannot be changed in place:

>>> cs = "hello"
>>> cs[0] = "H"
TypeError: 'str' object does not support item assignment

Strings as booleans

>>> bool("Hello")
True
>>> bool("")
False

The empty string is “smaller” than every other string under comparison ("" < "A" is True) — note it is distinct from a single space (len(" ") == 1, bool(" ") == True).

Tuples

A tuple is an immutable ordered collection of elements — elements need not share a type or be distinct. Round brackets () construct tuples.

>>> xs = (0, 1, 2, 3, 4, 5)
>>> type(xs)
<class 'tuple'>
>>> xs[-1]
5
>>> xs[0:4]
(0, 1, 2, 3)
>>> xs[0] = -1
TypeError: 'tuple' object does not support item assignment

Tuples support the same +/scalar-multiplication as strings:

>>> xs = (1, 'a', 2, 'b')
>>> ys = (3, 'c', 4, 'd')
>>> xs + ys
(1, 'a', 2, 'b', 3, 'c', 4, 'd')
>>> 2*xs
(1, 'a', 2, 'b', 1, 'a', 2, 'b')

Nomenclature

Tuples are named by size: couple (2), triple (3), quadruple (4), quintuple (5), sextuple (6), septuple (7), octuple (8), … an n-tuple in general ((0, 1, 2, ..., n-1) isn’t valid Python syntax itself — it’s just informal notation for the pattern).

Singleton and empty tuples

A single value in round brackets without a trailing comma is not a tuple — it’s just that value in parentheses. The trailing comma is what makes it a tuple:

>>> type((1))
<class 'int'>
>>> type((1,))
<class 'tuple'>
>>> (1,) + (2,)
(1, 2)
>>> (1) + (2,3)   # common error
TypeError: unsupported operand type(s)

The empty tuple () is falsy:

>>> type(())
<class 'tuple'>
>>> () + (1,)
(1,)
>>> bool(())
False

Comparing tuples

Tuples compare element-by-element, lexicographically (like strings) — a shorter tuple is less than a longer tuple that extends it:

>>> (1, 2, 3) == (1, 2, 3)
True
>>> (1, 2, 3) < (1, 2, 4)
True
>>> (1, 2) < (1, 2, 3)
True

Packing and unpacking

Multiple assignment/printing in one line, via an (implicit) tuple:

>>> x, y, z = 2, 3, 4
>>> x, y, z
2, 3, 4

Python Recursion

A recursive function is a function that calls itself. Every recursion needs at least one of each:

• Base case: a case defined outright, with no further recursive call (if base_case: return constant).
• Recursive step: a line where the function calls itself on “smaller” input, making progress toward a base case.

Canonical example: factorial

def fact(n: int) -> int:
    if not n:              # base case
        return 1
    return n * fact(n-1)   # recursive step

Evaluation has two phases:

• Winding: recursive calls build up a stack of pending computations (4 × (3 × (2 × (1 × fact(0))))).
• Unwinding: once the base case is hit, each pending computation resolves from the inside out.

If a base case is never reached, the recursion “bottoms out” with a RecursionError: maximum recursion depth exceeded once Python’s call stack limit (1000 by default) is hit. This limit can be raised with sys.setrecursionlimit(n), which is sometimes necessary for algorithms that legitimately need deeper recursion (as opposed to a genuine infinite recursion bug).

Choosing base cases

Type	Typical base case
int (counting down)	0
list	[]
str	'' (empty string)

For less obvious base cases, consider the smallest example that still needs one recursive call (the singleton case), and work out what value the base case must return for that example to behave correctly.

Linear vs. tree recursion

Most recursive functions make a single recursive call per invocation (linear recursion, e.g. fact, is_palindrome). Some make more than one (tree recursion), e.g. checking whether any sublist sums to a target:

def sublist_sum(xs: list[int], target: int) -> bool:
    if not xs:
        return not target
    return sublist_sum(xs[1:], target-xs[0]) or sublist_sum(xs[1:], target)

Tree recursion can recompute the same subproblem many times. Dynamic programming — caching previous results — avoids this when subproblems overlap heavily (the classic example being naive recursive Fibonacci, which is exponential without a cache but linear with one).

Relationship to induction

Recursion is essentially the Principle of Mathematical Induction realised as code: a base case (the \(P(0)\) case) plus a step that reduces a general case to a smaller one already known to work (the \(P(n) \implies P(\text{succ}(n))\) step).

See python-scope for how local variables/recursive calls interact with scope, and python-composition/python-inheritance for other structuring tools. See towers-of-hanoi for a worked induction/recursion example.

Python Representation Invariants

A representation invariant is a condition or property that must remain true about an object’s internal state throughout its lifetime. They’re primarily a development-time tool: they help catch bugs early, simplify method implementations (since you can assume a valid starting state), and document the assumptions a class relies on.

Documenting invariants

State invariants in the class docstring, underneath its attributes:

class Fraction():
    """Represents a mathematical fraction.

    Representation Invariants:
    - denominator != 0
    - if fraction is zero, it is represented as 0/1
    """

Enforcing invariants

Assertions

assert <condition that should be true>, "message if it's not"

• Raises AssertionError if the condition is false.
• Disabled when Python is run with optimization (python -O) — so asserts should catch bugs, not perform real input validation that must always run (use raise ValueError(...) etc. for that).

The _check_invariants() helper pattern

Centralise all invariant checks in one private method, and call it:

• At the end of __init__.
• At the end of any method that mutates state.
• At the start of any method that relies on the invariants already holding.

def _check_invariants(self) -> None:
    assert self._denom != 0, "Denominator cannot be zero."
    ...

Encapsulation: don’t expose mutable internals

Returning a direct reference to a private mutable attribute (like a list or dict) lets external code silently violate the class’s invariants:

def get_members(self):        # BAD -- exposes the real list
    return self._members

def get_members(self):        # GOOD -- caller gets an independent copy
    return list(self._members)

Best practices

• Document invariants in docstrings.
• Centralise invariant checking in a single method.
• Don’t expose methods/attributes that could let external code violate invariants.
• Write test cases that target edge cases.
• Type hints can express some invariants, but not all (e.g. numeric ranges still need explicit checks).
• Balance strictness with practicality — not every property needs an assertion.

Python Scope

The scope of a name is the region of code where that name is recognized. Python resolves names using the LEGB rule, searching in order:

1. Local — the current function.
2. Enclosing — an outer function, for nested functions.
3. Global — the module’s top-level variables.
4. Built-in — Python’s built-in names.

If a name isn’t found at any level, Python raises a NameError.

Global variables

Defined outside any function (module level); accessible everywhere in the module provided no local variable shadows the name. Avoid globals where possible — they make code harder to maintain. Constants are conventionally named in SNAKE_CASE_CAPS, but Python does not actually protect their value from being reassigned.

Local variables and shadowing

Assigning to a name anywhere inside a function body makes that name local to the entire function — even before the assignment line executes. This causes two common gotchas:

• Shadowing: a local variable (or parameter) with the same name as a global temporarily hides the global inside that function.
• UnboundLocalError: if a function reads a name before assigning to it, and also assigns to that same name later in its body, Python treats it as local throughout — so the read fails, because the local doesn’t have a value yet.

The global keyword

Declares that a name inside a function refers to the module-level variable, rather than creating a local shadow:

def foo():
    global x
    x = x + 1

A name cannot be declared as both a function parameter and global in the same function — this is a SyntaxError.

Python String Methods

Strings are objects with built-in methods — callable via obj.method() syntax, unlike free functions. Review all of them with help(str), or a specific one with help(str.<name>).

Reading a method’s help

Square brackets in a signature indicate optional parameters, and the rule recurses:

S.find(sub[, start[, end]]) -> int

means sub is required, start is optional, and end is optional but only meaningful once start is given.

Common string methods

Method	Description
s.find(sub[, start[, end]])	Lowest index where sub occurs in s[start:end], or -1
s.title()	Title-cased version of s
s.center(width, fillchar=' ')	Centre s in a string of length width
s.split(sep=None)	Split s on sep (default: any whitespace) into a list
sep.join(xs)	Join a list of strings xs, placing sep between each
s.strip(chars=None)	Remove leading/trailing whitespace (or chars) from s

>>> "team".find("I", 1, -1)
-1
>>> "a tale of two cities".title()
'A Tale Of Two Cities'
>>> "spam".center(10, "x")
'xxxspamxxx'
>>> "a, b, c".split(", ")
['a', 'b', 'c']
>>> "xxx".join(["A", "B", "C"])
'AxxxBxxxC'
>>> "  123  \n".strip()
'123'

Python Testing (doctest & Assertions)

doctest

A docstring test is an >>> example embedded in a function’s docstring. doctest.testmod() actually runs every such example in the current module and reports failures:

>>> import doctest
>>> doctest.testmod()
TestResults(failed=0, attempted=2)

doctest.testfile(path) instead runs every >>> example found in an arbitrary text file (useful for a test suite kept outside the functions being tested).

Doctest compares printed strings, not values

doctest compares Python’s exact printed output against the expected text — not whether two values are ==. identity(1.0) printing 1.0 will not match an expected 1, even though 1.0 == 1.

Consequences:

• Whitespace matters — [ ] != [], and Python always prints , (comma-space) inside collection literals.

• Unordered types (set, dict) don’t have a guaranteed print order for non-numeric elements — compare with == inside the doctest instead of relying on printed order:

  >>> {3, 1, 2} == some_function({1, 2, 3})
  True

• Floats are inexact — compare with a tolerance instead of exact equality:

  >>> abs(f(x) - expected) < 10**-3
  True

Writing a comprehensive doctest

1. Typical cases and edge cases.
2. The zero of the data type (0, [], "").
3. The singleton of the data type (1, [1], "a").
4. Correctness, not contract violations (don’t test precondition failures).
5. No redundant tests.

Assertions

assert <condition> raises AssertionError (halting the program) if <condition> is false — useful for catching impossible situations as soon as they occur, rather than letting them silently propagate:

assert ans > 0   # all factorials are positive/non-zero

assert False documents a line that should be unreachable (e.g. after an exhaustive if/else).

Python Variables and Memory Model

Memory

Computer memory is a very long series of on/off switches, called bits (short for binary digit). Eight consecutive bits form a byte; 4 or 8 bytes form a word (depending on machine architecture).

We put something in memory by toggling the bits into some meaningful configuration — in Python, the “somethings” we put in memory are called objects.

Interpreting memory: the integer type

A word of memory can be interpreted as an arithmetic expression in binary — e.g. \(1 \cdot 2^{32} + 1 \cdot 2^{31} + 1 \cdot 2^{30} + 0 \cdot 2^{29} + \cdots + 1 \cdot 2^0 = 3{,}931{,}377{,}233\).

When Python executes x = 3931377233 it toggles the bits at x’s memory location to this value and remembers to interpret that region as an (unsigned 32-bit) integer — its type. A value’s type ultimately dictates which functions are compatible with it.

Addresses and id

Memory is divided into addressed words. We can determine any object’s address with id:

>>> 42
42
>>> id(42)
4384160760

Variables

A variable is a nickname we give to an address in memory.

Assigning

>>> x = 3931377233
>>>

Assignment toggles the bits at the memory location nicknamed x. Nothing is printed, because the imperative here is to perform an action (a state change to memory), not to evaluate an expression.

Retrieving

Once x has been assigned a value, we retrieve it by evaluating it in the REPL — a variable evaluates to the value it was assigned, and can stand in for that value inside larger expressions:

>>> x
3931377233
>>> x // 100
39313772

Evaluating a name that has never been assigned raises a NameError:

>>> bear
NameError: name 'bear' is not defined

Meaningful names

Variable names should convey meaning. x = 2; y = 3; z = x*y is not meaningful, but width = 2; height = 3; area = width*height is — and area keeps working even after width/height change, which is another reason we use variables that can vary.

Naming rules

Variable names must start with a letter (a-z, A-Z) or underscore (_). Starting a name with a digit is a SyntaxError; digits are otherwise allowed.

>>> 1 = "one"
SyntaxError: cannot assign to literal
>>> x1 = 1
>>>

Reassignment

= in Python means assignment (“gets”), not mathematical equality:

>>> x = 1        # x "gets" 1
>>> x = x + 1    # x "gets" x+1
>>> x
2

In mathematics, \(x = x + 1 \implies 0 = 1\), a contradiction — so this would be an “illegal” statement. In Python it’s perfectly valid, because = is a one-time action performed left-to-right, not a persistent equality claim.

Python While Loops

A loop is a control structure that repeats code that belongs to it. A while-loop is a loop that repeats code while some condition is satisfied:

while <condition>:
    <code>

The condition is checked before every repetition (including the first) — if it’s false to begin with, the loop body never runs at all:

>>> x = 0
>>> while False:
...     print(x)
...     x += 1
>>> # nothing prints

Augmented assignment operators

Operator	Equivalent to
x += y	x = x + y
x *= y	x = x * y
x /= y	x = x / y
x %= y	x = x % y

break

The break keyword terminates the (innermost) loop immediately and continues with the rest of the program:

>>> while True:
...     print("hello")
...     break
...     print("world")
hello

Simulating a do-while

A do-while (or repeat-until) is a while-loop variant, available in other languages but not natively supported in Python, that runs its code at least once before checking the condition:

do:
    <code>
while <condition>   # not valid Python syntax

We can simulate one with while True (some programmers prefer 1 to True) and a break:

>>> x = 0
>>> while 1:
...     x += 1
...     if x > 0:
...         break
>>> x   # x retains its value outside the while
1

User input

x = input() waits for input from the keyboard and assigns it to x, always with type(x) is str.

Random number generation

Random number generation is handled by an external library (not built-in), so it must be imported:

>>> from random import randint
>>> randint(1, 6)   # chosen uniformly over the interval
2

or, importing the entire library:

>>> import random
>>> random.randint(1, 6)
2

UML Class Diagrams

UML (Unified Modelling Language) diagrams are the standard, language-agnostic way of visually describing the classes in a system and the relationships between them — useful for planning a design before writing code, and for communicating that design to others.

Class boxes

A class box has three parts:

ClassName
-----------------------
attributes
-----------------------
methods()

Each attribute/method is prefixed with a visibility marker:

Symbol	Visibility
-	private
+	public
#	protected

Relationship types

Relationship	Line style	Meaning
Inheritance	solid line, hollow (open) triangle arrowhead pointing to the parent	“is-a” — subclass inherits from superclass
Association	plain solid line	one class uses/references another, without ownership
Aggregation	solid line, hollow (open) diamond at the “whole” end	weak “has-a” — the part can exist independently of the whole
Composition	solid line, filled (solid) diamond at the “whole” end	strong “has-a” — the part cannot exist independently of the whole

Multiplicity

Multiplicity annotations on association/aggregation/composition lines describe how many objects on each end participate in the relationship:

Notation	Meaning
0..1	zero to one
n	an exact number
0..*	zero to many
1..*	one to many
m..n	a specific range

Why use UML?

• Plan a class hierarchy/object graph before writing any code.
• Communicate a design to teammates without needing to read source code.
• Document the intended structure and relationships for future maintenance.
• Class diagrams are the most commonly used UML diagram type in object-oriented design, but UML also includes other diagram types (e.g. sequence diagrams, use-case diagrams) not covered here.