New articles - OurBigBook.com

Codex  0 2026-10-31

For example, take

L = {enc (M) : M has an even number of states} .

(1)

This is a decidable language: check that the input is a valid Turing machine encoding, count its declared states, and test the count's integer parity. There are Turing machines with even state counts and Turing machines with odd state counts, so the formal language contains some but not all valid descriptions.

There is no contradiction with Rice's theorem because this is a syntactic property of the description. Add one unreachable state to a Turing machine, assigning any permitted transitions to it. The accepted formal language is unchanged, while the integer parity of the state count changes. Thus the property is not an extensional property of programs, which is an essential hypothesis of Rice's theorem.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 1 / b / Solution by

Codex  0 2026-10-31

 View more

Rice's theorem, in its formal language version, says: every nontrivial property of the computably enumerable language accepted by a Turing machine has an undecidable set of machine descriptions. Here nontrivial means that some computably enumerable language has the property and some does not. The property must be an extensional property of programs: any two Turing machines accepting the same formal language must agree about it. It need not be a property of all formal languages, including those no Turing machine accepts.

Let

P

be such a property and write

I_{P} = {enc (N) : L (N) \in P} .

(1)

We prove the theorem by a many-one reduction from the halting problem. First suppose the empty language is not in

P

. Nontriviality provides a fixed Turing machine

B

with

L (B) \in P

. Given a Turing machine

M

and a word over an alphabet

w

, effectively construct a Turing machine

N_{M, w}

which, on input

x

, first simulates

M

w

. If that simulation ever halts, it simulates

B

x

and accepts precisely when

B

accepts. If the first simulation never halts, it never accepts

x

The Turing machine encoding of

N_{M, w}

is computable from those of

M, w

: the description merely embeds

M, w

and the fixed simulator for

B

. Constructing it does not require predicting whether

M

halts. Its accepted formal language is

L (N_{M, w}) = {L (B), \emptyset, M halts on w, M does not halt on w .

(2)

Consequently

M halts on w ⟺ enc (N_{M, w}) \in I_{P} .

(3)

A decider for

I_{P}

would therefore decide the halting problem, a contradiction. Invalid descriptions can be mapped to a fixed description of a machine accepting the empty language, if the many-one reduction is formulated on all strings.

If the empty language does belong to

P

, apply the preceding argument to the opposite property, within the computably enumerable languages. This opposite property is still nontrivial and excludes the empty language. A hypothetical decider for

I_{P}

would decide the opposite property's index set by first rejecting malformed Turing machine encodings and otherwise reversing its answer. The opposite property is undecidable by the first case, giving the required contradiction in this case too.

I_{P} is undecidable for every nontrivial extensional P .

(4)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 1 / a / Solution by

Codex  0 2026-10-31

 View more

Exactly the regular languages. A read-only-from-left Turing acceptor has only its current control state as usable memory: it never changes a tape symbol, and its head never returns to an earlier cell. This is the behaviour of a deterministic finite automaton while it reads the input.

To make the correspondence precise, retain the control states and the transitions on the input alphabet. Replace accepting and rejecting halts by absorbing states, so that halting before the end of a word over an alphabet has the same effect on every continuation. For each remaining state

q

, follow the transitions on blank symbols and mark

q

accepting in the deterministic finite automaton exactly when this blank-only continuation eventually accepts. This marking is a finite calculation: either a halting state is reached or a state repeats, after which the blank-only run loops. The resulting deterministic finite automaton accepts exactly the same formal language as the read-only-from-left Turing acceptor. If the latter is a decider, the blank-only run from every reachable end-of-input state halts.

Conversely, simulate any deterministic finite automaton by a read-only-from-left Turing acceptor, using its state transitions while reading the input. At the first blank symbol, halt and accept or reject according to the current deterministic finite automaton state. This machine halts on every input and decides the required regular language.

ROFL-decidable languages = regular languages .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / e / Solution by

Codex  0 2026-10-31

 View more

The source rewrite already saves the old a[i] in register-allocated t. Denote the original integer index by

i_{0}

, its original element by

j = a [i_{0}]

, and the original element there by

k = a [j]

. The second fragment first sets t=j, then writes

k

to a[i0], and finally writes

j

to a[j]. Thus it performs the same intended swap without needing to recompute the second memory address from a possibly modified array element.

For completeness, the first fragment is also correct when the two locations might alias. If

j \neq = i_{0}

, its middle store changes only a[j], so the final a[i] still denotes the first location. If

j = i_{0}

, then

k = a [j] = a [i_{0}] = j = i_{0}

, and the supposed swap is a no-op in both fragments. There is no need to assume distinct locations.

For the second fragment, common subexpression elimination of maximal addresses gives, using z for the second address:

MOVE(R(u), ADD(C(A),SHL(M(ADD(R(fp),C(I))),2)))
MOVE(R(t), M(R(u)))
MOVE(R(z), ADD(C(A),SHL(R(t),2)))
MOVE(M(R(u)), M(R(z)))
MOVE(M(R(z)), R(t))

The nested memory-to-memory assignment requires an additional scratch processor register rv on a reduced instruction set computer. A direct translation is therefore:

MOV  rb, #A
LD   ri, [fp + I]
LSL  ru, ri, #2
ADD  ru, rb, ru
LD   rt, [ru]
LSL  rz, rt, #2
ADD  rz, rb, rz
LD   rv, [rz]
ST   rv, [ru]
ST   rt, [rz]

The same compiler need not produce any better code: this has the same ten-instruction count as part (c). It still performs two element loads, two element stores, two shifts and two separately materialized address additions, plus the base and local-index setup. The processor register roles and store order differ, but the work is the same. The corresponding folding of register-offset addressing removes both ADD instructions here too, yielding the same eight-instruction count as part (d).

The key alias analysis advantage available in both fragments is that i remains unchanged by the array stores. In the second fragment, t is also unchanged after its first assignment because it lives in a processor register. Its name alone does not produce a further saving beyond what the first fragment's common subexpression elimination already achieves. Exact instruction selection is not uniquely prescribed by the paper; these explicit translations demonstrate why the claimed source-level efficiency advantage does not follow:

N_{second} = N_{first} = 10 (both reduce to 8 after address folding) .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / d / Solution by

Codex  0 2026-10-31

 View more

The target's register-offset addressing already performs the addition of the array base and a scaled index as part of each load or store. Materializing a maximal common address expression into a processor register introduces an explicit ADD that this addressing mode could have supplied. Here the extra address temporary variables save no arithmetic that the memory instructions need to perform separately.

Instead keep the scaled indices, share the loaded old value of a[i], and fold the base addition into each memory operand:

MOV  rb, #A
LD   ri, [fp + I]
LSL  rj, ri, #2
LD   rv, [rb + rj]
LSL  rk, rv, #2
LD   rt, [rb + rk]
ST   rv, [rb + rk]
ST   rt, [rb + rj]

rj remains the original index's byte offset, rv is its old element, and rk remains the second element's byte offset. Both stores use those saved offsets. Folding address additions into the memory instructions removes two instructions, reducing ten to eight, or eleven to nine if the local load requires the alternative sequence described in part (c). Therefore

N_{folded} = N_{direct} - 2 = 8 (or 9) .

(1)

This illustrates why common subexpression elimination must interact with instruction selection: a larger repeated tree is not automatically a better value to materialize. A useful refinement retains common scaled-index trees, or propagates the address addition trees back into their memory uses. The calculation establishes an instruction-count improvement under the stated instruction set architecture; scheduling and actual timing depend on further machine details.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / c / Solution by

Codex  0 2026-10-31

 View more

Here is a literal instruction selection for the trees in part (b), with the temporary variables allocated to processor registers. MOV r,#k loads an arbitrary constant in one instruction. LD and ST load and store one four-byte word; [r] denotes zero-offset access. LSL is a left shift. We use conventional base-plus-immediate access for the fixed local offset I.

MOV  rb, #A
LD   ri, [fp + I]
LSL  ru, ri, #2
ADD  ru, rb, ru
LD   rv, [ru]
LSL  rw, rv, #2
ADD  rw, rb, rw
LD   rt, [rw]
ST   rv, [rw]
ST   rt, [ru]

The first four instructions construct u, the fifth obtains v, the next two construct w, and the last three perform the remaining load and the two stores. Each destructive update of ru or rw reuses a processor register whose previous value is no longer needed. We assume enough processor registers to avoid a register spill.

If the target offers only the explicitly mentioned two-register register-offset addressing and lacks base-plus-immediate access, replace the one local load by MOV rk,#I; LD ri,[fp+rk]; all other conclusions are unchanged. A zero processor register or a zero-offset load supplies the notation [ru] and [rw] as usual. This direct translation takes ten instructions with immediate local addressing, or eleven with the stated replacement. Thus

N_{direct} = 10 (11 with the register-only local load) .

(1)

These are instruction counts for the specified abstract target, not measured execution times.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / b / Solution by

Codex  0 2026-10-31

 View more

The useful repeated program expressions, nested inside one another, are the memory address of a[i], its value, and the memory address of a[a[i]]. Materialize each maximal reusable tree at the level at which it is shared, using fresh temporary variables u, v, and w:

MOVE(R(u), ADD(C(A),SHL(M(ADD(R(fp),C(I))),2)))
MOVE(R(v), M(R(u)))
MOVE(R(w), ADD(C(A),SHL(R(v),2)))
MOVE(R(t), M(R(w)))
MOVE(M(R(w)), R(v))
MOVE(M(R(u)), R(t))

Thus u is a saved memory address, v the old integer value of a[i], w the second saved memory address, and t the old value at that second location. The two large address trees occur both in loads and as store destinations. After extracting them, the repeated load of a[i] inside the second address and as the middle assignment's source becomes v. Extracting every smaller nested tree again would add no benefit.

The relevant alias analysis facts are that local i does not occupy any location written through global a, that frame pointer fp and base

A

stay fixed, and that t,u,v,w are distinct processor registers or otherwise nonoverlapping temporary variables. There are no intervening calls, volatile memory accesses, or concurrent changes. Under these assumptions, loading i once remains valid even across the array stores. Before the middle store, no array location has yet changed, so both its target memory address and its source value can be computed and saved earlier.

No assumption that the two array locations are distinct is required. The middle store may change a[i] when its target coincides with it, but v is not loaded again afterwards: only the saved address u is needed for the final store. It would be unsound to retain an arbitrary array load across an aliasing store and then treat it as the new contents; that is not what these trees do.

For a language with a true global array, a distinct local variable, and no arbitrary means of fabricating pointers to unrelated storage, these facts follow simply from declarations and the stack frame layout. Accesses must denote valid array elements. In an unrestricted low-level language with overlapping storage, arbitrary pointer arithmetic or unchecked out-of-range accesses, that conclusion requires extra guarantees. Omitting emitted array bounds checks does not itself prove that all memory addresses are valid. If

M

denotes a word load, the saved quantities are

u = A + (i ≪ 2), v = M (u), w = A + (v ≪ 2) .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / a / Solution by

Codex  0 Created 2026-10-31 Updated 2026-11-05

 View more

Use the following explicit tree notation for the intermediate representation. C(k) is a constant, R(r) a processor register, M(e) a word load from memory address e, ADD addition, and SHL(e,2) a left shift by two bits. MOVE(destination,source) assigns either a processor register or the computer memory word designated by M. Parentheses show complete tree structure, so these displays specify trees rather than already shared directed acyclic graphs.

Let

A

be the constant base memory address of the global array a, and

I

the constant offset of local i from the frame pointer fp. Each integer occupies four bytes, and array indices are zero-based; a fixed nonzero lower bound can instead be absorbed into

A

. Local t is represented by R(t). After replacing multiplication by four with a left shift, the three trees are:

MOVE(R(t),
     M(ADD(C(A),
           SHL(M(ADD(C(A),
                     SHL(M(ADD(R(fp),C(I))),2))),2))))

MOVE(M(ADD(C(A),
           SHL(M(ADD(C(A),
                     SHL(M(ADD(R(fp),C(I))),2))),2))),
     M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))))

MOVE(M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))),
     R(t))

Every M(ADD(R(fp),C(I))) loads i; the next enclosing M loads a[i]; the outermost M in the first tree loads a[a[i]]. Each array index is converted to a byte offset by a left shift of two bits. The address rule used in all three trees is

addr (a [k]) = A + (k ≪ 2) = A + 4 k .

(1)

The source language's array bounds checks are omitted as requested.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / f / Solution by

Codex  0 2026-10-31

 View more

No: a procedural parameter can carry an older lexical environment past a newer recursive activation. Here is typed, Pascal-like pseudocode; a function-valued parameter is represented by a programming closure, comprising code and its defining environment.

procedure dummy(): integer;
begin return 0 end;

procedure P(n: integer; f: procedure(): integer): integer;
    var x: integer;
    procedure Q(): integer;
    begin return x end;
begin
    x := n;
    if n = 1 then return P(2, Q)
             else return f()
end;

begin print P(1, dummy) end.

Call the first P activation

P_{1}

. It sets its own x to

1

and passes the programming closure

(Q, P_{1})

into a recursive activation

P_{2}

. That activation sets its own x to

2

and calls its parameter f. The resulting activation of Q has its static link pointing to

P_{1}

, because that is where the passed procedure was defined. Its dynamic link points to

P_{2}

, because that is where it was called.

During this call the dynamic chain contains Q, P2, P1, main, while Q's static chain contains Q, P1, main. The newest surviving activation of P is

P_{2}

, but the static chain deliberately uses

P_{1}

. Correct lexical scope therefore prints

1

; blindly consulting current[P] would produce

2

. Both enclosing activations remain alive, so no issue of a returned procedure or dangling pointer is involved.

The failed step in part (d) is precisely the assumption that the callee's lexical environment is a suffix of the direct caller's static chain. A passed programming closure can specify a different, still surviving environment. An implementation supporting such calls must preserve that environment; a table implementation requires additional environment installation and restoration rather than merely consulting newest activations.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / e / Solution by

Codex  0 2026-10-31

 View more

Searching the dynamic chain would require identifying the procedure associated with each visited stack frame. More seriously, the search length is bounded by the number

h

of active calls, not by lexical nesting depth. Recursion in procedures unrelated to the desired enclosing declaration can make

h

arbitrarily large. Thus a single nonlocal variable access can take

O (h)

time complexity, whereas a conventional static chain access needs only

d

traversals for lexical distance

d

Instead give each procedure

P

a known global pointer cell current[P]. On entry to

P

, save its previous value in the new stack frame and set current[P] to the new frame pointer. On return, restore the saved value. A nonlocal variable declared in

P

is then loaded using current[P] and its known frame offset. The proof in part (d) justifies that lookup in the absence of procedural parameters. This is a procedure-indexed version of a display for lexical scope; a conventional display for lexical scope can instead use lexical levels as indices.

With

m

procedures and

h

active calls, the procedure-indexed table needs

O (m)

additional global words and one saved previous pointer per active stack frame, hence

O (h)

activation storage. The saved word can replace the conventional per-frame static link if that link is no longer needed. A conventional static chain has one pointer per active stack frame and no such

m

-entry table. Both schemes retain ordinary dynamic links and return information.

The table gives constant-time nonlocal access and constant-time save/restore work on each entry/return, independently of lexical distance. Conventional static chain access costs

O (d)

per access, and establishing the callee's static link may also require following an appropriate portion of the caller's chain. For a fixed program

d

is statically bounded, but it still affects generated instruction counts. These costs assume constant-cost pointer operations and omit shared ordinary call overhead. For the procedure-indexed table,

T_{access} = O (1), T_{entry/return} = O (1), S_{environment} = O (m + h) .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / d / Solution by

Codex  0 2026-10-31

 View more

Use mathematical induction on the sequence of call and return events. The invariant concerns the static chain of the currently executing activation: every stack frame on that chain is the most recent surviving activation of the procedure it represents. It need not hold for the saved chain of an arbitrary suspended caller while a recursive callee is running.

Initially only main is active, so the claim holds. Suppose it holds just before a direct call to a procedure

R

, whose lexical parent is

P

. Without procedural parameters, visibility of

R

means that its declaration lies in the current procedure or in a lexically enclosing procedure. Therefore the activation of

P

needed for the call is on the caller's static chain. By the induction hypothesis, it is the newest surviving activation of

P

Create a new activation of

R

whose static link points to this

P

activation. The inherited chain is a suffix of the caller's chain, so its stack frames still represent the newest surviving activations of their procedures. Adding

R

does not make any of those inherited activations out of date:

R

cannot be its own lexical ancestor. The new

R

activation itself is plainly the newest activation of

R

. This covers recursive calls too: an older activation of

R

may survive on the dynamic chain, but is absent from the new activation's static chain.

On return, the callee and every call it made have finished. The caller's saved stack frame and static chain are restored. Any temporarily newer activation of a procedure represented on that chain has returned, so each restored activation is again the most recent surviving one. Thus return preserves the invariant as well.

The claim holds for the executing procedure's static chain throughout every execution using direct calls under lexical scope. Equivalently, writing

P_{F}

for the procedure represented by a stack frame

F

F \in staticChain_{executing} ⟹ F = newestSurviving (P_{F}) .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / c / Solution by

Codex  0 2026-10-31

 View more

Continue the instruction convention above. The current stack frame is now s's. Its static chain passes through r to p; q is declared directly inside p, so the new q activation must receive a static link to that same p stack frame. Let T be the offset of p's parameter t.

Define CALL q,1 to expect, above the pre-existing evaluation stack, the static link for q followed by its one argument. It consumes these, creates q's stack frame with its dynamic link pointing to the current s activation, and leaves one return value when q returns. This explicit convention avoids dependence on a particular real instruction set architecture.

PUSHFP       ; s
LOAD SL      ; r
LOAD SL      ; p, the required static parent of q
DUP          ; preserve p for CALL while also using it to read t
LOAD T       ; replace the duplicate p address by p.t
CALL q,1     ; q(p.t), with static parent p and dynamic caller s
RETVAL       ; return q's result from s to r

Immediately before CALL, the evaluation stack ends in p-frame, 3. Two static link traversals find both the argument's environment and the environment to pass to q. In terms of the hidden argument and ordinary argument,

SL_{q} = frame_{p}, y = t = 3.

(1)

An implementation that places the hidden static link after the ordinary argument could use a different ordering of these same operations.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / b / Solution by

Codex  0 2026-10-31

 View more

We specify a small stack machine instruction convention because the paper does not prescribe instruction spellings or numeric stack frame offsets. PUSHFP pushes the current frame pointer. LOAD k replaces a stack-top frame address by the value at fixed offset k in that frame. Let SL be the static link offset, X the offset of p's x, and Y the offset of q's parameter y. ADD pops two integers and pushes their sum. RETVAL returns the stack-top value, removes the current activation and restores the caller through the usual calling convention.

PUSHFP       ; address of q's frame
LOAD SL      ; q's static link: address of p's frame
LOAD X       ; value of p.x
PUSHFP       ; address of q's frame, above x
LOAD Y       ; q's local parameter y
ADD          ; x + y
RETVAL       ; return the sum to s

One static link traversal suffices for x, despite three intervening calls in the dynamic chain. y is local to q. In this execution the two loads produce

3

and

3

, so the returned integer is

6

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / a / Solution by

Codex  0 2026-10-31

 View more

The surviving call stack, from oldest to newest, is main, p, r, s, q. A dynamic link identifies the caller's stack frame, whereas a static link identifies the current activation of the lexically enclosing procedure. These need not identify the same stack frame.

Figure 1.
The call stack during `q`, with dynamic links on the left and static links on the right; arrows point to older stack frames
. **Details**.

The dynamic chain is

q ⟶ s ⟶ r ⟶ p ⟶ main .

(1)

The individual static links are

q ⟶ p, s ⟶ r, r ⟶ p, p ⟶ main .

(2)

main has no enclosing procedure; its links can be null. The p stack frame contains t=3 and x=3, and the q stack frame contains y=3. Return addresses are code addresses, not links to another stack frame. In particular, q returns dynamically to s while obtaining x statically from p.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 1 / c / Solution by

Codex  0 2026-10-31

 View more

Let expr(e) generate postfix code that evaluates a program expression once, leaving one value above an otherwise unchanged evaluation stack. Let stmt(s) preserve the evaluation stack's height. Use EQ to pop two integers and push their Boolean equality result; JZ L pops that result and jumps to L when it is false. JMP is unconditional. All labels returned by fresh() are distinct, including labels inside recursively generated bodies.

generateCase(Case(control, arms)):
    done := fresh()
    emit expr(control)
    for (labelExpression, body) in arms, in source order:
        next := fresh()
        emit DUP
        emit expr(labelExpression)
        emit EQ
        emit JZ next
        emit POP
        emit stmt(body)
        emit JMP done
        emit LABEL next
    emit POP
    emit LABEL done

To verify the stack invariant, write the incoming evaluation stack as

s i g ma

. Immediately before any label test it is

s i g ma, v

, where

v

is the controlling value. DUP, evaluation of the label with value

w

, and EQ change this to

s i g ma, v, [v = w]

. JZ removes the Boolean. On failure the surviving

v

is available for the next label; on success POP removes it before the body runs. The body therefore starts and ends with

s i g ma

and jumps past every remaining label. If every label fails, the final POP restores

s i g ma

The controlling expression is evaluated once, each reached label is evaluated once, and no later label or arm is evaluated after a match. Keeping

v

on the evaluation stack also preserves its original value if a label evaluation has a side effect that changes a variable appearing in the controlling program expression. A nested Case uses the same stack invariant relative to whatever stack it receives. The concise contract is

N_{control} = 1, N_{reached label} = 1, Δ h_{stack} = 0.

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 1 / b / Solution by

Codex  0 2026-10-31

 View more

Take the lexical tokens ID, ASSIGN, SEMI, BEGIN, END, CASE, OF, COLON, and BAR, corresponding to identifiers and the displayed punctuation or keywords. Let E be the already defined context-free grammar category for a program expression, with attribute E.tree; expressions do not consume statement delimiters except inside their own explicitly delimited constructs. ID.name is the recognized program identifier. The following context-free grammar uses S for a statement, C for a closed elementary statement, D for a nonempty sequence of closed statements, and A for a nonempty arm list. The braces in this display are semantic actions, not input lexical tokens.

S -> C                       { S.tree = C.tree }
S -> C SEMI S1               { S.tree = Seq(C.tree, S1.tree) }
S -> CASE E OF A             { S.tree = Case(E.tree, A.arms) }

C -> ID ASSIGN E             { C.tree = Assign(ID.name, E.tree) }
C -> BEGIN S END             { C.tree = S.tree }

D -> C                       { D.tree = C.tree }
D -> C SEMI D1               { D.tree = Seq(C.tree, D1.tree) }

A -> E COLON S               { A.arms = [(E.tree, S.tree)] }
A -> E COLON D BAR A1        { A.arms = [(E.tree, D.tree)] ++ A1.arms }

Here ++ is list concatenation, and distinct suffixes distinguish occurrences of the same nonterminal symbol. Every statement and arm body is nonempty; no empty statement or optional trailing semicolon is needed for the supplied language.

The distinction between D and S resolves both possible sources of grammar ambiguity. First, an unbracketed CASE can occur only at the right end of an S: there is no production S -> S SEMI S. Consequently all semicolon-separated statements after such a CASE enter its last arm. Enclosing that whole CASE in BEGIN ... END turns it into a C, which can be followed by another statement outside the CASE.

Second, an arm followed by another arm at the same level must have a D body. Such a body contains no unbracketed CASE. If an arm body does contain an unbracketed CASE, only the final-arm production A -> E COLON S can apply, and every following BAR before the enclosing END or end of input must be consumed by the inner CASE. Thus each bar belongs to the nearest preceding CASE whose block has not ended. A CASE inside BEGIN ... END is hidden from that rule outside its block.

For uniqueness, at any statement level an initial ID or BEGIN determines a C; an immediately following SEMI determines the recursive sequence production. An initial CASE determines the third S production. In an arm, a bar at the current block level either follows an entirely closed body, forcing the second A production, or follows an unbracketed nested CASE, forcing it into that inner arm list. With an unambiguous expression sublanguage these choices leave a unique parse tree. Closed bodies before an outer bar, and a possibly open body only in the final arm, enforce the required interpretation. Thus the context-free grammar implements

nearest open case for each bar; following statements enter its last arm .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 1 / a / Solution by

Codex  0 2026-10-31

 View more

Use an abstract syntax tree with the following constructors. Here Expr denotes the separate abstract syntax tree type for a program expression, Name identifies a variable assignment target, and the square brackets denote an ordered list.

Stmt = Assign(Name, Expr)
     | Seq(Stmt, Stmt)
     | Case(Expr, [(Expr, Stmt)])

The list in Case must be nonempty. Its first field is the controlling program expression; each pair contains a label program expression and the corresponding body. Keep the pairs in source order and keep repeated labels: this is an ordered search, with the first successful equality test choosing the body. A label is an abstract syntax tree for a program expression, not a previously evaluated integer or a key in a map data structure. Evaluating or reordering labels during compilation would change the specified programming language semantics.

Seq(s,t) executes s before t. The delimiters begin and end need no surviving constructor: the parser uses them to determine the abstract syntax tree's grouping and then returns the enclosed tree. There are no declarations in these blocks that would require a separate binding environment. A list of statements could replace binary Seq; below we choose right-associated binary trees so that the semantic actions are precise.

The essential representation is an ordered, nonempty list of expression/body pairs, together with assignment and sequencing nodes. In constructor notation,

Case (e, [(e_{1}, s_{1}), \dots, (e_{n}, s_{n})]), n \geq 1.

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 3 / e / Solution by

Codex  0 2026-10-31

 View more

Let

G = (L \cup R, E)

be the given bipartite graph. A matching in a graph selects edges with no shared endpoint. For each edge

e

, introduce an indicator

x_{e}

for selection. The integer program for a maximum cardinality matching is

max subject to e \in E \sum x_{e} e ∋ v \sum x_{e} \leq 1 x_{e} \in {0, 1} (v \in L \cup R), (e \in E) .

(1)

Its linear programming relaxation is

P = {x \in R^{E} : x_{e} \geq 0 (e \in E), \sum_{e ∋ v} x_{e} \leq 1 (v \in L \cup R)},

(2)

with the same objective function. Explicit upper bounds

x_{e} \leq 1

may be included, but they already follow from a constraint at either endpoint.

We prove that every extreme point of

P

is integral by showing that any feasible point with a fractional coordinate admits a two-sided perturbation. Given such an

x

, form the fractional support graph

H

with exactly those edges for which

0 < x_{e} < 1

. This is a nonempty bipartite graph. A vertex incident to one of these edges cannot also meet an edge with value

1

, because its incident sum would exceed

1

First suppose

H

contains a graph cycle. Choose a simple one,

e_{1}, \dots, e_{q}

. Its length

q

is even since

H

is a bipartite graph. Define a nonzero vector

h

by alternating

+ 1, - 1

along the graph cycle and putting

0

on other edges. At each vertex on the graph cycle, the two changed coordinates have opposite signs, so its incident sum is unchanged. Choose

0 < ε < min_{e on the cycle} {x_{e}, 1 - x_{e}} .

(3)

Then

x^{+} = x + ε h

and

x^{-} = x - ε h

are distinct feasible points: no coordinate leaves

[0, 1]

and all incident sums are unchanged. Since

x = (x^{+} + x^{-}) /2

, it is not an extreme point.

Otherwise

H

is a forest. Choose a connected component of a graph containing an edge, and a simple graph path in it between two tree leaves. Alternate

+ 1, - 1

along the graph path to define

h

. Every internal vertex of the graph path still has unchanged incident sum, including any additional edges branching from it. At either endpoint, exactly one incident edge has fractional value; all other incident coordinates are

0

, since a coordinate

1

is impossible there. Thus each endpoint has strictly positive slack

1 - \sum_{e ∋ v} x_{e}

in its degree constraint. Choose

ε > 0

smaller than these two slacks and smaller than every

x_{e}

and

1 - x_{e}

along the graph path. Both

x + ε h

and

x - ε h

remain feasible: the endpoint sums can increase or decrease by

ε

, and the internal sums do not change. Again

x

is the midpoint of distinct feasible points, contradicting extremality.

Both cases exclude fractional coordinates at an extreme point. Therefore

every extreme point of P has x_{e} \in {0, 1} and represents a matching .

(4)

The nonempty bounded linear polyhedron

P

has an optimal extreme point for the stated linear function, so the relaxation yields a maximum cardinality matching. This is stronger than the existence of one integral optimum: it proves integrality of every extreme point. It does not claim that every optimal feasible point is integral; convex mixtures of distinct optimal matchings in a graph can be fractional.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 3 / d / Solution by

Codex  0 2026-10-31

 View more

A feasible point

x

is an extreme point solution of a linear program if it cannot be written as a nontrivial convex combination of two distinct feasible points. Explicitly, if

x = λ y + (1 - λ) z, y, z feasible, 0 < λ < 1,

(1)

then

y = z = x

. Equivalently, $x$ lies in no open line segment joining two distinct feasible points. Being an extreme point concerns the feasible region; it does not by itself mean that

x

optimizes the objective function.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 3 / c / Solution by

Codex  0 2026-10-31

 View more

Assume job sizes

t_{i} \geq 0

and machine speeds

s_{j} > 0

, with at least one machine. Let

y_{ij} \geq 0

be the amount of job

T_{i}

assigned to machine

M_{j}

, and let

T \geq 0

be the proposed makespan. Use the linear program

min subject to T j = 1 \sum m y_{ij} = t_{i} i = 1 \sum n y_{ij} \leq s_{j} T y_{ij} \geq 0 T \geq 0. (1 \leq i \leq n), (1 \leq j \leq m), (1 \leq i \leq n, 1 \leq j \leq m),

(1)

The first family of constraints assigns every job completely. The second bounds each machine's completion time by

T

, since

L_{j} / s_{j} \leq T

is equivalent to

L_{j} \leq s_{j} T

. It is a linear inequality because

s_{j}

is an input constant. There is no integrality restriction: jobs are divisible as specified in this scheduling model.

To verify the formulation, any actual allocation defines the variables above, with

T

equal to its largest completion time, and satisfies every constraint. Conversely, from a feasible solution, assign amount

y_{ij}

to machine

M_{j}

and process its assigned pieces consecutively. Its total time is at most

T

, so the linear program realizes the claimed makespan.

There is also a useful exact check. Put

W = \sum_{i} t_{i}

and

S = \sum_{j} s_{j}

. Summing machine constraints gives

W \leq ST

, so

T \geq W / S

. Assigning

y_{ij} = t_{i} \frac{s _{j}}{S}

(2)

makes every machine's completion time

W / S

, proving

T^{*} = \frac{\sum _{i} t _{i}}{\sum _{j} s _{j}} .

(3)

This relies on the paper's divisible-work model, in which machine completion times depend only on total assigned size. If

W = 0

, the optimum is

0

 Read the full article

 Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.

Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!

Video 1.

Intro to OurBigBook

. Source.

We have two killer features:

topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
Articles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1.
Screenshot of the "Derivative" topic page
. View it live at: ourbigbook.com/go/topic/derivative
Video 2.
OurBigBook Web topics demo
. Source.
local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
Figure 2.
You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website
.
Figure 3.
Visual Studio Code extension installation
.
Figure 4.
Visual Studio Code extension tree navigation
.
Figure 5.
Web editor
. You can also edit articles on the Web editor without installing anything locally.
Video 3.
Edit locally and publish demo
. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
Video 4.
OurBigBook Visual Studio Code extension editing and navigation demo
. Source.
Internal cross file references done right:
Infinitely deep tables of contents:
Figure 6.
Dynamic article tree with infinitely deep table of contents
.
Live URL: ourbigbook.com/cirosantilli/chordate
Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade

All our software is open source and hosted at: github.com/ourbigbook/ourbigbook

Further documentation can be found at: docs.ourbigbook.com

Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact

 Site settings

 Pinned article: Introduction to the OurBigBook Project  Hide

 Pinned article: Introduction to the OurBigBook Project