Deep learning from scratch

1.Matrix multiply with shape check

Write matmul(A, B). A is an n×k matrix and B is a k×m matrix, each a list of rows. Return the n×m product C as a list of rows, where C[i][j] = Σ_t A[i][t]·B[t][j]. If the number of columns of A differs from the number of rows of B, return None. Inputs are non-empty and every row of a matrix has the same length.

2.Matrix transpose

Write transpose(M) for a matrix given as a list of rows (r rows, each of length c). Return the c×r matrix T as a list of rows with T[j][i] = M[i][j]. A 1×c input becomes c rows of one value each. An empty input [] returns [].

3.Scaled dot-product attention

Write attention(Q, K, V). Q is n×d (query rows), K is m×d (key rows), V is m×e (value rows). For each query q: score_j = (q·K[j]) / √d, weights w = softmax over the m scores (subtract the max score before exp), output = Σ_j w_j·V[j], a list of length e. Return the n outputs as a list of rows.

4.Causal self-attention

Write causal_attention(Q, K, V) for one sequence of n positions: Q and K are n×d, V is n×e, all lists of rows. Query i may only attend to positions j ≤ i. For query i: score_j = (Q[i]·K[j]) / √d for j ≤ i, softmax over those scores only (subtract their max), output = Σ_{j≤i} w_j·V[j]. Return the n output rows.

5.Split into attention heads

Write split_heads(X, h). X is n×D (n token rows of width D). Cut each row into h consecutive chunks of size D/h; chunk k belongs to head k. Return a list of h heads, each an n×(D/h) list of rows, so result[k][i] = X[i][k·D/h:(k+1)·D/h]. If D is not divisible by h, return None.

6.Merge attention heads

Write merge_heads(H), the inverse of a head split. H is a list of h heads, each n×s (n token rows of width s). Return the n×(h·s) matrix whose row i is the concatenation H[0][i] + H[1][i] + … + H[h−1][i], heads in order. If H is empty return [].

7.Layer normalization

Write layer_norm(x, gamma, beta, eps) for one vector x of length d. μ = mean of x, σ² = population variance Σ(x_i − μ)²/d. Return the list y with y_i = gamma_i·(x_i − μ)/√(σ² + eps) + beta_i. eps goes inside the square root. gamma and beta have length d.

8.RMS normalization

Write rms_norm(x, g, eps) for one vector x of length d. r = √(Σ x_i²/d + eps), with eps inside the root. Return y with y_i = g_i·x_i / r. Do not subtract the mean. g has length d.

9.GELU (tanh approximation)

Write gelu(xs) for a list of numbers using the tanh approximation: gelu(x) = 0.5·x·(1 + tanh(√(2/π)·(x + 0.044715·x³))). Return the list of gelu values in the same order. Use math.tanh.

10.Stable log-softmax

Write log_softmax(z) for a list of logits. Return the list with entries z_i − m − log Σ_j exp(z_j − m), where m = max(z) and log is natural. Subtracting m keeps exp from overflowing; logits can be as large as 1000.

11.Cross-entropy from logits

Write cross_entropy(logits, targets). logits is a batch of B rows, each with C class scores; targets is a list of B class indices. Per row, loss = −log_softmax(row)[target] = log Σ_j exp(z_j − m) + m − z_target with m = the row max. Return the mean loss over the batch (natural log). Logits can be as large as 1000.

12.Label smoothing targets

Write smooth_labels(targets, num_classes, eps). targets is a list of class indices. For each, build a row of length num_classes where every class gets eps/num_classes and the target class additionally gets 1 − eps (so it holds 1 − eps + eps/num_classes). Return the list of rows; each row sums to 1.

13.Sinusoidal positional encoding

Write positional_encoding(n, d). Return n rows of length d, row pos for pos = 0..n−1. For each even column 2i: PE[pos][2i] = sin(pos / 10000^(2i/d)); the odd column after it uses the same angle: PE[pos][2i+1] = cos(pos / 10000^(2i/d)). If d is odd the last column is a sin column. Use the full d in the exponent.

14.Rotary position embedding

Write rotary(x, pos, base) for a vector x of even length d. Split it into halves a = x[:d/2], b = x[d/2:]. For i = 0..d/2−1, θ_i = pos / base^(2i/d), a'_i = a_i·cos θ_i − b_i·sin θ_i, b'_i = a_i·sin θ_i + b_i·cos θ_i. Return a' followed by b' (length d). Pair i is (x[i], x[i + d/2]), not adjacent entries.

15.Inverted dropout with a given mask

Write dropout(x, mask, p, training). x and mask are lists of equal length; mask holds 1 (keep) or 0 (drop); p is the drop probability, 0 ≤ p < 1. If training is True return x_i·mask_i/(1 − p) for each i (inverted dropout). If training is False return x unchanged as a new list, ignoring the mask.

16.Gradient clipping by global norm

Write clip_by_global_norm(grads, max_norm). grads is a list of gradient vectors (one list per parameter). total = √(sum of squares of every entry across all vectors). If total > max_norm, multiply every entry by max_norm/total; otherwise leave them as they are. Return [clipped_grads, total], with clipped_grads the same nested shape as grads.

17.SGD with momentum step

Write sgd_momentum(w, g, v, lr, mu) for one step. w, g, v are lists of equal length (weights, gradients, velocity). New velocity v'_i = mu·v_i + g_i, then new weight w'_i = w_i − lr·v'_i, using the new velocity. Return [w', v'].

18.Adam step with bias correction

Write adam_step(w, g, m, v, t, lr, b1, b2, eps); w, g, m, v are equal-length lists, t is the step count starting at 1. m' = b1·m + (1−b1)·g; v' = b2·v + (1−b2)·g²; m̂ = m'/(1 − b1^t); v̂ = v'/(1 − b2^t); w' = w − lr·m̂/(√v̂ + eps), all elementwise; eps is outside the root. Return [w', m', v'], storing m', v' uncorrected.

19.Warmup then cosine learning rate

Write lr_at(t, base_lr, warmup, total, min_lr) for integer step t ≥ 0. If t < warmup: lr = base_lr·t/warmup. Otherwise p = min(1, (t − warmup)/(total − warmup)) and lr = min_lr + 0.5·(base_lr − min_lr)·(1 + cos(π·p)). Assume total > warmup ≥ 0. Return lr as a float.

20.Embedding lookup and gradient

Write embedding(table, ids, grad_out). table is V×d (row r is the vector of token r), ids is a list of n token ids, grad_out is n×d (gradient for each looked-up row). Return [out, grad_table]: out[k] = table[ids[k]] (copies), and grad_table is V×d starting at zeros with grad_out[k] added to row ids[k]; repeated ids add up.

21.1D convolution with stride and padding

Write conv1d(x, w, b, stride, padding). Pad x with padding zeros on each side to get xp. Output i = b + Σ_j w[j]·xp[i·stride + j] (no kernel flip), for i = 0, 1, … while i·stride + len(w) ≤ len(xp); length is ⌊(len(x) + 2·padding − len(w))/stride⌋ + 1. Return the outputs; return [] if the kernel is longer than xp.

22.1D max pooling

Write max_pool1d(x, size, stride). Windows start at 0, stride, 2·stride, …, and each covers size consecutive entries. Only full windows count: a trailing partial window is dropped. Return the max of each window in order. Values can be negative. If x is shorter than size return [].

23.Pre-norm residual block

Write prenorm_block(x, W, b, eps) for one vector x of length d. Step 1: h = layer norm of x without scale or shift: h_i = (x_i − μ)/√(σ² + eps), μ the mean, σ² the population variance. Step 2: f_j = Σ_i h_i·W[i][j] + b_j, W is d×d as a list of rows. Step 3: return x + f elementwise (the residual adds the original x, not h).

24.KL divergence

Write kl_divergence(p, q) for two probability lists of equal length. KL = Σ p_i·ln(p_i/q_i) over indices with p_i > 0; terms with p_i = 0 contribute 0 and are skipped. If some p_i > 0 has q_i = 0 the divergence is infinite: return None. Otherwise return the float.

25.Perplexity from log probabilities

Write perplexity(logprobs), where logprobs is a list of natural-log probabilities, one per token. Perplexity = exp(−(1/N)·Σ logprobs), using the mean, not the sum. Return it as a float, or None if the list is empty.

26.Top-k logit filter

Write top_k_filter(logits, k) with k ≥ 1. Let t be the k-th largest value in logits (counting duplicates). Keep every logit ≥ t and replace the rest with None (standing for −inf), keeping positions. Ties at t are all kept, so more than k may survive. If k ≥ len(logits) return a copy of logits.

27.Temperature-scaled softmax

Write temperature_softmax(logits, T). Divide every logit by T, then return softmax: p_i = exp(z_i/T − m) / Σ_j exp(z_j/T − m), where m = max_j z_j/T. If T ≤ 0 return None. Small T sharpens and makes z/T huge, so the max subtraction is required.

28.Greedy decoding on a transition table

Write greedy_decode(table, start, end, max_len). table[a][b] is the logit for token b following token a. Start with seq = [start]; repeatedly append the argmax of table[last token] (lowest index on ties). Stop right after appending end (start itself never stops it), or when len(seq) reaches max_len (max_len ≥ 1 includes start). Return seq as a list of ints.

29.Numerical gradient check

Write grad_check(coeffs, x, h). f(x) = Σ_k coeffs[k]·x^k (coeffs[0] is the constant). Return [numeric, analytic]: numeric = (f(x + h) − f(x − h)) / (2h), the central difference, and analytic = Σ_{k≥1} k·coeffs[k]·x^(k−1), the exact derivative; skip k = 0, since x can be 0 and 0^(−1) is undefined. Empty coeffs means f = 0.