R04 · Week 4 Recall & Drill

Assessment scope

Attempt the recall prompts before reading the worked drill and answer explanations. The worked examples below restore the combined teaching task, with explicit contracts and checks; a local model is distinguished from a reproduced external service. The minute allocations are adjustable practice suggestions, not evidence of learning speed.

Sessions covered

• S016 — Discrete Math — Sets, Logic, Combinatorics, Graphs
• S017 — Linear Algebra I — Vectors, Dot Product, Geometry
• S018 — Linear Algebra II — Matrices, Transforms, Eigenvalues
• S019 — Calculus I — Derivatives & Chain Rule
• S020 — Calculus II — Gradients & Gradient Descent from Scratch

By the end of this revision you can

1. Translate set-builder notation into both a Python comprehension and a SQL query, and apply De Morgan's laws to simplify a negated condition.

2. Pick permutation or combination correctly from the wording of a counting problem, and justify the choice.

3. Compute a dot product by hand, predict its sign from the geometry, and explain why cosine similarity discards magnitude.

4. Read a matrix as a linear transformation whose columns are where the basis vectors land, and explain matrix multiplication as function composition.

5. Apply the chain rule through a composition of three or more functions and verify the result numerically.

6. Implement gradient descent from scratch and diagnose a learning rate that is too high or too low from the shape of the loss curve.

90-min structure

Treat this as an adjustable practice budget: 5 minutes to recall the five subjects, 30 for the blank-page questions, 30 for the worked drill, 15 to compare answers and test a counterexample, and 10 to record a gap and plan an unseen retest. The solutions and transfer exercises can take longer; the goal is correct reasoning, not racing a timer.

Blank-page reconstruction · 30 min

S016 · Discrete Math

1. Write set-builder notation for "the even numbers in S", then the equivalent Python comprehension and the equivalent SQL WHERE clause.
2. State both of De Morgan's laws, then simplify NOT (x AND (y OR NOT z)) by hand.
3. You have 10 candidates and need 3 for a team. How many teams? Now how many if the three roles are distinct and ranked?

S017 · Vectors

1. Give two equally valid descriptions of a vector, and say when each view is the useful one.
2. Write both the algebraic and the geometric formula for the dot product, and say what each factor means in the geometric one.
3. You compute cosine similarity and get a negative value. What does that tell you about the angle?

S018 · Matrices

1. Say in one sentence what a matrix does to a vector, then say what the columns of the matrix are, geometrically.
2. State the shape rule for matrix multiplication, and explain why A times B generally differs from B times A.
3. Define an eigenvector and its eigenvalue in terms of what the transformation does to that direction.

S019 · Derivatives & Chain Rule

1. Write the definition of the derivative as a limit, without looking.
2. State the chain rule for a composition, then compute the derivative of a function composed three deep, showing each factor.
3. Explain the difference between symbolic, numeric, and automatic differentiation, and where each one is used in practice.

S020 · Gradients & Gradient Descent

1. Define the gradient in one sentence, and say why the update rule subtracts it rather than adding it.
2. Distinguish batch, mini-batch, and stochastic gradient descent, and say which one modern deep learning actually uses.
3. Describe the three learning-rate failure modes and what each one looks like on a loss curve.

Hands-on drill · 30 min

Recover a known linear function with least squares and gradient descent, derive the update, then probe where the reasoning stops applying. NumPy is an optional preinstalled dependency; no package installation is part of the verified run. The exact noiseless example gives a hand-computable oracle; the noisy extension separates the generating parameters from the fitted sample optimum.

Step 1 — generate data with known parameters (5 min)

Let x take -2,-1,0,1,2 and y=2x+1. Put the x values and a column of ones in the 5-by-2 design matrix A. The parameter vector has shape (2,), residuals shape (5,), and A.T @ residual shape (2,). Because the x column sums to zero, the two columns are orthogonal: A.T @ A = diag(10,5) and A.T @ y = (20,5). The unique minimizer is therefore (2,1).

Step 2 — the closed form, as ground truth (5 min)

Least squares minimizes the squared residual norm. Calling lstsq avoids explicitly forming and inverting normal equations, which can amplify conditioning problems. For a rank-deficient matrix, the solution need not be unique; NumPy returns the minimum-norm minimizer under its numerical rank decision. None of this turns noisy observations into exact knowledge of the generating parameters.

Step 3 — gradient descent by hand (12 min)

For L(theta) = ||A theta - y||² / n, expand each squared residual and differentiate: grad L = 2 A.T (A theta - y) / n. The Hessian is H = 2 A.T A / n = diag(4,2). Parameter error after a step is (I - eta H) times its previous value. Each eigen-direction contracts precisely when |1-eta lambda| < 1; here a positive constant rate below 0.5 converges. At 0.5 the slope error oscillates without shrinking; above 0.5 it grows. These are derived properties of this full-rank quadratic, not a universal learning-rate rule.

import numpy as np
x = np.array([-2., -1., 0., 1., 2.])
y = 2*x + 1
A = np.column_stack([x, np.ones_like(x)])
reference, _, rank, _ = np.linalg.lstsq(A, y, rcond=None)
assert rank == 2 and np.allclose(reference, [2., 1.])
 
def descend(A, y, rate, steps):
    theta = np.zeros(A.shape[1]); losses = []
    for _ in range(steps):
        residual = A @ theta - y
        losses.append(float(residual @ residual / len(y)))
        theta -= rate * (2 * A.T @ residual / len(y))
    return theta, np.array(losses)
 
theta, losses = descend(A, y, .1, 200)
assert np.allclose(theta, reference, atol=1e-10, rtol=0)
assert np.all(np.diff(losses) <= 1e-14)
slow, _ = descend(A, y, .001, 200)
assert np.linalg.norm(slow-reference) > .1
unstable, _ = descend(A, y, .6, 20)
assert abs(unstable[0] - 2) > 2
 
# Retain the original multifeature/noisy objective without writing data files.
rng = np.random.default_rng(0)
X = rng.normal(size=(100, 3))
B = np.column_stack([X, np.ones(100)])
truth = np.array([2., -3., .5, 1.5])
y_noise = B @ truth + rng.normal(scale=.1, size=100)
fitted = np.linalg.lstsq(B, y_noise, rcond=None)[0]
rate = .5 / np.linalg.eigvalsh(2*B.T@B/len(B))[-1]
estimate, _ = descend(B, y_noise, rate, 300)
assert np.allclose(estimate, fitted, atol=1e-8, rtol=0)
assert np.linalg.norm(fitted-truth) > 0  # sample optimum is not generating truth

A plateau alone does not diagnose the cause: a too-small rate, ill-conditioning, an incorrect gradient or floating-point limits can look similar. Check the analytic gradient, parameter error against an independent reference, and the spectrum before changing rates. Mini-batch gradients add sampling noise; the monotonic-loss check above is not appropriate for every stochastic step. Batch uses all samples; mini-batch uses a subset; one-sample stochastic updates are a special case.

Step 4 — verify the chain rule numerically (8 min)

For the original three-deep composition sin(exp(x²)), differentiate outside-in to obtain cos(exp(x²)) exp(x²) 2x. For the current worksheet variant sin(3x²+1), the derivative is cos(3x²+1) 6x. Central differences cancel the leading O(h) forward-difference error and have O(h²) truncation error for sufficiently smooth functions; subtraction roundoff grows roughly like machine epsilon divided by h. Making h arbitrarily small is not an improvement.

import math
functions = [
    (lambda x: math.sin(math.exp(x*x)),
     lambda x: math.cos(math.exp(x*x))*math.exp(x*x)*2*x),
    (lambda x: math.sin(3*x*x+1), lambda x: math.cos(3*x*x+1)*6*x),
]
for f, derivative in functions:
    for x in (.3, .7, 1.1):
        estimates = [(f(x+h)-f(x-h))/(2*h) for h in (1e-3, 1e-4, 1e-5)]
        assert math.isclose(estimates[-1], derivative(x), abs_tol=1e-6, rel_tol=1e-6)

A discrepancy can mean wrong algebra, inappropriate h, a nondifferentiable point or numerical overflow. Symbolic differentiation manipulates formulas; numerical differentiation samples values; automatic differentiation applies derivative rules to executed operations. Backpropagation is reverse-mode differentiation, not the optimizer itself.

Discrete and geometric answer key

Even elements are written mathematically as the elements x of S for which x mod 2 = 0; in Python, use a set comprehension with x % 2 == 0. In SQL, SELECT DISTINCT x FROM values_table WHERE x % 2 = 0 expresses a corresponding query for a dialect supporting %; SQL normally has bag semantics, and NULL requires its own interpretation. De Morgan gives NOT x OR (NOT y AND z) for NOT (x AND (y OR NOT z)). With ten distinct candidates, an unordered three-person team has 10×9×8 / 3! = 120 choices, whereas three distinct roles have 10×9×8 = 720. A DAG admits a topological ordering; a graph with a directed cycle does not.

For u=(1,2), v=(3,-1), the dot product is 1×3 + 2×(-1)=1, which is positive, so the angle between these nonzero real vectors is acute. Geometrically it is ||u|| ||v|| cos(theta). Negative dot/cosine implies an obtuse angle; zero vectors have undefined cosine. Equal-direction vectors can have cosine 1 but different norms. For unit vectors, squared Euclidean distance is 2-2 cos(theta), so rankings agree. Equal candidate norms also suffice for a fixed nonzero query; normalization is sufficient, not the only possible circumstance in which rankings agree. Choose the metric from the task, not a claim that all embedding systems normalize.

A matrix maps basis vectors to its columns. Let A scale x by 2 and B rotate a quarter-turn: applying AB to (1,0) yields (0,1), whereas BA yields (0,2). Thus composition order matters. An eigenvector is a nonzero v satisfying Av=lambda v; its span is invariant: a nonzero eigenvalue scales the vector (and a negative one reverses its direction), while a zero eigenvalue sends it to the zero vector, which has no direction. A small raw determinant is not a scale-independent singularity test. A linear solver cannot remove intrinsic ill-conditioning. For a square full-rank system M z = b, use np.linalg.solve(M, b) when the solution, not the inverse matrix, is needed. It factorizes and solves without materializing every column of an inverse; this avoids unnecessary work for that task, not a universal timing or accuracy ranking. For the rectangular or rank-deficient fitting problem here, use lstsq and inspect rank/residuals instead of assuming solve has the same contract.

M = np.array([[2., 1.], [1., 3.]])
b = np.array([5., 5.])
z = np.linalg.solve(M, b)
assert np.allclose(z, [2., 1.]) and np.allclose(M @ z, b)
# A zero eigenvalue is allowed; its eigenvector must still be nonzero.
zero_direction = np.array([1., 0.])
assert np.allclose(np.diag([0., 2.]) @ zero_direction, [0., 0.])

Exercise with solution: replace the x column by a constant-one column. The design matrix is rank one, so infinitely many slope/intercept pairs have the same sum. lstsq chooses the minimum-norm pair, but the original true slope is not identifiable. This is a modeling failure, not evidence that gradient descent needs more steps. For a nonconvex objective, a small gradient may indicate a saddle or local minimum and need not occur at all; training loss and held-out usefulness remain separate.

Definitions that make the numerical drill intelligible

For a differentiable scalar function, the derivative is the limit of (f(x+h)-f(x))/h as h approaches zero. It gives the local linear approximation f(x+h) ≈ f(x)+f'(x)h. For several coordinates the gradient is the vector of partial derivatives. The first-order change in direction v is the dot product of gradient and v. Choosing v equal to the negative gradient gives -||gradient||², so a sufficiently small step reduces a smooth function when the gradient is nonzero; a large finite step need not do so.

A vector can be coordinates relative to a chosen basis (useful for calculation) or a geometric displacement independent of that coordinate representation (useful for transformations). An m-by-k matrix times a k-by-n matrix gives an m-by-n matrix; the shared k is the intermediate vector space's dimension. With column vectors, AB means B first, then A.

For ordinary two-valued logic, not (x and y) is (not x) or (not y), and not (x or y) is (not x) and (not y). SQL additionally has UNKNOWN and bag semantics, so specify the translation rather than treating a table as a Python set. An inner equijoin is a filtered Cartesian product; an outer join also manufactures unmatched rows. DISTINCT removes duplicate result rows, and GROUP BY partitions rows by their grouping keys under SQL's grouping rules (including grouping NULL keys together). For example, SELECT parity, COUNT(*) FROM tagged GROUP BY parity counts the equivalence classes tagged by parity. Hash partitioning can use hash(key) % bucket_count with a positive bucket count; collisions share a bucket and do not make unequal keys equal. Dependency scheduling uses a DAG only when the dependencies are acyclic; a directed cycle is an error to detect, not a valid topological schedule.

# A hand-sized discrete/geometric transfer check.
import itertools
import math
S = {-3, -2, -1, 0, 1, 2, 3}
assert {x for x in S if x % 2 == 0} == {-2, 0, 2}
for p, q, r in itertools.product([False, True], repeat=3):
    assert (not (p and (q or not r))) == ((not p) or ((not q) and r))
assert math.comb(10, 3) == 120 and math.perm(10, 3) == 720
scale = np.diag([2., 1.])
rotate = np.array([[0., -1.], [1., 0.]])
v = np.array([1., 0.])
assert np.allclose(scale @ rotate @ v, [0, 1])
assert np.allclose(rotate @ scale @ v, [0, 2])
# Rank-one transfer solution: only slope+intercept can be identified.
C = np.ones((5, 2))
minimum_norm, _, rank, _ = np.linalg.lstsq(C, np.full(5, 3.), rcond=None)
assert rank == 1 and np.allclose(minimum_norm, [1.5, 1.5])

Learning-rate diagnosis: the exact quadratic supplies three contrasting observations: .001 contracts slowly, .1 contracts quickly, and .6 expands the slope error. At .5 the slope oscillates without decaying. For a different dataset, recompute the Hessian spectrum; do not carry those thresholds over. Mini-batch training is common in deep learning, but full-batch and one-example methods also exist. A loss curve alone cannot distinguish a bad gradient from a poor rate: the independent least-squares and finite-difference checks supply that missing evidence.

Answer constraints and corrections

The exact noiseless slope/intercept is (2,1). Avoid explicitly inverting AᵀA; lstsq also handles rank deficiency under its documented contract. Finite differences balance truncation and roundoff, so disagreement at tiny h need not mean wrong calculus. A small determinant alone is not a condition-number test.

Gap analysis + next week preview · 10 min

Score each original recall question separately: explain unaided; explain with a hint; or not yet. A fluent verbal answer is not a successful implementation. Choose one failed concept, write a counterexample that distinguishes the mistaken rule from the correct one, and schedule an unseen retest. Keep successes as well as failures in the log so the plan does not become a list of increasingly familiar problems.

For the drill, require an explicit input contract, a correctness argument or domain assumption, one ordinary case, one boundary case and an independent expected result. A chart, compile success or passing sample alone does not meet that rubric. Use the stated input contracts and named runtime when interpreting a result; finite tests and timing samples are not universal correctness or performance guarantees.

Next week (S021–S025) finishes the math block and opens data structures: probability with random variables, distributions and expectation; statistics with the central limit theorem, hypothesis testing and confidence intervals; then arrays and strings with the two-pointer pattern; hashmaps and sets with hash functions and collisions; and linked lists. The dot-product and Big-O reflexes you have been building are exactly what the DSA sessions assume you already own.

Corrective source notes

• NumPy 2.4.0 — solve source contract — solve requires a square full-rank coefficient matrix and uses LAPACK gesv; use the distinct least-squares contract otherwise. Pinned raw source retrieved and reviewed 2026-10-09.

• numpy.linalg.lstsq — NumPy v2.5 Manual — Least squares returns a minimum-norm minimizer when minimizers are nonunique. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.

• numpy.linalg.cond — NumPy v2.5 Manual — Condition number measures sensitivity; raw determinant magnitude is not a scale-independent substitute. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.

• 3.6 The Chain Rule - Calculus Volume 1 | OpenStax — The chain rule differentiates a composition through inner and outer derivatives. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.

• Lecture 7: Gradient Descent (and Beyond) — Excessive learning rate can cause divergence; the lesson derives its own exact quadratic threshold. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.

The cited passages support these named claims. The algebra, counterexamples and executable fixtures supply the lesson-specific reasoning; finite checks are not universal benchmarks.