Refresher in Computer Science

Introduction and overview

Independent study notes on the computing foundations used in the Graph × LLM reading route: scientific Python, algorithmic cost, graph representations and reproducible experiments. The catalog identity in the subtitle is a reference point, not a claim of institutional authorship, syllabus equivalence or enrolment advice.

The question this page answers: can you implement, measure and test the small computation before adding a learned model? Four predictions stored as (4,) minus four targets stored as (4,1) produce a (4,4) table, not four residuals. A BFS queue implemented with list.pop(0) can introduce quadratic work. Both failures can survive plausible-looking code.

Empirical first: time a loop against @, compare list and set membership, trace BFS on a toy graph — then explain the shapes, costs and correctness invariants.

Source labels and study budget

• Catalog-reported information: the SynapseS 2026–2027 sheet for CSC_51440_EP, “Scientific courses — Refresher in computer science”, reports 12 h of lectures–tutorials (CTD), period X-3A-P1 (17/09/26–18/12/26), English, with Amal Dev Parakkat listed as responsible. Its description, prerequisite and syllabus tabs are empty, and its assessment section for the LLGA track is empty.

  Total workload and ECTS are not displayed in the available sheet. “Not displayed” does not mean zero, and these notes do not supply an inferred credit value.

  The same 2026–2027 SynapseS listing of the LLGA track also shows a separate CSC_51438_EP “Refresher in Computer Graphics” (Marie-Paule Cani, Pascal Guehl), distinct from this computer-science refresher; these notes do not cover it.

• Suggested independent-work budget: allow approximately 36 h if you choose to work through the full page, code and exercises. This is an adjustable study estimate, not an official total, not additional catalog teaching time and not convertible here into ECTS. A selective refresher can be much shorter. The session plan below shows which chapters fit the 12 h of teaching and which ones belong to this independent work.

• Reading level and role: L3 refresherComputing foundations. These badges describe the reading role, not a verified administrative obligation. Catalog metadata, brochure/curriculum context and independent recommendations are separated in Sources and scope.

Audience: a technical reader already comfortable with basic Python variables, functions and loops, who wants more reliable data/ML code without restarting from a first programming course. Basic matrix notation is useful; the Refresher in Statistics is a complementary mathematical route. An empty catalog prerequisite field is not evidence that no prior knowledge is needed.

What you will be able to check

The list follows the chapter order. Items 1, 2, 4 and 5 are the in-class core (chapters 1, 2, 4 and 5); the others are reached through self-study.

• Write idiomatic Python for data: native structures, functions, iterators, context managers and small pytest suites (chapter 1).
• Vectorize numerical computation with NumPy while controlling shapes, broadcasting, copies and precision (chapter 2).
• Structure a small, rerunnable project with typed interfaces, exceptions, logging, an environment record and version control (chapter 3).
• Predict time and memory costs with big O notation, then check whether the measured bottleneck matches the model (chapter 4).
• Select arrays, linked structures, stacks, queues, hash tables, trees and heaps according to the dominant operations (chapter 5).
• Implement sorting, search and recursion, and reason about correctness by invariants and induction (chapter 6).
• Program graph traversals, shortest paths, connected components and spanning trees, and recognize when exact computation is out of reach (chapter 7).

Session plan

12 h in class = 4 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet for CSC_51440_EP (12 h of lectures–tutorials, CTD); the sheet publishes no session-by-session programme, so the split below is our proposal for the part of these notes that four sessions can cover for students about to start Machine Learning and Deep Learning. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods, 3 = advanced or research material; the level never goes down from one session to the next.

Self-study, outside the 12 h (about 18 h in total): ch. 3 Minimal software engineering: OOP, typing, exceptions, logging, git, environments, Docker, repository template (≈ 3 h) · ch. 6 Sorting, search, recursion (≈ 4 h) · ch. 7 Graph algorithms, including MST code, assignment and P vs NP (≈ 7 h, with Ex. 2, 8, 10, 11, 14 and 15) · ch. 8 Geometric algorithms and research connections, an optional extension (≈ 4 h, with Ex. 13).

These 18 h, together with about 18 h of exercises and revision for the four sessions, make up the approximately 36 h independent-work budget stated above. Chapter 3 sits between the taught chapters because it is easy and applies at once to the code of chapters 1–2: work through it alongside sessions 1–2 rather than at the end. Chapters 6 and 7 are the natural next step for the Graph × LLM route; chapter 8 is optional.

Before you start

Spend 10–15 minutes on these positioning checks. They are routing aids, not a formal assessment. Checks 1 and 2 test the in-class core (chapters 2, 4 and 5); check 3 tests the graph branch, which is self-study (chapter 7). If all three are routine, go directly to the exit checkpoint and return only for a specific gap.

1. Cost and containers. You deduplicate n=10^5 distinct integer identifiers by testing membership in a growing list before appending. What is the total cost? What changes with a set? Would that change also make an explicitly stored all-pairs distance table linear in memory?
   If uncertain: complexity and Python operation costs, §§4.2–4.4 (session 3), then hash tables, §5.2 (session 4).

2. Shapes and shared memory. Let X.shape == (4,3), w.shape == (3,) and y.shape == (4,1). Predict the shapes of X @ w and (X @ w) - y; repair the unintended residual table. Explain why modifying chunk = X[:2] can modify X.
   If uncertain: NumPy broadcasting, views and reductions, §§2.1–2.3 (session 2). Check your understanding with exercise 7 in the exercise set.

3. A graph you can trace. For adj = {0: [1,2], 1: [0,2], 2: [0,1,3], 3: [2]}, give the BFS distances from 0, choose an appropriate queue, and justify the traversal cost. What changes if vertex 4 is added with no edges?
   If uncertain: graph representations and traversals, §§7.1–7.2 (self-study). Exercises 2, 10 and 11 in the exercise set extend this check.

Reading route

This is a reading recommendation, not a course-selection plan. The first row is the in-class core of the session plan; the other rows are self-study. Select material by the checks above and by the computation you need next.

For active study:

• Type and modify the selected code. Snippets with unspecified inputs illustrate interfaces; provide a small fixture before treating them as a runnable experiment.
• Derive the cost from the representation and operations, then measure it. Record array shapes, dtype, hardware and numerical backend for timing comparisons.
• Apply pytest, §1.9, and version control, §3.6, to every later chapter rather than postponing them until the end.
• For the graph branch, redo a BFS and a component test without looking at the solution.
• Use the Statistics refresher for mathematical gaps; the two refreshers need not be read cover to cover or in a fixed order.

Contents

• Introduction and overview
• Before you start
• Reading route
• 1. Python for data science
• 2. NumPy: numerical linear algebra
• 3. Minimal software engineering (OOP, tests, git)
• 4. Complexity analysis
• 5. Fundamental data structures
• 6. Sorting, search, recursion
• 7. Graph algorithms
• 8. Geometric algorithms and research connections
• Exercises
• Exit checkpoint and connections
• Sources and scope
• Projects and assessment
• References

1. Python for data science

Opening scale: on a matrix (n,d)=(10^5,512), a pure-Python loop for Xw can take seconds, while the same NumPy product can fall below ~100 ms on a suitable machine. These are illustrative orders, not portable benchmark results: dtype, BLAS, threads and hardware matter. The matrix alone occupies about 410 MB in float64.

Python is the implementation language used throughout these notes and much of the ecosystem: PyTorch, PyG, Hugging Face, POT, NetworkX and scikit-learn. Basics are assumed; this chapter consolidates the idioms needed to inspect and repair data pipelines. Costs are written informally with the \mathcal{O} notation — \mathcal{O}(n) means work proportional to the input size n — until chapter 4 defines it precisely.

1.1. Essential idioms

import math

tokens = "graphs link text text".split()
vocab = sorted(set(tokens))

# List / dict / set comprehensions
squares  = [x**2 for x in range(10) if x % 2 == 0]
index    = {token: i for i, token in enumerate(vocab)}   # NLP vocabulary
uniques  = {w.lower() for w in tokens}

# Higher-order functions, unpacking, lambda
def softmax(logits):
    m = max(logits)
    exps = [math.exp(z - m) for z in logits]     # numerical stability
    Z = sum(exps)
    return [e / Z for e in exps]

first, *rest = [1, 2, 3, 4]                      # extended unpacking
key_fn = lambda kv: kv[1]                        # sort by value

# dataclasses: clean data objects
from dataclasses import dataclass
@dataclass
class Config:
    lr: float = 1e-3
    batch_size: int = 32

1.2. Decorators

A decorator is a function that takes a function and returns a function — syntactic sugar for wrapping a behavior. They appear throughout the ecosystem: PyTorch torch.no_grad, pytest @pytest.fixture, Flask routes and @functools.lru_cache. Understanding the mechanism makes framework code easier to read; writing custom decorators can wait until needed.

import functools, time

def timing(fn):
    """Measures and prints execution time — a small experiment tool."""
    @functools.wraps(fn)                     # preserves fn's name/docstring
    def wrapper(*args, **kwargs):
        t0 = time.perf_counter()
        out = fn(*args, **kwargs)
        dt = (time.perf_counter() - t0) * 1e3
        print(f"[{fn.__name__}] {dt:.2f} ms")
        return out
    return wrapper

@timing
# Equivalent to train_one_epoch = timing(train_one_epoch).
def train_one_epoch(model, loader):
    ...

# @property: accessor computed on the fly, access without parentheses
class Dataset:
    def __init__(self, x, y):
        self.x, self.y = x, y
    @property
    def n(self):                            # ds.n (not ds.n())
        return len(self.x)

# Parameterized decorator (decorator factory): LRU memoization
@functools.lru_cache(maxsize=None)          # keys = hashable arguments
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)
# Exponential -> linear number of distinct Fibonacci subproblems:
# memoization turns the recurrence into dynamic programming (chapter 6).
# This counts arithmetic operations, not the bit cost of growing integers.

1.3. Generators: the protocol and pipelines

A generator produces its values lazily: computation advances only when values are requested. A stateless element-by-element stage needs \mathcal{O}(1) auxiliary state, but the full pipeline must also account for buffers, current lines and token sizes. Streaming is a practical way to traverse corpora that do not fit in RAM — Wikipedia, Common Crawl or large logs — without materializing the whole corpus.

from itertools import islice

def stream_tokens(path):
    """Generator: yield suspends the function and preserves its state."""
    with open(path, encoding="utf-8") as f:
        for line in f:
            yield from line.lower().split()   # yield from: sub-iterator

def up_to(it, n):
    for x in islice(it, n):                   # no extra item consumed
        yield x

# Pipeline: each step is a generator, data flows element by element
tokens = up_to(stream_tokens("corpus.txt"), 1_000_000)
long_words = (t for t in tokens if len(t) >= 6)   # generator expression
first100 = list(zip(range(100), long_words))

# Full protocol: next() / send / close; in practice one usually loops:
# for tok in stream_tokens(path): ...

1.4. Context managers

# with: guarantee release of a resource (file, session, numerical state)
with open("out.txt", "w") as f:              # closes even on exception
    f.write("done")

# The protocol: __enter__ / __exit__
import contextlib, numpy as np
from copy import deepcopy

@contextlib.contextmanager
def seed_context(rng, seed):
    """Temporarily reseed a NumPy Generator, then restore its state."""
    state = deepcopy(rng.bit_generator.state)
    try:
        rng.bit_generator.state = type(rng.bit_generator)(seed).state
        yield rng
    finally:
        rng.bit_generator.state = state

rng = np.random.default_rng(0)
with seed_context(rng, 42) as local_rng:
    samples = local_rng.normal(size=3)
# The original generator state has now been restored.
# Do not share this temporarily mutated generator across concurrent tasks.

# Standard numerical usage: local error-handling policy
with np.errstate(divide="ignore"):
    z = np.log(np.array([0.0]))             # -inf, but no divide warning

1.5. Advanced dataclasses

from dataclasses import dataclass, field

@dataclass(frozen=True, slots=True)         # frozen fields + less per-object overhead
class HP:
    lr: float = 1e-3
    weight_decay: float = 0.0
    tags: tuple[str, ...] = ()             # immutable, hashable configuration field
    metrics: dict[str, float] = field(
        default_factory=dict, compare=False, hash=False
    )                                     # each instance gets its own dictionary

h = HP(lr=3e-4)
# h.lr = 0.1 -> FrozenInstanceError
# hash(h) works: metrics is excluded from equality and hashing.
# But h.metrics["loss"] = 0.2 is still possible: frozen is not deep immutability.

For larger experiments, separating immutable configuration from mutable results is often clearer. default_factory avoids a shared mutable default; it does not make the resulting object immutable.

1.6. itertools and collections: the toolbox

from collections import Counter, defaultdict, deque
from itertools import chain, islice, product, groupby

# Counter: NLP counting in one line
words = "the cat the dog the cat".split()
c = Counter(words)                    # {'the': 3, 'cat': 2, 'dog': 1}
c.most_common(2)                      # [('the', 3), ('cat', 2)]
# After counting, top-k over v distinct keys typically costs O(v log k).

# defaultdict: no more KeyError; typical: adjacency, inverted index
# edges, X, y_all, losses and run_experiment are pipeline inputs below.
adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)                  # graph (chapter 7)
by_label = defaultdict(list)
for x, y in zip(X, y_all):
    by_label[y].append(x)             # partition by class

# deque: O(1) queue at both ends (BFS, sliding window)
window = deque(maxlen=100)
for t, loss in enumerate(losses):
    window.append(loss)              # automatically evicts the oldest

# itertools: chain (lazy concat), islice (slice an iterator),
# product (hyperparameter grid), groupby (consecutive equal-key groups)
for lr, wd in product([1e-3, 3e-4], [0.0, 1e-2]):
    run_experiment(HP(lr=lr, weight_decay=wd))

groupby groups consecutive equal keys. Sort by the grouping key first if the intended groups are not already contiguous.

1.7. Memory and cost of objects

The schema is a conceptual reference model: Python variables refer to objects, and assigning another name does not copy the object. Exact frame layouts and object sizes depend on the implementation and version.

import sys

# Illustrative sizes on a typical 64-bit CPython build: measure yours.
sys.getsizeof([])                     # ~56 bytes: an empty list is not free
sys.getsizeof([0])                    # ~64 bytes; a list grown by append may use ~88
sys.getsizeof("token")                # ~54 bytes: the string carries a header
sys.getsizeof(2**100)                 # ~40 bytes: arbitrary-precision integer

# 1 million small ints in a Python list vs a NumPy array:
py_list = list(range(1_000_000))          # roughly 36–40 MB: pointers + int objects
np_arr  = np.arange(1_000_000, dtype=np.int64)   # ~8 MB contiguous data
# sys.getsizeof(py_list) alone does NOT include all referenced integer objects.
# Numerical computing benefits from contiguous buffers (BLAS, GPU, etc.).

1.8. Profiling: measure before optimizing

# timeit: isolated micro-benchmarks (normally disables GC, repeats measurements)
python -m timeit -s "import numpy as np; A = np.random.rand(600,600); x = np.random.rand(600)" \
                  "A @ x"
# A result around 1 ms per call is an illustrative scale, not a guarantee.

# cProfile: where does the time go in a full program?
python -m cProfile -s cumtime train.py
# Example of the kind of report to inspect:
#   ncalls  cumtime  function
#      200  120.3s  train.py:epoch
#    50000   90.1s  dataloader.py:__next__   <- investigate data loading
# Line-by-line profiling: line_profiler (kernprof -l -v train.py)

1.9. Testing with pytest

# test_softmax.py — small, executable invariants
import pytest, math
import numpy as np

def softmax(v):
    m = max(v)
    e = [math.exp(x - m) for x in v]
    Z = sum(e)
    return [x / Z for x in e]

def test_softmax_sums_to_one():
    out = softmax([1.0, 2.0, 3.0])
    assert abs(sum(out) - 1.0) < 1e-12          # fundamental invariant

def test_softmax_stable_under_shift():
    # Translation invariance: the property that justifies subtracting max.
    assert np.allclose(softmax([1000.0, 1001.0]), softmax([0.0, 1.0]))

def test_softmax_empty_raises():
    with pytest.raises(ValueError):
        softmax([])

@pytest.mark.parametrize("n", [1, 5, 100])       # same test, 3 sizes
def test_softmax_output_length(n):
    assert len(softmax(list(range(n)))) == n

@pytest.fixture                                    # reusable, isolated data
def toy_dataset():
    rng = np.random.default_rng(0)
    return rng.normal(size=(50, 3)), rng.integers(0, 2, 50)

@pytest.mark.skip(reason="Enable after supplying a suitable model fixture.")
def test_model_overfits_toy(model, toy_dataset):
    # Optional model-specific diagnostic: fit/score are an assumed interface.
    X, y = toy_dataset
    model.fit(X, y, epochs=500)
    assert model.score(X, y) > 0.95

The last test is deliberately disabled until a compatible model fixture exists. Its labels are random: fitting them requires enough capacity to memorize the sample. Failure is not automatically an implementation bug, and this is not a reasonable universal requirement for an affine classifier. Even successful memorization says nothing about generalization.

2. NumPy: numerical linear algebra

Much of the numerical core of deep learning is batched linear algebra. Review the operations and their costs, then three expensive sources of mistakes: broadcasting, views/copies and dtypes.

In the opening example, A\in\mathbb{R}^{n\times d} is a data matrix, not a graph adjacency matrix (graphs come in chapter 7). Here n=1000 observations and d=500 features.

import numpy as np

rng = np.random.default_rng(0)
A = rng.normal(size=(1000, 500))
x = rng.normal(size=500)
b = rng.normal(size=1000)

A @ x               # shape (1000,): O(n*d)
A.T @ A             # shape (500,500): O(n*d^2), via BLAS

np.linalg.norm(x)                       # Euclidean norm
np.linalg.solve(A.T @ A, A.T @ b)       # normal equations; see conditioning caveat below
w, V = np.linalg.eigh(np.array([[2,1],[1,2]]))
# w = [1, 3]; columns of V are orthonormal eigenvectors.

The normal-equation example has compatible dimensions, but forming A^\top A squares the condition number. For a least-squares problem, np.linalg.lstsq(A, b, rcond=None) is generally the safer default; “solve rather than invert” does not remove this conditioning issue.

2.1. Broadcasting: the rules, demonstrated on examples

# Center a data matrix: X (n,d), mean (d,).
X = A
Xc = X - X.mean(axis=0)

# All squared differences between two point sets:
a = rng.random((5, 3))
b = rng.random((7, 3))
d2 = ((a[:, None, :] - b[None, :, :])**2).sum(-1)
# (5,1,3) - (1,7,3) -> (5,7,3) -> (5,7)

# This pattern appears in k-means and kNN.
# A plain matrix product gives the same all-pairs layout without the 3D
# intermediate: a @ b.T has shape (5,7) and holds every inner product.
assert np.allclose(d2, (a**2).sum(1)[:, None] + (b**2).sum(1) - 2 * a @ b.T)

# The (n,) versus (n,1) trap:
v = np.ones(5)
w = v[:, None]                         # (5,1)
v + w                                 # (5,5), NOT (5,1)

The pairwise difference above materializes a (5,7,3) intermediate. At larger sizes, an (n,m,d) temporary may dominate memory. Algebraic reformulation, blocking or selecting only needed pairs can matter more than removing a Python loop.

2.2. Views versus copies

2.3. axis, reshape, reductions

X = rng.random((4, 3))
X.sum(axis=0)        # collapse axis 0 -> (3,): one result per column
X.sum(axis=1)        # collapse axis 1 -> (4,): one result per row
X.mean(axis=0, keepdims=True)   # (1,3), convenient for broadcasting
X.reshape(2, 6)
X.reshape(-1)                 # infer the one missing dimension
X.ravel()[::2]                # flattened view if possible, then every other value
# ravel/reshape may copy when the existing strides do not support a view.

2.4. Algebra: solve, lstsq, SVD and PCA in ten lines

# Solve a square system rather than explicitly computing inv(M) @ rhs.
M = np.array([[2.0, 1.0], [1.0, 2.0]])
rhs = np.array([1.0, 0.0])
w = np.linalg.solve(M, rhs)                  # [2/3, -1/3]

# Least squares: X need not be square or full rank.
y = rng.normal(size=X.shape[0])
beta, res, rank, sv = np.linalg.lstsq(X, y, rcond=None)

# PCA by SVD of centered data: Xc = U S Vt.
Xc = X - X.mean(axis=0)
U, S, Vt = np.linalg.svd(Xc, full_matrices=False)
Z = U * S                                  # component scores
explained = S**2 / (S**2).sum()             # explained-variance ratios
k = int(np.searchsorted(np.cumsum(explained), 0.95) + 1)
Zk = Z[:, :k]                              # retain at least 95% of sample variance

The PCA calculation assumes positive total variance. For n>1, component variances are S_j^2/(n-1); the factor cancels in the ratios. In a predictive experiment, fit the centering mean and PCA basis only on the allowed training data, then reuse them for validation/test data.

2.5. dtypes, precision and promotion

a = np.array([1, 2, 3], dtype=np.int64)
a.dtype, (a / 2).dtype              # int64, float64: division promotes
np.array([1, 2], dtype=np.int32) + np.array([3.0])   # float64
np.int8(127) + np.int8(1)           # -128: wraparound, often with an overflow warning
np.float32(1e8) + np.float32(1.0) == np.float32(1e8)   # True
# Adding 1 is below float32's resolution at this scale.
# Explicit scalar dtypes avoid relying on version-specific promotion rules.

# float32 halves data storage relative to float64.
# Check accumulation dtype and error tolerance rather than blindly choosing
# integers for sums or low precision for numerically sensitive reductions.

2.6. Vectorization: an annotated benchmark

# Illustrative timing scales for a dense matrix-product comparison:
#   triple loop C[i,j] += A[i,k]*B[k,j]       ~2500 ms
#   two Python loops, np.dot per output entry ~120 ms
#   A @ B (BLAS, float64)                       ~8 ms
# The last is about 300x faster than the first in this illustrative comparison.
#
# These are not portable benchmark results. Reproduce the comparison with:
# - explicit A/B shapes, dtype and memory order;
# - a fixed input seed and an np.allclose correctness check;
# - repeated timing after setup/warm-up;
# - recorded CPU, NumPy/BLAS versions and thread settings.
#
# A Python loop around scalar arithmetic is worth investigating.
# A loop over bounded-size vectorized blocks may be the right memory trade-off.

2.7. scipy.sparse: COO, CSR, matvec

from scipy import sparse

# COO: (row, column, value) triplets — natural for edge construction.
# Here data, rows, cols and shape (n,m) describe the matrix to construct.
S = sparse.coo_matrix((data, (rows, cols)), shape=(n, m))
S = S.tocsr()                        # CSR: row traversal and sparse arithmetic
y = S @ x                           # O(nnz) stored multiply-adds, plus output handling
S.T @ S                             # sparse product, but the result may become dense!

# For graph adjacency A in CSR:
# degrees = A @ np.ones(n)
# A @ H aggregates features H of shape (n,d), with O(nnz(A)*d) arithmetic.
# D^-1/2 A D^-1/2 is a normalized aggregation operator when degrees permit it.

Sparsity is not automatically preserved by matrix products. Handle isolated vertices when normalizing by degree, and state whether self-loops are added. These choices affect the computation, not just its implementation.

3. Minimal software engineering (OOP, tests, git)

Code that runs once in a notebook still has to be reused, debugged and rerun, often by someone else. This chapter collects the minimum of software engineering that keeps the Python and NumPy code of chapters 1–2 maintainable: how to structure classes, type interfaces, signal errors, log, review changes and record the environment.

3.1. Inheritance versus composition

This is an optional framework-interface example, not a neural-network training lesson. Unlike a from-scratch affine MNIST classifier, which applies a single affine map, it contains a hidden layer and a ReLU: 10\to64\to2. Shape correctness here does not demonstrate correct gradients or successful learning.

import torch, torch.nn as nn

class MLP(nn.Module):
    def __init__(self, d_in, d_hidden, d_out):
        super().__init__()                    # parameters(), to(), train(), etc.
        self.net = nn.Sequential(
            nn.Linear(d_in, d_hidden), nn.ReLU(),
            nn.Linear(d_hidden, d_out))
    def forward(self, x):                     # called by model(x)
        return self.net(x)

model = MLP(10, 64, 2)
x = torch.randn(4, 10)
assert model(x).shape == (4, 2)

3.2. Dunder methods: making an object “native”

from dataclasses import dataclass

@dataclass(frozen=True, slots=True)
class Vec:
    """Immutable R^2 vector illustrating dunder methods."""
    x: float
    y: float

    def __repr__(self):
        return f"Vec({self.x}, {self.y})"
    def __eq__(self, o):
        if not isinstance(o, Vec):
            return NotImplemented
        return (self.x, self.y) == (o.x, o.y)
    def __hash__(self):
        return hash((self.x, self.y))
    def __add__(self, o):
        if not isinstance(o, Vec):
            return NotImplemented
        return Vec(self.x + o.x, self.y + o.y)
    def __mul__(self, s):
        return Vec(self.x * s, self.y * s)
    def __len__(self):
        return 2
    def __getitem__(self, i):
        return (self.x, self.y)[i]

v = Vec(1, 2)
v + Vec(3, 4) * 2                         # Vec(7, 10)
# Python's operators call methods such as __add__, __mul__ and __matmul__.

A custom __eq__ does not require making an object hashable. Here hashing is appropriate because the coordinate fields are immutable. A mutable value object should normally remain unhashable unless a stable equality/hash contract is deliberately designed.

3.3. Typing: Generic and Protocol

from typing import Generic, TypeVar, Protocol, Iterator

T = TypeVar("T")

class Stack(Generic[T]):                    # typed stack: Stack[int], Stack[str]
    def __init__(self) -> None:
        self._items: list[T] = []
    def push(self, x: T) -> None:
        self._items.append(x)
    def pop(self) -> T:
        return self._items.pop()

class SupportsFit(Protocol):                # structural typing (duck typing)
    def fit(self, x: np.ndarray, y: np.ndarray) -> "SupportsFit": ...
    def predict(self, x: np.ndarray) -> np.ndarray: ...

def train_and_score(model: SupportsFit, x, y) -> float:
    """Accepts a classifier with fit/predict, without common inheritance:
    an sklearn classifier OR a homemade model — duck typing."""
    model.fit(x, y)
    return float((model.predict(x) == y).mean())

This last function reports training accuracy, useful as an interface smoke test. It is not an evaluation protocol: held-out data, splits and model selection belong in the Machine Learning notes.

3.4. Exceptions: hierarchy and good practices

import pickle

# Hierarchy (excerpts):
# BaseException
#   SystemExit, KeyboardInterrupt
#   Exception
#     ArithmeticError -> ZeroDivisionError
#     ValueError, TypeError, KeyError, OSError, ...

class DataValidationError(Exception):
    """The input data does not satisfy the expected contract."""

def load_batch(path):
    # Trusted local files only: unpickling untrusted input can execute code.
    try:
        with open(path, "rb") as f:
            data = pickle.load(f)
    except FileNotFoundError as e:
        raise DataValidationError(f"missing batch: {path}") from e
    except (pickle.UnpicklingError, EOFError, KeyError, ValueError) as e:
        raise DataValidationError(f"corrupted batch: {path}") from e
    return data

# Good practices:
# - Catch the most specific errors you can handle.
# - Avoid a bare "except:" that also swallows interrupts.
# - Preserve the cause with "raise ... from".
# - EAFP: try the operation and handle a relevant failure.
# - Catching exceptions does NOT make an unsafe serialization format safe.

3.5. Logging, docstrings, pre-commit

import logging

logging.basicConfig(
    level=logging.INFO,
    format="%(asctime)s %(name)s %(levelname)s %(message)s"
)
log = logging.getLogger(__name__)
epoch, loss = 0, 1.23
log.info("epoch %d loss %.4f", epoch, loss)   # formatting deferred if filtered

def fit(X, y, lr=1e-3, epochs=100):
    """
    Fit linear least squares by gradient descent.

    Parameters
    ----------
    X : np.ndarray, shape (n, d)
        Feature matrix.
    y : np.ndarray, shape (n,)
        Real targets.
    lr : float, optional
        Learning rate (default 1e-3).
    epochs : int, optional
        Number of iterations (default 100).

    Returns
    -------
    w : np.ndarray, shape (d,)
        Fitted weights.

    Examples
    --------
    >>> w = fit(np.eye(3), np.arange(3.0))   # n = 3 rows, 3 targets
    """
    ...                                      # documentation skeleton, not implementation

# Reading recommendation: document shapes and return values.
# This is not a reported submission rule.

# Sketch of .pre-commit-config.yaml; add pinned "rev" values to actual entries.
# repos:
# - repo: https://github.com/astral-sh/ruff-pre-commit
#   hooks: [{id: ruff}, {id: ruff-format}]
# - repo: https://github.com/pre-commit/pre-commit-hooks
#   hooks: [{id: end-of-file-fixer}, {id: check-yaml}, {id: check-merge-conflict}]

Use logging for configurable pipeline diagnostics rather than scattering unconditional prints. Document shapes, units, mutations and failure conditions before adding elaborate class hierarchies.

3.6. Advanced git and review

• Branches: use a focused branch such as feat/tokenizer when preparing a reviewable change. A pull request can record purpose, tests and limitations.
• Merge vs rebase: merge preserves the branching history; git rebase main replays commits on a new base. Rebase rewrites history, so avoid rebasing shared work without coordination. Interactive rebase (git rebase -i main) can clean up private work-in-progress commits before sharing.
• Code review: keep changes small, explain what/why/how to test, and review invariants as well as style. Branch protection and CI are useful independent-project practices, not claimed assessment arrangements.
• History debugging: git bisect performs bisection over commits to locate a regression — another use of chapter 6’s search pattern, provided the good/bad classification is reliable.

3.7. Environments: venv, uv, poetry

Project practice: one virtual environment per project. Record dependency versions and keep the environment setup alongside the experiment. A pip freeze snapshot records installed packages; a resolver lockfile can additionally describe how a project’s dependencies were resolved.

# venv + pip (standard Python tooling)
python -m venv .venv && source .venv/bin/activate
pip install -r requirements.txt && pip freeze > requirements.lock

# uv: environments and dependencies in one tool
uv venv && uv pip install -r pyproject.toml
uv add torch --upgrade

# poetry: pyproject.toml + poetry.lock
poetry install                          # installs from the existing lockfile

These are alternative workflows, not commands to mix indiscriminately. Version locks help reproducibility but do not fix hardware, numerical backends or all sources of nondeterminism.

3.8. Docker: a reproducible environment

# Minimal Dockerfile for a notebook experiment.
# requirements.txt must include jupyterlab and the experiment dependencies.
FROM python:3.12-slim
WORKDIR /app
COPY requirements.txt .
RUN pip install --no-cache-dir -r requirements.txt
COPY . .
RUN useradd -m appuser && chown -R appuser /app
USER appuser
CMD ["jupyter", "lab", "--ip=0.0.0.0", "--no-browser"]
# docker build -t llga-tp1 .
# docker run -p 127.0.0.1:8888:8888 llga-tp1

A container reduces environment differences; it does not guarantee identical numerical results across CPUs, GPUs or drivers. For stronger reproducibility, record an image digest, dependency versions, seeds and numerical backend settings. Keep notebook authentication enabled and avoid exposing a development server unnecessarily.

3.9. A repository template for projects

The pieces of chapters 1 and 3 fit into one layout. These notes propose it for every project repository and make it mandatory for every capstone repository (see Projects and assessment):

project/
├── pyproject.toml           # dependencies and tool settings (ruff, pytest)
├── uv.lock                  # or requirements.lock: resolved versions (§3.7)
├── Dockerfile               # pinned base image, non-root user (§3.8)
├── .pre-commit-config.yaml  # format and lint before each commit (§3.5)
├── README.md                # install, test, and the command behind each result
├── src/project/             # importable code with typed interfaces (§3.3)
│   └── log.py               # one logging configuration (§3.5)
├── tests/                   # pytest: invariants, edge cases, tiny fixtures (§1.9)
├── configs/                 # one frozen configuration per experiment, seeds included
└── results/                 # written by scripts, never edited by hand

A repository meets the template when a fresh clone, inside the container or the locked environment, passes pytest -q and regenerates every reported number with one documented command.

4. Complexity analysis

This chapter answers a practical question: before running a computation, how will its time and memory grow with the size of the input, and which part will dominate? Before formal notation, compare scales. At n=10^6, a quadratic enumeration has 10^{12} pairs; a logarithmic search needs only about 20 steps. Constants matter, but they do not make these growth rates interchangeable.

Complexity is measured in time and memory, in the worst case unless another regime is stated. Keep the parameters visible: graph costs depend on both |V| and |E|; an n\times d matrix computation depends on both n and d.

4.1. Master theorem

4.2. Amortized analysis: the dynamic array

4.3. Memory complexity and real Python operations

def all_pairs_dist(V, E):
    d = {}
    for u in V:              # n iterations
        for v in V:          # n iterations -> O(n^2) pairs
            d[u, v] = dist(u, v)
    return d
# dist is a supplied distance function; E is not used by this enumeration.

4.4. Memory: space complexity

Counting memory follows the same rules:

• dense adjacency: \Theta(|V|^2); adjacency lists: \Theta(|V|+|E|);
• an m\times n DP table may reduce to two rows — \mathcal{O}(\min(m,n)) storage for Levenshtein distance, section 6.6;
• recursion uses a call stack of depth \Theta(\text{depth}). Recursive DFS on a path of 10^6 nodes exceeds Python’s usual recursion limit of roughly 1000. An iterative traversal is safer than simply increasing the limit with sys.setrecursionlimit.

In deep learning, activations often contain a term of size \Theta(\text{batch}\times\text{length}\times\text{dims}). Preview, no prior knowledge needed: an attention layer, the core of the transformers met in Deep Learning, scores every pair of positions of a sequence, in several parallel copies called heads. Materialized, these scores add a quadratic length term, typically \Theta(\text{batch}\times\text{heads}\times\text{length}^2). Neither expression alone includes all parameters, optimizer state or saved intermediate tensors.

5. Fundamental data structures

The right container depends on the operations that dominate a program: lookup by key, insertion, extraction of the smallest element, prefix search or approximate membership. The table below summarizes the costs that the sections of this chapter then justify, one structure at a time.

5.1. Linked lists: references instead of positions

A linked list stores each element in its own node, together with a reference to the next node. Nothing is contiguous. Inserting or removing at the head, or just after a node you already hold, rewires one or two references and moves no element.

The price is access by position, which walks the chain in \mathcal{O}(n), and one extra reference per element that breaks the contiguous, cache-friendly layout of chapter 2.

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

class LinkedList:
    """Singly linked list with a head reference."""
    def __init__(self):
        self.head, self.size = None, 0
    def push_front(self, x):                  # O(1): no element moves
        self.head = Node(x, self.head)
        self.size += 1
    def pop_front(self):                      # O(1)
        if self.head is None:
            raise IndexError("pop from empty list")
        node, self.head = self.head, self.head.next
        self.size -= 1
        return node.value
    def __iter__(self):                       # O(n) traversal
        node = self.head
        while node is not None:
            yield node.value
            node = node.next
    def reverse(self):                        # O(n) time, O(1) extra memory
        prev, node = None, self.head
        while node is not None:
            node.next, prev, node = prev, node, node.next
        self.head = prev

ll = LinkedList()
for x in [3, 2, 1]:
    ll.push_front(x)
assert list(ll) == [1, 2, 3]
ll.reverse()
assert list(ll) == [3, 2, 1] and ll.pop_front() == 3

In Python you rarely write one: list is a dynamic array (theorem 4.4), and CPython implements collections.deque, the queue of BFS, as a doubly linked list of fixed-size blocks. Linked structures remain the mental model behind the chains of a hash table (§5.2), the adjacency lists of chapter 7 and the trees of this chapter: nodes joined by references.

5.2. Hash tables: under the hood of dict and set

vocab = {}                                # token -> id
def tokenize_id(text):
    out = []
    for tok in text.lower().split():
        if tok not in vocab:              # expected O(1) table lookup
            vocab[tok] = len(vocab)       # next free id
        out.append(vocab[tok])
    return out
# 10^9 tokens, vocabulary size 10^5:
# expected O(n) token-level work rather than O(n * vocabulary_size)
# for a list scan, with token hashing/processing costs accounted for separately.
# The same principle indexes graph entities or (user, item) pairs.

5.3. Balanced trees: AVL and red-black

5.4. Binary heap: heapify is linear

import heapq

def top_k(items, scores, k):
    """Return (score, item) pairs for the k highest scores.
    O(n log k) for k >= 2; items must be comparable when scores tie.
    """
    if k <= 0:
        return []
    heap = []                                  # min-heap of size <= k
    for it, s in zip(items, scores):
        if len(heap) < k:
            heapq.heappush(heap, (s, it))
        elif s > heap[0][0]:
            heapq.heapreplace(heap, (s, it))   # evicts the smallest
    return sorted(heap, reverse=True)

# NLP connection: select the k highest-scoring tokens before top-k sampling.
# heapq.nlargest(k, zip(scores, items)) packages this selection pattern.
# It does not require an earlier heapify call.
# Alternatively: heapify all n items, then extract k times -> O(n + k log n).

5.5. Tries: prefix search

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}            # char -> TrieNode (hash table)
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True
    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):           # autocompletion
        return self._walk(prefix) is not None
    def completions(self, prefix, limit=10):
        node = self._walk(prefix)
        out, stack = [], [(node, prefix)] if node else []
        while stack and len(out) < limit:    # lexicographic DFS
            n, s = stack.pop()
            if n.is_word:
                out.append(s)
            stack.extend(
                (child, s + ch)
                for ch, child in sorted(n.children.items(), reverse=True)
            )
        return out
    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

t = Trie()
for w in ["graph", "graphs", "grain", "gradient"]:
    t.insert(w)
assert t.starts_with("grad") and not t.starts_with("grapx")
print(t.completions("gra"))     # ['gradient', 'grain', 'graph', 'graphs']

5.6. Two heaps: the median of a stream

5.7. Bloom filters

import hashlib

class Bloom:
    def __init__(self, m_bits, k):
        if m_bits <= 0 or k <= 0:
            raise ValueError("m_bits and k must be positive")
        self.m, self.k = m_bits, k
        self.bits = bytearray((m_bits + 7) // 8)
    def _pos(self, x, i):
        h = hashlib.sha256(f"{i}:{x}".encode()).digest()
        return int.from_bytes(h[:8], "big") % self.m
    def add(self, x):
        for i in range(self.k):
            p = self._pos(x, i)
            self.bits[p // 8] |= 1 << (p % 8)
    def might_contain(self, x):
        return all(
            self.bits[p // 8] & (1 << (p % 8))
            for p in (self._pos(x, i) for i in range(self.k))
        )

b = Bloom(m_bits=8_000_000, k=7)      # ~1 MB
# At 1M inserted URLs: 8 bits/element, p ~ 0.023.
# For ~0.008 at 1M URLs, use about 10M bits (~1.25 MB) and k=7.
b.add("https://polytechnique.edu")
assert b.might_contain("https://polytechnique.edu")
# Uses: crawler prefilter, negative disk cache, candidate join filtering.
# Verify positive answers exactly when a false positive would lose needed data.

6. Sorting, search, recursion

Ordering data, finding an element and splitting a problem into smaller ones are the patterns behind many preprocessing and evaluation steps. This chapter analyses quicksort, merge sort and radix sort, selection, binary search with its loop invariant, and dynamic programming.

6.1. Quicksort: in-place partition and analysis

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    p = partition(a, lo, hi)          # pivot in its final position
    quicksort(a, lo, p - 1)           # everything left < pivot
    quicksort(a, p + 1, hi)           # everything right >= pivot
    return a

def partition(a, lo, hi):
    """Lomuto partition: pivot = a[hi], in place, O(hi-lo)."""
    pivot, i = a[hi], lo
    for j in range(lo, hi):
        if a[j] < pivot:              # maintain the invariant:
            a[i], a[j] = a[j], a[i]   # a[lo..i-1] < pivot
            i += 1                    # a[i..j-1] >= pivot
    a[i], a[hi] = a[hi], a[i]         # place the pivot between the two
    return i

6.2. Merge sort and counting inversions

def count_inversions(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left,  cl = count_inversions(a[:mid])
    right, cr = count_inversions(a[mid:])
    merged, cross = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:                              # left[i] > right[j]
            merged.append(right[j]); j += 1
            cross += len(left) - i          # all remaining left items form inversions
    return merged + left[i:] + right[j:], cl + cr + cross

count_inversions([5, 4, 3, 2, 1])   # -> ([1,2,3,4,5], 10), with 10 = C(5,2)

6.3. Radix sort: sorting without comparing

6.4. Selection: the median in expected \Theta(n)

6.5. Binary search: loop invariant and variants

def binary_search(a, x):           # a sorted ascending
    lo, hi = 0, len(a)             # search within [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return -1

def feasible(d, k, cap):                 # greedy contiguous partition
    load, machines = 0, 1
    for t in d:
        if t > cap:
            return False
        if load + t > cap:
            machines += 1
            load = t
        else:
            load += t
    return machines <= k

def min_makespan(d, k):
    if not d or k < 1:
        raise ValueError("need a nonempty duration list and k >= 1")
    lo, hi = max(d), sum(d)              # trivial bounds
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(d, k, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo                            # smallest feasible capacity

assert min_makespan([7, 2, 5, 10, 8], 2) == 18
# Groups [7,2,5] and [10,8] have loads 14 and 18.

6.6. Recursion and dynamic programming

• Memoize shared subproblems: turn repeated recursive work into one solution per state. Examples include edit distance in NLP, Viterbi decoding for HMMs and Bellman-style recurrences in reinforcement learning.
• Preview, no prior knowledge needed: a hidden Markov model (HMM) explains a sequence by hidden states that change from step to step; Viterbi decoding finds the most probable state sequence with one DP cell per (time, state) pair. A Bellman recurrence writes the value of a state as an immediate reward plus the value of the next state.
• Reduce memory when dependencies allow it: the m\times n Levenshtein table needs only the current and previous row if only the distance is required. Recovering an alignment needs additional bookkeeping or a reconstruction algorithm.

def levenshtein(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            cost = 0 if a[i-1] == b[j-1] else 1
            dp[i][j] = min(dp[i-1][j] + 1,        # deletion
                           dp[i][j-1] + 1,        # insertion
                           dp[i-1][j-1] + cost)   # substitution
    return dp[m][n]          # O(m n) time and memory
                            # distance-only memory can reduce to O(min(m,n))

print(levenshtein("graph", "giraffe"))  # 4

7. Graph algorithms

This chapter is central to the Graph × LLM reading route. Begin with a graph small enough to inspect: in the four-node example below, vertex 3 is two hops from vertex 0, through vertex 2. We can verify that fact with a queue or with adjacency algebra, while keeping their costs distinct.

A graph may encode observed relationships, a constructed neighborhood or a workflow. Those interpretations are not interchangeable. Classical algorithms provide vocabulary and reference computations for Graph ML; they do not by themselves teach learned message passing or establish that the chosen edges are useful.

7.1. Representations: lists, matrix, CSR

import numpy as np
from scipy import sparse

# 1) Adjacency lists: convenient for traversal.
# NetworkX uses richer neighbor dictionaries; PyG commonly uses edge-index tensors.
adj = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

# 2) Adjacency matrix: dense O(|V|^2) memory, but direct algebra.
A = np.array([[0, 1, 1, 0],
              [1, 0, 1, 0],
              [1, 1, 0, 1],
              [0, 0, 1, 0]])
print((A @ A)[0, 3] > 0)   # True: a length-2 walk goes from 0 to 3.

# 3) CSR (Compressed Sparse Row): three arrays.
# indptr[i] .. indptr[i+1] gives row i's range in indices[] and data[].
rows = np.array([0, 0, 1, 1, 2, 2, 2, 3], dtype=np.int32)
cols = np.array([1, 2, 0, 2, 0, 1, 3, 2], dtype=np.int32)
A_csr = sparse.coo_matrix(
    (np.ones(8), (rows, cols)), shape=(4, 4)
).tocsr()
print(A_csr.indptr, A_csr.indices)   # [0 2 4 7 8] [1 2 0 2 0 1 3 2]

# Illustrative graph: 5,000 vertices and 20,000 undirected edges.
# Dense float64 adjacency: 5000^2 * 8 = 200 MB.
# CSR with 40,000 stored directed entries and int32 indices: about 0.5 MB.
# Actual storage depends on dtype, index width and edge convention.

7.2. Breadth-first and depth-first traversal

BFS layers correspond to shortest unweighted distances. The DFS discovery order shown is one possible order, dependent on neighbor ordering; it is not a distance ordering.

from collections import deque

def bfs(adj, s):
    """Unweighted distances and parents from s. O(|V|+|E|).
    Every vertex, including sinks and isolates, should have an adjacency entry.
    """
    dist, parent = {s: 0}, {s: None}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v], parent[v] = dist[u] + 1, u
                q.append(v)
    return dist, parent

def dfs(adj, u, visited=None):
    """Recursive reachability traversal.
    Building block for components, cycle detection and DFS topological sorting.
    """
    visited = visited if visited is not None else set()
    visited.add(u)
    for v in adj[u]:
        if v not in visited:
            dfs(adj, v, visited)
    return visited

7.3. Topological sort of a DAG (Kahn’s algorithm)

from collections import deque

def topo_sort(adj, n):
    """Vertices are 0..n-1, with all adjacency entries present.
    Return an order where u -> v implies u before v, or None if cyclic.
    """
    indeg = [0] * n
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None

# A dependency workflow, not a learned graph:
dag = {0: [1, 2], 1: [3], 2: [3], 3: []}        # fetch -> {chunk, enrich} -> index
print(topo_sort(dag, 4))                        # [0,1,2,3] or [0,2,1,3]

7.4. Shortest paths

import heapq

def dijkstra(adj_w, s):           # adj_w[u] = [(v, w_uv), ...]
    # Node identifiers must be mutually comparable when heap distances tie.
    dist = {s: 0.0}
    pq = [(0.0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue               # stale entry
        for v, w in adj_w[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist                    # shortest distances to reachable vertices

def bellman_ford(n, edges, s):          # edges = [(u, v, w), ...]
    dist = [float("inf")] * n
    dist[s] = 0.0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # early convergence
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None                   # a negative cycle is reachable from s
    return dist

7.5. Minimum spanning trees (MST)

Both algorithms fit in a few lines. Union-find keeps one representative per tree of the growing forest: find returns it, and union merges two trees or reports that the edge would close a cycle.

With union by rank and path halving, a sequence of operations costs nearly constant amortized time per operation: the bound grows like the inverse Ackermann function, which stays below 5 for any input that fits in memory. Kruskal’s cost is therefore dominated by its sort.

import heapq

class UnionFind:
    def __init__(self, n):
        self.parent, self.rank = list(range(n)), [0] * n
    def find(self, x):                        # path halving
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):                    # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                      # same tree: the edge closes a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.rank[ra] += self.rank[ra] == self.rank[rb]
        return True

def kruskal(n, edges):                        # edges = [(w, u, v), ...]
    uf, tree = UnionFind(n), []
    for w, u, v in sorted(edges):             # O(|E| log |E|)
        if uf.union(u, v):
            tree.append((u, v, w))
    return tree                               # n-1 edges if the graph is connected

def prim(adj_w, s=0):                         # adj_w[u] = [(v, w), ...]
    seen, tree = {s}, []
    pq = [(w, s, v) for v, w in adj_w[s]]
    heapq.heapify(pq)
    while pq:
        w, u, v = heapq.heappop(pq)           # lightest edge leaving the tree
        if v in seen:
            continue                          # stale: both ends already in the tree
        seen.add(v)
        tree.append((u, v, w))
        for x, wx in adj_w[v]:
            if x not in seen:
                heapq.heappush(pq, (wx, v, x))
    return tree                               # lazy Prim: O(|E| log |V|)

edges = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3), (6, 3, 4), (7, 2, 4)]
adj_w = {u: [] for u in range(5)}
for w, u, v in edges:
    adj_w[u].append((v, w))
    adj_w[v].append((u, w))
assert sum(w for *_, w in kruskal(5, edges)) == 12
assert sum(w for *_, w in prim(adj_w)) == 12

Prim, like Dijkstra, keeps stale heap entries and skips them when popped; its key is an edge weight, not a path length. Exercise 14 checks both functions against scipy.sparse.csgraph.minimum_spanning_tree.

7.6. Max flow and cuts

7.7. Assignment: the Hungarian algorithm

Matching asks how many pairs can be formed; assignment asks which pairing is cheapest. The question appears whenever a model outputs an unordered set that must be compared with a target set.

The Hungarian, or Kuhn–Munkres, algorithm (Kuhn, 1955; Munkres, 1957) solves it exactly. It keeps a price on every row and column and grows a matching along augmenting paths, as in section 7.6, using only pairs whose cost equals the sum of their two prices.

Its standard implementations run in \mathcal{O}(n^3) time, where enumerating the n! permutations is hopeless. A rectangular matrix with more columns than rows leaves the extra columns unassigned.

import numpy as np
from scipy.optimize import linear_sum_assignment

C = np.array([[4.0, 1.0, 3.0],          # rows: predictions, tracks or agents
              [2.0, 0.0, 5.0],          # columns: targets, detections or tasks
              [3.0, 2.0, 2.0]])
rows, cols = linear_sum_assignment(C)  # exact, O(n^3); maximize=True for gains
print(cols, C[rows, cols].sum())        # [1 0 2] 5.0
# Greedy (cheapest remaining pair first) takes C[1,1] = 0, then C[2,2] = 2,
# and must finish with C[0,0] = 4: total 6, not optimal.

Three uses met later in the programme:

• Set prediction loss (DETR). A detector outputs a fixed number of unordered boxes. Training assigns them to the ground-truth objects at minimum cost, then applies the loss to the assigned pairs (Carion et al., 2020); see Computer Vision applications, ch. 2.
• Node matching in graph generation (GraphVAE). A one-shot decoder emits nodes in no canonical order, so its output is compared with the target graph after a node matching whose final step is a Hungarian assignment (Simonovsky and Komodakis, 2018); see Graph ML, ch. 9.
• Multi-object tracking (SORT). At each frame, predicted track positions are assigned to new detections with cost one minus their box overlap ratio (Bewley et al., 2016); see Computer Vision applications, ch. 5. The same step distributes formation slots among agents in Real-time AI, ch. 4.

Discrete optimal transport generalizes assignment to weighted couplings with prescribed marginals. It is a useful optional bridge, not a prerequisite for every graph or language-model application.

7.8. Community detection: label propagation

import random

def label_propagation(adj, n, rounds=20, seed=0):
    """Heuristic: adopt the most frequent current neighbor label.
    Fixed rounds; no guarantee of a unique or meaningful partition.
    """
    rng = random.Random(seed)
    labels = list(range(n))                        # distinct initialization
    for _ in range(rounds):
        order = list(range(n))
        rng.shuffle(order)                        # asynchronous update
        for u in order:
            if adj[u]:
                counts = {}
                for v in adj[u]:
                    counts[labels[v]] = counts.get(labels[v], 0) + 1
                labels[u] = max(counts, key=counts.get)
    return labels
# Near-linear work per round; no prescribed number of communities.
# Results depend on update order and tie-breaking.
# Compare with trivial partitions and several seeds before interpreting them.

This is a useful community-detection baseline, not a guarantee that label consensus corresponds to meaningful communities. Graph ML provides the place to compare structural and learned methods under an explicit evaluation task.

7.9. P vs NP: limits of exact computation

8. Geometric algorithms and research connections

This is an optional research extension, not a verified part of the catalog syllabus (which the sheet does not display) and not a chapter attributed to the teaching team. Computational geometry is useful when data arrive as point clouds, meshes or maps and connectivity must be constructed rather than assumed.

For example, A=(0,0), B=(2,0) and C=(2,2) give determinant 4: a left turn. The same constant-time predicate supports convex hulls and triangulations. Those constructions can produce candidate graphs for learning — but geometric proximity is a modeling choice, not proof that two points should exchange information.

8.1. Primitives: orientation by cross product

def orient(a, b, c):
    """Return the determinant: >0 left, <0 right, 0 collinear."""
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

assert orient((0, 0), (2, 0), (2, 2)) == 4

The code returns the determinant rather than only its sign, so callers can inspect either.

8.2. Convex hull: Jarvis then Graham

import math

def graham_scan(points):
    pts = sorted(set(points), key=lambda p: (p[1], p[0]))
    if len(pts) <= 1:
        return pts
    pivot = pts[0]
    rest = sorted(
        pts[1:],
        key=lambda p: (
            math.atan2(p[1]-pivot[1], p[0]-pivot[0]),
            (p[0]-pivot[0])**2 + (p[1]-pivot[1])**2
        )
    )
    hull = [pivot]
    for p in rest:
        while len(hull) >= 2 and orient(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

# Square plus interior and boundary points.
hull = graham_scan([(0,0), (2,0), (2,2), (0,2), (1,1), (0,1)])
assert set(hull) == {(0,0), (2,0), (2,2), (0,2)}
assert graham_scan([]) == []
assert graham_scan([(0,0), (1,0), (2,0)]) == [(0,0), (2,0)]

8.3. Closest pair of points

8.4. Triangulations and Delaunay

from scipy.spatial import Delaunay, Voronoi
import numpy as np

rng = np.random.default_rng(0)
pts = rng.uniform(0, 1, (200, 2))
tri = Delaunay(pts)
print(tri.simplices.shape)        # roughly (390, 3), depending on hull size

# Proximity graph: collect the edges of all triangles.
edges = set()
for s in tri.simplices:
    for i, j in [(0,1), (1,2), (0,2)]:
        edges.add((min(s[i], s[j]), max(s[i], s[j])))
print(len(edges), "proximity edges")

8.5. Optional research readings: reconstruction from points

These publications are Reading connections. Their presence does not establish an official syllabus topic or institutional authorship of this chapter.

Exercises

Choose exercises according to the reading route. The solutions support self-assessment; completing every exercise is not necessary before continuing to ML.

1. ★ Master theorem. Solve: (a) T(n)=2T(n/2)+n; (b) T(n)=T(n/9)+n; (c) T(n)=7T(n/2)+n^2; (d) T(n)=2T(\sqrt n)+\log n. For (d), set m=\log n.

   1. \Theta(n\log n): equality case.

   2. d=1>\log_9 1=0, so \Theta(n): the root dominates.

   3. \log_2 7\approx2.81>2, so \Theta(n^{\log_2 7}): the leaves dominate.

   4. Write S(m)=T(e^m), up to the chosen logarithm base. Then S(m)=2S(m/2)+m, hence \Theta(m\log m)=\Theta(\log n\log\log n).

2. ★ Connected components. Write components(adj) returning a list of vertex sets for an undirected graph. Test a graph with 3 components, including one isolated vertex.

   def components(adj):
       seen, comps = set(), []
       for s in adj:
           if s in seen:
               continue
           comp = dfs(adj, s, visited=set())   # dfs from chapter 7
           seen |= comp
           comps.append(comp)
       return comps
   
   G = {0:[1], 1:[0], 2:[3], 3:[2], 4:[]}
   assert components(G) == [{0,1}, {2,3}, {4}]

   Every vertex, including an isolate, needs an adjacency entry. For large-depth components, replace the recursive DFS with an explicit stack.

3. ★ Anagrams. Write group_anagrams(words) with expected \mathcal{O}(nk\log k) work for n words of length at most k, using a dictionary of sorted-character signatures. In what sense is the work linear in n?

   from collections import defaultdict
   
   def group_anagrams(words):
       groups = defaultdict(list)
       for w in words:
           groups[tuple(sorted(w))].append(w)
       return list(groups.values())
   
   assert group_anagrams(["listen", "silent", "enlist", "hello"]) == [
       ["listen", "silent", "enlist"], ["hello"]
   ]

   Words have the same signature exactly when their character multisets agree. Sorting each signature costs \mathcal{O}(k\log k); hashing and comparing it may cost \mathcal{O}(k). Dictionary access has expected constant probe count under ordinary assumptions. Total expected work is \mathcal{O}(nk\log k) — linear in the number of words when the word-length bound is fixed.

4. ★ Generators. Write lines(path) -> tokens -> ngrams(k) without loading the whole corpus. Explain the \mathcal{O}(k) sliding-window bound, and account separately for the longest line and token sizes.

   from collections import deque
   
   def lines(path):
       with open(path, encoding="utf-8") as f:
           yield from f
   
   def tokens(lines):
       for line in lines:
           yield from line.lower().split()
   
   def ngrams(toks, k):
       if k < 1:
           raise ValueError("k must be positive")
       window = deque(maxlen=k)
       for t in toks:
           window.append(t)
           if len(window) == k:
               yield tuple(window)
   
   # ngrams(tokens(lines("corpus.txt")), 3)

   The deque holds \mathcal{O}(k) token references, independent of corpus length. The line reader and split still require storage proportional to the current line; token strings also occupy memory. With maximum line size L_{\max} and bounded token size T_{\max}, a useful byte-level bound is \mathcal{O}(L_{\max}+kT_{\max}), excluding outputs retained by the consumer.

   Each emitted tuple costs \mathcal{O}(k) to construct. This version lets n-grams cross line boundaries; reset the window if those boundaries represent separate documents.

5. ★ Retry decorator. Write @retry(times=3, delay=0.5) with exponential backoff, returning the first successful result and re-raising the last failure. Test a function that succeeds on its third attempt using a counter.

   Use a decorator factory, functools.wraps, a loop over range(times), and try/except. After failed attempts, sleep for delay * 2**attempt, but do not sleep after the final failure. Re-raise that failure with raise.

   Validate that times is positive. The test should check both the returned result and exactly 3 calls; patch the sleep function to avoid a slow test. In actual pipelines, retry only failures plausibly transient — not every programming or data-validation error.

6. ★ Bloom filter. Use m/n=12 bits per inserted element. Choose k, predict the false positive rate, then test 100,000 inserted strings and 100,000 distinct absent strings.

   k^\star=12\ln2\approx8.3, so try k=8:

   p\approx(1-e^{-8/12})^8\approx3.1\times10^{-3}.

   For 100,000 inserted elements, use m=1{,}200{,}000 bits. Expect roughly 0.31% false positives on absent queries — around 310 out of 100,000, with sampling variation — and zero false negatives under the insertion-only implementation. Record the generated key sets and ensure the “absent” strings really were not inserted.

7. ★ Broadcasting. Predict shapes without running: (a) (4,3)+(3,); (b) (4,1)+(1,3); (c) (4,3)+(4,); (d) (2,1,3)+(5,3); (e) (6,)+(6,1). Which raises an error?

   1. (4,3).
      
   2. (4,3) — outer sum.
      
   3. Error: size 4 aligns with the last axis of size 3.
      
   4. (2,5,3).
      
   5. (6,6) — the row/column trap.

   Repair (c) by turning the per-row vector into a column: x[:, None] gives (4,1)+(4,3)\to(4,3).

8. ★★ Complexity. Classify binary search, merge sort, Dijkstra with a heap, A^\top A, BFS and all-pairs distance computation. Can they be put in one increasing order without specifying graph density and feature dimension? Compare a sparse graph with |E|=\Theta(n) and a matrix A\in\mathbb{R}^{n\times d}, first for fixed d, then for d=\Theta(n).

   • Binary search: \mathcal{O}(\log n) worst case.
   • Merge sort: \Theta(n\log n).
   • BFS: \mathcal{O}(|V|+|E|).
   • Heap Dijkstra on a simple graph: \mathcal{O}((|V|+|E|)\log|V|).
   • A^\top A: \mathcal{O}(nd^2) by ordinary dense multiplication.
   • All Euclidean pair distances: \mathcal{O}(n^2d) arithmetic and \Theta(n^2) stored outputs.

   With |V|=n, |E|=\Theta(n) and fixed d, BFS and A^\top A are linear-scale computations, merge sort and heap Dijkstra are \mathcal{O}(n\log n), and explicit all-pairs distances are quadratic. With d=\Theta(n), both matrix products and pairwise distance arithmetic become cubic. With a dense graph, BFS itself becomes quadratic. There is no universal total ordering independent of these parameters.

9. ★★ Dynamic array. If the growth factor were c=1.1 rather than 2, show that append remains amortized \mathcal{O}(1), with a copy-cost bound proportional to c/(c-1)=11 per insertion. What trade-off does this illustrate for Python lists?

   Bound the copied elements by

   n(c^0+c^{-1}+c^{-2}+\dots) \leq n\frac{c}{c-1}.

   For c=1.1, this gives 11n copies, compared with 2n for doubling: the same asymptotic cost but a bound about 5.5 times larger. CPython’s progressive over-allocation has historically used growth around 1.125, with implementation-specific rounding and adjustments. Smaller growth wastes less spare memory but copies more often.

10. ★★ Walks of length k. Show that (A^k)_{ij} counts walks of exactly length k from i to j in an unweighted graph.

    Verify on a small graph. Compare computing all of A^k with repeatedly applying A to one vector or a small feature matrix.

    Induction:

    (A^{k+1})_{ij}=\sum_l(A^k)_{il}A_{lj}.

    Every length-(k+1) walk has a penultimate vertex l; count its length-k prefix and final edge. The base case k=1 is the adjacency matrix itself. Repeated vertices are allowed, so these are walks, not necessarily simple paths.

    import numpy as np
    
    A = np.array([[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]])
    assert np.linalg.matrix_power(A, 2)[0,3] == 1

    Repeated dense multiplication costs \mathcal{O}(kn^3); exponentiation by squaring uses \mathcal{O}(\log k) dense products. Sparse powers can fill in and become dense. A shorthand estimate such as \mathcal{O}(k\,\mathrm{nnz}\,\bar d) requires controlled sparsity at every step and is not a general bound on sparse powers.

    Applying A repeatedly to one vector instead uses approximately \mathcal{O}(k\,\mathrm{nnz}(A)) arithmetic; a feature matrix with d columns gives \mathcal{O}(k\,\mathrm{nnz}(A)d). This distinction matters for graph propagation and walk-based encodings. Exact counts can also overflow a fixed-width integer dtype.

11. ★★ Cycle detection and topological sort. Detect a directed cycle using white/gray/black colors, then apply Kahn’s algorithm to the workflow fetch → chunk → embed → index → answer.

    def has_cycle(adj, n):
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * n
    
        def visit(u):
            color[u] = GRAY
            for v in adj[u]:
                if color[v] == GRAY:
                    return True              # back edge
                if color[v] == WHITE and visit(v):
                    return True
            color[u] = BLACK
            return False
    
        return any(
            color[u] == WHITE and visit(u)
            for u in range(n)
        )
    
    wf = {0:[1], 1:[2], 2:[3], 3:[4], 4:[]}
    assert not has_cycle(wf, 5)
    assert topo_sort(wf, 5) == [0, 1, 2, 3, 4]
    wf[4].append(0)
    assert has_cycle(wf, 5) and topo_sort(wf, 5) is None

    A gray-to-gray edge returns to an ancestor on the current recursion stack, closing a directed cycle. A black vertex is already completely processed; merely reaching it does not imply a cycle.

12. ★★ Autocompletion. Extend the Trie of section 5.5 with word frequencies and return the k most frequent completions. State the cost of traversing the prefix, exploring its subtree and selecting results.

    Descending the prefix takes \Theta(L) character steps. Let S be the number of visited subtree nodes and M its terminal words. Traversal costs at least \mathcal{O}(S), and heap selection costs \mathcal{O}(M\log k) for k\geq2, plus string construction and output.

    The shorthand \mathcal{O}(L+M\log k) assumes bounded word lengths and subtree work proportional to the number of words; it is not a complete bound for arbitrary long strings.

    # Minimal extension: replace is_word with a terminal frequency
    # (0 = not a word), traverse the prefix subtree, and select with:
    # heapq.nlargest(k, (frequency, word) pairs)

13. ★★ Convex hull. Test Graham scan on a square plus an interior point, a collinear set and 1,000 random points. Compare the nondegenerate case with scipy.spatial.ConvexHull.

    The square assertion appears in section 8.2. With the distance tie-break and the \leq0 eviction, a fully collinear set retains its two extreme endpoints. Test empty and singleton inputs too.

    For the random cloud, compare hull vertex sets rather than only counts; cyclic start position and orientation may differ. A cross-product comparator with functools.cmp_to_key avoids atan2 ordering, but a floating-point determinant can still be unreliable near collinearity. Python integer coordinates permit exact determinant signs; robust floating-point geometry needs a suitable predicate strategy.

14. ★★ Minimum spanning tree, two ways. Run Kruskal by hand on the five-vertex graph of section 7.5, listing the edges that union-find rejects. Prove that distinct edge weights make the MST unique. Then test kruskal and prim against scipy.sparse.csgraph.minimum_spanning_tree on random connected graphs. Which two single-link clusters remain after deleting the heaviest MST edge?

    Kruskal scans the edges by increasing weight:

    • it accepts (0,1) of weight 1, (1,3) of weight 2 and (1,2) of weight 3;
    • it rejects (0,2) of weight 4, since 0 and 2 are already joined through 1, and (2,3) of weight 5;
    • it accepts (3,4) of weight 6 and rejects (2,4) of weight 7.

    The tree weighs

    1+2+3+6=12,

    and Prim from vertex 0 returns the same four edges.

    Uniqueness, by exchange.

    • Suppose two different minimum spanning trees T_1\neq T_2. Let e be the lightest edge that lies in exactly one of them, say e\in T_1\setminus T_2.
    • Adding e to T_2 closes a cycle. Its other edges cannot all lie in T_1, which is acyclic: pick one, f\in T_2\setminus T_1.
    • By the choice of e and distinct weights, w(f)>w(e).
    • So T_2+e-f is a spanning tree lighter than T_2: a contradiction.

    Tests. SciPy reads a matrix in which a zero entry means “no edge”, so draw positive weights. Build connected graphs as a random tree plus random extra edges, and compare total weights; compare edge sets only when the weights are distinct.

    Deleting the heaviest MST edge (3,4) leaves the clusters \{0,1,2,3\} and \{4\}.

15. ★★★ Dijkstra on a grid, then A*. On a 50×50 grid with 20% walls, compare explored vertices between opposite corners. Use four-direction unit-cost moves and Manhattan distance as the A* heuristic. Keep endpoints free and check reachability.

    Use an implicit graph whose neighbors are the valid four-direction moves. Count finalized/expanded vertices consistently, not stale heap entries. Manhattan distance is admissible and consistent for unit orthogonal moves, even with walls.

    Both algorithms must return the same finite distance, or both report unreachable. A* can explore about 2× fewer vertices on some instances, but that ratio is not guaranteed: large equal-f plateaus and tie-breaking can erase much of the gain. Record seeds, reachability, distances and expansion counts over several grids.

Exit checkpoint and connections

You can leave the core refresher — the four sessions of chapters 1, 2, 4 and 5 — when you can produce and explain a small, rerunnable computation, not when every self-study or optional chapter has been read. The example below uses only NumPy and scipy.sparse from chapter 2; the graph vocabulary it needs (adjacency, neighbors, isolated vertex) is the one of positioning check 3, developed in self-study chapter 7.

A shared hand-off example: features plus a graph

Reuse the four-node graph of positioning check 3 (also the opening graph of chapter 7). Each node now has two numerical features. Compare an affine score from those features with the same score after neighbor averaging.

Preview, no prior knowledge needed: neighbor averaging followed by an affine score is the shape of one graph-neural-network layer, here with hand-chosen weights instead of learned ones. Nothing in this example is trained.

import numpy as np
from scipy import sparse

A = sparse.csr_matrix([
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
], dtype=np.float64)

X = np.array([
    [1.0, 0.0],
    [0.0, 2.0],
    [3.0, 1.0],
    [0.0, 1.0],
])                                          # (4 nodes, 2 features)

neighbor_sum = A @ X                         # (4,2)
np.testing.assert_allclose(neighbor_sum, [
    [3.0, 3.0],
    [4.0, 1.0],
    [1.0, 3.0],
    [3.0, 1.0],
])

degree = np.asarray(A.sum(axis=1)).ravel()    # [2,2,3,1]
H = np.divide(
    neighbor_sum, degree[:, None],
    out=np.zeros_like(X), where=degree[:, None] != 0
)                                          # zero vector for an isolated node

w = np.array([1.0, -1.0])
b = 0.5
score_features = X @ w + b
score_neighbors = H @ w + b

np.testing.assert_allclose(score_features, [1.5, -1.5, 2.5, -0.5])
np.testing.assert_allclose(score_neighbors, [0.5, 2.0, -1/6, 2.5])
assert score_features.shape == score_neighbors.shape == (4,)

# Relabeling vertices must relabel the aggregation result in the same way.
perm = np.array([2, 0, 3, 1])
np.testing.assert_allclose(
    A[perm][:, perm] @ X[perm],
    neighbor_sum[perm]
)

For node 0, the neighbors’ features sum to (3,3) and average to (1.5,1.5), so its neighbor-based score is 1.5-1.5+0.5=0.5. All shapes and values can be checked by hand.

What this demonstrates: compatible shapes, sparse aggregation, an explicit isolated-node convention and a relabeling check. What it does not demonstrate: learning, predictive quality or an advantage from using the graph. The weights were chosen, no targets were supplied, and the graph may smooth away useful distinctions.

Evidence to keep

• A small test file runnable with python -m pytest -q (§1.9), covering at least one shape trap, one graph edge case and one numerical invariant.
• One timing comparison with input sizes, dtype and environment recorded (§§1.8 and 2.6). Explain the asymptotic cost (chapter 4) as well as the measured ratio.
• One choice of container justified by its dominant operations (chapter 5), for example a set or dictionary instead of a list scan, or a heap for top-k selection.
• If you followed the graph branch: a short note stating the graph’s direction convention, the meaning of its edges, whether self-loops are used, and what happens to isolated vertices.
• Solutions to the positioning checks, or equivalent evidence from an existing project. Exercises 1, 3–7, 9 and 12 practise the in-class core; exercises 2, 8, 10, 11, 14 and 15 the graph branch.

Where to go next

In the Site reading route, use refreshers on demand, then proceed Machine Learning → Deep Learning. Graph ML and NLP form coordinated structural and textual branches before deeper Graph × LLM coupling. The computational-geometry extension here is optional; optimal transport, geometric deep learning or reinforcement learning become useful according to the problem, not as universal entry requirements.

Sources and scope

Sources and reading route. The brochure, captured curriculum information, the SynapseS catalog record and this repository’s reading recommendations are different kinds of evidence. Source labels and administrative information are recorded separately from this site’s study choices. Consult current official sources for enrolment requirements.

Catalog record reported on this page

The metadata below are reported from the SynapseS 2026–2027 sheet for CSC_51440_EP, titled “Scientific courses — Refresher in computer science”. This is a dated source record, not a claim that current catalog details have been reverified. Use the code and academic year to identify the official entry.

The captured catalog context also identifies sharing with the Visual Computing and Creative AI and Trustworthy and Responsible AI tracks, and a distinct Computer Graphics refresher, CSC_51438_EP. That separate unit is not covered by these notes. These contextual facts do not establish the content of the CS syllabus, which the sheet does not display.

Brochure/curriculum context versus reading recommendations

• Brochure/curriculum context: the Year 1 / Period 1 organization helps locate the refresher in the site catalogue. This page does not derive selection rules, mandatory status or equivalences from the module title or from links between pages.
• Site coverage: Python, NumPy, software practice, complexity, data structures, sorting/search/DP and graph algorithms form the independent computing refresher. Chapters 1, 2, 4 and 5 are the proposed in-class core of the 12 h; chapters 3, 6 and 7 are self-study, and chapter 8 with its research readings is an optional extension.
• Suggested workload: approximately 36 h of independent work is a planning budget for the full page, including coding and exercises. It is adjustable, is not a catalog total and has no assigned ECTS equivalent.
• Coverage limit: because official objectives and syllabus topics are not displayed in the available entry, an “official theme ↔︎ chapter” completeness mapping cannot be justified. No teaching-team authorship, endorsement or assessment equivalence is claimed.
• Reading limit: passing the exit checkpoint supplies computing evidence. Probability, calculus, statistical evaluation, learned representations and graph-specific modeling assumptions still need their own checks.

Projects and assessment

The SynapseS 2026–2027 sheet for CSC_51440_EP gives the grade format, a numeric mark out of 20 with a US letter grade, but its assessment section for the LLGA track is empty: the assessment form is not displayed (see Sources and scope). Everything below is therefore a proposal of these notes, not an official rule. The solo subjects are refresher-sized studies; the group subjects build tools that later LLGA modules reuse; the written exam shows what a short test of the in-class core and of the graph branch could look like.

The projects exercise mainly O7 (hands-on and industry practice: tests, locked environments, containers, profiling) and O4 (graph-structured data: representations, traversals, shortest paths, spanning trees), with O1 through the NumPy and cost-model foundations and O3 through the corpus and tokenizer subjects. In these proposals the repository template of §3.9 — pytest suite, lockfile, Dockerfile, logging — is mandatory for every project below and for every capstone repository.

Solo projects

1. [Solo · ≈ 20 h] Web-corpus deduplication with a Bloom filter: a paper study. Does a hand-written Bloom filter reach the false-positive rate predicted by Bloom (1970), and what does exact verification of its positives cost on a real web corpus?
   • Implement: a streaming generator pipeline that never loads the corpus into memory (ch. 1); the Bloom filter of §5.7 with double hashing (Kirsch and Mitzenmacher, 2006); an exact second pass that verifies every positive.
   • Data and papers: one WET (extracted-text) file of a recent Common Crawl snapshot, deduplicated by URL, by document and by line. B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors”, Communications of the ACM, 1970. Lee et al., “Deduplicating Training Data Makes Language Models Better”, ACL 2022, explains why the step matters; see Large Language Models, §3.1.
   • Success criterion: no false negatives; measured false-positive rates inside a 95 % binomial interval around (1-e^{-kn/m})^k for m/n\in\{6,8,12\} and three values of k, or a measured explanation of any gap; peak memory independent of the file size.
   • Deliverables: a repository in the §3.9 template with a pytest suite and a cProfile report, a 4–6 page report, a 10-minute talk. Chapters 1, 3, 4, 5.
2. [Solo · ≈ 20 h] Grid path planning: Dijkstra versus A*, a paper study. How many expansions does A* save over Dijkstra on real game maps, and when do plateaus and tie-breaking erase the gain?
   • Implement: Dijkstra and A* on implicit 8-connected grids with the octile-distance heuristic, two tie-breaking rules among equal f values, and weighted A* with f=g+w\,h for w\in\{1.5,2\}, extending Ex. 15.
   • Data and papers: the Moving AI grid benchmarks, for instance the Dragon Age: Origins maps with their scenario files (N. Sturtevant, “Benchmarks for grid-based pathfinding”, IEEE Transactions on Computational Intelligence and AI in Games, 2012). P. Hart, N. Nilsson and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths”, IEEE Transactions on Systems Science and Cybernetics, 1968.
   • Success criterion: every optimal search returns the length listed in the scenario file, under the movement rules published with the benchmark; weighted A* paths cost at most w times the optimum; expansion ratios reported as distributions over at least 200 scenarios, not single runs.
   • Deliverables: code with tests, a 4–6 page report, a 10-minute talk. Chapters 4, 5, 7. It prepares the navigation chapter of Real-time AI in Video Games.

Group projects

1. [Group of 3 · ≈ 30 h each] A tested mini graph library: adjacency lists versus CSR. When does a CSR backend beat a dictionary of lists in time and memory, and do the measured costs follow the predictions of ch. 4?
   • Implement: BFS, components, Kahn’s topological sort, Dijkstra, Bellman–Ford, Kruskal with a union-find written from scratch, and label propagation, each on both backends (§2.7 and ch. 7).
   • Data: random graphs of controlled size and density from NetworkX generators, and the SNAP road network roadNet-PA, about 1.1 million vertices (Leskovec, Lang, Dasgupta and Mahoney, Internet Mathematics, 2009). The road network is undirected and large: run Kahn’s sort on random DAGs and Bellman–Ford on the smaller graphs only.
   • Work split: traversals and topological order; shortest paths; MST, union-find and label propagation. Each member owns the invariant tests of their family; the benchmark harness is shared.
   • Success criterion: outputs of the deterministic algorithms equal to NetworkX and scipy.sparse.csgraph on at least 200 random graphs and on edge cases (empty graph, isolated vertices, self-loops, parallel edges), label propagation checked by invariants over several seeds; log–log slopes of time against |E| close to 1 for the linear-time algorithms, with the logarithmic factor of the sort- and heap-based ones visible; CSR array sizes equal to the bytes predicted from the dtypes.
   • Deliverables: an installable package in the §3.9 template with continuous integration running pytest, a 6-page report, a 15-minute talk. Chapters 2, 3, 4, 5, 7. The library then serves as the data layer of the team project of Graph ML.
2. [Group of 3 · ≈ 30 h each] From point clouds to graphs: Delaunay, kNN and radius graphs. How does the choice of proximity graph change connectivity, degrees and a neighbor-averaging feature on a labelled task?
   • Implement: kNN and radius graphs with scipy.spatial.cKDTree, Delaunay edges (ch. 8), single-link clusters from the Kruskal of §7.5, and the neighbor averaging of the exit example followed by a logistic regression.
   • Data: the make_moons and make_circles sets of scikit-learn at several noise levels for the labelled task; point clouds sampled from ModelNet10 meshes (Wu et al., “3D ShapeNets”, CVPR 2015) for the graph statistics.
   • Work split: graph builders with degeneracy tests (duplicate, collinear and cocircular points); graph statistics and MST clustering; features and evaluation against a feature-only baseline.
   • Success criterion: tested invariants (symmetric edges, no self-loops, Euclidean MST contained in the Delaunay edges for points in general position); accuracies with intervals over 10 seeds; a clear statement of when the graph helps and when it does not.
   • Deliverables: code in the §3.9 template, a 6-page report, a 15-minute talk. Chapters 2, 7, 8. It prepares the kNN graphs of point-cloud networks (DGCNN) in Analysis and Deep Learning on Geometric Data.
3. [Group of 2 · ≈ 25 h each] Prefix autocompletion with a frequency trie. Does a frequency trie with heap top-k beat binary search over a sorted array on latency and memory for a real vocabulary?
   • Implement: the frequency trie of Ex. 12, a sorted-array baseline with bisect (ch. 6), and a small HTTP service from the standard library, packaged with the Dockerfile of §3.8.
   • Data: word counts from WikiText-103 (Merity, Xiong, Bradbury and Socher, ICLR 2017), and the 50,257-entry GPT-2 tokenizer vocabulary for the extension.
   • Work split: one member writes the trie and its tests; the other writes the baseline, the service and the benchmark.
   • Success criterion: identical top-k answers from both backends on 10,000 random prefixes; p50 and p99 latencies and memory per backend; an extension that lists the GPT-2 tokens extending a given prefix, the step behind prefix-constrained decoding, which restricts the decoding step of Large Language Models, §6.1 to allowed tokens.
   • Deliverables: code in the §3.9 template, a 4-page report, a 10-minute demonstration. Chapters 3, 5, 6.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet allowed, no electronic device; four independent questions on the in-class core (chapters 1, 2, 4 and 5) and on the graph branch (chapter 7).

1. Question (5 points). Course question. Define f=\mathcal{O}(g), f=\Omega(g) and f=\Theta(g). Then explain the difference between an amortized and an expected cost, using list.append and x in set, and say why a BFS queue implemented with list.pop(0) can make BFS quadratic.

   Expected:

   • Definition 4.1, with its constants and threshold n_0.
   • Amortized: a worst-case bound on the total over any sequence of operations, with no probability (theorem 4.4, by summation or by the potential). Expected: an average under a hashing model; one lookup can still cost \Theta(n).
   • pop(0) shifts every remaining element. On a star explored from its center, the queue holds all leaves at once, so the dequeues cost \Theta(|V|^2); deque.popleft keeps BFS in \mathcal{O}(|V|+|E|).

2. Question (6 points). Computation. An undirected graph on the vertices a, b, c, d, e has the weighted edges a–b 4, a–c 1, b–c 2, b–d 5, c–d 6, c–e 10, d–e 2 and b–e 9.

   1. Run Dijkstra from a: give the order in which vertices are settled, their distances and the shortest-path tree. (b) Run Kruskal: list the accepted and rejected edges and give the MST weight. (c) Is the shortest-path tree a minimum spanning tree here? Explain why the two objectives differ.

   Expected:

   • 1. Settled in the order a 0, c 1, b 3 (through c), d 7 (through c), e 9 (through d). Tree edges a–c, c–b, c–d, d–e, of total weight 11.
   • 2. Accepted: a–c 1, b–c 2, d–e 2, b–d 5. Rejected, each closing a cycle: a–b 4, c–d 6, b–e 9, c–e 10. MST weight 10.
   • 3. No, since 11 > 10. A shortest-path tree minimizes each distance from a; an MST minimizes the total edge weight. Vertex d is closer to a through c–d (7) than through b–d (8), yet b–d is the lighter connecting edge.

3. Question (4 points). Computation. A crawler expects n=10^6 distinct URLs and can spend 1 MB on a Bloom filter. (a) Compute the bits per element, the optimal number of hash functions and the predicted false-positive rate. (b) How many bits per element, hash functions and megabytes would a false-positive rate of 10^{-3} require?

   Expected:

   • 1. 1 MB is 8\times10^6 bits, so m/n=8 and k^\star=8\ln2\approx5.5. With k=6 (or 5),

     p\approx\big(1-e^{-6/8}\big)^6\approx0.022.

   • 2. From p^\star\approx0.6185^{m/n}, a rate of 10^{-3} needs m/n\approx14.4 bits per element and k\approx10 hash functions, so m\approx1.44\times10^7 bits, about 1.8 MB.

4. Question (5 points). Short proof. (a) Prove the cut property: if e is the unique lightest edge crossing a cut of a connected weighted graph, every minimum spanning tree contains e. (b) Deduce that Kruskal’s algorithm returns the minimum spanning tree when all weights are distinct.

   Expected:

   • 1. Suppose an MST T misses e. Adding e closes a cycle, which crosses the cut an even number of times: through e and through at least one other edge f, heavier than e.
   • Removing f gives the spanning tree T+e-f, lighter than T: a contradiction.
   • 2. When Kruskal accepts an edge e, let S be the current tree that contains one of its ends. Every lighter edge was examined earlier: an accepted one lies inside a current tree, and a rejected one had both ends in a tree that can only have grown since.
   • So no lighter edge crosses the cut around S: e is its lightest crossing edge and lies in every MST by (a). The |V|-1 accepted edges therefore form the unique MST.

Grading rubric (proposal)

References

• Introduction to Algorithms (CLRS), 4th ed., MIT Press, 2022 — data structures, algorithm analysis and graph algorithms.
• Algorithm Design, Pearson, 2005 — modeling exercises, greedy algorithms, graphs and dynamic programming.
• Algorithms, 4th ed., Addison-Wesley, 2011 — readable implementations and analyses transferable to Python.
• Fluent Python, 2nd ed., O’Reilly, 2022 — advanced Python idioms, particularly relevant to chapters 1 and 3.
• Delaunay Mesh Generation, CRC Press, 2012 — empty-circle geometry, triangulation and refinement for chapter 8.
• The Python Tutorial, NumPy: the absolute basics and the pytest documentation — implementation references to keep alongside selected exercises.
• NetworkX tutorial — practical graph construction and algorithms; library representations should still be checked against their documented contracts.
• Optional reconstruction readings from chapter 8: A unified approach towards reconstruction of a planar point set (Computers & Graphics, 2015) · Hole detection in a planar point set: an empty disk approach (SMI 2017) · BallMerge: High-quality Fast Surface Reconstruction via Voronoi Balls (Computer Graphics Forum / Eurographics, 2024) · related publication index.