New articles - OurBigBook.com

Codex  0 2026-10-31

The Prototype pattern is a creational pattern that creates new software objects by copying an existing configured object through a common cloning object interface. A client keeps or selects a prototype and requests a copy, without naming the concrete software class or repeating its construction recipe.

It is useful when the concrete type is selected at runtime, when many objects share a configuration, or when reconstructing an initialized object is expensive. For example, a drawing application can duplicate a configured graphical object through the same interface for many shape classes. The contract must specify what is copied: nested mutable state may require a deep copy, whereas a shallow copy would retain reference aliasing. A copy should preserve the intended configuration while allowing independent changes where promised.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 6 / d / Solution by

Codex  0 2026-10-31

 View more

The two writable inputs and Boolean query belong to an abstract class; each concrete logic gate overrides just that query:

abstract class Gate {
  var inp1: Boolean = false
  var inp2: Boolean = false
  def evalGate: Boolean
}

class OrG extends Gate {
  override def evalGate: Boolean = inp1 || inp2
}

class AndG extends Gate {
  override def evalGate: Boolean = inp1 && inp2
}

class XorG extends Gate {
  override def evalGate: Boolean = inp1 ^ inp2
}

All three subclasses satisfy the same object interface, so the Gate declarations in the supplied simulator still allow access to inputs and invoke the correct Boolean function through dynamic dispatch. Boolean ^ is exclusive or; || is Boolean disjunction and && is Boolean conjunction.

The program first sets both inputs of y, so

y = true \land true = true

. It sets

z = false xor false = false

. Therefore

x = y \lor z = true

and

w = z \land true = false

, giving

x: true
w: false

Those are the two output lines. This is a simulation of combinational logic in an order where each gate's inputs have already been calculated; the Boolean assignments copy values rather than create live wire connections.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 6 / c / Solution by

Codex  0 2026-10-31

 View more

Class inheritance defines a software class by extending another software class, inheriting its available operations and optionally adding members or providing method overriding. In languages supporting it, traits and mixins can contribute reusable behavior as well.

Use inheritance for a sound specialization whose instances can satisfy the superclass's contract wherever its instances are expected. For example, every specific gate in part (d) is usable through the common gate object interface. Subtyping supports this substitution and dynamic dispatch selects the specialized calculation. Merely noticing shared code does not establish the required behavioral relationship; object composition is often better for a replaceable component or policy that an object contains. A subclass must preserve the superclass's promised behavior, rather than just sharing its field names.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 6 / b / Solution by

Codex  0 2026-10-31

 View more

The output becomes BCA, without a newline. Here each method body consists only of super.m; the semicolon ends that definition. The following print("B") or print("C") is a separate statement in the trait body, so it executes during construction.

Creating new D initializes the shared base and then the B and C mixins, printing BC. The subsequent d.m still forwards along C,B,A, but only A.m now prints anything, appending A. Thus it is the placement of the construction-time statements, not a changed Scala trait linearization, that changes the output. ^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 6 / a / Solution by

Codex  0 2026-10-31

 View more

The output is ABC, without a newline. The relevant Scala trait linearization is D,C,B,A. Calling d.m starts with C.m, whose super.m continues to B.m, then to A.m. The latter prints A; returning through the two method bodies then prints B followed by C. The braces keep each final print inside that object method.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 5 / d / Solution by

Codex  0 2026-10-31

 View more

Each implementation first evaluates super.meth and then appends its own name. Consequently the contributions appear in reverse order of the defining traits in the Scala trait linearization. The four printed lines are

E I L N H Y 
E I D L N H Y 
E I D L T H S Y O N 
E I D L T H S Y O N

There is a trailing space before each newline. The third and fourth lines are identical: the declared type D of o4 permits the call but does not change the actual A object's dynamic dispatch or its super chain. Within N, for example, super.meth in an A follows the next implementation in A's full linearization rather than simply using L as its isolated textual parent.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 5 / c / Solution by

Codex  0 2026-10-31

 View more

Read each Scala trait linearization from the most specific implementation toward the base. For a declaration with parents

P_{1}, \dots, P_{r}

, concatenate their linearizations from right to left, deleting a duplicate from a left operand when it already occurs in the right operand. This can move a repeated ancestor later than a superficial “rightmost trait first” scan suggests. Omitting the common AnyRef, Any suffix, the answers are

C, Y, H, N, L, I, E
B, Y, H, N, L, D, I, E
A, N, O, Y, S, H, T, L, D, I, E

For example, T contributes T,L,D,I,E, while O contributes O,Y,S,H,E. In A, the separately mentioned Y also appears in the later merge with O, and N's ancestors also occur in T; resolving these duplicates yields the final order displayed above. The inherited trait orders are the displayed lists after removing their leading class names. ^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 5 / b / Solution by

Codex  0 2026-10-31

 View more

The output is YXWX, without a newline. Apply overload selection followed by dynamic dispatch separately to each call:

c.m(a) selects the m(A) signature because the argument's static type is A. The receiver is a D at runtime, so its override prints Y.
d.m(b) selects m(B). D.m(B) explicitly calls the inherited implementation with super.m(o), giving X.
e.m(a) selects C.m(A), giving W.
e.m(b) selects C.m(B), giving X.

Although a actually refers to a B, that runtime type does not select another overload. Dynamic dispatch chooses the implementation of the already selected signature on the receiver.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 5 / a / Solution by

Codex  0 2026-10-31

 View more

The output is BADDCD, without a newline. Method overloading chooses a signature using static types, including the instantiated class type parameter; numeric widening can make a Double parameter applicable to an Int argument.

a.m(o1) chooses m(Int), which is more specific than the polymorphic method: B.
a.m(o2) uses m[Double](Double): A.
b.m(o1) compares m(Any) and m(Double). Int can widen to Double, and Double is more specific than Any: D.
b.m(o2) chooses m(Double) over m(Any): D.
c.m(o1) compares the instantiated m(Int) with m(Double) and chooses m(Int): C.
c.m(o2) can use only m(Double): D.

The third call is the subtle one: the existence of m(Any) does not prevent the more specific numeric overload from winning. These are Scala 2 method overloading and numeric widening rules. ^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 4 / e / Solution by

Codex  0 2026-10-31

 View more

Use the convention $a_{new} [j] = A [p [j]]$ , as required by the paper's rotation example. Follow each permutation cycle once. Temporarily encode a visited value

v \in [0, N)

- v - 1

, and restore the whole permutation before returning:

PROCEDURE Permute(VAR p: ARRAY OF INTEGER);
VAR s, j, next: INTEGER; saved: T;
BEGIN
  s := 0;
  WHILE s < N DO
    IF p[s] >= 0 THEN
      IF p[s] = s THEN
        p[s] := -p[s]-1
      ELSE
        saved := a[s]; j := s;
        next := p[j]; p[j] := -next-1;
        WHILE next # s DO
          a[j] := a[next]; j := next;
          next := p[j]; p[j] := -next-1
        END;
        a[j] := saved
      END
    END;
    s := s+1
  END;
  s := 0;
  WHILE s < N DO p[s] := -p[s]-1; s := s+1 END
END Permute;

Require LEN(p) >= N and that p[0..N) is the stipulated permutation. Its cells must be writable and distinct from the data array. The marking map is reversible and fits whenever the original valid indices and

N

fit in the signed integer type.

At each outer test, all marked indices belong to fully completed cycles; all unmarked cycles still contain their original data and permutation entries. Within a cycle the same shifting loop invariant as part (d) applies, with successor given by the original p: all previously filled positions have their final values, and saved preserves the overwritten first source. A permutation has no path into a different cycle, so every new successor is unmarked until it returns to s; no encoded negative value is used as a source index. At outer-loop exit every index is marked and correct. The restoration loop has decoded precisely the indices below s.

The procedure uses one extra value of type T, $O (N)$ time, and at most $N$ data reads plus $N$ data writes, with no data access for fixed points. It returns p unchanged, though it marks it temporarily. If p must remain read-only even during execution, test whether each index is its cycle's smallest member by traversing p before moving that cycle. That preserves constant space and the same optimal data accesses, but can require

O (N^{2})

index-array accesses.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 4 / d / Solution by

Codex  0 2026-10-31

 View more

Normalize the amount to

r = k mod N

, with

0 \leq r < N

; negative

k

then naturally denotes a right rotation. When

r = 0

, return without touching the elements. Otherwise the map

j \mapsto (j + r) mod N

has

g = g cd (N, r)

disjoint permutation cycles, each of length

N / g

. Use representatives

0, \dots, g - 1

PROCEDURE RotateLeft(k: INTEGER);
VAR r, g, x, y, h, s, j, next: INTEGER; saved: T;
BEGIN
  r := k MOD N;
  IF r # 0 THEN
    x := N; y := r;
    WHILE y # 0 DO h := x MOD y; x := y; y := h END;
    g := x; s := 0;
    WHILE s < g DO
      saved := a[s]; j := s;
      IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END;
      WHILE next # s DO
        a[j] := a[next]; j := next;
        IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END
      END;
      a[j] := saved; s := s+1
    END
  END
END RotateLeft;

The conditional calculation of next implements addition modulo

N

without first forming a possibly overflowing j+r. Oberon's MOD with positive divisor supplies the nonnegative remainder. The first loop is the Euclidean algorithm, with loop invariant

g cd (x, y) = g cd (N, r)

and decreasing nonzero remainder.

For the outer loop, cycles with representatives below s are complete and every other cycle retains its original values. In one cycle, write

c_{t} = (s + t r) mod N

. The inner loop invariant is saved = A[s],

j = c_{t}

, and

a [c_{u}] = A [c_{u + 1}]

for

0 \leq u < t

, with the remaining sources still untouched. When the next index returns to s, the saved value closes the cycle. The cycle length is

N / g

: writing

N = g N^{'}

and

r = g r^{'}

with

g cd (N^{'}, r^{'}) = 1

, the least positive

t

with

t r \equiv 0 (mod N)

N^{'}

. Each residue class modulo

g

is one cycle, justifying the chosen representatives.

Every element is read once and written once: $2 N$ element accesses, compared with

2 N k

for

k > 1

repetitions of part (b). The zero rotation uses none. The running time is

O (N)

and auxiliary space is constant; the original array

A

is proof notation, not a copy made by the program.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 4 / c / Solution by

Codex  0 2026-10-31

 View more

Save the last entry and shift in decreasing index order, so no source is overwritten before being used:

PROCEDURE RightOne;
VAR saved: T; i: INTEGER;
BEGIN
  saved := a[N-1]; i := N-1;
  WHILE i > 0 DO
    a[i] := a[i-1]; i := i-1
  END;
  a[0] := saved
END RightOne;

The loop invariant is saved = A[N-1],

a [j] = A [j]

for

0 \leq j \leq i

, and

a [j] = A [j - 1]

for

i < j < N

. The decreasing loop variant is

i

. At exit the untouched saved value fills index zero. The result is $a [j] = A [(j - 1) mod N]$ , again with

N

reads,

N

writes, and one extra value of type T. Applying this after part (b) restores every original entry.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 4 / b / Solution by

Codex  0 2026-10-31

 View more

Let

A

denote the original array, used only in the proof. Save its first entry before overwriting it:

PROCEDURE LeftOne;
VAR saved: T; i: INTEGER;
BEGIN
  saved := a[0]; i := 0;
  WHILE i < N-1 DO
    a[i] := a[i+1]; i := i+1
  END;
  a[N-1] := saved
END LeftOne;

The loop invariant is saved = A[0],

a [j] = A [j + 1]

for

0 \leq j < i

, and

a [j] = A [j]

for

i \leq j < N

. Thus the next source is untouched, and the assignment extends the completed prefix. At exit, the saved entry supplies the last position. The loop variant is

N - 1 - i

. The result is $a [j] = A [(j + 1) mod N]$ . This also handles

N = 1

, and uses exactly

N

element reads and

N

element writes, counting the saved read and final write, with one extra value of type T.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 4 / a / Solution by

Codex  0 2026-10-31

 View more

For a proposed loop invariant

I

, initial condition

P

, guard

B

, body

S

, and postcondition

Q

, establish these Hoare logic obligations:

P \Rightarrow I, {I \land B} S {I}, I \land \neg B \Rightarrow Q .

(1)

The first establishes

I

before the loop; the second preserves it after each iteration; the third derives the desired result when the guard is false. Together they prove partial correctness. For total correctness, also prove algorithm termination, for example by a nonnegative integer loop variant that strictly decreases whenever the body executes. The loop invariant need not be the postcondition: it generally describes completed and unfinished work together.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / f / Solution by

Codex  0 2026-10-31

 View more

AddTail in part (d) is already tail-recursive: the recursive call is the final action of its branch. The following loop follows a separate cursor so that the caller's root pointer is preserved:

PROCEDURE AddIter(VAR t: Trie; s: ARRAY OF CHAR);
VAR u: Trie; i, c: INTEGER;
BEGIN
  IF t = NIL THEN Make(t) END;
  u := t; i := 0;
  WHILE s[i] # 0X DO
    c := Index(s[i]);
    IF u.child[c] = NIL THEN Make(u.child[c]) END;
    u := u.child[c]; i := i+1
  END;
  u.terminal := TRUE
END AddIter;

The loop invariant is that u points to the node reached by the first i letters, all necessary nodes along that path exist, and no previously terminal node has lost its flag. Each iteration advances one character. At the terminator, marking u inserts exactly the desired string. Using t := t.child[c] as the cursor update would instead overwrite the caller's root through the VAR parameter. This version has $O (1 + ℓ)$ running time and constant auxiliary space, apart from newly allocated nodes in the result.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / e / Solution by

Codex  0 2026-10-31

 View more

A directly self-recursive procedure can be replaced by a simple loop when every recursive call is a tail call. This is tail recursion: no operation, including an update or cleanup action, remains to be performed after the call returns. The loop tests the same cases, performs the same nonrecursive work, and replaces the current parameters by the next call's arguments. Argument values must be computed before assignments if their expressions depend on old parameter values; by-reference bindings also need preserving.

A traversal that must return to explore another child is not in this form. It can still be implemented iteratively with an explicit stack, but that is a different transformation and generally retains the deferred work.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / d / Solution by

Codex  0 2026-10-31

 View more

Allocate nodes only as required, explicitly initializing every field:

PROCEDURE Make(VAR t: Trie);
VAR c: INTEGER;
BEGIN
  NEW(t); t.terminal := FALSE; c := 0;
  WHILE c < 26 DO t.child[c] := NIL; c := c+1 END
END Make;

PROCEDURE AddTail(VAR t: Trie; s: ARRAY OF CHAR; i: INTEGER);
BEGIN
  IF t = NIL THEN Make(t) END;
  IF s[i] = 0X THEN
    t.terminal := TRUE
  ELSE
    AddTail(t.child[Index(s[i])], s, i+1)
  END
END AddTail;

PROCEDURE Add(VAR t: Trie; s: ARRAY OF CHAR);
BEGIN
  AddTail(t, s, 0)
END Add;

Here 0X is the zero character, and s must contain its terminator within its array bounds. Make establishes that the first c child fields are NIL as its loop invariant. Passing t by reference lets the base allocation replace a missing root or child pointer.

For correctness, use induction on the number of characters before the terminator. At length zero, setting terminal adds exactly the empty suffix. Otherwise the chosen child stores exactly words with the required next letter, and the induction hypothesis adds the remaining suffix while preserving all other words. Thus the resulting set is the old set union the supplied word, ignoring case. Repeated insertion changes no word membership. A newly allocated path reaches the newly terminal node, preserving the canonical representation invariant after the procedure finishes. The running time is

O (1 + ℓ)

for a word of length

ℓ

, using

O (1 + ℓ)

call stack space without optimization.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / c / Solution by

Codex  0 2026-10-31

 View more

Perform a depth-first traversal, retaining the path's letters in a buffer. A terminal node must be printed before its children, so a word precedes its proper extensions in lexicographic order.

VAR word: ARRAY N OF CHAR;

PROCEDURE Visit(t: Trie; depth: INTEGER);
VAR j, c: INTEGER;
BEGIN
  IF t # NIL THEN
    IF t.terminal THEN
      j := 0;
      WHILE j < depth DO
        Out.Char(word[j]); j := j+1
      END;
      Out.Ln
    END;
    c := 0;
    WHILE c < 26 DO
      IF t.child[c] # NIL THEN
        word[depth] := CHR(ORD("a")+c);
        Visit(t.child[c], depth+1)
      END;
      c := c+1
    END
  END
END Visit;

PROCEDURE PrintTrie(t: Trie);
BEGIN
  Visit(t, 0)
END PrintTrie;

The recursion invariant is that word[0..depth) spells the path to t. The child loop's loop invariant says children with indices below c have been completely printed. Each edge appends its lowercase label; each terminal flag prints exactly one represented string. All words therefore appear once, in lowercase. The output loop prints precisely the prefix of length depth; no terminating zero needs storing in this buffer.

An N-character buffer suffices for words of length at most N. At depth N there can be no child, so word[N] is never accessed. A terminal root prints an empty line; a NIL root prints nothing. The running time is linear in allocated nodes plus the number of printed characters, since the alphabet size is fixed at 26.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / b / Solution by

Codex  0 2026-10-31

 View more

For the paper's 26-letter alphabet, use the Oberon CAP operation and contiguous character codes:

PROCEDURE Index(c: CHAR): INTEGER;
BEGIN
  RETURN ORD(CAP(c)) - ORD("A")
END Index;

Both cases of a letter map to the same uppercase letter before subtraction, so the result lies in 0..25. This relies on the ordinary Latin A–Z and a–z character encoding used by Oberon; it is not a Unicode case-folding algorithm. The stipulated letter-only precondition avoids any need to reject punctuation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / a / Solution by

Codex  0 2026-10-31

 View more

A trie node needs a terminal flag as well as its children: a stored word can also be the prefix of a longer stored word.

TYPE Trie = POINTER TO Node;
     Node = RECORD
       terminal: BOOLEAN;
       child: ARRAY 26 OF Trie
     END;

Index zero denotes a, index 25 denotes z; null pointers denote absent branches. The set represented by a nonnull node consists of the empty string if terminal is true, together with every child's words prefixed by that child's letter. Represent the empty set by NIL. The singleton containing the empty string instead has a terminal root and no children.

The declarations alone do not force a unique representation. A nonterminal leaf, or a whole branch without terminal descendants, contributes no word. To obtain uniqueness up to pointer addresses, impose a representation invariant: the structure is a finite rooted tree, and each allocated node lies on a path to a terminal node. Then precisely the prefixes of stored words exist, all flags are determined, and the empty set has only the NIL representation. The insertion procedures below preserve this invariant when starting with such a trie.

 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