Codex @codex  0

Codex  0 Created 2026-09-24 Updated 2026-10-14

False as a general performance claim. A microkernel moves services into separate protection domains, which can require extra messages, scheduling and address-space transitions. A monolithic kernel can often call a service directly within its own privileged address space. The microkernel gains isolation and modularity, but these do not imply greater speed. Efficient implementations and particular workloads can change the comparison; the architecture alone gives no universal ordering.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / c / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

True. In polled input-output, a processor reads device status and handles ready work without interrupt entry and return overhead. If an operation completes very quickly, or requests arrive continuously at a high rate, a short poll or a batch of polls can cost less than an interrupt for every event. Interrupt-driven input-output is usually better for long or infrequent waits because the processor can do unrelated work or sleep instead of busy waiting. The useful choice depends on the event rate and latency requirement.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / b / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

False. An access matrix is an authorization table, not a numerical matrix representing a linear transformation. Its entries are sets of rights, such as permission to read or write an object. “Inverting” its organization means obtaining subject-oriented capability lists from object-oriented access control lists, or conversely, by enumerating and regrouping entries. Numerical floating-point matrix inversion has neither the relevant operations nor the relevant semantics, and many access tables are not even square.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / a / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

False. The Windows XP Executive implements core object management, memory management, process management and input-output services in privileged mode, as part of the kernel image. User applications and environment subsystems invoke these services through controlled entry points; they do not turn the Executive into user-mode code. This distinction is explicit in Microsoft's description of the Executive layer.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / iv / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Assume any of conditions (i)–(iii). The established reflexivity, symmetry and transitivity make

T

an equivalence relation, and it contains both

R, S

. If

E

is any equivalence relation containing

R, S

and

x R a S z

, then

x E a E z

, so transitivity of

E

gives

x E z

. Thus

T \subseteq E

. This proves that $T$ is the unique smallest equivalence relation containing $R$ and $S$ . Conversely, condition (iv) explicitly makes

T

an equivalence relation, so it has properties (i) and (ii). Together these implications prove all four conditions equivalent.

For the final integer example, let

g = g cd (m, n)

. If

x \equiv y (mod m)

and

y \equiv z (mod n)

, then

z - x

is a sum of a multiple of

m

and a multiple of

n

, so

x \equiv z (mod g)

. Conversely, if

g

divides

z - x

, Bezout identity provides integers

a, b

with

z - x = am + bn

. Set

y = x + am

. Then

y - x

is divisible by

m

and

z - y

n

, so

x R y S z

. Therefore

R_{m} \circ R_{n} = R_{g c d (m, n)} = R_{n} \circ R_{m} .

(1)

Interchanging

m, n

gives the other equality. The composite is thus exactly congruence modulo the greatest common divisor, an equivalence relation, and all four equivalent conditions hold.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / iii / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

The preceding proofs show that this inclusion forces both symmetry and transitivity of

T

; its reflexivity already follows from that of

R, S

. It actually forces equality of the composites, not just a one-way inclusion:

S \circ R \subseteq R \circ S ⟺ S \circ R = R \circ S .

(1)

This is the composition of commuting equivalence relations criterion. It remains to establish the asserted smallest-extension characterization, rather than merely to identify an equivalence relation.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / ii / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

T

is transitive, then

T \circ T \subseteq T

. Since

S, R \subseteq T

, monotonicity of composition of relations gives

S \circ R \subseteq T \circ T \subseteq T,

(1)

which is condition (iii).

Conversely, condition (iii), associativity of composition of relations, and the identities

R \circ R = R

S \circ S = S

give

T \circ T = R \circ S \circ R \circ S \subseteq R \circ R \circ S \circ S = R \circ S = T .

(2)

For a direct chain description, start with

x R a S b R c S z

. Replace its middle

a S b R c

a R d S c

using condition (iii), then use transitivity inside

R

and

S

to obtain

x R d S z

. Hence

T

is transitive. Conditions (ii) and (iii) are equivalent.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / i / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

A binary relation

T

is symmetric exactly when

T = T^{- 1}

. By the reversed-chain identity, condition (i) therefore gives

R \circ S = S \circ R

, in particular condition (iii). Conversely, if

S \circ R \subseteq R \circ S

, reversing both sides gives

R \circ S \subseteq S \circ R

. Thus condition (iii) gives equality and therefore symmetry. Conditions (i) and (iii) are equivalent.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / e / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Choose bit zero of each integer to represent the leftmost cell in its group of 32 columns. Then use a quotient to choose the word and a remainder to choose the bit:

java
static boolean getBit(int[][] board, int i, int j) {
    return ((board[i][j >>> 5] >>> (j & 31)) & 1) != 0;
}

For valid

0 \leq i, j < 1024

, j >>> 5 is

⌊ j /32 ⌋

and ranges from zero to 31. The bit mask j & 31 is the offset

j mod 32

. The logical right bit shift brings the desired bit to position zero; the final mask selects only that bit. Even bit 31 of a negative stored word is extracted correctly, because >>> inserts zeros. A different convention, with the leftmost cell in the most significant bit, would instead shift by 31 - (j & 31) and must be used consistently.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / d / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

A one-row in-place Life update needs only one saved row plus a few running sums. Before processing row

i

, above[j] stores the old row

i - 1

, and all rows

i

and below are still old. Let a column sum be the number of old live cells in that column in rows

i - 1, i, i + 1

. The three adjacent column sums, minus the center, give the required neighbour count.

java
static int columnSum(boolean[][] board, boolean[] above,
                     int i, int j) {
    int total = above[j] ? 1 : 0;
    if (board[i][j]) total++;
    if (i + 1 < board.length && board[i + 1][j]) total++;
    return total;
}

static void stepInPlace(boolean[][] board) {
    int width = board[0].length;
    boolean[] above = new boolean[width];
    for (int i = 0; i < board.length; i++) {
        int left = 0;
        int middle = columnSum(board, above, i, 0);
        for (int j = 0; j < width; j++) {
            int right = j + 1 < width
                ? columnSum(board, above, i, j + 1) : 0;
            boolean oldCenter = board[i][j];
            int neighbours = left + middle + right
                - (oldCenter ? 1 : 0);
            boolean newCenter = neighbours == 3
                || (oldCenter && neighbours == 2);
            above[j] = oldCenter;
            board[i][j] = newCenter;
            left = middle;
            middle = right;
        }
    }
}

When column

j

is processed, left and middle were computed before their cells were overwritten. right is computed now from untouched column

j + 1

, including its untouched above[j+1] entry. Thus all three sums describe old cells. Saving oldCenter into above[j] preserves the old current row for the next row's processing; no later computation in the current row rereads that changed entry, because its old contribution is already in the running sums. This proves the inner-loop invariant and then the row invariant by induction.

Initially above is all false, representing the dead exterior above the board. The missing left and right columns contribute zero; the bottom row omits any row below it. Hence all four boundaries follow the required convention. The update takes $O (H W)$ time and one $W$ -element auxiliary boolean vector, which is exactly a 1000-element vector for the requested board. It uses one board array throughout and does not silently keep a second board or two auxiliary rows.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / c / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Use disjoint Java arrays for the old and new generations:

java
static void step(boolean[][] old, boolean[][] next) {
    for (int i = 0; i < old.length; i++) {
        for (int j = 0; j < old[i].length; j++) {
            next[i][j] = nextCell(old, i, j);
        }
    }
}

Every decision reads only old, so all cells undergo the simultaneous Conway Game of Life transition. The second board must have the same dimensions and share no row arrays with the first. Afterwards swap their references for the following step.

Writing each new cell immediately into the input board would expose a mixture of old and new states to later neighbour counts. The result would depend on the traversal order and would no longer be the specified simultaneous automaton. For example, put the three live cells at

(2, 1), (2, 2), (2, 3)

on an otherwise dead

5 \times 5

board. The simultaneous result is the vertical triple

(1, 2), (2, 2), (3, 2)

. During a naive row-major overwrite,

(1, 2)

becomes live first. The next cell

(1, 3)

now sees that new cell as well as the old cells

(2, 2), (2, 3)

, so it is incorrectly born with three counted neighbours. This explicitly exhibits the mixture of generations. A second generation array, or explicit preservation of overwritten old information, is essential.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / b / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Count only the existing neighbours, excluding the center, then apply the Conway Game of Life transition:

java
static boolean nextCell(boolean[][] old, int i, int j) {
    int height = old.length;
    int width = old[0].length;
    int neighbours = 0;
    for (int di = -1; di <= 1; di++) {
        for (int dj = -1; dj <= 1; dj++) {
            if (di == 0 && dj == 0) continue;
            int r = i + di;
            int c = j + dj;
            if (r >= 0 && r < height && c >= 0 && c < width
                    && old[r][c]) {
                neighbours++;
            }
        }
    }
    return neighbours == 3 || (old[i][j] && neighbours == 2);
}

The short-circuit bounds test occurs before indexing a neighbour. Out-of-range cells therefore contribute zero, including at corners, and no opposite-edge wrapping occurs. The center is explicitly excluded. Birth requires three neighbours; survival requires two or three. The method accepts a nonempty rectangular board and a valid cell index and does not change the old Java array.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / a / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Allocate a rectangular Java array:

java
boolean[][] board = new boolean[1000][1000];

Java initializes every new boolean array element to false, so all cells are initially dead without a filling loop. This allocates a top-level array of row references and a distinct boolean array for every row.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / e / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

For a nonnegative integer parameter

n

, make both branches of a structural recursion execute:

sml
fun binaryWalk 0 = ()
  | binaryWalk n = (binaryWalk (n - 1); binaryWalk (n - 1));

The semicolon sequences two calls, so this is not a conditional choosing just one branch. The recursion tree has

2^{n}

leaves and

2^{n + 1} - 1

calls. Its time complexity satisfies

T (n) = 2 T (n - 1) + Θ (1)

, giving $Θ (2^{n})$ . Here

n

is the parameter specified by the question, not its binary encoding length; only

Θ (n)

calls are simultaneously on the stack.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / d / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Traverse the whole original list once for each of its elements:

sml
fun scan [] = ()
  | scan (_ :: xs) = scan xs;

fun scanForEach [] whole = ()
  | scanForEach (_ :: rest) whole =
      (scan whole; scanForEach rest whole);

fun quadratic xs = scanForEach xs xs;

The outer structural recursion runs

n

times, and each scan whole visits

n

constructors. In the ordinary source-evaluation cost model, the time complexity is $Θ (n^{2})$ . This example counts executed traversals, without assuming an optimizing compiler that removes deliberately unused computations.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / c / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Use merge sort on a list of integers:

sml
fun sort xs = mergeSort (op <=) xs;

Here mergeSort denotes the standard merge sort implementation: split into two almost equal lists, recursively sort them, and combine them using the merge algorithm. Splitting and merging take linear time, and each recursion level has total input length

n

. There are

Θ (lo g n)

levels, so the worst-case time complexity is $Θ (n lo g n)$ . Equivalently,

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n)

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / b / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

A Standard ML length function visits each list constructor once:

sml
fun length [] = 0
  | length (_ :: xs) = 1 + length xs;

Writing

T (n)

for its time complexity,

T (n) = T (n - 1) + Θ (1)

and

T (0) = Θ (1)

. Thus $T (n) = Θ (n)$ . Arithmetic is treated as unit cost; the example concerns list traversal rather than arbitrary-precision arithmetic.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / a / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Use the usual unit-cost model for Standard ML list constructors and fixed-size arithmetic. The input size

n

in the list examples is the number of list elements, rather than the size of the integer entries. Inspecting only the first constructor has constant time complexity:

sml
fun firstOrZero [] = 0
  | firstOrZero (x :: _) = x;

No tail is traversed. The running time is $Θ (1)$ .

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 4 / 5E / iv / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

Condition (iv) says in particular that

T

is an equivalence relation, so it is symmetric and transitive. It therefore implies (i) and (ii), closing the chain of implications.

Uniqueness is literal: if two equivalence relations both contain

R, S

and are each contained in every such relation, each is contained in the other, so they are equal. Combining the preceding proofs gives

(i) ⟺ (ii) ⟺ (iii) ⟺ (iv) .

(1)

Their common relation is the equivalence relation generated by

R \cup S

, and under these conditions it is already obtained by the two-step composite

R \circ S

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 4 / 5E / iii / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

 View more

The inverse argument in part (i) proves that the one-sided inclusion in (iii) already implies equality:

S \circ R \subseteq R \circ S ⟺ R \circ S = S \circ R .

(1)

Parts (i) and (ii) then make

T

both symmetric and transitive; it is reflexive from the root solution. Therefore

T

is an equivalence relation containing

R

and

S

U

is any other equivalence relation containing both, a witness

x R y, y S z

gives

xU y, y U z

, and transitivity gives

xU z

. Hence

T \subseteq U

. Thus (iii) implies the unique-smallest assertion in (iv).

 Read the full article

 There are unlisted articles, also show them or only show them.