Three ways a program lets you down

Until now your programs have lived in an ideal world: the input is always valid, the data is always clean, the size is always small.

The real world is not like that. Programs disappoint in three ways:

The three look unrelated but are one question wearing three hats: how do you know your program actually works?

---

I. Too slow: complexity

Why not just use a stopwatch

The obvious way to find out whether an algorithm is fast is to time it:

import time

def sum_to(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    return total

for n in [10_000, 100_000, 1_000_000]:
    t = time.perf_counter()
    sum_to(n)
    print(f"n = {n:>9,}  took {time.perf_counter() - t:.4f} s")

That number is useful, but it cannot compare algorithms, because it depends on the machine, what the CPU is doing at that moment, the Python version, and whether you have other programs open.

We need a measure that is independent of the machine.

Count steps, not seconds

Instead: count how many basic operations the algorithm performs. A basic operation is arithmetic, a comparison, an assignment, an index — anything that takes one step.

def sum_to(n):
    total = 0            # 1 step
    for i in range(n):   # n iterations
        total += i       # 1 step each
    return total         # 1 step

About n + 2 steps.

Another:

def has_duplicate(items):
    for i in range(len(items)):        # n times
        for j in range(len(items)):    # n times each
            if items[i] == items[j]:   # 1 step
                ...

That is n × n = n² steps.

The essential difference is how they grow as n increases.

Multiply n by ten and the first grows tenfold; the second grows a hundredfold.

Big-O notation

Since only the trend at large n matters:

• keep the fastest-growing term: n² + 3n + 5 → n²
• drop constant factors: 5n and 100n are both n

Written O(...):

• n + 2 → O(n), linear
• n² → O(n²), quadratic
• 3 → O(1), constant (independent of n)

Why can the constants go? Because once the order differs, no constant can compensate:

for n in [10, 100, 1000, 10000]:
    linear = 100 * n
    quadratic = n * n
    winner = "O(n) wins" if linear < quadratic else "O(n^2) wins"
    print(f"n={n:>6}  100n = {linear:>10,}   n^2 = {quadratic:>12,}   {winner}")

Past n = 100 the O(n) version never loses again. That is why the order matters more than the constant.

The common orders

Fastest to slowest:

import math
print(f"{'n':>8} {'log n':>7} {'n':>8} {'n log n':>11} {'n^2':>14}")
for n in [10, 1000, 100000]:
    print(f"{n:>8} {math.log2(n):>7.1f} {n:>8,} {n*n*math.log2(n):>11,.0f} {n*n:>14,}")

The cost of Python’s operations

This table is worth memorizing:

This is behind L6’s claim that lists search slowly and sets search fast:

import time

n = 30_000
data_list = list(range(n))
data_set = set(data_list)

t = time.perf_counter()
for x in range(0, n, 100):
    x in data_list
list_time = time.perf_counter() - t

t = time.perf_counter()
for x in range(0, n, 100):
    x in data_set
set_time = time.perf_counter() - t

print(f"list in: {list_time:.4f} s")
print(f"set  in: {set_time:.6f} s")
print(f"ratio: {list_time / set_time:,.0f}")

Double the length of the list and the search time roughly quadruples; the set barely moves. This time the conclusion has data behind it.

Is concatenating in a loop actually slow?

Lab 4’s triangle problem, and a great many textbooks, say that s += w in a loop is O(n²) and you should use join. That claim needs a qualifier.

Measure it first:

import time

words = ["hello"] * 80_000

t = time.perf_counter()
s = ""
for w in words:
    s += w
plain = time.perf_counter() - t

t = time.perf_counter()
keep = []
for w in words:
    keep.append(keep[-1] + w if keep else w)
kept = time.perf_counter() - t

t = time.perf_counter()
s2 = "".join(words)
joined = time.perf_counter() - t

print(f"plain s += w:        {plain:.5f} s")
print(f"keeping every prefix:{kept:.4f} s")
print(f"join:                {joined:.6f} s")
print(f"same result: {s == s2 == keep[-1]}")

What comes out is that the plain s += w loop and join land in the same range, while the version that keeps every intermediate result is three orders of magnitude slower.

The reason is a CPython implementation detail: when a string has exactly one reference, s += w can extend it in place instead of copying the whole old string each time. The moment an intermediate result is referenced by another name or held in a container, that optimization no longer applies, every step has to build a fresh string and copy the old contents, and the total cost degrades to quadratic.

Write the conclusion as “it depends on whether other references exist”, not as “concatenation in a loop is always quadratic”. In your own code, still prefer join: it does not rely on that implementation detail, and it is linear under every implementation and every reference pattern.

Why binary search is O(log n)

L7 wrote binary search and deferred the complexity to here.

Each comparison halves the range: n → n/2 → n/4 → … → 1.

The question is: how many halvings take n down to 1? That is log₂ n.

import math
for n in [100, 1_000, 1_000_000, 1_000_000_000]:
    print(f"{n:>15,} elements need at most {math.ceil(math.log2(n)):>2} comparisons")

A billion elements, thirty comparisons. That is what logarithmic complexity buys, and why sorted data is so valuable.

Space complexity

The same notation describes memory.

# O(1) space: a few variables regardless of n
def sum_loop(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    return total

# O(n) space: builds a list of length n
def sum_list(n: int) -> int:
    return sum([i for i in range(n)])

print(sum_loop(1000), sum_list(1000))

L13 shows how generators bring O(n) space back down to O(1).

How to improve complexity

In order of effectiveness:

1. change the algorithm: O(n²) to O(n log n) is a change of order
2. change the data structure: list lookup to set lookup is O(n) to O(1)
3. avoid recomputation: memoization, which section IV develops
4. use built-ins: sum(), sorted(), "".join() are implemented in C and run an order of magnitude faster than a Python loop

import time
n = 2_000_000

t = time.perf_counter()
total1 = 0
for i in range(n):
    total1 += i
loop_t = time.perf_counter() - t

t = time.perf_counter()
total2 = sum(range(n))
builtin_t = time.perf_counter() - t

print(f"hand-written loop: {loop_t:.4f} s")
print(f"built-in sum:      {builtin_t:.4f} s")
print(f"{loop_t / builtin_t:.1f}x faster (both O(n); the difference is the constant)")

---

II. It crashes: exceptions

Syntactically valid, still fails

x = 10
y = 0
print(x / y)

That code is entirely valid and compiled without complaint, but failed at run time. An error that occurs during execution is an exception.

Left unhandled, it terminates the program — not one further line runs. The last line of the traceback gives the exception type and message; the lines above it point at where things went wrong.

Two more common runtime failures:

value = 4
print(value + spam * 3)

text = "2"
print(text + 2)

NameError says a name was never defined; TypeError says two types cannot be combined that way. What they share is that neither names nor types can be checked ahead of time — only actually executing that line reveals the problem.

try / except

def safe_divide(a: float, b: float) -> float | None:
    try:
        return a / b
    except ZeroDivisionError:
        print("cannot divide by zero")
        return None

print(safe_divide(10, 2))
print(safe_divide(10, 0))
print("the program continues")

The try body runs normally; the moment an exception is raised, control jumps to the matching except.

Catch specific exceptions

def parse_age(text: str) -> int | None:
    try:
        return int(text)
    except ValueError:
        print(f"'{text}' is not an integer")
        return None

for s in ["18", "abc", "3.14", ""]:
    print(s, "->", parse_age(s))

This closes the loop from L3, where non-numeric input crashed the program and I said L11 would fix it.

Several except clauses

def get_item(data: dict[str, list[int]], key: str, index: int) -> int | None:
    try:
        return data[key][index]
    except KeyError:
        print(f"no key {key}")
    except IndexError:
        print(f"index {index} out of range")
    except TypeError as error:
        print(f"wrong type: {error}")
    return None

d = {"a": [1, 2, 3]}
print(get_item(d, "a", 1))
print(get_item(d, "b", 0))
print(get_item(d, "a", 10))

At most one clause runs — the first one, top to bottom, that matches.

else and finally

def divide(a: float, b: float) -> None:
    try:
        result = a / b
    except ZeroDivisionError:
        print("   failed")
    else:
        print(f"   succeeded, result {result}")   # only when nothing was raised
    finally:
        print("   cleanup")                        # always

print("10 / 2:")
divide(10, 2)
print("10 / 0:")
divide(10, 0)

• else runs when the try body raised nothing. Put “things to do only on success” here
• finally runs regardless. Put cleanup here — closing files, dropping connections

finally even beats return:

def f() -> str:
    try:
        return "returned from try"
    finally:
        print("   finally ran anyway")

print(f())

raise: throwing your own

def set_age(age: int) -> int:
    if age < 0:
        raise ValueError(f"age cannot be negative: {age}")
    if age > 150:
        raise ValueError(f"implausible age: {age}")
    return age

print(set_age(18))
print(set_age(-5))

When should you raise rather than return None?

When the caller must not be allowed to ignore the problem. A returned None is easy to overlook, and the error then surfaces far from its cause. An exception stops immediately, and the traceback points at where it went wrong.

Custom exceptions

class InsufficientFunds(Exception):
    """Not enough money in the account."""
    def __init__(self, balance: float, amount: float) -> None:
        super().__init__(f"balance {balance}, cannot withdraw {amount}")
        self.balance = balance
        self.amount = amount


def withdraw(balance: float, amount: float) -> float:
    if amount > balance:
        raise InsufficientFunds(balance, amount)
    return balance - amount


try:
    withdraw(100, 500)
except InsufficientFunds as error:
    print("caught:", error)
    print("short by:", error.amount - error.balance)

Custom exceptions inherit from Exception — L10’s inheritance earning its keep. The benefit is that a caller can catch precisely this failure rather than every ValueError.

with: automatic cleanup

# the manual version, easy to forget
handle = open("demo.txt", "w", encoding="utf-8")
handle.write("hello")
handle.close()

# the with version, closed automatically
with open("demo.txt", "w", encoding="utf-8") as handle:
    handle.write("hello")
print("closed after the block:", handle.closed)

# an exception inside the block still closes it
try:
    with open("demo.txt", encoding="utf-8") as reader:
        raise ValueError("body failed")
except ValueError:
    print("closed after the exception too:", reader.closed)

with guarantees cleanup on exit — equivalent to a correctly written try...finally. Only when __enter__ returns successfully is __exit__ called at all. Files in full are L12.

Check first, or apologize after

Two styles:

d = {"a": 1}

# style one: Look Before You Leap
if "b" in d:
    print(d["b"])
else:
    print("LBYL: no such key")

# style two: Easier to Ask Forgiveness than Permission
try:
    print(d["b"])
except KeyError:
    print("EAFP: no such key")

Python prefers the second (EAFP), because:

• the normal path costs nothing extra (exceptions only cost when raised)
• it avoids the state changing between the check and the use
• the main line of the code stays clear, with failure handling to one side

But write the simple check when it is simple. if not items: return is far clearer than wrapping things in a try.

---

III. Quietly wrong: assertions and tests

assert: checking what you believe must hold

def average(nums: list[float]) -> float:
    assert len(nums) > 0, "average does not accept an empty list"
    return sum(nums) / len(nums)

print(average([1, 2, 3]))

assert condition, message says: “I believe this must be true here. If it is not, my program has a bug — stop immediately.”

Assertions disappear in optimized mode

print("__debug__ =", __debug__)
print("assert statements:", "enabled" if __debug__ else "removed")

Under normal mode __debug__ is True and assertions run. With the -O flag:

python3 -O myscript.py      # __debug__ becomes False; every assert vanishes

Measured on the average above: in normal mode an empty list raises AssertionError; under -O the assertion is skipped, execution reaches sum([]) / 0, and what comes out is a ZeroDivisionError.

So assertions cannot validate user input. Validating input needs if plus raise, a path that optimization never removes.

Assertions are not exception handling

The most-confused point in the lecture. Keep them apart:

Assertions as executable documentation

def binary_search(sorted_nums: list[int], target: int) -> int:
    assert sorted_nums == sorted(sorted_nums), "the input must be sorted"
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        if sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7], 5))
print(binary_search([1, 3, 5, 7], 4))

That assertion turns the precondition “the input must be sorted” into an executable check. Better than a comment — comments go stale, assertions do not.

A postcondition can be written the same way: the index returned really does hold the target, or −1 was returned and the target really is absent.

pytest: making testing routine

L8 established that tests, not plausibility, decide whether code is correct. We hand-wrote a checking loop there. Here is the standard tool.

Install:

python3 -m pip install pytest

The rules are simple:

• files named test_*
• functions named test_*
• express expectations with assert
• use pytest.raises when you expect a failure

Given mymath.py:

# mymath.py
def add(a: int, b: int) -> int:
    return a + b

def divide(a: float, b: float) -> float:
    if b == 0:
        raise ValueError("cannot divide by zero")
    return a / b

the test file:

# test_mymath.py
import pytest
from mymath import add, divide


def test_add_two_positive():
    assert add(2, 3) == 5

def test_add_negatives():
    assert add(-1, -1) == -2

def test_divide_normal():
    assert divide(10, 2) == 5.0

def test_divide_by_zero():
    with pytest.raises(ZeroDivisionError):   # we expect it to raise
        divide(10, 0)

The last case is deliberately wrong: divide raises ValueError while the test expects ZeroDivisionError. That is what makes it worth reading what pytest prints on failure. The real run:

$ python3 -m pytest -q
.F..                                                                     [100%]
=================================== FAILURES ===================================
_____________________________ test_divide_by_zero ______________________________

    def test_divide_by_zero():
        with pytest.raises(ZeroDivisionError):
>           divide(10, 0)

test_mymath.py:17:
    def divide(a: float, b: float) -> float:
        if b == 0:
>           raise ValueError("cannot divide by zero")
E           ValueError: cannot divide by zero

mymath.py:6: ValueError
=========================== short test summary info ============================
FAILED test_mymath.py::test_divide_by_zero - ValueError: cannot divide by zero
1 failed, 3 passed in 0.01s

Three things come out of that, and you need all three: which test failed, what it expected (ZeroDivisionError), and what actually happened (ValueError). That is what pytest gives you over a hand-written checking loop.

The usual options:

python3 -m pytest              # run everything
python3 -m pytest -v           # name each test
python3 -m pytest -k divide    # only those matching "divide"

What to test

Recalling L8’s edge list, a function deserves at minimum:

• the normal case: typical input
• empty input: empty list, empty string
• a single element
• boundaries: zero, negatives, largest and smallest
• failure: does invalid input raise as it should

def clamp(x: float, lo: float, hi: float) -> float:
    """Constrain x to [lo, hi]."""
    if lo > hi:
        raise ValueError("lo must not exceed hi")
    return max(lo, min(x, hi))


checks = [
    ("inside", clamp(5, 0, 10), 5),
    ("below", clamp(-3, 0, 10), 0),
    ("above", clamp(99, 0, 10), 10),
    ("on the bound", clamp(0, 0, 10), 0),
    ("equal bounds", clamp(7, 3, 3), 3),
]
for name, got, expected in checks:
    print(f"  {'PASS' if got == expected else 'FAIL'} {name}: {got}")

try:
    clamp(5, 10, 0)
    print("  FAIL: no exception raised")
except ValueError:
    print("  PASS: ValueError raised for an impossible range")

Testing code you did not write

This week’s lab hands you a module that is “already written”. Your job is not to change it, it is to write tests from what its documentation promises:

# textstats.py
def word_count(text: str) -> int:
    """Count the words."""
    return len(text.split())

def longest_word(text: str) -> str:
    """Return the longest word. On a tie, the first one."""
    words = text.split()
    return max(words, key=len)

def average_word_length(text: str) -> float:
    """Return the mean word length."""
    words = text.split()
    return sum(len(w) for w in words) / len(words)

All three come with a docstring, and none of them says what happens on an empty string. Measured:

word_count("")             -> 0
longest_word("")           -> ValueError
average_word_length("")    -> ZeroDivisionError

Two of the three fail on an empty string: max() on an empty sequence raises ValueError, and dividing by zero raises ZeroDivisionError.

The inputs the documentation never pins down are exactly where things go wrong. You did not write this module, so the docstrings are your only guide — and the purpose of a test is to write the expectation down first and then see whether the implementation meets it.

How the platform marks your work

---

IV. Five methods and memoization

What the five prime methods cost

This week’s solo assignment implements five ways to count primes over the same range. Their complexities:

The first three share an order and differ in constants; the sieve drops the order but pays for an array of length n.

Complexity describes the shape of growth; the clock also depends on the constant. Measured on the build machine at n = 100000, taking the best of several runs:

(All five return 303 at n = 2000 and 9592 at n = 100000. The counts must agree exactly — that is what “verify correctness before timing” means.)

Square-root pruning and 6k±1 are the same order with constants about three apart; the sieve is fastest throughout and pays for it with that O(n) array. The sieve earns its keep only when you want the count for a whole range; to test whether one large number is prime, Miller–Rabin’s O(1) space and O(log³ n) cost fit better.

Choosing among them

• many numbers over a modest range: the sieve
• one very large number: Miller–Rabin
• this week’s task (n ≤ 100000): any of the three trial divisions finishes; they differ in seconds, not in order

Memoization: exponential down to linear

L7 found that naive Fibonacci needs a quarter of a million calls, and promised a fix here.

First, how bad is the recomputation really:

fib(20) =     6765   calls =    21,891
fib(25) =    75025   calls =   242,785
fib(28) =   317811   calls = 1,028,457

Raising n by 3 multiplies the call count by about 4 while the answer grows by about 3. The cause is the same subproblem being computed over and over.

The remedy is direct: remember what you have already computed.

fib(28) = 317811, calls = 55, cache entries = 27

Same answer, call count down from 1,028,457 to 55, and only 27 entries in the cache — because fib has only 28 distinct subproblems.

Complexity falls from O(2ⁿ) to O(n), since each n is computed once. The price is storing n results: another instance of trading space for time.

The cache key must identify the subproblem

Carrying the same trick over to the coin problem from L7 is easy to get wrong:

key = amount:            129
key = (amount, index):    11

The correct answer is 11; keying on amount alone gives 129.

The reason: ways(amount, coins, index) has two arguments that change. Looking only at amount merges “make 10 using the first two denominations” with “make 10 using all four”, so the cache stores a value that belongs to a different subproblem.

Two conditions make a cache correct:

1. the key identifies the subproblem uniquely — every varying argument goes into it
2. the function returns the same output for the same input — a function depending on the clock, on randomness or on outside state cannot be cached

The corrected version:

ways(100) = 2156, calls = 801, cache entries = 400

With the key written as the tuple (amount, index), the 400 entries are exactly the valid combinations of the two.

functools.lru_cache

The standard library ships the decorator (L14 explains what a decorator is):

fib(10) = 55
cache_info: 8 hits, 11 misses, 11 entries
fib(10) again = 55
hits afterwards = 9
fib(100) = 354224848179261915075

cache_info() reports hits, misses and the number of entries. The second call to fib(10) moves hits from 8 to 9, which is how you know it did not recurse again.

One line of @lru_cache turns exponential into linear. Two things to watch:

• cached arguments must be hashable. Hand it a list and it fails outright:

TypeError: unhashable type: 'list'

Pass a tuple instead — total((1, 2, 3)) — and it returns 6. That is exactly what Q5 tests.

• maxsize caps the number of entries; maxsize=None means no limit. Give it a number and you get LRU eviction: bounded memory, at the cost of recomputing what was evicted.

---

Reference: extended mechanisms, legacy examples and submission details

This section is for after class; it is not part of the ninety minutes.

Worst, best and average case

The same algorithm at the same size can take different amounts of time on different inputs. Searching a list for a value, for instance: the target sitting first and the target being absent differ enormously in how far you scan.

• worst case: the cost of the most expensive input. Unless stated otherwise, this course analyses the worst case
• best case: the cheapest input; usually not worth quoting
• average case: the expectation over all inputs. It requires an assumption about how inputs are distributed, and without that assumption the conclusion does not hold

What the asymptotic notation actually says

O(f(n)) is an upper bound, not an exact step count. n + 2 is written O(n), but n + 2 is also O(n²) — n² really does bound it from above. What we usually write is the tightest such bound.

Two places students go wrong:

• dropping constants is only safe when the input is large enough and the orders differ
• when the orders agree, the constant is the only thing left that matters (square-root pruning versus 6k±1 is exactly this case)

Polynomial evaluation: one formula, different multiplication counts

The naive form raises to a power term by term:

def naive(x, coefficients):
    total = 0
    for power, c in enumerate(coefficients):
        total += c * x ** power
    return total

Horner’s form replaces the powers with repeated multiply-and-add:

def horner(x, coefficients):
    total = 0
    for c in reversed(coefficients):
        total = total * x + c
    return total

The two are mathematically identical, but with 400 coefficients they measured about 37× apart. The difference is not the order (both O(n)) but the number of multiplications per iteration.

The list memory model

Two assumptions:

1. elements are stored contiguously
2. the index and the element correspond one to one

Together they give: a[i] is O(1) (one address calculation), while a.insert(0, x) and a.pop(0) are O(n) (everything after shifts by one). Measured inserting at the front on the build machine:

Double n and the time roughly quadruples — the O(n) operation is itself being performed n times.

Hash tables

Dict and set lookups are O(1) because they compute the storage location with a position function instead of comparing from the front. The price is space for time: the table reserves more slots than it holds elements.

Collisions are real and have standard remedies. This course does not ask you to design a hash function, only to know the contract.

The hash contract

hash(1) == hash(1.0)     -> True
hash(True) == hash(1)    -> True
hash((1, 2))             -> fine
hash([1])                -> TypeError
hash({"a": 1})           -> TypeError

The rules:

• equal objects must have equal hashes. 1 == 1.0 == True, so all three hash the same
• mutable containers are unhashable. Their contents can change; if they could be dict keys, changing the contents would leave the key unfindable
• a class that defines __eq__ and not __hash__ has __hash__ set to None, so its instances cannot be hashed

To use your own objects as dict keys, supply a consistent __eq__ and __hash__ together. The easier route is usually to make the object immutable, or to key on a tuple.

The cost of recursion

Naive recursive Fibonacci, measured:

The call count runs about three times the answer, meaning the overwhelming majority of calls recompute something already known.

There is also a depth limit. sys.getrecursionlimit() measured 1000 on the build machine; past that comes RecursionError. So a naive fib(2000) does not merely run slowly, it crashes — while the memoized version descends only one level at a time and never hits the limit.

Two ways to write the cache

A dictionary (better when the subproblems are sparse):

cache: dict[int, int] = {}

def fib(n: int) -> int:
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    result = fib(n - 1) + fib(n - 2)
    cache[n] = result
    return result

A list (faster when they are dense, but you need a known bound):

def fib(n: int, memo: list[int]) -> int:
    if memo[n] != -1:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

memo = [-1] * (n + 1)

Both are O(n) time and O(n) space; they differ in lookup constants and in how much memory is actually used.

Space and recursion

Each level of a recursive call saves its own state, so naive fib also occupies O(n) of stack. The iterative version finishes in O(1) space:

def fib_iter(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

L13 takes “produce one value at a time instead of building a list” to its limit with iterators and generators.

Forms of raise

raise ValueError("message")       # class plus argument; most common
raise ValueError                  # type only, no message
raise                             # bare raise, re-raise the current exception

A bare raise works only inside an except block, and its purpose is to continue upward with the original traceback:

try:
    ...
except ValueError:
    print("logging this")
    raise          # hand it to the caller without losing the traceback

Exception chaining keeps the cause explicit:

except KeyError as error:
    raise ValueError("the configuration is missing a field") from error

Multiple handlers and the fallback

except (KeyError, IndexError):     # tuple form, two types together

The except clauses of one try do not catch each other’s exceptions. An exception raised inside an except block will not be caught by a sibling clause; it travels upward.

When you need a catch-all:

except Exception as error:
    print("unexpected problem:", error)
    raise

That records the information without swallowing the failure.

Custom exception hierarchies

When a module defines several related exceptions, the usual pattern is a base class plus subclasses:

class ConfigError(Exception):
    """Base class for configuration problems."""

class ConfigMissing(ConfigError):
    """A required field is absent."""

class ConfigFormat(ConfigError):
    """A field has the wrong format."""

A caller can catch ConfigError to take the whole family, or name a subclass for precision. Once L09’s Temperature raises instead of returning False, its interface changes from a value the caller may ignore to a TemperatureError the caller must deal with.

Resource and system errors

with and a hand-written try/finally achieve the same thing, but with is far shorter. One boundary: __exit__ is called only if __enter__ returned successfully, and if __exit__ returns a truthy value the exception propagating out of the block is suppressed. A file object returns falsy on a normal close, so exceptions travel outward as usual.

Inside an except block, sys.exc_info() gives the (type, value, traceback) triple of the current exception; it is mostly for logging.

What float() actually accepts

The old notes treated float("inf") as invalid input. Measurement disagrees:

So “is this string a number” cannot be answered by guessing at formats. Either call float() and catch ValueError, or state precisely which format you accept. Note also that after float("nan"), nan != nan — a comparison trap.

pytest conventions and options

Test files live beside the code or in a tests/ directory and are named test_*. pytest discovers them on its own; nothing has to be registered by hand.

Float comparison deserves its own line: 0.1 + 0.2 == 0.3 measured False, because binary fractions cannot hold those three values exactly. Compare floats with pytest.approx, or allow a tolerance in the assertion.

Why the notes and a real test suite differ

The code blocks in these notes are single-file and reproducible — they run as they are. pytest cannot work that way: it needs to discover files and collect test functions. So this section shows the same idea as a checking loop, and quotes the real pytest output in section III.

Both check the same thing: when the expected value and the actual value disagree, print enough to locate the problem.

The edge-case checklist

At least one case per branch. When an AI helps you add cases, still list this table yourself first — L8 found that “empty” and “one” are the two an AI most often misses.

How textstats behaves under test

The docstrings say “return the longest word” and “return the mean word length”; neither pins down the empty string. That is what a test is for: put the unpinned-down input on the table and make the discrepancy a visible fact, rather than reading the implementation first and writing a test that is guaranteed to pass.

The five prime methods in full

Brute trial division

def count_primes_brute(n: int) -> int:
    count = 0
    for p in range(2, n):
        for d in range(2, p):
            if p % d == 0:
                break
        else:
            count += 1
    return count

The for...else earns its keep here: else runs when the loop was never broken out of, that is, when no divisor was found. O(n²).

Square-root pruning

def count_primes_sqrt(n: int) -> int:
    count = 0
    for p in range(2, n):
        d = 2
        while d * d <= p:
            if p % d == 0:
                break
            d += 1
        else:
            count += 1
    return count

If p has a factor at all, one of them is at most √p, so trial division up to √p suffices. O(n√n).

6k±1 pruning

Rule out multiples of 2 and 3 first; what remains are numbers of the form 6k±1, so the candidate divisors reduce to 5, 7, 11, 13, …:

def count_primes_6k(n: int) -> int:
    if n <= 2:
        return 0
    if n <= 3:
        return 1
    count = 2                      # 2 and 3
    for p in range(5, n):
        if p % 2 == 0 or p % 3 == 0:
            continue
        d = 5
        while d * d <= p:
            if p % d == 0 or p % (d + 2) == 0:
                break
            d += 6
        else:
            count += 1
    return count

The order is unchanged at O(n√n), but roughly two thirds of the trial divisions disappear — measured, about three times faster.

The sieve of Eratosthenes

def count_primes_sieve(n: int) -> int:
    if n <= 2:
        return 0
    flags = [True] * n
    flags[0] = flags[1] = False
    p = 2
    while p * p < n:
        if flags[p]:
            for multiple in range(p * p, n, p):
                flags[multiple] = False
        p += 1
    return sum(flags)

Marking starts at p * p, because smaller multiples were already marked by smaller primes. O(n log log n) time, O(n) space.

Miller–Rabin

Handle the small cases, write n−1 as d × 2ʳ, and test a^d mod n for each base a:

def is_prime_mr(n: int) -> bool:
    if n < 2:
        return False
    for base in (2, 3):
        if n == base:
            return True
        if n % base == 0:
            return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for base in (2, 3):
        x = pow(base, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

The domain has to be stated. With bases 2 and 3 the conclusion is certain for n < 1,373,653. This week’s range, n ≤ 100000, is inside it. It does not generalise to arbitrary large integers — past that bound these two bases are only probabilistic evidence.

pow(base, d, n) is the three-argument built-in, doing modular exponentiation. Each test costs O(log³ n) (the number of digits is log n, and modular exponentiation is cubic in the digits), in O(1) space.

Timing fairly

The numbers in a report have to be comparable, so:

• verify correctness before timing. All five methods must return the same count at the same small size
• fix the size, use one machine, state the environment
• repeat after a warm-up and take the minimum, to avoid scheduler noise
• a slow method may use a size it can finish (brute force, say, only up to 2000), but it may not swap in a different algorithm and pass it off

The figures in this section come from one measurement on the build machine. They are for comparing orders and ratios, not a promise about seconds on your laptop.

The solo assignment 2 specification

As configured, solo assignment 2 covers weeks 10 and 11, its due date reads the shared calendar, and each of the three solo assignments is worth 5%. Complete reference solutions are not published; the markers check that each method is a real implementation.

The seven Lab 11 entry points

The test problem is marked not only on whether the tests pass but on whether they cover empty, single, boundary and invalid input. This week’s lab declares AI use at Level 1.

---

Summary

Complexity

• Measure algorithms by counted basic operations, independent of the machine
• Big-O keeps the highest-order term and drops constants, because a different order always wins eventually
• The ladder: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• Learn Python’s costs: in on a list is O(n); on a set or dict it is O(1)
• The cost of += on strings in a loop depends on whether other references exist; write join, which does not rely on that detail
• Memoization takes overlapping-subproblem recursion from O(2ⁿ) to O(n); the key must contain every varying argument
• Built-ins are faster by a smaller constant and cannot rescue a bad algorithm. Fix the order first

Exceptions

• Valid code still fails at run time; that is an exception
• try / except SpecificType / else (nothing raised) / finally (always)
• Never write a bare except:
• raise throws your own; custom exceptions inherit from Exception
• with guarantees cleanup, equivalent to a well-written try...finally
• Python prefers EAFP over LBYL

Assertions and tests

• Exceptions handle expected external problems; assertions check impossible internal states
• Never catch AssertionError — a failed assertion should crash
• Assertions are skipped under -O, so they cannot validate user input
• assert (condition, message) as a tuple is always true; do not put side effects in an assertion
• pytest: test_-prefixed files and functions, assert for expectations, pytest.raises for failures
• The platform calls your function and compares the return value — so you must return
• Test at least: normal, empty, single, boundary, failure

Exercises

1. Give the time complexity of each and justify it:

   def f1(n): return sum(range(n))
   def f2(a): return [x for x in a if x in a]
   def f3(a): return sorted(set(a))
   def f4(n):
       count = 0
       i = n
       while i > 1:
           i = i // 2
           count += 1
       return count

2. Add memoization to your count_ways (coin combinations) from L7 and measure the speedup. Work out which arguments belong in the key.
3. Write safe_int(text: str, default: int = 0) -> int, returning the default instead of crashing on failure. Catch only specific exception types.
4. What is wrong with this? Fix it:

   def process(filename):
       try:
           f = open(filename)
           data = f.read()
           return int(data)
       except:
           return 0

5. Write a pytest suite for the Stack class you built in Lab 9, covering at least: empty, one element, several elements, and popping an empty stack.
6. Add pre- and postconditions with assert to L7’s binary_search. (Hint: the postcondition can check that the returned index really holds the target, or that −1 was returned and the target really is absent.)
7. Measure it yourself: time 10,000 calls each of list.insert(0, x) and list.append(x) with time.perf_counter() and confirm the O(n) versus O(1) difference.

The lab problems are in Lab 11; the solo assignment is Solo assignment 2.

Sources

• Python 3.13 compound statements: the semantics of try / except / else / finally / with
• Python 3.13 built-in exceptions: the hierarchy and the common types
• functools.lru_cache
• Miller–Rabin primality test: deterministic bases over small ranges