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 / 4 / f / Solution by

Codex  0 2026-10-25

The

n

independent eigenvectors

v_{1}, \dots, v_{n}

B

from part (e) are also eigenvectors of

A

. Put

S = (v_{1} \dots v_{n})

and

P = S^{- 1}

. Then

P A P^{- 1} = diag (μ_{1}, \dots, μ_{n}), PB P^{- 1} = diag (λ_{1}, \dots, λ_{n}) .

This supplies the required simultaneous diagonalization over the same field as in part (e).

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 / 4 / e / Solution by

Codex  0 2026-10-25

Work over the field containing the stated

n

distinct eigenvalues of

B

; in a real formulation these must be real to obtain real eigenvectors. Choose one eigenvector for each distinct eigenvalue. By independence of eigenvectors for distinct eigenvalues, these

n

vectors are a basis. Consequently each eigenspace

E_{λ} (B)

has dimension one: in an expansion in this eigenbasis,

Bw = λ w

forces every coefficient with a different eigenvalue to vanish.

Now let

v \neq = 0

be any eigenvector of

B

. By part (d),

A v

belongs to its one-dimensional eigenspace, so

A v = μv

for some scalar

μ

. This proves that $v$ is an eigenvector of $A$ , including the case

A v = 0

, where

μ = 0

. This is the crucial one-dimensional step in simple spectrum gives simultaneous diagonalization.

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 / 4 / d / Solution by

Codex  0 2026-10-25

Using

B A = A B

and linearity,

B (A v) = A (B v) = A (λ v) = λ A v .

This establishes that commuting maps preserve eigenspaces. The vector

A v

can be zero, so this step alone does not assert that

A v

is 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 / 4 / c / Solution by

Codex  0 2026-10-25

With the two diagonal matrices from the preceding part, write

D_{A} = P A P^{- 1}

and

D_{B} = PB P^{- 1}

. Their diagonal products agree entry by entry, so

D_{A} D_{B} = D_{B} D_{A}

. Therefore

A B = P^{- 1} D_{A} D_{B} P = P^{- 1} D_{B} D_{A} P = B A .

Hence simultaneous diagonalization implies that

A, B

are commuting operators.

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 / 4 / b / Solution by

Codex  0 2026-10-25

Let

P A P^{- 1} = diag (α_{1}, \dots, α_{n})

and

PB P^{- 1} = diag (β_{1}, \dots, β_{n})

. Then

P (A + B) P^{- 1} = diag (α_{1} + β_{1}, \dots, α_{n} + β_{n}) .

By matrix similarity, every eigenvalue of $A + B$ is $α_{i} + β_{i}$ for some $i$ . These are corresponding eigenvalues on the common eigenbasis, rather than every possible pairwise sum. This is eigenvalue addition in a common eigenbasis.

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 / 4 / a / Solution by

Codex  0 2026-10-25

Write

A = diag (λ_{1}, \dots, λ_{n})

and

v_{i} = P^{- 1} e_{i}

, where

e_{i}

are the standard basis vectors. Since

A P^{- 1} = P^{- 1} A

A v_{i} = P^{- 1} A e_{i} = λ_{i} v_{i} .

Thus the columns of $P^{- 1}$ form an eigenbasis, and the requested ordered basis is

D = (P^{- 1} e_{1}, \dots, P^{- 1} e_{n})

. Its basis matrix is

P^{- 1}

, giving

[t]_{D} = P A P^{- 1} = A

. More completely, for each distinct eigenvalue

λ

, its eigenspace is

E_{λ} (A) = span {P^{- 1} e_{i} : λ_{i} = λ} .

(2)

All nonzero vectors in these eigenspaces are eigenvectors; when an eigenvalue repeats, they need not be individual columns of

P^{- 1}

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 / 3 / d / Solution by

Codex  0 2026-10-25

In a cooperative scheduler, a permanently runnable background operating-system process that never yields can monopolize the CPU. The timer service, smoothing operating-system process, and display may then fail to run even when their messages are ready. Correct message passing alone does not supply process scheduling.

Use timer-driven scheduling preemption, so an interrupt can force a context switch without cooperation. To give the measurement and display work bounded response despite background computation, use priority scheduling with the background operating-system process below the responsive services, or an explicit reservation policy. Round-robin scheduling gives CPU access among a fixed finite runnable set, but meeting a particular deadline additionally requires bounded service execution and sufficient CPU capacity.

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 / 3 / c / Solution by

Codex  0 2026-10-25

With a synchronous reply, send(client,&answer) blocks until the client receives. An indefinitely unready client therefore stalls the smoothing operating-system process, which may in turn stall the timer service and its other clients as in the preceding part. If the client is merely delayed, this is blocking and delayed service; a deadlock requires a circular wait or a client that will never receive.

Requiring correctly used synchronous send-and-receive helps. A client calling sendrec(SMOOTH,&m) is committed to waiting for the matching reply as soon as its request has been accepted. This closes the scheduling window between a separate send and receive and prevents unrelated client computation from postponing that receive. It does not by itself fix slow measurements, arbitrary failures, circular dependencies between other services, or lack of CPU scheduling. With buffered replies the initial effect may instead be queue growth, depending on the message passing contract.

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 / 3 / b / Solution by

Codex  0 2026-10-25

With synchronous message passing, the smoothing operating-system process can still be waiting for TEMP when its next PING is due. If the timer service sends to subscribers serially, it blocks on this unready recipient and cannot deliver the other subscribers' ticks: one slow sensor can delay every timer client through head-of-line blocking. Once it resumes, implementations may deliver late ticks, drift from their schedule, or accumulate overdue work.

The consequence depends on the delivery model. With buffered sends the timer need not block immediately, but its queue can grow or overflow; the smoothing operating-system process still cannot process readings at a sustained rate faster than the sensor. A nonblocking notification mechanism or separate timer-delivery workers can isolate other subscribers, while coalescing missed ticks prevents an unlimited backlog. These changes do not make an over-slow sensor meet the original sampling rate.

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 / 3 / a / Solution by

Codex  0 2026-10-25

Maintain the latest five temperature readings in a circular buffer, together with their running sum. The following C programming language code spells out the message passing interface rather than assuming a particular library: send(dst,&m) is a blocking synchronous message passing send; receive(src,&m) receives from the specified sender or ANY and returns the sender's identity; sendrec(dst,&m) atomically sends the request and waits for that sender's reply in the same message object. Successful, reliable operations are assumed. Message contents are copied by the interface.

enum { ANY = -1, TIMER = 1, TEMP = 2 };
enum { PULSE, PING, REQUEST, REPLY };
typedef struct {
    int type;
    int period_ms;
    double value;
} Message;

extern void send(int dst, const Message *m);
extern int receive(int src, Message *m);
extern void sendrec(int dst, Message *m);

void smooth(void) {
    double history[5] = {0};
    double sum = 0;
    int count = 0, next = 0;
    Message m = { .type = PULSE, .period_ms = 1000 };
    send(TIMER, &m);                 /* subscribe once */

    for (;;) {
        int sender = receive(count < 5 ? TIMER : ANY, &m);
        if (sender == TIMER && m.type == PING) {
            Message t = { .type = REQUEST };
            sendrec(TEMP, &t);       /* matching REPLY contains t.value */
            if (count == 5)
                sum -= history[next];
            else
                ++count;
            history[next] = t.value;
            sum += t.value;
            next = (next + 1) % 5;
        } else if (count == 5 && m.type == REQUEST) {
            Message answer = { .type = REPLY, .value = sum / 5.0 };
            send(sender, &answer);
        }
    }
}

Before the fifth reading, selective reception from TIMER prevents premature client requests from being accepted. Such clients wait at their synchronous sends; they are not given a partial arithmetic mean. Thereafter the operating-system process receives both timer messages and client requests. Each accepted PING initiates one measurement; each accepted client request returns the arithmetic mean of the five most recently completed measurements, without initiating another measurement or changing the circular buffer.

The loop invariant is that count is the number of valid readings, capped at five, sum is their sum, and next is the next unused slot during startup or the oldest slot afterwards. Removing the overwritten reading and adding the new one preserves this loop invariant. Each update and reply uses

O (1)

time complexity and

O (1)

storage, since the window length is fixed. Under timely sensor replies, timer delivery and process scheduling, measurements are initiated once per second. The next parts explain failures of these timing assumptions; the code does not promise one-second sampling when the sensor itself cannot sustain it.

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 / 2 / c / Solution by

Codex  0 2026-10-25

Keep total in the callee-saved register r4, and the first returned sum in the callee-saved register r5. Suppose the surrounding function has made an aligned stack frame with the local seven-halfword array at the current sp, occupying fourteen bytes in a sixteen-byte slot. One possible frame setup is push {r4,r5,r6,lr} followed by sub sp,sp,#16; the earlier code initializes total, regular, and special before this fragment.

    ldr  r0, =regular       @ assembler literal load of the global array address
    movs r1, #7
    bl   sum16
    movs r5, r0             @ first sum must survive the next call

    add  r0, sp, #0         @ current frame's local special array
    movs r1, #7
    bl   sum16
    muls r0, r5, r0         @ second sum times first sum
    adds r4, r4, r0         @ update total

The AAPCS32 permits each call to overwrite r0–r3, r12, and condition flags, but requires preservation of r4–r8, r10, r11, and sp. Thus both r4 and r5 remain valid even if sum16 is replaced by another conforming implementation. bl changes the link processor register lr, so the enclosing function saves its own return address in its prologue. Its epilogue can use add sp,sp,#16 and pop {r4,r5,r6,pc}. The frame uses thirty-two bytes in total, preserving the required eight-byte stack pointer alignment at both calls.^[ref]

The two calls may be evaluated in this order. Assume the product and final addition fit the signed 32-bit result expected by the source program; unlike each individual seven-element sum, their product need not fit. The assembly language operations retain their low 32 bits if this assumption fails, whereas signed integer overflow in the C programming language has different 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 / 2 / b / Solution by

Codex  0 2026-10-25

Let the stored bits be

b_{15}, \dots, b_{0}

and let

s = b_{15}

. The sign extension performed by ldrsh keeps output bit

i

equal to

b_{i}

for

0 \leq i \leq 15

, and sets every output bit

16 \leq i \leq 31

s

. Thus a nonnegative halfword gets sixteen leading zero bits, while a negative halfword gets sixteen leading one bits.

Its signed 32-bit two's complement value is

- s 2^{31} + s \sum_{i = 16}^{30} 2^{i} + \sum_{i = 0}^{15} b_{i} 2^{i} = - s 2^{16} + s 2^{15} + \sum_{i = 0}^{14} b_{i} 2^{i} = - s 2^{15} + i = 0 \sum 14 b_{i} 2^{i} .

The last expression is exactly the original signed 16-bit value. The equality uses the finite geometric series

\sum_{i = 16}^{30} 2^{i} = 2^{31} - 2^{16}

. In particular, simply inserting zero bits would be wrong for a negative halfword: its unsigned interpretation differs from its signed value by

2^{16}

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 / 2 / a / Solution by

Codex  0 2026-10-25

Use the AAPCS32 convention: r0 holds the input address, r1 the length, and r0 receives the result. The following Thumb instruction set assembly language uses only scratch processor registers, so no callee-saved registers need saving. Assume the array is valid, halfword-aligned, and has nonnegative length; for the mathematical sum assume it fits a signed 32-bit two's complement integer.

.syntax unified
.thumb
.thumb_func
sum16:
    movs r2, #0             @ accumulated sum
    cmp  r1, #0
    ble  .Ldone             @ empty array; also returns 0 if n < 0
.Lloop:
    movs r3, #0             @ Thumb signed load needs a register offset
    ldrsh r3, [r0, r3]      @ signed halfword at a; offset read before r3 changes
    adds r2, r2, r3         @ include this signed value
    adds r0, r0, #2         @ advance by one short, not one byte
    subs r1, r1, #1         @ one fewer element remains
    bne  .Lloop
.Ldone:
    movs r0, r2             @ result register
    bx   lr                 @ leaf routine: lr was not overwritten

After

j

iterations, the loop invariant is that r2 contains the first

j

elements' sum, r0 points to element

j

, and r1 is

n - j

. The sign extension in ldrsh supplies the correct signed addend. One iteration preserves this loop invariant, and the decreasing remaining length proves algorithm termination. For the seven-element calls, the sum lies between

- 229376

and

229369

, so it fits. For longer arrays that overflow, these instructions compute the sum modulo

2^{32}

; that is not a claim about defined signed C programming language overflow behavior. The operand forms are those of the paper's reference sheet.^[ref]

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 / 1 / d / Solution by

Codex  0 2026-10-25

Use a hierarchical leading-zero counter. A block of

2^{j}

bits returns a zero flag

z

and

j

low count bits

r

: its count leading zeros result is the concatenation

(z, r)

. Thus

z = 1

means that the block is entirely zero and

r = 0

; otherwise

z = 0

and

r

is its leading-zero count. A one-bit block needs just

z = \neg x

and no low count bits.

For a block of

n = 2^{k}

bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as

z_{H}, z_{L}

and their

k - 1

low count bits as

h_{i}, ℓ_{i}

. Set

z = z_{H} \land z_{L}, r_{k - 1} = z_{H} \land \neg z_{L}, r_{i} = (\neg z_{H} \land h_{i}) \lor (z_{H} \land ℓ_{i}) (0 \leq i < k - 1) .

The last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and

r_{k - 1} = 0

. When only the upper half is zero,

r_{k - 1} = 1

supplies the contribution

n /2

while the multiplexers supply the lower half's count. When both halves are zero, the answer is

(1, 0, \dots, 0)

, representing

n

. This special encoding avoids an adder on the critical path.

Each node adds constant circuit depth, even though it uses

O (k)

logic gates for its parallel multiplexers. Hence

D (2^{k}) = D (2^{k - 1}) + O (1) = O (k), S (2^{k}) = 2 S (2^{k - 1}) + O (k) = O (2^{k}) .

(2)

Indeed the internal-node work is bounded by a constant times

\sum_{j = 1}^{k} (n / 2^{j}) j < 2 n

, and the

n

leaves add

O (n)

. Delay is $O (lo g n)$ and size is $O (n)$ , counting fixed-fan-in logic gates and the usual wire fan-out model.

Figure 1.
Leading-zero summaries combine in parallel: the input $00000101$ gives the four-bit count $0101$
. Internal nodes display their block length and encoded leading-zero count; leaves display the one-bit count. A count's first bit is the shared all-zero flag. The highlighted branch supplies the low count at the root. **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 / 1 / c / Solution by

Codex  0 2026-10-25

Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two

n

, the circuit size and circuit depth satisfy

S (n) = 2 S (n /2) + O (1), D (n) = D (n /2) + O (1) .

There are

n

leaves and

n - 1

internal nodes, so the circuit size is $O (n)$ and the combinational delay is $O (lo g n)$ . Here each fixed-fan-in logic gate has bounded delay. For arbitrary

n

, pad both inputs with leading zero bits to the next power of two, which is less than

2 n

; this preserves their unsigned interpretation and both bounds.

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 / 1 / b / Solution by

Codex  0 2026-10-25

Split each input into its more and less significant

n

-bit halves:

a = 2^{n} a_{H} + a_{L}

and

b = 2^{n} b_{H} + b_{L}

. Let the two digital comparators produce

(L_{H}, G_{H})

and

(L_{L}, G_{L})

. The more significant halves are equal exactly when

E_{H} = \neg (L_{H} \lor G_{H})

. The comparator composition is therefore

L = L_{H} \lor (E_{H} \land L_{L}), G = G_{H} \lor (E_{H} \land G_{L}) .

Implement

E_{H}

with a logical disjunction followed by a negation, then use two AND gates and two more logical disjunction logic gates. If

a_{H} \neq = b_{H}

, the difference

2^{n} (a_{H} - b_{H})

has magnitude at least

2^{n}

, whereas

∣ a_{L} - b_{L} ∣ \leq 2^{n} - 1

; hence the more significant comparison decides the result. If

a_{H} = b_{H}

, the lower comparison decides it. This proves correctness in every case using a constant number of extra logic gates.

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 / 1 / a / Solution by

Codex  0 2026-10-25

For bits

a, b

, use two negation logic gates and two AND gates:

L = (\neg a) \land b, G = a \land (\neg b) .

The two unequal bit pairs activate their respective output; the equal pairs activate neither. In particular, a digital comparator never produces

L = G = 1

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 / 8 / e / Solution by

Codex  0 2026-10-25

First negate the implication, then move the negation through the existential quantifier and the logical conjunction:

\neg φ \equiv (\forall x P (x)) \land \neg\exists y (Q (y) \land z < y) \equiv (\forall x P (x)) \land \forall y (\neg Q (y) \lor \neg (z < y)) .

This is negation normal form, because each negation is immediately in front of an atomic predicate. The occurrence of

z

remains free. Keeping

\neg (z < y)

also avoids assuming any additional order axioms for the relation symbol

<

; if it has its usual linear-order interpretation, that atom can instead be expressed as

z \geq y