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

Source paper: released examination archive, member 2021/L/a10100w1.pdf. The cover identifies the September 2022 resit; the source filename is undated and the ZIP directory says 2021.

Let $A$ and $B$ be the finite sets of objects satisfying the two properties. The rule of sum says that mutually exclusive alternatives have additive counts: if $A\cap B=\varnothing$, then $|A\cup B|=|A|+|B|$. Without disjointness, the corresponding inclusion-exclusion principle isThe rule of subtraction counts objects satisfying the first property but not the second:In particular, if the objects with the second property form a subset of those with the first, the count is $|A|-|B|$. These conditions prevent either double counting an overlap or subtracting objects that were not counted initially.

The rule of product says that if a construction has $r$ stages, with exactly $a_j$ choices at stage $j$ after every permitted earlier history, then it has ${\prod }_{j=1}^r{a}_j$ possible outcomes. The later choices need not be identical sets after different histories; their numbers must have the stated values.

For a permutation of $n$ distinct objects, choose the first object in $n$ ways, the second in $n-1$ ways, and continue until only one remains. Thus the number isEvery ordered arrangement is produced exactly once by its successive choices, so this counts permutations without omissions or repetitions. For $n=0$, the unique empty arrangement agrees with $0!=1$.

An allocation is a tuple $(x_1,\dots ,x_k)$ of nonnegative integers with ${\sum }_j{x}_j=n$, where $x_j$ is the number in labelled box $j$. Empty boxes are allowed. Encode the allocation by $n$ stars and $k-1$ bars: put $x_1$ stars before the first bar, $x_2$ between the first two bars, and so on. Adjacent bars represent an empty intermediate box; a bar at an end represents an empty end box.

Reading the group sizes recovers exactly one allocation from every such string, so this is a bijection. There are $n+k-1$ positions and we choose the $k-1$ bar positions. Hence stars and bars givesNo extra factor for ordering the objects is present, because the objects are indistinguishable. For $k=1$ the string has no bars and gives the single allocation of all objects to that box; for $n=0$ all boxes are empty, also a single allocation.

Pad every integer from $0$ through $999999$ with leading zeros to obtain a unique six-digit decimal string. If its digits sum to $5$, each digit is automatically at most $5$, so the usual digit upper bound $9$ adds no restriction. We therefore count the nonnegative integer solutions ofBy stars and bars, there are $\left(\genfrac{}{}{0ex}{}{5+6-1}{6-1}\right)=\left(\genfrac{}{}{0ex}{}{10}{5}\right)$. The all-zero string is not counted because its digit sum is zero, so every counted integer is positive. Thus the answer is $252$.

For real-valued functions, use magnitude comparisons. The constants below are independent of $n$.

The statement $f(n)=O(g(n))$ in Big O notation means that some $C>0$ and integer $N$ satisfy $|f(n)|\le C|g(n)|$ for all $n\ge N$. The statement $f(n)=\Omega (g(n))$ in big omega notation means that some $c>0$ and $N$ satisfy $|f(n)|\ge c|g(n)|$ for all $n\ge N$.

Finally, $f(n)=\Theta (g(n))$ in big theta notation means that some $c,C>0$ and $N$ satisfyEquivalently it is both an eventual upper bound and an eventual lower bound. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.

Suppose first that $f=O(g)$. Choose $C>0$ and $N$ so that $|f(n)|\le C|g(n)|$ for $n\ge N$. There are only finitely many natural numbers below $N$. Because $g(n)\ne 0$ at each of them, all ratios $|f(n)|/|g(n)|$ in this finite prefix are finite. LetThen $|f(n)|\le c|g(n)|$ both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.

Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because $g$ never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.

True. For every integer $n\ge 1$, $n^2\le n^3$ and $1\le n^3$. ThereforeThe constants $C=1097$ and $N=1$ satisfy the definition of Big O notation. Whether the chosen convention for natural numbers includes zero is immaterial to this eventual assertion.

False. Put $r_n=3^n/n^3$ for $n\ge 1$. For $n\ge 4$,Thus $r_n\ge r_4(192/125{)}^{n-4}\to \infty$. No fixed constant can bound $3^n/n^3$ eventually, so $3^n\ne O(n^3)$. This is an explicit comparison of exponential growth with polynomial growth.

True. Rationalization gives, for $n\ge 1$,This lies between zero and $1/4$, so it is $O(1)$ in Big O notation. In fact it converges to $1/4$, rather than to zero. The rationalized form also avoids the catastrophic cancellation of subtracting two nearby large quantities.

True for every fixed $k\ge 0$. Extract $e^n$ from inside the logarithm:Choose an integer $m>k$. The nonnegative terms of the exponential series give $e^n\ge n^m/m!$ for $n>0$, whenceSince $0\le \log (1+u)\le u$ for $u\ge 0$, the displayed expression tends to zero and is therefore $O(1)$. The constant and cutoff may depend on the fixed $k$; no uniform assertion over unbounded $k$ is being made.

False. On the unbounded subsequence of odd positive integers, $f(n)/g(n)=n$. For any proposed constants $C>0,N$, choose an odd $n>\max (C,N)$. Then $|f(n)|=n>C|g(n)|=C$, contradicting the eventual upper bound required by Big O notation. The small ratio on even integers cannot compensate for this failure on infinitely many odd integers.

The integer congruence $x\equiv y(\mathrm{mod}n)$ means $n\mid (x-y)$: the difference is an integer multiple of the positive modulus $n$. Write $x_1-x_2=na$ and $y_1-y_2=nb$ for integers $a,b$. Thenso addition preserves integer congruence. For multiplication,The final coefficient is an integer, so multiplication also preserves integer congruence. These properties make addition and multiplication well defined on residue classes.

The Euclidean algorithm givesThe last nonzero remainder is $g=92$. Back-substitution produces its Bézout coefficients:Thus $(m,n)=(-8,11)$ is a requested pair. The final equality independently checks the calculation.

The pigeonhole principle states that if more than $r$ objects are placed in $r$ boxes, with $r\ge 1$, at least one box contains two or more objects. Equivalently, a function from a finite set of more than $r$ elements to a set of $r$ elements cannot be injective: if every box held at most one object, there would be at most $r$ objects altogether.

For five points, partition the unit square into four squares of side $1/2$. Assign boundary points to just one neighbouring piece. By the pigeonhole principle, two of the points lie in one piece, whose diameter is its diagonal, $\sqrt{(1/2{)}^2+(1/2{)}^2}=\sqrt{2}/2$.

For eight points, use seven smaller-diameter pieces rather than eight rectangles. Start with the convex pentagonTake its four reflected copies at the corners of the square. The remaining pieces are the left triangle with vertices $(0,1/4),(1/4,1/2),(0,3/4)$, its right-hand reflection, and the central diamond with vertices $(1/4,1/2),(1/2,1/4),(3/4,1/2),(1/2,3/4)$. These seven polygons cover the square with disjoint interiors. To verify coverage directly, for $0\le y\le 1/4$ the two bottom pentagons split the horizontal section at $x=1/2$. For $1/4\le y\le 1/2$, the five successive sections have endpoints $0,y-1/4,3/4-y,y+1/4,5/4-y,1$ and belong respectively to the left triangle, bottom-left pentagon, diamond, bottom-right pentagon and right triangle. Reflection gives the top half.

The diameter of a finite convex hull is the greatest distance between its vertices: if two points are convex combinations of vertices, their difference is a convex combination of vertex differences, and the triangle inequality bounds its norm by the largest such distance. Checking the five vertices of $P$ gives diameter $\sqrt{(1/2{)}^2+(1/4{)}^2}=\sqrt{5}/4$; reflections preserve that value. Each remaining triangle and the diamond has diameter $1/2$, which is smaller. After assigning shared boundaries to one piece, eight points in these seven pieces force a pair in a common piece. Hence some pair is at distance at most $\sqrt{5}/4$.

Both arguments are instances of a pigeonhole distance bound from a partition.

Prove the stronger statement with a nonempty subset. Order the $n\ge 1$ integers as $a_1,\dots ,a_n$, and form the prefix sumsThere are $n+1$ such sums but only $n$ residue classes modulo $n$. The pigeonhole principle gives indices $0\le i<j\le n$ with $s_i\equiv s_j(\mathrm{mod}n)$. Their difference satisfiesThe selected elements form a nonempty subset of $S$, proving the claim. Neither positivity nor distinct values in a general ordered sequence are needed for the consecutive sum divisible by the sequence length argument; distinctness merely makes the present input a set.

Let $e_n=x_n-x_{\ast }$ for the limit $x_{\ast }$. Quadratic convergence means that eventually $|e_{n+1}|\le C|e_n{|}^2$ for a fixed constant $C$; exact asymptotic order two has $|e_{n+1}|/|e_n{|}^2\to c$ with $0<c<\infty$.

For this iteration and $x_{\ast }=3$, direct algebra givesUsing the stipulated convergence $x_n\to 3$, the ratio of successive squared errors isThus the convergence is quadratic. The iteration is well defined here: $x_1=7/2$, and thereafter $x_n>3$ implies $3<x_{n+1}<x_n$. The initial point is not already the limit, so the error ratio is meaningful.

Assume $f$ and $g$ are continuously differentiable near the point. At a regular feasible point, meaning $g(x)=0$ and $\nabla g(x)\ne 0$, a differentiable constrained local extremum satisfies the Lagrange multiplier equationsThey arise by differentiating the optimization Lagrangian $L(x,\lambda )=f(x)-\lambda g(x)$ with respect to all coordinates and the multiplier. Geometrically, the objective has zero derivative along the tangent space of the constraint surface, so its gradient must lie in the normal direction.

Solve these equations for candidates, examine feasible points where the regularity condition fails separately, and compare objective values or use a second-order test restricted to feasible directions. The equations locate stationary points; they do not by themselves establish which are minima or whether a global minimum is attained.

Use $F=x^6+\frac{3}{2}{y}^4$ and $G=x^4-2y^2-3$. Every feasible point has $x\ne 0$, so $\nabla G=(4x^3,-4y)$ cannot vanish. The Lagrange multiplier equations areThe first gives $\lambda =\frac{3}{2}{x}^2>0$. If $y\ne 0$, the second would give $\lambda =-\frac{3}{2}{y}^2<0$, a contradiction. Therefore $y=0$, and the constraint gives $x^4=3$. The only constrained stationary points are $(\pm 3^{1/4},0)$.

For a global certificate, feasibility implies $x^4\ge 3$, and henceEquality requires $y=0$ and $x^4=3$. ThusThe case split is essential: dividing by $y$ would discard precisely the minimizers.

Here the constraint surface $x^4+2y^2=3$ is compact and regular, so a global minimum exists and satisfies the Lagrange multiplier equationsKeep the zero-coordinate cases. If $y=0$, the two points are $(\pm 3^{1/4},0)$, with value $3\sqrt{3}$. If $x=0$, the two points are $(0,\pm \sqrt{3/2})$, with value $27/8$. If both coordinates are nonzero, the equations give $x^2=y^2=t>0$. The constraint becomes $t^2+2t=3$, whose only positive solution is $t=1$. These are the four points $(\pm 1,\pm 1)$, all with value $5/2$.

These cases exhaust the stated eight constrained stationary points. Comparing their values givesFor additional classification, substituting $u=x^2\in [0,\sqrt{3}]$ gives $F(u)=u^3+\frac{3}{8}(3-u^2{)}^2$, withIt decreases from $u=0$ to $u=1$ and increases from $u=1$ to $u=\sqrt{3}$. Thus the two $y$-axis points are constrained local maxima, the two $x$-axis points are global maxima, and the four mixed-coordinate points are global minima.

Both terms $x^6$ and $\frac{3}{2}{y}^4$ are nonnegative, and they vanish simultaneously only at $(0,0)$. That point satisfies $x^4+2y^2\le 3$. Consequentlyand the global minimum is unique. No Lagrange multiplier calculation is needed: nonnegativity gives a lower bound attained at a feasible point.

Use compatible dimensions $A\in {\mathbb{R}}^{d\times d}$ and $b,x\in {\mathbb{R}}^d$; the printed “b-by-b” size is read consistently with the displayed products and domain. Take derivatives as column gradients. Symmetry of $A$ givesFor example, the directional differential of $x^{T}Ax$ is $d{x}^{T}Ax+x^{T}Adx=2(Ax{)}^{T}dx$. The linear term contributes $b$ to the gradient and zero to the Hessian matrix.

The eigenvector identity $Ab=\frac{1}{2}b$ gives $\nabla f(-b)=-2Ab+b=0$. Since $H_f=2A$ is a positive-definite matrix, this is a strict local minimum. A global certificate follows by completing the quadratic form:Positive definiteness makes the first term nonnegative, with equality only at $x=-b$. Thus $-b$ is the unique global minimum, with value $-1/2$.

The full, undamped Newton's method in optimization step isThe eigenvector identity gives $A^{-1}b=2b$. Consequently $x_1=-b$ for every starting point. This is a one-step Newton solution of a quadratic stationary equation: its gradient is an affine function, so a single exact Newton solve resolves it completely.

Write $(x^{T}b{)}^2=x^{T}b{b}^{T}x$ and put $C=A-b{b}^T$, which is symmetric. Differentiating this quadratic form givesUnlike $A$, $C$ need not be a positive-definite matrix. Its behaviour must be checked before classifying the stationary point.

The gradient vanishes at $0$. Decompose any vector as $x=tb+w$, with $w\perp b$. Symmetry of $A$ and $Ab=\frac{1}{2}b$ imply $b^{T}Aw=(Ab{)}^{T}w=0$. Since $\Vert b\Vert =1$,If $d\ge 2$, choose a nonzero $w\perp b$. Arbitrarily close to zero, the direction $b$ gives negative values and the direction $w$ gives positive values. Thus $0$ is a saddle point for $d\ge 2$. Equivalently, the Hessian matrix has one negative eigenvalue and all its other eigenvalues positive.

The dimension matters: if $d=1$, the orthogonal complement is zero-dimensional and $g(tb)=-t^2/2$. In that case $0$ is the unique global maximum. This edge case is not excluded by the stated hypotheses. The decomposition is a rank-one downdate along an eigenvector.

The matrix $C=A-b{b}^T$ is an invertible matrix. Indeed, on the line spanned by $b$ it has eigenvalue $-1/2$, and on $b^{\perp }$ it agrees with the positive-definite restriction of $A$. Therefore the full Newton step is well defined and givesThis is the unique stationary point because $C$ is an invertible matrix. The algebra applies to every starting point, but it does not make the answer a minimum: for $d\ge 2$ it is the saddle point just classified, and for $d=1$ it is a maximum. A safeguarded minimization algorithm that replaces an indefinite matrix used as its Hessian matrix or damps the step need not take this exact step; the assertion concerns the ordinary full Newton step formula.

Put $q(x)=x^{T}Ax$ and $t(x)=x^{T}b$. The product rule givesDifferentiate each term. The derivative of $2tAx$ is $2(Ax)b^T+2tA$, while that of $qb$ is $2b(Ax{)}^T$. HenceThe last two terms are transposes of each other, so this Hessian matrix is symmetric, as expected.

At $x=0$, the gradient from the preceding part vanishes and the Hessian matrix is zero. The second-order test is therefore inconclusive. Instead inspect the eigenline:For arbitrarily small positive and negative $t$, these values have opposite signs. Thus $0$ is neither a local maximum nor a local minimum. In dimension at least two it is a degenerate saddle point; in one dimension it is a stationary inflection point. Looking only at the zero Hessian matrix would not determine this classification.

Use mathematical induction on the iteration. Initially $x_0=b=1\cdot b$. If $x_n={\lambda }_{n}b$, then $A{x}_n={\lambda }_{n}b/2$, $x_n^{T}b={\lambda }_n$, and $x_n^{T}A{x}_n={\lambda }_n^2/2$. ThereforeA gradient descent step with any scalar step length ${\alpha }_n$ consequently has the formThus every iterate remains on the same eigenline, withThis proves that gradient descent preserves an eigenline for a cubic product. The statement is invariance, not convergence to a minimum: along the negative direction of this line the cubic polynomial objective is unbounded below.

The displayed rational expression has domain $\mathbb{R}\setminus \{0\}$; its value at zero is undefined despite the printed $\mathbb{R}\to \mathbb{R}$ notation. On that domain, the power rule givesThese derivatives are smooth on every interval avoiding zero, including all intervals used below.

Substitution givesIn particular, $1$ is a stationary point. For $x$ sufficiently close to $1$, Taylor's theorem with fifth-order remainder giveswhere $\xi$ lies between $1$ and $x$. The fifth derivative is bounded near $1$, so the remainder is $O((x-1{)}^5)$ and is smaller in magnitude than half the positive quartic term for sufficiently small nonzero $x-1$. Therefore $x=1$ is a strict local minimum, despite the vanishing second derivative.

An exact algebraic check gives the stronger global conclusion:Equality holds only at $x=1$, so it is the unique global minimum on the actual domain.

Let $h=(b-a)/n$ and let $M_4={\max }_{x\in [a,b]}|f^{(4)}(x)|$. A composite Simpson's rule panel covers two strips, so it has width $2h$ and absolute error at mostThere are $n/2$ panels. By the triangle inequality, the absolute error of their sum is at most the sum of their absolute errors. HenceThis assumes even $n$ and, for the usual Simpson remainder theorem, $f\in C^4[a,b]$. In particular its fourth derivative is bounded on the interval. It is the error bound for composite Simpson's rule, expressed in strip count rather than panel count.^[ref]

Write $f^{(4)}(x)=24(5-4x)/x^6$. Its derivative is $f^{(5)}(x)=240(2x-3)/x^7$, so on $[1,2]$ it decreases to $x=3/2$ and then increases. Its endpoint and turning-point values areThus $M_4=24$, and the preceding bound becomesFor the rounding estimate, standard binary64 has spacing $ϵ=2^{-52}$ above one. Balancing this nominal absolute accuracy with the bound givesThus a few thousand even strips, roughly $5000$, reach the double-precision scale according to this bound. A scale-aware estimate leads to the same order. Indeed,lies in magnitude between $4$ and $8$, where the binary64 spacing is $2^{-50}$. Balancing the error bound against half that spacing gives about $4.16\times 10^3$ strips.

These are saturation estimates from balancing quadrature truncation and round-off error, not sharp guarantees of the actual rounding plateau. The error bound can be conservative, and evaluation and summation errors can limit accuracy earlier. Merely storing the final result does not specify every source of rounding error.

Not near the minimum at $1$. The derivative being set to zero factors asso $1$ has multiplicity of a root equal to three. The ordinary Newton iteration at a multiple root is generally only linearly convergent, with error ratio $(3-1)/3=2/3$ here.

In fact, cancellation in $x-f^{\prime }(x)/f^{\prime \prime }(x)$ gives the exact error identity, away from the original undefined quotient at the root,For iterates approaching $1$, the factor tends to $2/3$, proving linear convergence. The other zero of $f^{\prime }$ at $-1$ is simple and could instead give quadratic local convergence; the failure at $1$ is due to its multiplicity, not to every stationary point of this rational function.

For each integer $x$, the events $\{X=x,Y=y\}$, indexed by the integers $y$, are disjoint and their union is $\{X=x\}$. Therefore countable additivity gives the marginal probability mass functionThe nonnegative terms make this sum well-defined, even when the support is infinite.

The random variables are independent random variables if the events determined by one are independent of the events determined by the other. For integer-valued variables, this is equivalent to the factorizationIndeed, independence gives the factorization by taking singleton events. Conversely, summing it over $x\in A$ and $y\in B$, for any subsets $A,B\subseteq \mathbb{Z}$, gives $\mathbb{P}(X\in A,Y\in B)=\mathbb{P}(X\in A)\mathbb{P}(Y\in B)$. Thus the singleton condition implies independence of all events in question.

Interpret existence of the expectations as finite expected values, equivalently $\mathbb{E}|X|<\infty$ and $\mathbb{E}|Y|<\infty$. First justify the summations rather than assuming that a signed double series can be rearranged. Independence and Tonelli theorem giveConsequently $XY$ is an integrable random variable, and Fubini theorem permits summing the signed terms in either order:If extended infinite expectations are allowed instead, the phrase “exist” needs additional care: expressions such as $0\cdot \infty$ do not define an expectation. The finite-expectation convention avoids that ambiguity.

Summing the two nonzero entries with $X=1$ givesThe remaining probability is $\mathbb{P}(X=0)=1-p$, so $X$ has the Bernoulli distribution with parameter $p$.

For the other marginal, the two entries at $Y=0$ add to $e^{-p}$, the entry at $Y=1$ is $p{e}^{-p}$, and for $k⩾2$ the only nonzero entry is already $e^{-p}{p}^k/k!$. Thusand $Y$ has the Poisson distribution with parameter $p$. This also checks normalization of the joint probability mass function by summing the marginal.

Equality can occur only at the two pairs $(0,0)$ and $(1,1)$. Their combined probability isTaking the complementary probability givesSince $1+2p>0$, the supplied exponential bound impliesThis is a bound on the mismatch probability for this particular coupling of the two marginal distributions; the variables are not presumed independent.