Exercises

Assume $\sqrt 2 = p/q$ in lowest terms and look at parity.

If $p^2 = 2q^2$ then $p^2$ is even, so $p$ is even: $p = 2k$. Then $4k^2 = 2q^2$, so $q^2 = 2k^2$ and $q$ is even too, contradicting that $p/q$ was in lowest terms.

$0.1$, $0.2$ and $0.3$ have infinite binary expansions, so each is rounded to the nearest double. The rounded $0.1$ plus the rounded $0.2$, rounded again, lands on a different double than the rounded $0.3$. Compare with a tolerance: $|a - b| \le \varepsilon \max(|a|, |b|)$.

$-5 < 2x - 3 < 5 \iff -1 < x < 4$, i.e. $x \in (-1, 4)$.

Domain: $4 - x^2 > 0 \iff x \in (-2, 2)$. On it $4 - x^2 \in (0, 4]$, so the range is $(-\infty, \ln 4]$.

No: the same (empty) input gives different outputs. It becomes a mathematical function if the time is made an explicit input, $f(t)$ — which is exactly what makes code testable.

Naively $4 + 3 + 1 = 8$ (computing each power from scratch). Horner: $((3x - 2)x + 0)x + 1)x - 7$, 4 multiplications.

$2^{t/1.5} = 100 \Rightarrow t = 1.5 \log_2 100 \approx 1.5 \cdot 6.64 \approx 10$ years.

Both are equal since $e^{z_i} = e^m e^{z_i - m}$. But $e^{1000}$ overflows a double, while every $e^{z_i - m} \le 1$ and at least one equals 1, so the sum is in $[1, n]$ and safe.

$|\frac{3n+1}{n} - 3| = \frac1n < \varepsilon$ whenever $n > 1/\varepsilon$; take $N = \lfloor 1/\varepsilon \rfloor + 1$.

$2 \cdot 2^{-k} < 10^{-3} \iff k > \log_2 2000 \approx 10.97$, so 11 epochs. The error shrinks by a constant factor: linear (geometric) convergence.

Multiply and divide by $\sqrt{1+x} + 1$.

$\frac{(1+x) - 1}{x(\sqrt{1+x} + 1)} = \frac{1}{\sqrt{1+x}+1} \to \frac12$.

The graph oscillates between $-1$ and $1$ infinitely often near 0. Along $x_n = \frac{1}{2\pi n}$ the values are $0$; along $x_n = \frac{1}{2\pi n + \pi/2}$ they are $1$. Two sequences, two different limits.

Left limit $k + 1$, value $f(1) = 4$. Continuity requires $k + 1 = 4$, so $k = 3$.

$H$ is constant except at 0, so its derivative is 0 almost everywhere (and undefined at 0). Every gradient flowing through it is zero: the weights never move.

$\frac{1}{h}\left(\frac{1}{x+h} - \frac1x\right) = \frac{-h}{h\,x(x+h)} = \frac{-1}{x(x+h)} \to -\frac{1}{x^2}$.

$f'(x) = 3x^2 - 3$: zero at $x = \pm1$ (a local max at $-1$, a local min at $1$), negative on $(-1,1)$ where $f$ decreases, positive outside.

$L'(w) = 2(w - 3)$. $w_1 = 0 - 0.1\cdot(-6) = 0.6$; $w_2 = 0.6 - 0.1\cdot(-4.8) = 1.08$. Each step closes 20% of the gap to the minimum $w = 3$.

$f'(x) = \frac{(2x + x^2)e^x(1 + x) - x^2 e^x}{(1+x)^2} = \frac{x e^x (x^2 + 2x + 2)}{(1 + x)^2}$.

$\sigma'(x) = \frac{e^{-x}}{(1 + e^{-x})^2} = \frac{1}{1 + e^{-x}}\cdot\frac{e^{-x}}{1 + e^{-x}} = \sigma(1 - \sigma)$. Since $s(1 - s) \le \frac14$, the maximum is $\frac14$ at $x = 0$ — so each sigmoid layer shrinks gradients by at least a factor 4, one cause of vanishing gradients.

$h'(x) = \frac{1}{1 + e^{3x}}\cdot 3e^{3x} = 3\,\sigma(3x)$ — the derivative of softplus is a sigmoid.

Each $\sigma' \le \frac14$, so the product is at most $4^{-20} \approx 9 \cdot 10^{-13}$: vanishing gradients. ReLU ($\text{derivative } 1$ when active) and residual connections avoid it.

$f'(x) = 4x^2(x - 3)$: critical points 0 and 3. $f'(x) = 12x^2 - 24x$; $f'(3) = 36 > 0$ → minimum. At 0, $f' = 0$ and $f'$ does not change sign (negative on both sides): not an extremum.

$c'(n) = -100/n^2 + 4 = 0 \Rightarrow n = 5$; $c'(n) = 200/n^3 > 0$, so it is a minimum, $c(5) = 40$.

$2^{-(k+1)} < 10^{-6} \iff k + 1 > 6\log_2 10 \approx 19.9$: $k = 19$ steps.

On each strip the midpoint rectangle over- and under-estimates by nearly equal amounts on the two halves, so the first-order errors cancel and only a curvature term $O(\Delta x^3)$ per strip survives: total $O(1/n^2)$ instead of $O(1/n)$.

$[x^3 - x^2]_0^2 = 8 - 4 = 4$. Positive: the area above the axis (for $x > 2/3$) exceeds the small negative part on $(0, 2/3)$.

$\pi = 4\int_0^1\sqrt{1 - x^2}\,\dd x \approx \frac4N\sum\sqrt{1 - u_i^2}$ with $u_i$ uniform. The standard error is about $0.9/\sqrt N$; for $\pm 0.0005$ you need $N \approx 3\cdot10^6$. Monte Carlo is simple but slow.

No: $\frac{k}{k^2+1} \ge \frac{1}{2k}$ for $k \ge 1$, and $\sum\frac1{2k}$ diverges (comparison with the harmonic series).

$H_{10^6} \approx \ln 10^6 + 0.577 \approx 14.39$, so about $2\cdot10^6\cdot14.39 - 4\cdot10^6 \approx 2.5\cdot10^7$ comparisons ($\approx 1.39\,n\log_2 n$).

$\sum 0.99^k = \frac{1}{0.01} = 100$. Rewards beyond about $\frac{1}{1-\gamma} = 100$ steps contribute little: the effective horizon is ~100 steps.

$1 + i = \sqrt 2\, e^{i\pi/4}$, so $(1+i)^8 = 2^4 e^{2\pi i} = 16$.

At $e^{2\pi i k/6}$, $k = 0,\dots,5$: the vertices of a regular hexagon inscribed in the unit circle.

$(\log n)^{10} \ll n\log^2 n \ll n^{3/2} \ll n^{\log n} \ll 2^{\sqrt n}$ (compare logarithms: $10\log\log n$, $\log n$, $1.5\log n$, $\log^2 n$, $\sqrt n$).

$\Theta(n^2)$: factor $10^6$ → about 11.6 days. $\Theta(n\log n)$: factor $1000 \cdot \frac{\log 10^6}{\log 10^3} = 2000$ → about 33 minutes.

$\sqrt{4.1} \approx 2 + \frac{1}{2\sqrt4}\cdot 0.1 = 2.025$ (true value $2.02485…$).

$\sin x - \sin y = \cos(c)\,(x - y)$ for some $c$, and $|\cos c| \le 1$.

Average speed $= 10 / (5/60) = 120$ km/h. By the MVT, at some instant $s'(t) = 120 > 110$.

By the FTC and the chain rule: $e^{-x^4}\cdot 2x$.

Position is $s(0) + \int_0^T v$ (FTC). With samples, approximate the integral by a sum, e.g. the trapezoidal rule $\sum \frac{v_k + v_{k+1}}{2}\,0.1$. Errors accumulate (drift), which is why IMUs are fused with GPS.

Three applications: $\frac{1 - \cos x}{3x^2} \to \frac{\sin x}{6x} \to \frac{\cos x}{6} \to \frac16$.

$f'(x) = \sigma(x)$ and $f'(x) = \sigma(x)(1 - \sigma(x)) > 0$.

No. Swapping two hidden neurons (and their outgoing weights) gives a different weight vector with the same loss. If $\theta_1 \ne \theta_2$ are both minima, convexity would make their midpoint at least as good — but the midpoint averages the two neurons into identical ones, generally worse. Symmetric minima rule out convexity.

$x_{k+1} = x_k - \frac{x_k^3 - 2x_k - 5}{3x_k^2 - 2}$. $x_1 = 2 - \frac{-1}{10} = 2.1$, $x_2 = 2.1 - \frac{0.061}{11.23} \approx 2.094568$ (root $2.0945515$).

$x_1 = 0 - \frac{2}{-2} = 1$, $x_2 = 1 - \frac{1}{1} = 0$: a 2-cycle. The tangents bounce between 0 and 1 forever; the real root ($\approx -1.77$) is in another basin.

Take $f(x) = \frac1x - a$: $x_{k+1} = x_k - \frac{1/x_k - a}{-1/x_k^2} = x_k(2 - a x_k)$. No division needed — this is how many processors divide.

$T_4 = 1 - \frac{x^2}{2} + \frac{x^4}{24}$; $T_4(0.5) = 0.8776041\overline{6}$ vs $\cos 0.5 = 0.8775826$ (error $2 \cdot 10^{-5}$).

$L(w + h) \approx L + L'h + \frac12 L''h^2$; setting the derivative in $h$ to zero gives $h = -L'/L''$. That is Newton's method for optimization.

$|R_n| \le \frac{e}{(n+1)!} < \frac{3}{(n+1)!}$. $(n+1)! > 3 \cdot 10^{10}$ needs $n + 1 = 14$ ($14! \approx 8.7 \cdot 10^{10}$), so $n = 13$.

$\frac{1}{1+x^2} = \sum (-1)^k x^{2k}$; integrate: $\arctan x = \sum\frac{(-1)^k x^{2k+1}}{2k+1}$. At $x = 1$: $\frac\pi4 = 1 - \frac13 + \frac15 - \dots$ (Leibniz; very slow).

$f_x = ye^{xy}$, $f_y = xe^{xy}$, $f_{xx} = y^2e^{xy}$, $f_{yy} = x^2e^{xy}$, $f_{xy} = f_{yx} = (1 + xy)e^{xy}$.

$\frac{\partial L}{\partial\hat y} = \frac{\hat y - y}{\hat y(1 - \hat y)}$, $\frac{\partial\hat y}{\partial z} = \hat y(1 - \hat y)$, $\frac{\partial z}{\partial w_1} = x_1$. The product simplifies to $(\hat y - y)x_1$: sigmoid and cross-entropy cancel beautifully.

$\nabla f = (2xy, x^2 + z^3, 3yz^2) = (4, 0, 6)$. $D_u f = (4 + 0 + 6)/\sqrt3 = 10/\sqrt3 \approx 5.77$; the maximum possible is $\norm{\nabla f} = \sqrt{52} \approx 7.21$.

Level curves are ellipses, wider in $x$. The gradient $(4, 8)$ is perpendicular to the ellipse through $(2,1)$, which is not the radial direction $(2, 1)$ because the ellipse is not a circle.

Finite differences perturb one parameter at a time. Reverse mode runs the program once forward, then once backward propagating $\partial L/\partial(\text{intermediate})$; each intermediate is visited once, so the cost is a constant multiple of the forward pass, independent of the number of parameters (one scalar output).

$(y, x) = \lambda(1, 1)$ gives $x = y = \lambda$, and $x + y = 10$ gives $x = y = 5$, $f = 25$, $\lambda = 5$.

$\partial_{p_i}\big[-\sum p\ln p - \lambda(\sum p - 1) - \beta(\sum pE - \bar E)\big] = -\ln p_i - 1 - \lambda - \beta E_i = 0$, so $p_i = e^{-1-\lambda}e^{-\beta E_i}$: a softmax of $-\beta E$.

$w_r = f_x\cos\theta + f_y\sin\theta$, $w_\theta = -f_x r\sin\theta + f_y r\cos\theta$.

Let $z_1 = W_1x$, $a = \sigma(z_1)$, $z_2 = W_2a$. With $g = \partial\ell/\partial z_2$: $\partial L/\partial W_2 = g\,a^{\mathsf T}$ and $\partial L/\partial W_1 = \big((W_2^{\mathsf T}g)\odot\sigma'(z_1)\big)x^{\mathsf T}$. The upstream gradient $g$ is computed once and reused: that sharing is what makes backprop cheap.

$J = \begin{pmatrix}2x & -2y\\ 2y & 2x\end{pmatrix}$, $\det J = 4(x^2 + y^2)$. Only at the origin ($F$ is $z \mapsto z^2$ in complex form).

$\det J = \ell_1\ell_2\sin q_2$: zero when $q_2 = 0$ or $\pi$ — arm fully stretched or folded. There the hand cannot move radially.

$\nabla f = (3x^2 - 3, 2y) = 0$ at $(\pm1, 0)$. $H = \operatorname{diag}(6x, 2)$: at $(1,0)$ positive definite → minimum; at $(-1, 0)$ indefinite → saddle.

$H = \operatorname{diag}(1, 100)$, so $\eta < 2/100 = 0.02$. Along $x$ each step multiplies the error by $1 - \eta \approx 0.98$: $0.98^k = 10^{-3} \Rightarrow k \approx 342$. Condition number 100 makes it slow.

$2xy - 2xy + 1 = 1$.

With $y_1 = y$, $y_2 = y'$: $y_1' = y_2$, $y_2' = \sin t - 2y_1 - 3y_2$.

$T - 20 = 15e^{-kt}$; $10 = 15e^{-10k} \Rightarrow k = \ln(1.5)/10$. $2 = 15e^{-kt} \Rightarrow t = 10\ln 7.5/\ln 1.5 \approx 49.7$ min.

$y_1 = 1 + 0.5(0 - 1) = 0.5$; $y_2 = 0.5 + 0.5(0.5 - 0.5) = 0.5$; $y_3 = 0.5 + 0.5(1 - 0.5) = 0.75$ (exact $y(1.5) = 1.5 - 1 + 2e^{-1.5} \approx 0.946$).

Each explicit step moves along the tangent, outside the circle: the radius and energy grow every step and the planet spirals out. Semi-implicit Euler is symplectic: it preserves a slightly perturbed energy, so the orbit stays closed for very long times.

Near a minimum $\nabla L \approx H(\theta - \theta^\ast)$, so GD is Euler on $\dot e = -He$. Along the top eigenvector, $e_{k+1} = (1 - \eta\lambda_{\max})e_k$, which grows when $|1 - \eta\lambda_{\max}| > 1$, i.e. $\eta > 2/\lambda_{\max}$.

$\int_0^1 x(1-x)\,\dd x = \frac16$, so $c = 6$. By symmetry $P(X > 0.5) = 0.5$.

By parts: $\int_0^\infty x\lambda e^{-\lambda x}\,\dd x = \big[-xe^{-\lambda x}\big]_0^\infty + \int_0^\infty e^{-\lambda x}\,\dd x = \frac1\lambda$.

If the batch is drawn uniformly at random, $\E[\frac1{|B|}\sum_{i\in B}\nabla\ell_i] = \frac1N\sum_i\nabla\ell_i$ by linearity of expectation (and exchanging gradient and expectation, which needs mild smoothness). Non-random batches (e.g. sorted data) break it.

Euler: $h \approx 10^{-6}$ → $10^6$ evaluations. RK4: $h^4 \approx 10^{-6}$ → $h \approx 0.03$, about 32 steps → ~130 evaluations. Higher order wins by orders of magnitude.

$x = 0$ and $x = 1$. $f'(x) = 1 - 2x$: $f'(0) = 1 > 0$ unstable, $f'(1) = -1 < 0$ stable. Every positive population tends to the carrying capacity.

$b_n = \frac2\pi\int_0^\pi\sin nt\,\dd t = \frac{2}{n\pi}(1 - (-1)^n)$: $\frac{4}{n\pi}$ for odd $n$, 0 for even $n$.

Three FFTs of size ~$2N$ plus a pointwise product: about $3\cdot 2N\log_2(2N) \approx 1.3\cdot10^8$ vs $10^{12}$ — roughly 8000 times faster.

A narrow pulse has a very wide, flat spectrum (all frequencies); a long pure tone has a narrow peak. Time width × frequency width is bounded below.

$[0.5,\ 1.5,\ 2.5,\ 1.5]$: a moving average (with the edges padded by zeros).

$\ell(\lambda) = N\ln\lambda - \lambda\sum x_i$; $\ell'(\lambda) = N/\lambda - \sum x_i = 0 \Rightarrow \hat\lambda = 1/\bar x$.

$-\log p(y\mid x) = |y - f_\theta(x)|/b + \text{const}$; summing over the data, maximizing likelihood is minimizing $\sum|y_i - f_\theta(x_i)|$.

$t = \ln(10^6)/0.5 \approx 27.6$ days. With $10^{-12}$: $55.3$ days. A million times better data only doubles the horizon.

The truncation error is $\approx \frac{h}{2}f''$ but the rounding error of the numerator is $\approx \varepsilon f/h$. Their sum is minimized at $h \approx \sqrt\varepsilon \approx 10^{-8}$; smaller $h$ amplifies rounding.

$-\ln 0.01 \approx 4.6$ vs $-\ln 0.9 \approx 0.105$. Confidently wrong predictions are punished ~44 times more.

$\theta_{k+1} = (1 - \eta a)\theta_k$, which tends to 0 iff $|1 - \eta a| < 1$. With $\eta = 1/a$ it jumps to the minimum in one step.

P pushes up in proportion to the 2 m error; D brakes as the error shrinks quickly, preventing overshoot; I accumulates any persistent error. With only P, gravity needs a non-zero thrust, which requires a non-zero error: the drone settles below the target (steady-state error) and may oscillate if $K_p$ is large.

$y(t) = 20t - 4.9t^2$; $y'(t) = 20 - 9.8t = 0 \Rightarrow t \approx 2.04$ s, $y \approx 20.4$ m.

Differentiation amplifies high-frequency noise (in Fourier terms it multiplies by $2\pi i\xi$). Smoothing first suppresses those frequencies; since derivative and convolution commute, $\nabla(G * I) = (\nabla G) * I$, so one convolution with the derivative of a Gaussian does both.

$\partial L/\partial w = (\hat y - y)\,\hat y(1 - \hat y)\,x$ and $\partial L/\partial b = (\hat y - y)\,\hat y(1 - \hat y)$.

The local derivatives ($\sigma'(z^{(\ell)})$, $a^{(\ell-1)}$) depend on forward values. Checkpointing stores only some layers' activations and recomputes the others during the backward pass: memory drops (to $O(\sqrt L)$ with optimal placement) at the cost of roughly one extra forward pass.

$W = 1/(\mu - \lambda)$: 20 ms, 100 ms and 1 s. Going from 90% to 99% utilization multiplies latency by 10.