Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics (A10100W1)

Solutions to every answerable part of the 22 June 2023 preliminary examination in the Year 1 of the computer science course of the University of Oxford. The source groups Questions 1–3, 4–6 and 7–9 into its discrete, continuous and probability sections respectively. All nine questions are treated, although candidates were permitted at most five, with at most two from each section. Throughout, $\mathbb{N}=\{0,1,2,\dots \}$, consistent with the source's explicit exclusions of zero. Source release, member 2022/T/a10100w1.pdf: the PDF itself prints Trinity Term 2023 and A10100W1. Question statements are not reproduced.

A preorder is a binary relation that is both reflexive and transitive: $a⪯a$ for every $a\in A$, and $a⪯b⪯c$ implies $a⪯c$.

A partial order is a preorder satisfying the antisymmetric relation axiom. In addition to reflexivity and transitivity, it satisfies $a⪯b$ and $b⪯a$ only when $a=b$.

A total order is a partial order in which every pair is comparable: for every $a,b\in A$, at least one of $a⪯b$ and $b⪯a$ holds. Both hold exactly when $a=b$.

For the product order, reflexivity follows from $a_i\le a_i$ in every coordinate. If $\mathbf{a}⪯\mathbf{b}$ and $\mathbf{b}⪯\mathbf{a}$, the antisymmetric relation axiom for the usual real order gives $a_i=b_i$ for every $i$, hence $\mathbf{a}=\mathbf{b}$. If $\mathbf{a}⪯\mathbf{b}⪯\mathbf{c}$, transitivity in each coordinate gives $a_i\le c_i$, hence $\mathbf{a}⪯\mathbf{c}$. Thus this is a partial order.

For $n\ge 2$, the vectors $(1,0,0,\dots )$ and $(0,1,0,\dots )$ are incomparable: each has a coordinate larger than the corresponding coordinate of the other. It is not a total order for $n\ge 2$. The dimension qualification matters: for $n=1$ this is the usual total order on $\mathbb{R}$, so the printed non-totality claim needs the implicit assumption $n\ge 2$.

For the pointwise order on real polynomials, $p(x)\le p(x)$ proves reflexivity. Two opposite inequalities imply $p(x)=q(x)$ for every real $x$; the polynomials are therefore equal, proving the antisymmetric relation axiom. Chaining the inequalities at every $x$ proves transitivity.

To disprove total order, take $p(x)=x$ and $q(x)=0$. The inequality $p⪯q$ fails at $x=1$, whereas $q⪯p$ fails at $x=-1$. The order is partial but non-total.

The greatest element of $S$, also called its maximum, is an element $m\in S$ such that $s⪯m$ for every $s\in S$. Membership in $S$ is essential; an upper bound need not belong to $S$.

A least upper bound of $S$ is an element $u\in A$ such that $s⪯u$ for every $s\in S$, and such that $u⪯v$ for every other upper bound $v\in A$ of $S$. It need not belong to $S$. The antisymmetric relation axiom makes it unique whenever it exists.

Write each member as $3-2/(n+1)$. Every member is strictly below $3$, so $3$ is an upper bound. If $u<3$, the Archimedean property supplies $n\in \mathbb{N}$ with $n+1>2/(3-u)$; then $3-2/(n+1)>u$. Thus no smaller number is an upper bound, proving $\sup S=3$. Since $3\notin S$, there is no greatest element. Equivalently, each member is followed by a larger member because $2/(n+2)<2/(n+1)$.

For every $a$, both $aRa$ and $aSa$ hold, so the intersection of equivalence relations is reflexive. If $a(R\cap S)b$, symmetry of both component binary relations gives $bRa$ and $bSa$, hence $b(R\cap S)a$. Finally, if $a(R\cap S)b$ and $b(R\cap S)c$, transitivity in each component gives $aRc$ and $aSc$, hence $a(R\cap S)c$. These are precisely the three conditions for an equivalence relation.

For every $x\in A$, membership in the relevant equivalence class satisfiesEquality follows by axiom of extensionality. Thus $[a{]}_{R\cap S}=[a{]}_R\cap [a{]}_S$.

The floor function is constant at $j$ on the four consecutive integers $4j,4j+1,4j+2,4j+3$. Consequently the partition of a set is $\{\{4j,4j+1,4j+2,4j+3\}:j\in \mathbb{N}\}$. Different blocks are disjoint and every nonnegative integer has exactly one quotient and remainder upon division by $4$.

Take the nonempty intersections of the length-three and length-four blocks. Within the first twelve nonnegative integers the common cut points are $0,3,4,6,8,9,12$, givingThe complete partition of a set consists of these six blocks translated by $12j$ for every $j\in \mathbb{N}$. Indeed, adding $12$ increases the two floor quotients by $4$ and $3$ respectively, preserving equality of both quotients within each translated block. No adjacent displayed blocks can merge because at least one quotient changes at their boundary. This is the periodic common refinement of floor-quotient partitions, with period $\mathrm{lcm}(3,4)=12$.

Use strong induction with three consecutive base cases:For $n\ge 11$, assume all values from $8$ through $n-1$ have the required representation. Since $8\le n-3<n$, write $n-3=3k+5m$ with $k,m$ nonnegative integers. Then $n=3(k+1)+5m$ is another such representation. Strong induction proves the claim for every $n\ge 8$. This is a consecutive-base induction for additive semigroups: the three base cases handle all residues before repeated addition of $3$.

At $n=2$, the product is $1-1/4=3/4$, as required. Suppose the formula holds at $n\ge 2$. Appending the next factor giveswhich is exactly the formula at $n+1$. Thus mathematical induction gives $(n+1)/(2n)$ for every $n\ge 2$. The factorization $1-i^{-2}=(i-1)(i+1)/i^2$ also explains the cancellation in this telescoping product.

Fix $m\ge 1$ and use two-base mathematical induction on $n$. At $n=0$, the proposed right side is $F_m$; at $n=1$, it is $F_{m-1}+F_m=F_{m+1}$. Suppose the identity holds at $n$ and $n+1$. The defining recurrence relation for the Fibonacci numbers givesThis is the assertion at $n+2$, completing the proof of the Fibonacci addition formula. The argument includes $m=1$, since $F_{m-1}=F_0$ is defined.

Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of $g$ gives $f(a)=f(a^{\prime })$, and injectivity of $f$ then gives $a=a^{\prime }$. Thus the function composition is injective.

For any $c\in C$, surjectivity of $g\circ f$ supplies $a\in A$ with $g(f(a))=c$. Taking $b=f(a)\in B$ proves that $c$ has a preimage under $g$. Thus $g$ is surjective.

If $f(a)=f(a^{\prime })$, applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of the function composition forces $a=a^{\prime }$. Hence $f$ is injective.

Suppose $g(b)=g(b^{\prime })$. Since $f$ is surjective, choose $a,a^{\prime }\in A$ with $f(a)=b$ and $f(a^{\prime })=b^{\prime }$. Then $(g\circ f)(a)=(g\circ f)(a^{\prime })$, so injectivity gives $a=a^{\prime }$ and therefore $b=b^{\prime }$. Thus $g$ is injective. The use of surjectivity is what makes every point of $B$ accessible to this argument.

Fix $b\in B$. Since $g\circ f$ is surjective, there is $a\in A$ with $g(f(a))=g(b)$. Injectivity of $g$ gives $f(a)=b$, proving that $f$ is surjective. All five conclusions are instances of injectivity and surjectivity under composition.

The greatest common divisor of positive integers $a,b$ is the largest positive integer dividing both, denoted $\gcd (a,b)$. The set of positive common divisors contains $1$ and is finite, so this definition supplies a value.

The Euclidean algorithm repeatedly replaces $(r_{i-1},r_i)$ by $(r_i,r_{i-1}-q_i{r}_i)$, where the new remainder lies between $0$ and $r_i-1$. Common divisors are unchanged by this subtraction, and decreasing positive remainders ensure termination. The last nonzero remainder is the greatest common divisor.

The extended Euclidean algorithm also tracks coefficients $r_i=u_{i}a+v_{i}b$, beginning with coefficient pairs $(1,0)$ and $(0,1)$ and applying the same subtraction to the pairs. This invariant produces Bézout coefficients for the last nonzero remainder. Here the divisions areBack substitution givesThus $\gcd (580,252)=4$, with $m=10$ and $n=-23$ in Bézout's identity.

Use strong induction on the positive integer $n$. The case $n=1$ is represented by the empty product. For $n>1$, if $n$ is prime it is already a product of one prime. Otherwise $n=ab$ with $1<a,b<n$; the induction hypothesis gives prime factorizations for both $a$ and $b$, and concatenating them gives one for $n$. This proves existence in the fundamental theorem of arithmetic without presupposing uniqueness.

If $p\mid a$, there is nothing to prove. Otherwise the only possible positive common divisors of the prime $p$ and $a$ show that $\gcd (p,a)=1$. By Bézout's identity, $up+va=1$ for some integers $u,v$. Multiplying by $b$ gives $b=upb+vab$. Both terms on the right are divisible by $p$, the second because $p\mid ab$. Hence $p\mid b$. This proves Euclid's lemma, including when either factor is zero or negative.

Suppose $n=p_1\cdots p_r=q_1\cdots q_s$ are two products of positive primes. If $r=0$, then $n=1$, and necessarily $s=0$, since any nonempty product of positive primes is at least $2$. Otherwise Euclid's lemma, applied repeatedly to the right-hand product, says $p_1$ divides one $q_j$. Since $q_j$ is prime, $p_1=q_j$. Reorder the right-hand factors and cancel this common nonzero factor. Repeating, or using induction on the number of factors, matches every factor. Neither side can have factors left over, because their product would then equal $1$. Thus the prime factorization is unique up to rearrangement.

The allowed primes are exactly $2,3,5,7$. DefineThe fundamental theorem of arithmetic makes this definition unambiguous and proves injectivity. For every $(a,b,c,d)\in {\mathbb{N}}^4$, the positive integer $2^a{3}^b{5}^c{7}^d$ belongs to $S$ and maps to that tuple, proving surjectivity. The inverse function is explicitly ${\Phi }^{-1}(a,b,c,d)=2^a{3}^b{5}^c{7}^d$. In particular, $1$ maps to $(0,0,0,0)$. This is the prime-exponent parametrization of smooth numbers.

Put $\mathbf{h}=\mathbf{y}-\mathbf{x}$. For $0<t\le 1$, convexity gives $f(\mathbf{x}+t\mathbf{h})\le (1-t)f(\mathbf{x})+tf(\mathbf{y})$, henceBy the first-order form of Taylor's theorem, the right side tends to ${\mathbf{h}}^{\mathsf{T}}\nabla f(\mathbf{x})$ as $t\downarrow 0$. ThereforeThis is the supporting inequality for a differentiable convex function. The stated partial derivatives are enough: coordinate derivatives give directional Taylor expansion for convex functions, so no unmentioned continuity assumption on the second partial derivatives is needed. The result in fact needs less smoothness than the question assumes.

No. Both $f(x)=x$ and $g(x)=-x$ are affine functions, hence convex functions. Their product $h(x)=-x^2$ is not convex: at the midpoint of $-1$ and $1$, $h(0)=0>\frac{1}{2}h(-1)+\frac{1}{2}h(1)=-1$. Thus products of convex functions need not be convex, even for smooth functions on all of $\mathbb{R}$.

Differentiating on the given domain yieldsThe denominator and $\ln x+1$ are positive there. Thus $j$ is strictly concave, and is not convex.

The denominator is positive throughout the domain. Holding $y$ fixed, differentiate with respect to $x$:At the interior point $(1,1/2)$ this second partial derivative is $-2/9<0$, so the restriction to a horizontal line is locally strictly concave, ruling out convexity. At the interior point $(1,2)$ it is $4/9>0$, ruling out concavity. Restrictions of a convex function or a concave function to every line segment must retain that property. Consequently $k$ is neither convex nor concave on its stated domain.

Since $\mathbf{a}\ne 0$, the line $\mathbf{x}=t\mathbf{a}/\Vert \mathbf{a}{\Vert }^2$ lies in the domain and satisfies ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}=t$. The restriction of $l$ to this line is $t^3$, whose second derivative is $6t$: negative for $t<0$ and positive for $t>0$. It can be neither globally convex nor globally concave. Hence $l$ is neither. Equivalently, its Hessian matrix is $6({\mathbf{a}}^{\mathsf{T}}\mathbf{x})\mathbf{a}{\mathbf{a}}^{\mathsf{T}}$, changing the sign of its nonzero directional curvature across ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}=0$.

Eliminate the constraint by writing $y=1/x$, with $x>0$. The logarithms cancel, so the objective becomes $q(x)=1/x+2x$. Its derivatives are $q^{\prime }(x)=-1/x^2+2$ and $q^{\prime \prime }(x)=2/x^3>0$. Thus the unique stationary point is the unique global minimum, at $x=1/\sqrt{2}$. Restoring $y$ givesAs a direct global check, the arithmetic-geometric mean inequality gives $1/x+2x\ge 2\sqrt{2}$, with equality exactly at the same point.

Interpret the norms as Euclidean norms and set $B=A^{\mathsf{T}}A$. This is a real symmetric matrix with ${\mathbf{x}}^{\mathsf{T}}B\mathbf{x}=\Vert A\mathbf{x}{\Vert }^2\ge 0$, hence a positive semidefinite matrix. Squaring the nonnegative objective does not change its argmin. Let ${\lambda }_{\min }$ be the smallest eigenvalue of $B$ and $E_{\min }$ its eigenspace.

First minimize on the unit sphere. The Lagrange multiplier function $L(\mathbf{x},\lambda )={\mathbf{x}}^{\mathsf{T}}B\mathbf{x}-\lambda ({\mathbf{x}}^{\mathsf{T}}\mathbf{x}-1)$ has stationarity condition $B\mathbf{x}=\lambda \mathbf{x}$. Multiplication by ${\mathbf{x}}^{\mathsf{T}}$ shows that the squared objective at such a point is $\lambda$. The spectral theorem for real symmetric matrices also gives, for every unit vector, ${\mathbf{x}}^{\mathsf{T}}B\mathbf{x}\ge {\lambda }_{\min }$, with equality exactly in $E_{\min }$. This proves global minimality, rather than merely finding stationary candidates.

If ${\lambda }_{\min }>0$, every point with $\Vert \mathbf{x}\Vert >1$ has a strictly smaller objective after rescaling to unit length. ThereforeIf ${\lambda }_{\min }=0$, the kernel of a linear map satisfies $\ker B=\ker A$, since $B\mathbf{x}=0$ implies $\Vert A\mathbf{x}{\Vert }^2=0$, and the converse is immediate. The minimum is then zero, attained precisely atIn this case minimizers need not have unit length. This distinction is essential for a rank-deficient $A$, including any real $m\times n$ matrix with $m<n$. The result is the minimum image norm outside a Euclidean unit ball, governed by the least singular value.

The origin is feasible and has objective zero, while a Euclidean norm is nonnegative. Thus the minimum is $0$, and the complete argmin isIf $A$ is injective, this set contains only the origin. If it has a nontrivial kernel, every feasible kernel vector is also a minimizer. No Lagrange multipliers are needed.

Use bisection on $f^{\prime }$ when the derivative is cheap and a bracket $f^{\prime }(a)<0<f^{\prime }(b)$ is easy to obtain. For a differentiable convex function, $f^{\prime }$ is nondecreasing, so such a bracket locates a global minimum, allowing a flat minimizing interval. Without convexity, first isolate a region containing the desired local minimum; arbitrary stationary points need not be minima.

Use golden-section search when reliable function values are available but derivatives are unavailable or expensive. It needs a bracket on which the objective is a unimodal function, commonly found by three ordered points whose middle value is below the two outer values. Those inequalities alone do not prove that the objective is a unimodal function. A convex function supplies the needed shape; for a nonconvex objective, isolate an interval on which it is a unimodal function.

Both methods have linear convergence of bracket width. Bisection contracts the width by $1/2$ per new derivative evaluation. Golden-section search contracts it by $(\sqrt{5}-1)/2\approx 0.618$ per new function evaluation after initialization, reusing one earlier value. Choose by evaluation cost and bracket availability as well as this contraction factor: comparing iteration counts alone can misidentify the faster method.

Convexity of the components of a vector field is not the decisive criterion for a root-finding problem. Neither method becomes globally reliable merely because each component is convex.

Prefer the Newton root-finding iteration when the Jacobian matrix is available accurately and at reasonable cost. Solve $J({\mathbf{x}}_k){\mathbf{s}}_k=-\mathbf{f}({\mathbf{x}}_k)$ rather than explicitly forming an inverse matrix. Near a root with a nonsingular Jacobian matrix and a locally Lipschitz Jacobian matrix, the usual exact iteration has quadratic convergence.

Prefer Broyden's method when evaluating or differentiating the vector field makes a fresh Jacobian matrix expensive. It learns an approximate Jacobian matrix through secant updates using function differences. Under appropriate local regularity and initialization assumptions it has superlinear convergence, generally slower asymptotically than the quadratic convergence of exact Newton steps, but often with cheaper iterations.^[ref]

Dimension matters through storage and solves. A full dense Newton factorization costs order $d^3$ arithmetic operations; a dense Broyden approximation uses order $d^2$ storage, and maintained inverse or factorization updates can cost order $d^2$. A naive fresh dense solve can still cost order $d^3$. Sparsity can favour Newton, while very large $d$ can make either dense formulation unsuitable. Neither local rate guarantees convergence from an arbitrary starting point.

Gradient descent uses only the current gradient and a suitable step size; its additional storage is order $d$. It is attractive for very large $d$ or when low per-iteration cost matters most. For a smooth strongly convex function, standard step choices give linear convergence, with a rate sensitive to the condition number. Mere convexity gives a global-minimum interpretation but does not alone imply a linear rate; for nonconvex objectives the usual guarantee concerns stationary points.

BFGS uses successive gradients to update an approximation to inverse curvature, incorporating information that can correct poor scaling. Full BFGS uses order $d^2$ storage and update work. With suitable line searches and local smoothness and positive-curvature assumptions near a nondegenerate minimum, it has superlinear convergence. This often favours it in moderate dimensions when gradients are not extremely cheap relative to the extra work.

Neither gradient descent nor BFGS requires an explicitly evaluated Hessian matrix. Thus an expensive Hessian matrix is compatible with both, rather than a reason to reject BFGS. If an accurate Hessian matrix and its factorization are exceptionally cheap, Newton's method in optimization becomes an additional reasonable option. Convexity helps identify a stationary point as a global minimum; without it, both methods need suitable descent and curvature safeguards. The BFGS update learns curvature from the Quasi-Newton secant equation.^[ref]

The Newton root-finding iteration isIt requires $f$ and its derivative to be defined at the current point, and requires $f^{\prime }(x)\ne 0$. A step can leave the domain, making a subsequent iteration undefined. In floating-point arithmetic, division by zero, overflow or non-finite function evaluations can also prevent a usable step. At a root where $f^{\prime }$ is zero the displayed quotient itself remains undefined unless the implementation stops before evaluating it.

Taylor's theorem at zero gives $f(x)=-1000+x+\frac{1}{2}{x}^2{f}^{\prime \prime }(\xi )$ for a point $\xi$ between zero and $x$. At $x=1000$, strict negativity of the second derivative gives $f(1000)<0$. At $x=2000$, its lower bound givesBy the intermediate value theorem there is a root strictly between these values. The given uniqueness identifies it as $1000<x^{\ast }<2000$.

The Newton root-finding iteration gives $x_1=0-(-1000)/1=1000$.

Set $h=x_{n+1}-x_n=-f(x_n)/f^{\prime }(x_n)$. By Taylor's theorem,The first two terms cancel by the definition of the Newton root-finding iteration. Thuswith $\xi$ between the consecutive iterates. In particular, a nonzero step has negative new residual under the stated strict concavity.