New articles - OurBigBook.com

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 5 / a / Solution by

Codex  0 2026-10-25

Choose $A = I_{2}$ and $B = 3 I_{2}$ . Then

A B = 3 I_{2} = A^{2} + A + I_{2}

. Both are real

2 \times 2

matrices, as required.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / f / Solution by

Codex  0 2026-10-25

The initial vector decomposes especially simply in the eigenbasis:

(12) = v_{φ} + v_{ψ},

because

φ + ψ = 1

. Applying

A^{n}

multiplies the two eigenvectors by

φ^{n}

and

ψ^{n}

. Part (b) then yields

(L_{n + 1} L_{n}) = φ^{n} (φ 1) + ψ^{n} (ψ 1) .

(2)

Reading the second coordinate gives the Lucas closed form

L_{n} = φ^{n} + ψ^{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n} (n \geq 0) .

(3)

n = 0

this is 2 and at

n = 1

it is 1. Each summand obeys the same recurrence relation, which independently verifies the formula and explains why the irrational parts cancel to give an integer.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / e / Solution by

Codex  0 2026-10-25

The requested order is

A = P^{- 1} D P

. To obtain this order directly, put the transposes of the two eigenvectors in the rows of

P

, using the fact that

A

is symmetric:

P = (φ ψ 11), D = (φ 0 0 ψ) .

Then

det P = φ - ψ = 5 \neq = 0

, so

P

is an invertible matrix, with

P^{- 1} = \frac{1}{5} (1 - ψ - 1 φ) .

(2)

Multiplication gives

P A = (φ + 1 ψ + 1 φ ψ) = D P

, since

φ^{2} = φ + 1

and

ψ^{2} = ψ + 1

. Multiplying by

P^{- 1}

proves the required diagonalization. Putting the eigenvectors in columns would instead give the equally standard order

A = Q D Q^{- 1}

, so the convention must be checked rather than copied mechanically.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / d / Solution by

Codex  0 2026-10-25

For an eigenvalue

t \in {φ, ψ}

, the equation

A (x, y)^{T} = t (x, y)^{T}

gives

x = t y

and

(t + 1) y = t^{2} y

. The second identity holds because

t^{2} = t + 1

. Taking

y = 1

gives the eigenvectors

v_{φ} = (φ 1), v_{ψ} = (ψ 1) .

Each associated eigenspace consists of all scalar multiples of its displayed vector. A zero vector is excluded when speaking of an eigenvector.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / c / Solution by

Codex  0 2026-10-25

The characteristic polynomial is

det (t I - A) = det (t - 1 - 1 - 1 t) = t^{2} - t - 1.

Its two distinct real roots are the eigenvalues

φ = \frac{1 + 5}{2} > 0, ψ = \frac{1 - 5}{2} < 0.

(2)

Their product is

- 1

, so

ψ = - 1/ φ

. Equivalently,

φ^{2} = φ + 1

implies

1/ φ = φ - 1

. The positive eigenvalue is the golden ratio.

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

Codex  0 2026-10-25

Use mathematical induction on

n

. For

n = 0

, the identity matrix gives

(1, 2)^{T} = (L_{1}, L_{0})^{T}

. If

A^{n} (1, 2)^{T} = (L_{n + 1}, L_{n})^{T}

, applying

A

and using part (a) gives

A^{n + 1} (1, 2)^{T} = (L_{n + 2}, L_{n + 1})^{T}

. Therefore

A^{n} (12) = (L_{n + 1} L_{n}) (n \geq 0) .

The base case is essential: the starting vector represents consecutive Lucas numbers, not two arbitrary initial values.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / a / Solution by

Codex  0 2026-10-25

The update must place the sum of the two current entries in the first coordinate and retain the old first coordinate in the second. Thus choose the matrix

A = (1110) .

By matrix multiplication,

A (L_{n}, L_{n - 1})^{T} = (L_{n} + L_{n - 1}, L_{n})^{T} = (L_{n + 1}, L_{n})^{T}

for every

n \geq 1

, using the given recurrence relation. This is the companion-matrix representation of the Lucas numbers.

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

Codex  0 2026-10-25

Use a synchronous sequential circuit with four Moore machine states.

R

is ready,

P

is the one-cycle pulse state,

D

is disabled with no qualifying final zero, and

Z

is disabled after one sampled zero. Reset into

R

, so an initial sampled high generates a pulse immediately. The complete transition/output table is:

State	Code $q_{1} q_{0}$	Next if $a = 0$	Next if $a = 1$	$z$
$R$	$00$	$R$	$P$	$0$
$P$	$10$	$Z$	$D$	$1$
$D$	$11$	$Z$	$D$	$0$
$Z$	$01$	$R$	$D$	$0$

A particularly small implementation uses two D flip-flops with the next-state equations

q_{1}^{+} = a, q_{0}^{+} = q_{1} \lor (q_{0} \land a), z = q_{1} \land \neg q_{0}, (q_{1}, q_{0})_{reset} = (0, 0) .

Both D flip-flops share the clock; their outputs feed the displayed logic gates. The output depends only on the stored state, not combinationally on the external input. At each edge, evaluate the right-hand sides using the old state and the sampled input, then update both flip-flops together. The resulting

z

applies throughout the following clock period.

From

R

, a high enters

P

. The next edge always leaves

P

, so the pulse lasts exactly one period. In the disabled states, a high leads to

D

and erases progress towards rearming. A zero enters

Z

, and a second successive zero enters

R

. A later high can then enter

P

. This proves both the two-zero requirement and the startup exception. For example, sampled inputs

1, 1, 0, 1, 0, 0, 1, 0, 0, 1

yield outputs

1, 0, 0, 0, 0, 0, 1, 0, 0, 1

Figure 1.
Original Moore-state design and clocked example for the two-zero rearming pulse detector. State and output are shown after each sampling edge.
**Details**.

The construction is a synchronous pulse detector with two-zero rearming. Assume

a

meets setup/hold requirements at the sampling edges. A genuinely asynchronous input would first require synchronization, with its associated latency; that is separate from this sampled-input specification.

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

Codex  0 2026-10-25

Factor the common input before constructing the networks. Use an NMOS transistor controlled by

b

in series with parallel NMOS transistors controlled by

a

and

c

. Its conducting condition remains

b (a \lor c)

. The complementary upper network is a PMOS transistor controlled by

b

in parallel with a series chain of PMOS transistors controlled by

a

and

c

; its conducting condition is

\neg b \lor \neg a \neg c

This is the right panel in part (a). It uses three lower plus three upper transistors, six in total instead of eight, and needs no separate inverter or complemented external input. The complementary CMOS network duality ensures the same static Boolean function and complementary rail connections.

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

Codex  0 2026-10-25

The pull-down Boolean function is

ab \lor b c = b (a \lor c)

. A conducting pull-down makes

z = 0

, so

z = \neg (b \land (a \lor c)) = \neg b \lor (\neg a \land \neg c) .

In particular, if

b = 0

the output is always high; if

b = 1

, the output is high precisely when both other inputs are low. These cases give the truth table without confusing a network's conducting condition with the output voltage.

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

Codex  0 2026-10-25

The lower NMOS transistor network conducts through either the

a, b

series branch or the

b, c

series branch. Complete the upper PMOS transistor network by the series-parallel dual: between

V_{dd}

and an intermediate node put

p (a)

and

p (b)

in parallel, and between that node and

z

put

p (b)

and

p (c)

in parallel. There are four upper transistors, complementing the four lower transistors. Use the usual body ties to the corresponding supply rails. Each

p (x)

denotes a PMOS transistor controlled by input

x

, so it conducts when

x = 0

The upper conducting condition is

(\neg a \lor \neg b) \land (\neg b \lor \neg c)

, exactly the complement of

ab \lor b c

. Thus for every stable input the output has a conducting path to exactly one rail in the ideal static CMOS model. The left panel below specifies the added network independently of the source drawing; join its lower terminal to the existing output.

Figure 1.
Original solution schematics: the required four-device pull-up network, and a factored six-transistor realization of the same gate. Bubbles identify PMOS gates.
**Details**.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 2 / c / Solution by

Codex  0 2026-10-25

A 32-bit free-running timer operates modulo

M = 2^{32}

. If its previous reading is

p

, and the actual elapsed count is

d

with

0 \leq d < M

, the new reading is

(p + d) mod M

. The modulo-counter elapsed-time identity therefore gives

(uint32_t) (now - previous_tick) = d .

Unsigned integer arithmetic in C reduces the subtraction modulo

2^{32}

, so the identity remains valid when a wrap occurs between pulses. For example, readings

2^{32} - 8000

and

8000

give 16,000 ticks, hence one millisecond, rather than a negative interval.^[ref]

At the specified clock rate, the true wrap period is $2^{32} /16, 000, 000 = 268.435456$ seconds. The printed 256 seconds is inconsistent with the other two specifications. The implementation uses the stated 32-bit width and 16 MHz rate. Assuming consecutive handled pulses are less than 256 seconds apart is a sufficient conservative bound; the exact allowable bound is less than 268.435456 seconds.

This calculation requires less than one entire timer modulus of elapsed ticks between successive stored timestamps. If a whole wrap or several wraps elapse, identical register readings cannot reveal how many occurred; an overflow counter or an independent longer-range clock would be needed. Also assume pulse events are not lost and interrupt latency is constant or sufficiently small for the required accuracy: timestamps read in software measure handler-to-handler intervals, not perfect hardware capture times. Conversion to milliseconds occurs after modular subtraction, so separately rounded absolute timestamps cannot corrupt the wrap calculation.

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

Codex  0 2026-10-25

The interrupt handler is the only writer of interval_ms, valid and next_slot. The foreground function takes an interrupt-safe ring-buffer snapshot inside a short critical section, copying the count and exactly that many valid entries before restoring the previous mask. It performs the comparatively expensive summation and division after interrupts are restored. A new pulse then affects the next query, while the current query consistently describes the earlier snapshot.

Without exclusion, the foreground could read an old entry, be interrupted while the buffer is updated, then read new entries or an inconsistent count. Even indivisible 32-bit loads would not make that multi-element snapshot atomic. The volatile-qualified objects in C ensure that the compiler performs required shared or device accesses; volatile does not provide mutual exclusion or a coherent multiword snapshot.^[ref]

This design assumes a single-core foreground/interrupt execution model: no other interrupt, DMA engine or core modifies the protected buffer. The mask hooks must prevent compiler reordering across their boundaries and really mask the GPIO interrupt. Restoring the saved mask also makes the function safe to call when interrupts were already disabled. Keep the critical section short enough that the event register does not coalesce multiple heartbeats while interrupts are masked; otherwise the hardware interface cannot reconstruct events it never recorded.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 2 / a / Solution by

Codex  0 2026-10-25

Keep successive timestamps in raw unsigned ticks, and convert their modular difference to milliseconds only after subtraction. The first pulse establishes a timestamp; it does not create a fictitious interval from startup. Store valid intervals in a five-element ring buffer. During startup, average the one to four intervals actually available; return zero until there is at least one valid interval. Here zero is explicitly an unavailable-data sentinel.

The following C programming language code uses the supplied register names through an abstract memory-mapped input-output register interface. The board port supplies the actual register mapping and interrupt vector; no undocumented addresses are assumed. The two interrupt-mask hooks have the exact semantics described below and are interface requirements, not names asserted to exist in an unspecified device library.

#include <stdint.h>
#include <stdbool.h>

struct gpio_registers { volatile uint32_t EVENT; };
struct timer_registers { volatile uint32_t COUNT; };
extern struct gpio_registers GPIO;
extern struct timer_registers TIMER;

uint32_t irq_save_disable(void);
void irq_restore(uint32_t old_mask);

static volatile uint32_t interval_ms[5];
static volatile uint32_t next_slot = 0;
static volatile uint32_t valid = 0;
static volatile uint32_t previous_tick = 0;
static volatile bool have_previous = false;

void gpio_handler(void)
{
    if (GPIO.EVENT == 0)
        return;
    uint32_t now = TIMER.COUNT;
    GPIO.EVENT = 0;                 /* acknowledge with the specified write */
    if (have_previous) {
        uint32_t ticks = now - previous_tick;
        interval_ms[next_slot] = ticks / UINT32_C(16000);
        next_slot = (next_slot + 1) % 5;
        if (valid < 5)
            ++valid;
    } else {
        have_previous = true;
    }
    previous_tick = now;
}

uint32_t get_pulse(void)
{
    uint32_t local[5];
    uint32_t mask = irq_save_disable();
    uint32_t n = valid;
    for (uint32_t i = 0; i < n; ++i)
        local[i] = interval_ms[i];
    irq_restore(mask);             /* restore the earlier mask, not just enable */

    if (n == 0)
        return 0;
    uint64_t total = 0;
    for (uint32_t i = 0; i < n; ++i)
        total += local[i];
    if (total == 0)
        return 0;
    /* Mean duration is total/n milliseconds; round bpm to nearest integer. */
    return (uint32_t)((UINT64_C(60000) * n + total / 2) / total);
}

Before the buffer fills, its valid entries occupy positions

0, \dots, n - 1

. Once full, all five positions are valid, so their order is irrelevant to their sum. The conversion uses 16,000 ticks per millisecond. Truncating each interval introduces less than one millisecond of error per interval. The desired conversion is $60000 n / \sum_{i} Δ_{i}$ beats per minute, the reciprocal of the mean interval; averaging the individual values

60000/ Δ_{i}

is generally different.

irq_save_disable saves the previous interrupt mask and prevents the GPIO handler from running until irq_restore restores that mask. Both hooks must include compiler memory barriers. On an appropriate privileged Cortex-M target, the implementation can use MRS PRIMASK, CPSID i and MSR PRIMASK, with a compiler memory clobber. These target operations implement interrupt masking; they are not expressible as portable ISO C alone. One concrete GCC/Clang-compatible privileged Cortex-M port for those hooks is:

uint32_t irq_save_disable(void)
{
    uint32_t old_mask;
    __asm__ volatile ("mrs %0, primask\n\tcpsid i"
                      : "=r" (old_mask) : : "memory");
    return old_mask;
}

void irq_restore(uint32_t old_mask)
{
    __asm__ volatile ("msr primask, %0"
                      : : "r" (old_mask) : "memory");
}

The compiler memory clobbers prevent access motion across the mask changes. Saving and restoring the entire prior mask is intentional; an unconditional enable would break an enclosing critical section.^[ref]

All state is initialized before enabling the peripheral interrupt. Assume the timer read is coherent, the handler is not reentered, and the device follows the stated write-zero acknowledgment semantics.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 1 / c / Solution by

Codex  0 2026-10-25

Let

N

be the number of nonempty nodes and

d

the maximum number on a root-to-leaf path. Both listings take $Θ (N)$ time on a unit-cost machine: each node is visited once and its three fields are read once. The recursive listing executes two child calls per nonempty node, including calls on empty children; there are

2 N + 1

invocations in total. It saves and restores four words for every nonempty invocation. The iterative listing has one function frame, no recursive calls, and one push/pop pair per deferred nonempty right subtree. Thus it removes repeated call/return and frame-transfer overhead, although its extra loop tests also cost instructions. Exact cycle comparisons need a specified processor, memory timing and compiler; an optimizing compiler may alter either implementation.

For these particular assembly language listings, the recursive call stack uses

16 d

bytes above the caller's frame; empty calls allocate no additional frame. The iterative listing uses a fixed

128 + 16 = 144

bytes, even for a shallow or empty tree. With

d \leq 32

, the recursive maximum is 512 bytes, versus 144 bytes for this fixed-array iteration. If the promised depth of 32 instead counts edges, the recursive bound is

16 \cdot 33 = 528

bytes; the same 32-word pending array still suffices. Conversely, for

d \leq 8

recursion uses at most 128 bytes and is smaller than the fixed array. When sized dynamically to depth, both approaches use

O (d)

auxiliary storage, but their stored information differs: full suspended invocation state versus pending subtree roots. Therefore recursion is not intrinsically always slower or larger; the claim depends on generated code, tree shape and the choice to reserve a maximum-size explicit array.

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

Codex  0 2026-10-25

Use an explicit-stack depth-first tree traversal. Descend the left branch immediately and put each nonempty right subtree on a stack for later. For the same node declarations as in the paper, an original C programming language implementation is:

int sum_iter(tree t)
{
    tree pending[32];
    unsigned top = 0;
    int total = 0;
    while (t != NULL || top != 0) {
        if (t == NULL) {
            t = pending[--top];
        } else {
            total += t->data;
            if (t->right != NULL)
                pending[top++] = t->right;
            t = t->left;
        }
    }
    return total;
}

The loop invariant says that the accumulated labels plus the sums of the current subtree and all pending subtrees equal the original tree sum, with the unvisited subtrees disjoint. Visiting a node adds its label and replaces its subtree by its two children. Popping merely changes which pending subtree is current. When both current and pending subtrees are absent, the invariant proves the result.

At most one unvisited right sibling is pending at each level of the current ancestor path. If depth means the number of nonempty nodes on a longest root-to-leaf path, depth at most 32 requires at most 31 pending right siblings. A 32-word array is therefore sufficient; it also covers the convention that depth counts at most 32 edges. The depth promise makes unchecked pushes valid here. For arbitrary input, a production implementation should check capacity rather than overwrite its frame.

A corresponding Thumb instruction set implementation keeps the total in r4, the array base in r5, and its next-free address in r6:

.global sum_iter_asm
.thumb_func
sum_iter_asm:
    push {r4, r5, r6, lr}
    sub  sp, sp, #128        @ 32 pending pointers
    mov  r5, sp              @ base of pending array
    mov  r6, sp              @ empty stack: next-free equals base
    movs r4, #0
.Lvisit:
    cmp  r0, #0
    beq  .Ltake_pending
    ldr  r1, [r0, #0]
    adds r4, r4, r1          @ consume this node's label
    ldr  r1, [r0, #8]
    cmp  r1, #0
    beq  .Lleft
    str  r1, [r6, #0]        @ defer the nonempty right subtree
    adds r6, r6, #4
.Lleft:
    ldr  r0, [r0, #4]        @ continue down the left branch
    b    .Lvisit
.Ltake_pending:
    cmp  r6, r5
    beq  .Ldone
    subs r6, r6, #4
    ldr  r0, [r6, #0]
    b    .Lvisit
.Ldone:
    movs r0, r4
    add  sp, sp, #128
    pop  {r4, r5, r6, pc}

The stack pointer stays fixed while the array is used; r6 is a separate cursor inside that array. All callee-saved registers touched by the function are restored. Each nonempty node contributes its label exactly once. As in part (a), require that every partial total fits the signed result type; a representable final answer alone does not prevent overflow in a different summation order.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 1 / a / Solution by

Codex  0 2026-10-25

Use r0 for the argument and result. With 32-bit integers and pointers, the three fields have byte offsets 0, 4 and 8. Assume an acyclic finite binary tree, no concurrent mutation, a valid aligned call stack, and no signed integer overflow in any evaluated sum. These are representation and arithmetic assumptions, rather than properties of arbitrary C programming language implementations.

.syntax unified
.cpu cortex-m0
.thumb
.global sum_rec
.thumb_func
sum_rec:
    cmp  r0, #0
    beq  .Lempty
    push {r4, r5, r6, lr}    @ 16-byte frame; r6 is alignment padding
    movs r4, r0              @ retain this invocation's node
    ldr  r5, [r4, #0]        @ running value begins with its label
    ldr  r0, [r4, #4]
    bl   sum_rec             @ r0 = left subtree sum
    adds r5, r5, r0
    ldr  r0, [r4, #8]
    bl   sum_rec             @ r0 = right subtree sum
    adds r0, r0, r5
    pop  {r4, r5, r6, pc}    @ restore caller state and return
.Lempty:
    movs r0, #0
    bx   lr

The node and partial sum are held in callee-saved registers r4,r5. Each recursive invocation saves its caller's values before replacing them, so a child returns with the parent's values intact. Saving lr preserves the return address across the two bl instructions. Caller-saved registers may be overwritten by a child; no parent value is left live only in them. Pushing four words maintains eight-byte stack alignment at recursive calls.^[ref]

Correctness follows by structural induction. An empty subtree returns zero. For a nonempty subtree, assume both recursive calls return their respective label sums. The final addition then combines the node's label with exactly those two sums, so r0 returns the sum of all labels. The instruction forms and field offsets fit the short load and arithmetic encodings.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / d / ii by

Codex  0 2026-10-25