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

This is the 22 June 2017 preliminary examination. All 54 printed subparts are answered, including the continuation of Question 2(d) across a page break. Source paper: released examination archive, member a10100w1-1.pdf.

The relative complement consists of the elements of the first set absent from the second, while the symmetric difference consists of elements in exactly one set:The two parts of the symmetric difference are disjoint sets.

For the first set inclusion, take $x\in A\setminus (A\setminus B)$. Then $x\in A$ but $x\notin A\setminus B$. Since membership in $A$ is already known, failure to lie in that relative complement forces $x\in B$. Hence $x\in A\cap B$.

Conversely, if $x\in A\cap B$, then $x\in A$ and its membership in $B$ excludes it from $A\setminus B$. Therefore $x\in A\setminus (A\setminus B)$. The two inclusions prove the stated equality with the set intersection.

If $x\in A\oplus B$, the definition of symmetric difference puts it in exactly one of $A,B$. It is therefore in their set union and outside their set intersection, giving $x\in (A\cup B)\setminus (A\cap B)$.

Conversely, an element of $(A\cup B)\setminus (A\cap B)$ lies in at least one of the two sets but not both. It consequently belongs to $A\setminus B$ or to $B\setminus A$, and hence to $A\oplus B$. Both set inclusions hold.

The outermost braces form a singleton set, regardless of how its one element is nested. Its cardinality is therefore $1$. A set containing the empty set is different from the empty set itself.

A Cartesian product with the empty set is empty: there is no possible second coordinate. Thus the requested cardinality is $0$, independently of the first factor's power set.

The singleton set $\{\varnothing \}$ has cardinality one, so its power set has cardinality two. Taking the Cartesian product with the singleton $\{\varnothing \}$ leaves that cardinality equal to two. The outer power set therefore has $2^2=4$ elements.

One example is the identity function, $f(n)=n$. A second is the permutationBoth are bijections of $\mathbb{N}$, whichever convention includes or excludes zero. For the second, applying $f$ three times returns every input to itself. Thus $f^3=\mathrm{id}$, and composing with the inverse function gives $f^2=f^{-1}$. This permutation cube identity criterion also shows why three-cycles work whereas a nontrivial two-cycle would not.

Use the convention that $R\circ S$ applies $S$ first. Reflexivity inserts an identity step: if $aRb$, use $aSa$ to obtain $(a,b)\in R\circ S$; if $aSb$, use $bRb$ for the same conclusion. Thus $R\cup S\subseteq R\circ S$. By monotonicity of relation composition,For strictness, take $A=\{0,1,2,3\}$ and let $R=S$ consist of the identity pairs together with $(0,1),(1,2),(2,3)$. Both are reflexive relations. The left side permits at most two forward chain steps, so does not contain $(0,3)$. The right side permits four steps, including $0\to 1\to 2\to 3\to 3$, so does contain it. Equality therefore need not hold.

Use modular arithmetic modulo eight: $801\equiv 1$, $32\cdot 19\equiv 0$, and $29\cdot 13\equiv 5\cdot 5\equiv 1$. The squared difference is consequently congruent to one, giving the remainder

Modulo seven, $19\equiv -2$ and $(-2{)}^3=-8\equiv -1$. Therefore $19^9\equiv (-1{)}^3\equiv -1\equiv 6(\mathrm{mod}7)$. The remainder is $6$, using modular exponentiation.

For integers $a,b$ not both zero, replace them first by their absolute values, then repeat integer division:

while b != 0:
    (a,b) := (b, a mod b)
return a

This is the Euclidean algorithm. Its loop invariant is that $\gcd (a,b)$ equals the original greatest common divisor. When $b>0$, the new remainder lies in $[0,b)$, so $b$ is a strictly decreasing nonnegative loop variant. At termination, $\gcd (a,0)=a$, proving correctness, including the case where one original input is zero.

The Euclidean algorithm givesThus the greatest common divisor is $34$. Back-substitution, as in the extended Euclidean algorithm, givesHence $\gcd (306,1394)=34$, with $x=2$ and $y=-9$.

For one colour, the box occupancies form a weak composition of $k$ into $n$ nonnegative parts. For $n\ge 1$, stars and bars gives $\left(\genfrac{}{}{0ex}{}{k+n-1}{n-1}\right)$ choices. The three colours' occupancies can be selected independently, so the number isBoxes are labelled, while equal-colour balls contribute only occupancy counts; no extra factorial for permuting such balls is appropriate.

There are $6^3=216$ unrestricted placements, since one colour has $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ occupancy vectors. For any specified empty box, the two remaining boxes admit $3^3=27$ placements. For any specified pair of empty boxes, the one remaining box admits one placement. All three boxes cannot be empty.

The inclusion-exclusion principle therefore givesThe empty-box events are not disjoint events, so subtracting their counts without restoring their pairwise overlaps would be incorrect.

The base cases are $13=3(2)+7(1)$, $14=3(0)+7(2)$ and $15=3(5)+7(0)$. Suppose a counterexample exists and choose the least integer $n\ge 13$ failing the claim. It is not one of these base cases, so $n\ge 16$ and $n-3\ge 13$.

Minimality supplies nonnegative integers $x,y$ with $n-3=3x+7y$. Then $n=3(x+1)+7y$, a contradiction. This proof by minimal counterexample establishes the claim. Three consecutive base cases are needed because the reduction subtracts three.

As $x\to +\infty$, big O notation meansThe same constant must work on the entire sufficiently large tail. Absolute values accommodate signed functions. A two-sided convention at infinity would replace $x\ge x_0$ by $|x|\ge x_0$; the positive-integer arguments in the later parts use the positive-tail convention.

Choose constants $C_1,C_2>0$ and a common threshold beyond which $f_1\le C_1{g}_1$ and $f_2\le C_2{g}_2$. Positivity permits multiplication:The fixed constant $C_1{C}_2$ proves $f_1{f}_2=O(g_1{g}_2)$ by the definition of big O notation.

Beyond the same common threshold, the triangle inequality givesThus $f_1-f_2=O(g_1+g_2)$. The absolute value matters because the difference need not itself be positive, even though the four original functions are.

TakeThe premises hold with constants two and one. ButNo fixed bounding constant can satisfy the proposed conclusion. This proves the failure of unrestricted Big O composition: a constant factor in an inner argument can become an unbounded factor after applying an exponential.

A stronger exact formula makes the induction explicit:For $n=1$, the recurrence gives $S_1=S_0+m=1+m$. For $n\ge 2$, set $j=\lfloor n/2\rfloor$, so $1\le j<n$. In the relevant binary interval, $\lfloor {\log }_{2}j\rfloor =\lfloor {\log }_{2}n\rfloor -1$. The strong induction hypothesis givesFor $n\ge 2$, $S_n\le 1+m+m{\log }_{2}n\le (1+2m){\log }_{2}n$. Hence $S_n=O({\log }_{2}n)$. This is an integer-halving recurrence with constant toll; the separately defined $n=0$ case does not require evaluating $\log 0$.

A preorder is reflexive and transitive: $xRx$ for every element, and $xRy,yRz$ imply $xRz$. A partial order additionally requires antisymmetry: $xRy$ and $yRx$ imply $x=y$. It need not compare every pair of distinct elements.

No. On $\{0,1,2\}$ take $R=\{(0,1),(1,2),(2,0)\}$. This is an antisymmetric relation because it contains no opposite pair of distinct elements. Its reflexive transitive closure contains every ordered pair: following the directed three-cycle reaches any vertex from any other. In particular it contains both $(0,1)$ and $(1,0)$, violating antisymmetry.

This illustrates the reachability preorder: collapsing mutually reachable vertices into strongly connected components yields a partial order, but retaining all original vertices need not.

The gradient equations areThus $x=3$ gives $y=2$, while $x=-3$ gives $y=8$. The Hessian matrix isAt both critical points the determinant is $-36<0$, so the Hessian is indefinite and the second-derivative test classifies both as saddle points. Direct substitution givesThe factorization $f+30=(x^2-9)(x+y-5)$ also shows the crossing level-set branches through each saddle.

Write $\dot{x}=dx/du$, $\ddot{x}=d^{2}x/d{u}^2$, $A_v=dA/dv$, $A_{vv}=d^{2}A/d{v}^2$, and $y_w=dy/dw$, $y_{ww}=d^{2}y/d{w}^2$. Put $S=A+A^T$. The product rule and chain rule giveHere $w^{\prime },w^{\prime \prime }$ are derivatives with respect to $v$. In the first derivative, $x^{T}A\dot{x}={\dot{x}}^T{A}^{T}x$ because the expression is scalar. Likewise ${\dot{x}}^{T}S\dot{x}=2{\dot{x}}^{T}A\dot{x}$ if desired. This differentiation of a parameter-dependent quadratic form does not assume that $A$ is symmetric. The positive linear term $y^{T}b$ contributes the positive chain-rule terms in the $v$ derivatives; it is independent of $u$.

Complete the square:The minimum locus of a squared function occurs where its residual vanishes. Hence the minimum is $-6$ on $y=-x^2/2$, provided these points lie in the ellipse. Setting $t=x^2$ in the constraint gives $t+t^2/2\le 9$, or $0\le t\le \sqrt{19}-1$. ThusFor the maximum, let $q=x^2+2y$. The ellipse givesAlso $q\ge 2y\ge -3\sqrt{2}$, whose absolute value is less than $19/2$. Therefore $q^2\le (19/2{)}^2$. Equality is attained at $y=1/2$, $x^2=17/2$, givingThese attained bounds are global, not merely stationary-point tests. The minimizing locus is a parabola segment.

Use partial fraction decomposition:Integrating givesThis real antiderivative is valid on each interval avoiding $x=\pm 2$, with its own integration constant. In particular, $I(1)-I(0)=\frac{1}{4}\log 3$.

For positive bounds, integration by parts with $u=\log x$ and $dv=x^{2}dx$ givesFor negative bounds, specify the complex logarithm on the negative real axis. With argument $\pi$, namely the upper-bank boundary value of the principal logarithm, $\log x=\log (-x)+i\pi$. Substitute $t=-x$ in the real part:More generally, a continuous branch taking argument $(2k+1)\pi$ replaces $i\pi$ by $(2k+1)i\pi$. The imaginary part depends on that choice. The analytic principal branch excludes the negative axis itself, so the boundary-value convention is part of this interpretation.

A horizontal strip at height $y$ has width $4-2\sin (\pi y/2)$. The sine term is odd, so the area isReflection symmetry in the $y$-axis gives $\bar{x}=0$. For uniform density, the constant density cancels from the center of mass ratio. Its first moment in the vertical coordinate isConsequentlyThe wider part below the horizontal axis accounts for the negative vertical coordinate.

For $h=1/N$, the composite trapezoidal rule isWith $f(x)=1/(4-x^2)$ this becomesWrite the requested right Riemann sum as $S_N$. The trapezoidal endpoint correction for a right Riemann sum givesThe integrand is continuous on $[0,1]$, so the trapezoidal values converge to its definite integral; the endpoint correction tends to zero. Therefore

The characteristic polynomial of this constant-coefficient differential equation is $r^2-r-2=(r-2)(r+1)$. Its distinct roots give

For the forcing $8e^{-2x}$, the method of undetermined coefficients gives the particular term $2e^{-2x}$. The term $e^{-x}$ is resonant with a homogeneous solution, so use $ax{e}^{-x}$ for its forcing; substitution gives $a=1$.

Thus $y=C_1{e}^{2x}+C_2{e}^{-x}+2e^{-2x}+x{e}^{-x}$. The two initial conditions reduce to $C_1+C_2=3$ and $2C_1-C_2=0$, so $C_1=1$, $C_2=2$. The solution of the initial value problem isThe extra factor $x$ in the resonant particular solution is essential.

The Forward Euler method uses the current slope:Here $x_n=x_0+nh$ and the initial approximation normally equals the given initial value. Each step takes a tangent-line increment of width $h$.

Define the one-step local truncation error as the defect obtained by inserting the exact solution into an update:For a smooth solution, Taylor's theorem and $y^{\prime }=f(x,y)$ giveThus $m=2$ for the one-step defect convention. The leading derivative can also be written $y^{\prime \prime }=f_x+f_{y}f$ by the chain rule.

Some conventions instead call ${\tau }_{n+1}={\delta }_{n+1}/h$ the truncation error. That normalized local truncation error is $O(h)$, so $m=1$ under the normalized convention. Both describe the same Euler one-step defect; neither should be confused with an unqualified global error claim.

Factor the right side as $(x-1{)}^2(x-3)$. On $-1<x<1$, division by $x^2-1$ gives a first-order linear differential equation with integrating factorMultiplication makes the equation $(\mu y{)}^{\prime }=3-x$, so $\mu y=3x-x^2/2+C$. At zero, $\mu (0)y(0)=1$, hence $C=1$. Simplifying givesIts derivative isThe derivation solves the initial-value problem on $(-1,1)$. The simplified expression also extends smoothly through $x=1$ and satisfies the original undivided equation there, giving a solution on all $x>-1$; its pole prevents continuation through $x=-1$.

The variable has positive-integer support, so $\mathbb{P}(X>0)=1$. Subtract consecutive values of the survival function:This is the positive-support convention for the geometric distribution.

Summing a geometric series gives the probability generating functionThe series converges absolutely for $|s|<1/(1-p)$. Differentiating the rational expression yields

The expected value is the derivative of the probability generating function at one. The expression from part (ii) givesIts finiteness also follows directly from the exponentially decaying geometric probabilities.

By independence, for $k\ge 0$,This is the geometric minimum law, givingThe support remains the positive integers; this parameter is a success probability, not a mean.

Since $Y\ge 1$, its finite expected value satisfies $1\le \mu <\infty$. Every $q_k=k{p}_k/\mu$ is nonnegative andThus these values are a probability mass function. They define the size-biased distribution of $Y$: larger values receive proportionally more weight.

For $0\le s<1$, differentiate the probability generating function term by term and multiply by $s/\mu$:This is the size-biased probability generating function identity. At $s=1$, the finite-mean assumption gives the limiting value one on both sides; at zero, positive support gives value zero.

For $Y\sim \mathrm{Geom}(p)$, its mean is $1/p$, so the size-biased probability generating function isChoose $X_1,X_2$ independent with distribution $\mathrm{Geom}(p)$. Their shifted sum has generating function, initially for $s>0$,with both sides continuous and zero at $s=0$. Equality of probability generating functions provesEquivalently, $X_1+X_2=k+1$ has $k$ possible positive summand pairs, each of probability $p^2(1-p{)}^{k-1}$, matching the size-biased geometric distribution probabilities.