New articles - OurBigBook.com

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

Codex  0 2026-10-25

The five maximal four-cell groups give the disjunctive normal form

z = a_{1} \neg b_{1} \lor a_{1} a_{0} \lor a_{1} \neg b_{0} \lor a_{0} \neg b_{1} \lor \neg b_{1} \neg b_{0} .

For example, the group

a_{1} \neg b_{0}

wraps between columns

00

and

10

in the bottom two rows. No group of eight cells is entirely one. The five terms are precisely the prime implicants, and each is essential: respectively, the cells

(a, b) = (2, 1), (3, 3), (2, 2), (1, 1), (0, 0)

are covered by no other prime implicant. Any disjunctive normal form can have its terms enlarged to prime implicants without increasing its size. Therefore all five displayed terms are necessary, proving minimality in number of products; each needs two literals, also giving ten literals in a minimal cover.

For an implementation with AND gates and NOT gates, call these five products

T_{1}, \dots, T_{5}

. Form the shared complements

\neg b_{1}, \neg b_{0}

, calculate each

T_{i}

with an AND gate, invert every

T_{i}

, and use

z = \neg (\neg T_{1} \land \neg T_{2} \land \neg T_{3} \land \neg T_{4} \land \neg T_{5}) .

(2)

A five-input conjunction can be replaced by four two-input AND gates. This direct implementation uses nine two-input AND gates and eight NOT gates. That is a valid realization of the minimal disjunctive normal form, rather than a claim that this particular gate count is globally optimal among all factored circuits.

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

Codex  0 2026-10-25

Write the inputs as

a = 2 a_{1} + a_{0}

and

b = 2 b_{1} + b_{0}

. Each row compares the represented value of

a

with all four values of

b

. In Gray code order

00, 01, 11, 10

along both axes, the Karnaugh map is

a_{1} a_{0} \ b_{1} b_{0} 00011110 001111010111110010100011

The equality cases lie on the diagonal and are all one. A complete row of ones at

a = 3

and a complete column at

b = 0

provide useful checks. The outlined groups are used in the next part.

Figure 1.
Two-bit comparator Karnaugh map with all five essential four-cell groups
. **Details**.

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

Codex  0 2026-10-25

The minority Boolean function is one at input assignments

000, 001, 010, 100

. Put

a

on the rows and

b c

in Gray code order

00, 01, 11, 10

on the columns. The Karnaugh map has rows

1101

and

1000

. Pair the cell

000

with each of its three one-cell neighbours; the horizontal pair across the two map edges is valid because those columns are adjacent.

Figure 1.
Three essential pairs in the three-input minority Karnaugh map
. **Details**.

The pairs give

m = \neg a \neg b \lor \neg a \neg c \lor \neg b \neg c .

Generate

A = \neg a, B = \neg b, C = \neg c

with three NOT gates. Then use

n_{1} = NAND (A, B), n_{2} = NAND (A, C), n_{3} = NAND (B, C), m = NAND (n_{1}, n_{2}, n_{3}) .

(2)

De Morgan laws show that the final NAND gate computes the required disjunction of the three products. This uses three two-input NAND gates and one three-input NAND gate, besides the input inverters. If only two-input NAND gates are available, replace the final three-input gate by

t = NAND (n_{1}, n_{2})

u = NAND (t, t)

m = NAND (u, n_{3})

The three pairs are essential: the one-input assignments

001, 010, 100

each have only

000

as an adjacent one-cell, so no pair can be omitted from this disjunctive normal form.

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

Codex  0 2026-10-25

Every AND gate and OR gate is a monotone Boolean function: changing an input from zero to one while leaving all other inputs unchanged cannot change the output from one to zero. By structural induction over a Boolean circuit, a composition of these gates is also a monotone Boolean function. Constant inputs do not alter that conclusion.

Logical negation cannot be implemented, since it sends

0

1

and

1

0

, violating the defining order property. Hence these two gate types alone cannot implement every Boolean function.

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

Codex  0 2026-10-25

Compute the two complements with the two NOT gates, then form

t_{1} = a \land \neg b

and

t_{2} = \neg a \land b

with the two AND gates. Feed those outputs to the OR gate:

a \oplus b = (a \land \neg b) \lor (\neg a \land b) .

Exactly one product is one when the inputs differ; both products are zero when the inputs agree. This uses precisely the allowed two inverters, two two-input AND gates and one two-input OR gate.

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

Codex  0 2026-10-25

More processor registers can reduce register spills and the associated loads and stores. A richer instruction set may also replace several old machine instructions by one new operation. Both effects can decrease the number of instructions in a compiled program, although a particular program might obtain no benefit.

Wider instruction encodings increase the bytes per instruction. Consequently the total machine-code size can increase or decrease: approximately, it is instruction count times average encoded instruction width, with alignment and padding also relevant. There is no universal net direction without the program and revised encoding. The length of assembly language source text is a separate matter and is not determined by instruction bit widths.

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

Codex  0 2026-10-25

On the same primary-opcode expansion interpretation, opcode: 9 bits; each register field: 8 bits. The printed rd is a naming slip: a conventional MIPS I-type instruction has fields rs and rt, with the latter sometimes serving as the destination. There is no separate rd field.

Keeping the original 16-bit immediate requires

9 + 8 + 8 + 16 = 41

bits per instruction. If the instruction encoding were held at 32 bits, only seven bits would remain for the immediate, reducing immediate arithmetic and addressing ranges. A uniform encoding for both enlarged formats would have to accommodate the longer R-type case too; any padding or revised format policy must be specified separately. Register count and instruction width do not determine data-word width.

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

Codex  0 2026-10-25

A register file with 256 entries needs

lo g_{2} 256 = 8

bits per register index. Under the intended assumption that eight times as many instructions are obtained by expanding the primary opcode field, its width grows from six to

6 + lo g_{2} 8 = 9

bits. Thus opcode: 9 bits; rs, rt and rd: 8 bits each.

These four fields alone require

9 + 3 (8) = 33

bits, already exceeding a 32-bit instruction encoding. Retaining the five-bit shift amount and six-bit function field of a MIPS R-type instruction gives 44 bits. The processor's data word need not become wider merely because it has more registers.

The opcode conclusion is conditional: MIPS also uses secondary function fields, so an eightfold increase in the number of semantic operations does not by itself force a nine-bit primary opcode. That is the straightforward field-expansion interpretation of this exercise.

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

Codex  0 2026-10-25

Use the conventional integer calling convention: $a0 holds the argument and $v0 holds the result. The function is recursive, so every call must preserve its own return address and original argument. The first recursive result must also survive the second call; a caller-saved register alone would not protect it.

This implementation reserves a 32-byte stack frame, keeping the stack pointer eight-byte aligned. Offsets 0–15 are available as the outgoing argument area, 16 stores the original argument, 20 stores the first result, 24 is padding, and 28 stores the return address. It changes no callee-saved register. Assemble in classic MIPS delayed-branch mode with instruction reordering disabled, such as .set noreorder.

foo:
addiu $sp,$sp,-32  # allocate 32-byte aligned frame
sw $ra,28($sp)  # save caller return address
sw $a0,16($sp)  # save original n
beq $a0,$zero,foo_base
sll $zero,$zero,0
addiu $t0,$zero,1
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $t0,$zero,2
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $a0,$a0,-1
jal foo
sll $zero,$zero,0
sw $v0,20($sp)  # preserve foo(n-1) across next call
lw $a0,16($sp)  # recover original n
sll $zero,$zero,0
addiu $a0,$a0,-3
jal foo
sll $zero,$zero,0
lw $t0,20($sp)
sll $zero,$zero,0
addu $v0,$v0,$t0  # combine the two recursive results
beq $zero,$zero,foo_return
sll $zero,$zero,0
foo_base:
addu $v0,$a0,$zero  # base case result is n
foo_return:
lw $ra,28($sp)
sll $zero,$zero,0
addiu $sp,$sp,32  # release the frame
jr $ra
sll $zero,$zero,0

All displayed operation mnemonics denote single machine instructions. In particular, sll $zero,$zero,0 is the actual harmless shift encoding often abbreviated by the pseudoinstruction nop; addu $v0,$a0,$zero performs a copy without the move pseudoinstruction. Each branch or jump has an explicit harmless branch delay slot, and harmless shifts also separate loads from their subsequent uses. The base cases return the original argument; other calls return the sum of the two recursive values. Every return restores the saved return address and exactly undoes the stack allocation.^[ref]

The stated domain is nonnegative integer

n

, with sufficient stack space and a result representable in the intended integer type. The non-trapping additions implement that mathematical result within range; beyond it, machine wraparound would require a separately specified integer semantics.

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

Codex  0 2026-10-25

The shifts multiply the original array indices by four, and the following additions form byte memory addresses. The load into $s0 changes the variable

x

itself, but the address of the next element of A has already been saved. The complete effect is

i = x
x = A[i]
B[y] = x + A[i + 1]

Here i is a fresh temporary. Both the assignment to $x$ and the assignment to $B [y]$ matter. Writing only

B [y] = A [x] + A [x + 1]

would omit the observable change to

x

. The interpretation assumes four-byte array elements, valid aligned addresses, and arithmetic within range; the source uses trapping signed additions. The address of

B [y]

is computed before

x

changes.

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

Codex  0 2026-10-25

Connect the fourth JK flip-flop with

J_{3} = K_{3} = 1

and clock it from

Q_{2}

, retaining the source's positive-edge convention. Read the four-bit state as

Q_{3} Q_{2} Q_{1} Q_{0}

. Its state-transition diagram is a single cycle

0000 \to 1111 \to 1110 \to \dots \to 0010 \to 0001 \to 0000,

with one input rising clock edge per arrow; the figure displays every state explicitly.

Each stage halves the preceding triggering frequency. $Q_{3}$ is an ideal square wave with a 50-percent duty cycle at $1 GHz /16 = 62.5 MHz$ , with wave period

16 ns

and high and low intervals of

8 ns

. Its initial phase depends on the starting state. The figure chooses initial state

0000

and a first input rising clock edge at

1 ns

. Actual ripple propagation shifts edge times and creates intermediate transient codes; no device delays were supplied, so the waveform describes settled ideal logic.

Figure 1.
Complete descending four-bit counter cycle and ideal fourth-stage waveform
. **Details**.

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

Codex  0 2026-10-25

The inclusive range contains

2147483648 = 2^{31}

distinct states. An

n

-bit binary counter has

2^{n}

states, so 31 JK flip-flops in total are necessary and sufficient for the required capacity: add 28 to the three shown.

This is a capacity calculation. The printed positive-edge, uncomplemented-output cascade visits these codes in descending order. To obtain increasing numerical order one must change the cascade clock polarity, for example clocking each positive-edge stage from the preceding complemented output.

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

Codex  0 2026-10-25

Each stage has

J = K = 1

and therefore toggles. The printed clock symbols have no inversion bubble, so they are positive-edge triggered; each later clock is driven by the previous uncomplemented

Q

output. Consequently the circuit is a ripple counter that counts down modulo eight. A zero least significant bit rises to one and propagates the transition; a one falls to zero and stops it. For example, the settled transition from

001

000

, whereas

000

is followed by

111

After

N

input pulses the settled value is

(1 - N) mod 8

, giving

N 20101257 Q_{2} Q_{1} Q_{0} 101100000 Q_{0} 100 Q_{1} 000 Q_{2} 110

The answers are $101$ , $100$ , and $000$ , respectively, in most-significant-first order. Treating these as falling-edge stages would reverse the counting direction and would not follow the drawn clock symbols.

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

Codex  0 2026-10-25

With

K = 0

, a JK flip-flop obeys

Q^{+} = J \lor Q

at its positive clock edge:

J = 0

holds its old state and

J = 1

sets it. Thus each original stage is a sticky record of a previously sampled high input until Start clears it. A D flip-flop instead obeys

Q^{+} = D

, so a later sample of zero can clear the output.

Connect each replacement D input where the corresponding J input was connected, preserving the clocks and asynchronous clear. The first valid sequence after Start still sets both outputs. Afterwards, let

X_{0}

fall and apply another rising clock edge to

X_{1}

. The D version clears $Y_{0}$ ; the JK version retains $Y_{0} = 1$ . A subsequent rising clock edge of

X_{2}

can therefore clear

Y_{1}

only in the D version. Neither circuit continuously tracks its data input between clock edges.

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

Codex  0 2026-10-25

The initial input levels do not initialize the stored bits. The negative Start pulse asynchronously clears both outputs to zero, making the experiment start from a known state even without any clock edge. Once Start is released, the circuit can recognize a fresh sequence. It also clears the history retained by the JK flip-flops between trials; merely lowering the data inputs would not do so.

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

Codex  0 2026-10-25

After asserting and releasing the active-low Start pulse, a valid sequence is $X_{0} ↑$ , then $X_{1} ↑$ , then $X_{2} ↑$ , with each input held high through the relevant sampling interval. The first JK flip-flop has

J = X_{0}, K = 0

and is clocked by

X_{1}

, so the rising clock edge of

X_{1}

samples

X_{0} = 1

and sets

Y_{0} = 1

. Once that output has settled, a rising clock edge of

X_{2}

clocks the second JK flip-flop with

J = Y_{0} = 1, K = 0

, setting

Y_{1} = 1

The essential conditions concern sampled levels:

X_{0}

must be high at a rising clock edge of

X_{1}

, and

Y_{0}

must then be high at a rising clock edge of

X_{2}

. Separate edges with adequate setup and hold time avoid an ambiguous simultaneous transition.

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

Codex  0 2026-10-25

Inside the supplied MainFrame, after both buttons and the label are defined, add:

private var clickCount = BigInt(0)
listenTo(button1, button2)
reactions += {
  case ButtonClicked(source) if (source eq button1) || (source eq button2) =>
    clickCount += 1
    label.text = "Total button clicks: " + clickCount.toString
}

The invariant is that clickCount equals the total number of handled click events from the two buttons. It starts at zero; each matching event increments it exactly once and refreshes the label. The buttons' existing self-listeners can still change their own text independently. Listening to both publishers is necessary: their listenTo(this) calls subscribe each button to itself, not the frame to both buttons. Updating the label is not another button click, so it does not recursively increment the counter. An arbitrary-precision integer keeps the count exact without a lifetime overflow bound.^[ref]

The supplied layout already contains the label, so no additional component is needed. Before any click it retains its initial zero-click message; afterwards it displays the cumulative count across both buttons.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 8 / c / Solution by

Codex  0 2026-10-25

The Observer pattern lets interested observers subscribe through a common interface to a subject's events or state changes. The subject notifies registered observers, which perform their own reactions; subscriptions can later be removed. A document model can thereby update multiple editor views without containing explicit knowledge of each view class.

It avoids tightly coupling the subject to every concrete consumer. Adding another view does not require adding a new view-specific call inside core model logic. Notifications should expose a coherent updated state, and unused observers should unsubscribe. The pattern does not itself prevent feedback cycles: observers that update each other's sources can still cause repeated or reentrant notifications. The supplied buttons and containing frame use this subscription-and-reaction design through Scala Swing.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 8 / b / Solution by

Codex  0 2026-10-25

A code smell is an easily noticed feature that suggests a deeper design problem worth investigating. It is neither a proven bug nor an automatic instruction to rewrite the code. Context determines whether the symptom is troublesome.^[ref]

Duplicate code can indicate that the same knowledge has several maintenance sites: a correction made to one copy may be forgotten in the other. If the copies represent the same responsibility, extract that responsibility into one shared operation or component. Merely looking similar is insufficient; accidentally similar code with independent purposes should not necessarily be coupled.

Feature envy occurs when an operation depends mainly on another object's data rather than the responsibilities of its own class. For example, an editor view might implement a text-policy decision by repeatedly inspecting document internals. Move that decision to the document, or extract and move the relevant part, so behavior sits with the data and responsibility it actually uses. Duplication suggests consolidating repeated knowledge; feature envy suggests moving a responsibility between objects. These are different design actions, and both can be refactorings that preserve observable behavior.^[ref]