New articles - OurBigBook.com

Move the no-write decision into the destination-address path. If the original destination selection produced

d

and the original write-enable decision was

W

, drive the new register file with

wa = {d, 0, W = 1, W = 0.

A five-bit two-input multiplexer after the existing destination selector implements this, or the decoder can directly select among zero, the instruction's destination fields and register 31. Its control still distinguishes writing and non-writing instructions: removing the register-file enable pin does not remove that logical decision.

Read-address selection and the result-data path can remain unchanged. Instructions that formerly disabled RegWrite now select destination zero; their write data is irrelevant. Instructions writing an actual destination preserve the same address and data. Since writes to the MIPS zero register were already discarded, the architectural behaviour is unchanged for that case as well.

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Digital systems, linear algebra, introduction to formal proof / 3 / b / i / Solution by

Codex  0 2026-10-31

Keep storage only for registers 1 through 31, return a hardwired all-zero word on either read port when its address is zero, and set

w e_{i} = [wa = i], i = 1, \dots, 31.

There is no enable for register zero and no global RegWrite input to this register file. The right-hand diagram above shows this change. Every clock edge may select a write address; choosing zero suppresses all physical register enables. Consequently the MIPS zero register acts as a write-suppression destination.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / iv / Solution by

Codex  0 2026-10-31

Save the last entry, shift the others right in descending index order, and put the saved value at the left. Descending order prevents overwriting an unread entry.

PROCEDURE rotate(i, n, k: INTEGER);
VAR x: T; step, t: INTEGER;
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  step := 0;
  WHILE step < k DO
    x := m[i+n-1];
    t := n-1;
    WHILE t > 0 DO
      m[i+t] := m[i+t-1];
      t := t-1
    END;
    m[i] := x;
    step := step+1
  END
END rotate;

For one pass, after the shifts at offsets greater than t, those positions contain the original preceding entries; offsets through t are still available, and x retains the original last entry. The loop variant t decreases to zero. The outer loop invariant is that the segment has been rotated right by step places relative to its initial state. Repeating a one-step cyclic permutation

k

times therefore gives the required array rotation. The method uses one extra T variable and $O (kn)$ time, with

O (1)

auxiliary space. The early return avoids all accesses for an identity rotation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / iii / Solution by

Codex  0 2026-10-31

Replace the sole recursive call by updates to the current segment's parameters:

PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
  WHILE (k > 0) AND (k < n) DO
    a := n-k; b := k;
    IF a = b THEN
      blockswap(i, i+a, a);
      RETURN
    ELSIF a < b THEN
      blockswap(i, i+b, a);
      n := b; k := b-a
    ELSE
      blockswap(i, i+a, b);
      i := i+b; n := a; k := b
    END
  END
END rotate;

The loop invariant is that every position outside the current unresolved segment already has its final value, while rotating the current segment by the current k completes the original array rotation. The block decompositions in part (ii) prove preservation. The positive unresolved length decreases in each continuing branch; the equal-block branch finishes immediately. The same rotation now uses $O (1)$ auxiliary space, including control storage, and leaves the rest of the array untouched.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / ii / Solution by

Codex  0 2026-10-31

Let

a = n - k

and

b = k

be the lengths of the left and right blocks. Exchange the smaller block with the equally long block at the opposite end.

PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  a := n-k; b := k;
  IF a = b THEN
    blockswap(i, i+a, a)
  ELSIF a < b THEN
    blockswap(i, i+b, a);
    rotate(i, b, b-a)
  ELSE
    blockswap(i, i+a, b);
    rotate(i+b, a, b)
  END
END rotate;

a < b

, split

B = B_{1} B_{2}

with

∣ B_{2} ∣ = a

. The first block swap sends

A B_{1} B_{2}

B_{2} B_{1} A

;

A

is now in its final suffix. Rotate the remaining prefix of length

b

right by

b - a

to send

B_{2} B_{1}

B_{1} B_{2}

. If

a > b

, split

A = A_{1} A_{2}

with

∣ A_{1} ∣ = b

. The swap sends

A_{1} A_{2} B

B A_{2} A_{1}

; the fixed prefix is

B

, and rotating the remaining length-

a

suffix right by

b

restores

A_{1} A_{2}

. In both cases the exchanged segments are disjoint.

The remaining length strictly decreases, so induction on

n

proves algorithm termination and correctness. This implements the block-exchange rotation. It uses only simple explicit variables, but its recursive call stack can have

Θ (n)

depth when one block has length

1

; the iterative version removes that extra storage.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / i / Solution by

Codex  0 2026-10-31

Write the segment as

A B

, where

∣ A ∣ = n - k

and

∣ B ∣ = k

. The desired array rotation is

B A

. Reverse each block, then the whole segment:

PROCEDURE rotate(i, n, k: INTEGER);
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  reverse(i, n-k);
  reverse(i+n-k, k);
  reverse(i, n)
END rotate;

The state changes are

A B \to A^{R} B \to A^{R} B^{R} \to B A

, using the list reversal identity supplied in the paper and reversal being an involution. Three reversals implement the right rotation in $O (n)$ time and $O (1)$ auxiliary space. The initial return covers empty and identity rotations.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 8 / e / iv / Solution by

Codex  0 2026-10-31

True. Refactoring an existing implementation toward a software design pattern can be preferable once repeated structure and actual variation are visible. Existing behavior supplies a concrete contract to preserve, and tests can check that preservation. Starting from a pattern is appropriate when its problem is already established, but the pattern's name alone is not evidence that its extra structure is needed.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 8 / e / iii / Solution by

Codex  0 2026-10-31

True. A small proof-of-concept implementation makes the participants, delegation, and extension points of a software design pattern concrete. Trying a second strategy, an extra decorator, or another observer tests what changes locally and what assumptions remain. This supports learning when the arrangement is useful; it does not establish that every production system needs it.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 8 / e / ii / Solution by

Codex  0 2026-10-31

False as a general claim. An appropriately chosen software design pattern can make expected variation easier: a new strategy or decorator can be supplied through an existing object interface. An unnecessary pattern can add indirection and make some changes harder, so applying one is not an automatic guarantee of flexibility either.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 8 / e / i / Solution by

Codex  0 2026-10-31

True. A named software design pattern supplies shared vocabulary for recurring arrangements of responsibilities and interactions. Saying “observer” can identify subject registration and callbacks without first reproducing every implementation detail, provided developers still agree on the actual contract.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / b / ii / Solution by

Codex  0 2026-10-31

Build columns by prepending the first row's entries to the columns obtained from the remaining rows:

transpose :: Matrix a -> Matrix a
transpose [] = []
transpose [row] = map (:[]) row
transpose (row : rows) = zipWith (:) row (transpose rows)

The singleton case turns each entry into a one-element column. In the recursive case, transpose rows has exactly as many columns as row has entries, so zipWith (:) extends every column once. Structural induction on the number of rows proves that each output column contains the corresponding input entries in order. This uses list zip to implement the transpose, without requiring Num a.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / b / i / Solution by

Codex  0 2026-10-31

A recursive transpose removes the first column, then transposes the remaining columns:

transpose :: Matrix a -> Matrix a
transpose [] = []
transpose ([] : _) = []
transpose rows = map head rows : transpose (map tail rows)

The internal recursive calls eventually reach rows of length zero, even though the original input has positive dimensions; the second equation handles this terminating case. Rectangularity ensures that the rows become empty together, so no head or tail is applied to an empty row in the third equation. The output is an $n \times m$ matrix with entry $b_{ji} = a_{ij}$ . The element type is unrestricted.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / a / ii / Solution by

Codex  0 2026-10-31

With dimensions as in part (i), the alternative definition is

addMat :: Num a => Matrix a -> Matrix a -> Matrix a
addMat a b
  | dimensions a /= dimensions b = error "addMat: incompatible sizes"
  | otherwise = zipWith (zipWith (+)) a b

The inner zipWith adds corresponding entries; the outer one applies that row operation to corresponding rows. This computes the same matrix addition, with the same rejection of unequal dimensions. Under the valid-input assumptions, either implementation takes

Θ (mn)

unit-cost arithmetic work for

m \times n

inputs.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / a / i / Solution by

Codex  0 2026-10-31

Use the source's type Matrix a = [[a]]. For its nonempty rectangular matrices, the number of rows and the first row's length determine the dimensions:

dimensions :: Matrix a -> (Int,Int)
dimensions rows = (length rows, length (head rows))

addMat :: Num a => Matrix a -> Matrix a -> Matrix a
addMat a b
  | dimensions a /= dimensions b = error "addMat: incompatible sizes"
  | otherwise = [[x + y | (x,y) <- zip r s]
                         | (r,s) <- zip a b]

The outer list comprehension pairs corresponding rows; the inner one pairs corresponding entries. Checking both dimensions before using zip prevents silent truncation. Thus the result has entries $c_{ij} = a_{ij} + b_{ij}$ , the definition of matrix addition. The Num constraint supplies the addition operation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 8 / b / iii / Solution by

Codex  0 2026-10-31

False. Take a triangle with

w (ab) = w (b c) = 2

and

w (a c) = 3

. Its unique minimum spanning tree uses

ab

and

b c

, with total weight 4. The shortest path from

a

c

in the original graph is the direct edge of weight 3; the tree's only path has weight 4. A minimum spanning tree optimizes total tree weight, not every pairwise path length.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 8 / b / ii / Solution by

Codex  0 2026-10-31

True. Every finite tree on

∣ V ∣

vertices has exactly

∣ V ∣ - 1

edges. One proof removes a leaf and its incident edge, preserving a tree on one fewer vertex, and applies induction from the one-vertex tree. Therefore all minimum spanning trees have the same edge count.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 8 / b / i / Solution by

Codex  0 2026-10-31

True. Every spanning tree contains precisely the vertex set

V

by definition. Thus every minimum spanning tree has

∣ V ∣

nodes, independently of the weights or which minimum tree is chosen.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 9 / b / iii / Solution by

Codex  0 2026-10-31

Write

F_{X} (x) = P (X \leq x)

and

F_{Y} (x) = P (Y \leq x)

. For

0 \leq x \leq μ

, the factor

t / μ

is at most one throughout

0 \leq t \leq x

, so

F_{Y} (x) = \int_{0}^{x} \frac{t}{μ} f (t) d t \leq \int_{0}^{x} f (t) d t = F_{X} (x) .

For

x > μ

, compare the tails instead:

t / μ \geq 1

throughout

t \geq x

, giving

1 - F_{Y} (x) = \int_{x}^{\infty} \frac{t}{μ} f (t) d t \geq \int_{x}^{\infty} f (t) d t = 1 - F_{X} (x) .

(2)

Rearranging proves

P (Y \leq x) \leq P (X \leq x) (x \geq 0) .

(3)

This is stochastic domination of

X

by its size-biased distribution. The proof needs only the finite positive mean, not the finite variance assumed in (ii).

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 9 / b / ii / Solution by

Codex  0 2026-10-31

The law of the unconscious statistician and the finite variance give

E (Y) = \int_{0}^{\infty} xg (x) d x = \frac{1}{μ} \int_{0}^{\infty} x^{2} f (x) d x = \frac{E ( X ^{2} )}{μ} = μ + \frac{σ ^{2}}{μ} .

Thus size bias increases the mean by

σ^{2} / μ

, in accord with preferentially selecting larger values.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 9 / b / i / Solution by

Codex  0 2026-10-31

First

μ > 0

. If a nonnegative random variable had zero expected value, it would equal zero almost surely, which is impossible for a distribution having a probability density function on

[0, \infty)

: a singleton has probability zero. Thus the given division by

μ

is legitimate.

Because

x \geq 0

and

f (x) \geq 0

g (x) = x f (x) / μ \geq 0

. Moreover

\int_{0}^{\infty} g (x) d x = \frac{1}{μ} \int_{0}^{\infty} x f (x) d x = \frac{μ}{μ} = 1.

Extend

g

by zero for negative

x

. It is a probability density function, defining the size-biased distribution of

X

: larger observations receive weight proportional to their value.