Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation (CCOM 4214, Paper 2)

Original examination: Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation examination paper by the University of Oxford (2003).

The repeated root of the characteristic equation suggests factoring out $e^x$. Set $y=e^{x}u$. The product rule givesThus the ordinary differential equation reduces to $u^{\prime \prime }=1$, with general solution $u=x^2/2+Ax+B$. The first initial condition gives $B=1$. Since $y^{\prime }(0)=A+B=2$, the other initial condition gives $A=1$. ThereforeSubstitution into the reduced ordinary differential equation and the two initial conditions verifies the result.

For $y_1=(1-x{)}^{-1}$, the derivatives are $y_1^{\prime }=(1-x{)}^{-2}$ and $y_1^{\prime \prime }=2(1-x{)}^{-3}$. Consequently the left-hand side of the ordinary differential equation iswhere $x\ne 1$.

Use reduction of order, writing $y=u/(1-x)$. A direct application of the product rule givesFor $v=u^{\prime }$ the resulting first-order ordinary differential equation is $v^{\prime }/v=2/(1-x)$ whenever $v\ne 0$. Integration yields $v=C(1-x{)}^{-2}$ and $u=A+B/(1-x)$; the case $v=0$ is already included. Henceon either interval $x<1$ or $x>1$. The two displayed solutions of a differential equation are linearly independent, so they span the solution space of a homogeneous linear differential equation on either interval. The point $x=1$ is a singular point of a differential equation and cannot be crossed by a nonzero member of this family that remains finite there.

Multiplying the ordinary differential equation by two suggests using the dependent variable $Y=y^2$, whose derivative is $Y^{\prime }=2y{y}^{\prime }$. On the interval through $x=1$, this gives the linear ordinary differential equationAfter integration, $Y=x^2+Cx$. The initial condition $Y(1)=4$ gives $C=3$. As $y(1)>0$, continuity selects the positive branch:The interval $x>0$ is the maximal real interval through the given initial condition: at $x=0$ the formula approaches $0$, but its derivative is unbounded, so it does not extend through zero as a differentiable solution of a differential equation.

Assume all partial derivatives needed below are continuous. The multivariable chain rule iswhere the partial derivatives of $g$ are evaluated at $(u(x,y),v(x,y))$. Apply the product rule and the multivariable chain rule once more:Clairaut's theorem gives $g_{vu}=g_{uv}$, soDifferentiating $f_x$ with respect to $y$ instead gives

For this change of variables,and $u_{xx}+u_{yy}=0=v_{xx}+v_{yy}$. The second derivative chain rule therefore givesThus the transformation rule for the Laplacian isFor $f=x+y$, its Laplacian is zero. At every point with $(x,y)\ne (0,0)$, division by $4(x^2+y^2)$ provesThis conclusion applies to each local inverse branch of the change of variables: its Jacobian determinant is $4(x^2+y^2)$, so such a branch exists away from the origin by the inverse function theorem. A single globally defined $g$ cannot represent $x+y$ on the entire plane, since $(x,y)$ and $(-x,-y)$ give the same $(u,v)$ but generally opposite values of $x+y$. Nor can a differentiable $g$ represent this $f$ in a neighborhood of the origin: the multivariable chain rule there would give $f_x=f_y=0$, contradicting $f_x=f_y=1$. The requested harmonic function conclusion is therefore a local statement on nonsingular branches.^[ref]

Write $z(x,y)=Z(r,s)$ in the new coordinates. Sincethe partial differential equation becomesFor a twice continuously differentiable solution of a differential equation, $Z_r$ is independent of $s$, so integration first in $r$ and then in $s$ givesThis is the decomposition of the one-dimensional wave equation into waves traveling in opposite directions.

The first initial condition gives $\varphi (y)+\psi (y)=\cos y$. The second initial condition gives ${\varphi }^{\prime }(y)-{\psi }^{\prime }(y)=0$. Differentiating the first relation and combining the two relations yields ${\varphi }^{\prime }=ps{i}^{\prime }=-\frac{1}{2}\sin y$. Thus $\varphi (y)=\frac{1}{2}\cos y+C$ and $\psi (y)=\frac{1}{2}\cos y-C$. The constants cancel, and the cosine addition formula givesBoth initial conditions and the partial differential equation follow directly by differentiation.

For a linear map $T:V\to W$, its image of a linear map and kernel of a linear map areTheir dimensions define the rank of a linear map and nullity:The image of a linear map measures which output vectors can occur, while the kernel of a linear map measures which input vectors are sent to zero.

The rank-nullity theorem states that a linear map $T:V\to W$ with finite-dimensional $V$ satisfiesChoose a basis $k_1,\dots ,k_r$ of $\ker T$ and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We prove that $T{u}_1,\dots ,T{u}_s$ is a basis of $\mathrm{im}T$.

Every $v\in V$ is a linear combination of the extended basis. Applying $T$ kills the $k_i$ terms, so $Tv$ is a linear combination of $T{u}_1,\dots ,T{u}_s$. This proves the linear span assertion. For linear independence, if ${\sum }_j{b}_{j}T{u}_j=0$, then ${\sum }_j{b}_j{u}_j$ belongs to the kernel of a linear map. Hence ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some scalars $a_i$. The linear independence of the extended basis forces every $a_i$ and $b_j$ to vanish. Consequently $\mathrm{rank}T=s$ and $\mathrm{nullity}T=r$, while $\dim V=r+s$, proving the theorem.

By diagonalizability, $V$ has an eigenbasis $e_1,\dots ,e_m$ with $T{e}_j={\lambda }_j{e}_j$. Arrange the basis so that ${\lambda }_1=\cdots ={\lambda }_r=0$ and the remaining eigenvalues are nonzero. If there are no zero or no nonzero eigenvalues, the corresponding linear span below is simply the zero vector subspace.

For $v={\sum }_j{a}_j{e}_j$, the equation $Tv=0$ holds precisely when $a_j=0$ for every $j>r$. ThusEvery output is in $\mathrm{span}\{e_{r+1},\dots ,e_m\}$, and conversely $e_j=T({\lambda }_j^{-1}{e}_j)$ for each $j>r$. ThereforeThese two disjoint parts of a basis span $V$ and their linear spans intersect only at zero. This is exactly the direct sum of vector spaces assertion

Take the linear mapIts kernel of a linear map consists of all $(x,0)$, and its image of a linear map is the same line:Their set intersection is nonzero and their sum is only one-dimensional. In particular, $(0,1)$ cannot be written as a sum of one vector from each of these vector subspaces. The nonzero set intersection also prevents an internal direct sum of vector spaces. ThusThe matrix is a nonzero nilpotent matrix; its failure of diagonalizability explains why the preceding result does not apply.

The three elementary row operations are:

The nonzero requirement in the second operation ensures that each elementary row operation is reversible.

For a square matrix, the corresponding changes in its determinant areThese follow respectively from the alternating property, multilinearity in the rows, and the fact that a determinant with two equal rows vanishes.

If a square matrix $A$ is an invertible matrix, multiplicativity of the determinant givesso $\det A\ne 0$.

Conversely, suppose $\det A\ne 0$. Use Gaussian elimination to reduce $A$ to row echelon form $U$. Each elementary row operation multiplies the determinant by a nonzero factor, so $\det U\ne 0$. If this square matrix had fewer than $n$ pivots, its row echelon form would have a zero row and hence zero determinant, a contradiction. Therefore it has a pivot in every row and column, and further elementary row operations reduce it to $I$.

Each elementary row operation is multiplication on the left by an invertible matrix, its inverse being the reverse operation. Thus $E_k\cdots E_{1}A=I$ implies $A=E_1^{-1}\cdots E_k^{-1}$, a product of invertible matrices. Hence

Let $A_n$ denote the given tridiagonal matrix and put $D_n=\det A_n$, including $D_0=1$ for the empty determinant. The starting values areFor $n\ge 3$, apply the following elementary row operations in the indicated order, always using the updated rows:The first three rows now beginwith the fourth column omitted if $n=3$. When $n\ge 4$, also use $R_4\leftarrow R_4-R_3$. The resulting block upper triangular matrix has a $3\times 3$ upper triangular matrix with diagonal entries all one in its top left corner, and $A_{n-3}$ in its bottom right corner. All elementary row operations preserved the determinant except the single row interchange. ThereforeApplying this recurrence relation to the three starting values proves by mathematical induction thatEquivalently, the sequence is periodic with period six, with values $1,1,0,-1,-1,0$ starting at $n=0$. A compact closed form is $D_n=\sin ((n+1)\pi /3)/\sin (\pi /3)$.

A square matrix is an invertible matrix exactly when its determinant is nonzero. The preceding recurrence relation therefore gives

For events $A,B$ with $\mathbb{P}(B)>0$, the conditional probability isIt measures the probability of $A$ after restricting the sample space to $B$ and renormalizing. This quotient does not define conditional probability given an event of zero probability.

The partition theorem is the law of total probability. If $B_1,B_2,\dots$ form a finite or countable partition of a sample space into pairwise disjoint events with positive probabilities, then for any event $A$,Indeed, $A$ is the disjoint union of the events $A\cap B_j$, so countable additivity gives the formula after applying the definition of conditional probability. Zero-probability members can be omitted.

Let $X_j$ be the indicator random variable that coin $j$ shows a head. Each expectation is $\mathbb{E}{X}_j=1/2$, so linearity of expectation gives the expected number of heads:For the game, write $p_i$ for the probability that $H$ eventually holds all $n$ coins when starting with $i$. The states $0,n$ are absorbing, so $p_0=0$ and $p_n=1$. Conditioning on the first toss and using the law of total probability givesThus $p_{i+1}-p_i=p_i-p_{i-1}$: successive differences are constant, and $p_i=A+Bi$. The boundary values give $A=0$, $B=1/n$, hence the gambler's ruin answer isFor completeness, the game terminates with probability one. From any nonabsorbing state, a run of $n$ consecutive heads would reach $n$ within the next $n$ tosses, and that run has probability $2^{-n}$. Conditional on survival, the same bound applies to the next block. Therefore the probability of surviving $kn$ tosses is at most $(1-2^{-n}{)}^k$, which tends to zero.

Let $W$ be the event that $H$ wins, and $F$ the event that his first toss is a tail. For a nontrivial starting state $1\le i\le n-1$, a first tail has probability $1/2$ and changes his holding to $i-1$. By the chain rule for probabilities,Since $\mathbb{P}(W)=i/n>0$, the definition of conditional probability givesIn particular, when $i=1$, losing the first coin would end the game in defeat, so the conditional answer is zero. At $i=0$ conditioning on victory is undefined, while at $i=n$ the game has already ended and no first toss occurs.

Let $I$ be the number of heads in the initial allocation tosses. Then $I$ has the binomial distribution with parameters $n$ and $1/2$. Given $I=i$, the winning probability is $i/n$, including the already finished games $i=0,n$. The law of total probability and linearity of expectation giveThus, for $n\ge 1$,

The binary relation $x\le y$ on the natural numbers is not a Euclidean relation. Choose $x=1$, $y=3$, $z=2$. Then $1\le 3$ and $1\le 2$, but $3\nleqq 2$. Thus

The divisibility binary relation on positive natural numbers is not a Euclidean relation. With $x=1$, $y=2$, $z=3$, we have $1\mid 2$ and $1\mid 3$ but $2\nmid 3$. Therefore

Equality of remainders after division by eight is a Euclidean relation. If $x$, $y$ have the same remainder and $x$, $z$ have the same remainder, then $y$, $z$ have the same remainder. In the notation of modular arithmetic,Hence

Inequality on a domain containing at least two people is not a Euclidean relation. Choose distinct people $a,b$ and put $x=a$, $y=z=b$. Both premises $a\ne b$ hold, but the conclusion would be $b\ne b$. ThusThe possibility $y=z$ matters: the defining universal quantifiers do not require distinct arguments. On a domain with at most one element the inequality binary relation is empty and the condition holds by vacuous truth.

The “same age” binary relation is a Euclidean relation, with age understood as one consistently measured value at a fixed time. If $x$ has the same age as both $y$ and $z$, the ages of $y$ and $z$ are equal. HenceThis is another instance of equality of the values of a function inducing an equivalence relation.

A binary relation $R$ on a set $X$ is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation. In first-order logic, these three requirements are

Suppose $R$ is an equivalence relation, and $xRy$, $xRz$. Since it is a symmetric relation, $yRx$. Since it is a transitive relation, $yRx$ together with $xRz$ implies $yRz$. This proves

Suppose $R$ is a reflexive relation and a Euclidean relation. To prove it is a symmetric relation, assume $xRy$. Reflexivity gives $xRx$, so applying the Euclidean implication to $xRy$ and $xRx$ gives $yRx$.

To prove it is a transitive relation, assume $xRy$ and $yRz$. The symmetry just established gives $yRx$. Apply the Euclidean implication with common predecessor $y$ to $yRx$ and $yRz$; the conclusion is $xRz$. Thus all three requirements hold:

On the nonempty set $X=\{a\}$ take the empty binary relation $R=\varnothing$. There are no triples for which $xRy\wedge xRz$ holds. The defining implication is therefore true for every triple by vacuous truth, making $R$ a Euclidean relation.

But $aRa$ is false, so $R$ is not a reflexive relation and hence is not an equivalence relation:

The answer is no, even when both original binary relations are equivalence relations. On $X=\{a,b,c\}$, let $R_1$ have equivalence classes $\{a,b\},\{c\}$ and $R_2$ have equivalence classes $\{a\},\{b,c\}$. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations: $xRy$ means $x{R}_{1}z$ and $z{R}_{2}y$ for some $z$. The possible successors areIndeed, from $a$ or $b$ the first step can reach $a$ or $b$, whose $R_2$ successors together exhaust $X$; from $c$ the first step must stay at $c$, whose $R_2$ successors are only $b,c$. Consequently $cRb$ and $bRa$, but not $cRa$. Therefore

First, the product order is a partial order. Reflexivity and transitivity hold in each coordinate. If $(p,q){\le }_R(p^{\prime },q^{\prime })$ and $(p^{\prime },q^{\prime }){\le }_R(p,q)$, antisymmetry in $P,Q$ gives $p=p^{\prime }$ and $q=q^{\prime }$, proving antisymmetry in the product.

Let $D$ be a nonempty directed set in $P\times Q$. Its coordinate projectionsare directed sets. For example, if $p_1,p_2\in D_P$, choose $(p_1,q_1),(p_2,q_2)\in D$. Directedness supplies $(p_3,q_3)\in D$ above both, so $p_3\in D_P$ is a common upper bound of $p_1,p_2$ inside $D_P$. The argument for $D_Q$ is identical.

By the assumed directed-complete partial order property, $p_{\ast }=\sup D_P$ and $q_{\ast }=\sup D_Q$ exist. Every $(p,q)\in D$ satisfies $p{\le }_P{p}_{\ast }$ and $q{\le }_Q{q}_{\ast }$, so $(p_{\ast },q_{\ast })$ is an upper bound of $D$. If $(u,v)$ is any other upper bound, then $u$ bounds $D_P$ and $v$ bounds $D_Q$. Hence $p_{\ast }{\le }_{P}u$, $q_{\ast }{\le }_{Q}v$, proving leastness. ThusThe printed definition of a directed set also permits $D=\varnothing$.^[ref] Under that convention, the hypotheses require $P,Q$ to have least elements, namely the least upper bounds of their empty subsets. Their pair is the least element of the product and is $\sup \varnothing$ there. This handles the empty case as well; under the convention restricting directed sets to nonempty sets, only the preceding nonempty argument is needed.

Take the five-element partially ordered set $P=\{\perp ,a,b,u,v\}$. Its strict comparisons are $\perp <a$, $\perp <b$, and $a<u$, $a<v$, $b<u$, $b<v$, together with their transitive consequences. The elements $a,b$ are incomparable, as are $u,v$.

A finite directed set has a greatest element whenever it is nonempty: list its elements and repeatedly use directedness to find an internal upper bound of the previously chosen element and the next one. The final element is above every member of the directed set, and is its least upper bound. Thus every nonempty directed set in $P$ has a least upper bound. The empty subset also has a least upper bound, namely $\perp$. Therefore $P$ satisfies the paper's completeness condition under either convention.

However, $\{a,b\}$ is bounded above by both $u$ and $v$. A least upper bound would have to be an upper bound lying below both $u$ and $v$. Neither $u$ nor $v$ has that property, and none of $\perp ,a,b$ is an upper bound of $\{a,b\}$. Hence

Take the natural numbers including zero with their usual total order:A nonempty subset with an upper bound $m\in P$ is contained in the finite set $\{0,1,\dots ,m\}$. It therefore has a greatest element, which is its least upper bound. The empty subset has least upper bound $0$. Thus $P$ is a bounded-complete partially ordered set.

But $D=P$ is a directed set, since $\max (x,y)\in P$ is above any two members. It has no upper bound in $P$: for any proposed bound $m$, the member $m+1$ is larger. It therefore has no least upper bound. Hence

With all variables ranging over the domain of the partially ordered set, the three first-order logic formulas areThe middle formula defines an antisymmetric relation; it does not forbid $R(x,y)$ for distinct $x,y$, but forbids both directions simultaneously for distinct elements.

Let $\mathbf{A}$ be the one-element partially ordered set $\{a\}$ with $R(a,a)$. Taking $x=a$ witnesses the existential quantifier, and the only $y$ is comparable with $a$. Thus $\mathbf{A}\models \phi$.

Let $\mathbf{B}$ be the two-element antichain $\{a,b\}$, with $R$ consisting only of $(a,a)$ and $(b,b)$. This is a partial order. If $x=a$, choose $y=b$, and if $x=b$, choose $y=a$. In either case both $R(x,y)$ and $R(y,x)$ are false. Therefore no witness for the existential quantifier exists:

In the language of first-order logic, defineThus a least element lies below every element, whereas a minimal element merely has no distinct element below it. The latter definition allows multiple incomparable minimal elements.

Here is a formal natural deduction proof, with the antisymmetry axiom available as a premise. Assume $\mathrm{Bottom}(b)$ and take a fresh arbitrary variable $t$. Assume $R(t,b)$. By universal elimination applied to $\mathrm{Bottom}(b)$, obtain $R(b,t)$. By conjunction introduction, obtain $R(t,b)\wedge R(b,t)$. Instantiate antisymmetry at $t,b$, and use modus ponens rule to obtain $t=b$. Discharge the assumption $R(t,b)$ by implication introduction, obtaining $R(t,b)\Rightarrow t=b$. Since $t$ was arbitrary and is free in no undischarged assumption, universal introduction gives $\mathrm{Minimal}(b)$. Discharge the initial assumption and universally quantify $b$ to concludeOnly antisymmetry was needed for this implication; reflexivity and transitivity are part of the ambient partial order axioms.

The assertion is true. Every single finite string $w=b_1\cdots b_k$ over $\{0,1\}$ is denoted by the regular expression $b_1\cdots b_k$. The empty string is denoted by $ϵ$. Hence if $F=\{w_1,\dots ,w_m\}$ is a finite formal language, the regular expressiondenotes precisely $F$, with each $w_j$ read as its concatenation of symbols. This uses the defining union and concatenation operations for regular expressions. For $F=\varnothing$, use the regular expression $\varnothing$. Therefore

The assertion is false. Use the pumping lemma for regular languages: if $L$ is a regular language, there is $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ admits a factorization $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{k}z\in L$ for every integer $k\ge 0$.

Suppose the stated formal language were a regular language, and take $w=0^{2p}{1}^p$. This string has twice as many zeros as ones, so it belongs to $L$. In every allowed factorization, the first $p$ positions are all zeros, forcing $y=0^d$ with $1\le d\le p$. Pumping down with $k=0$ producesIt still has $p$ ones but fewer than $2p$ zeros, contradicting the pumping lemma for regular languages. Thus