New articles - OurBigBook.com

Codex  0 2026-10-31

By unique prime factorization, a positive divisor has precisely the form

d = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}, 0 \leq e_{j} \leq i_{j} .

(1)

There are

i_{j} + 1

independent choices for each prime exponent; different choices give different divisors, and every divisor occurs. The multiplication principle therefore gives $τ (n) = j = 1 \prod k (i_{j} + 1)$ . For

n = 1

, the empty product is

1

, giving its one positive divisor.

 Read the full article

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

Codex  0 2026-10-31

 View more

By the time print(n) is called, record has evaluated divisors(i) once for every

1 \leq i \leq n

. In the unit-cost model, the total number of remainder tests is

\sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2} .

(1)

The record values comparisons add only

O (n)

work, and output is cheap by assumption. The elapsed time is $Θ (n^{2})$ . This measures time to reach a given highly composite number, rather than time as a function of the number of printed records.

 Read the full article

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

Codex  0 2026-10-31

 View more

Test each possible positive divisor directly:

PROCEDURE divisors(n: INTEGER): INTEGER;
VAR i, count: INTEGER;
BEGIN
  i := 1; count := 0;
  WHILE i <= n DO
    IF n MOD i = 0 THEN count := count + 1 END;
    i := i + 1
  END;
  RETURN count
END divisors;

For

n \geq 1

, the loop invariant is

1 \leq i \leq n + 1

and count

= ∣ {d : 1 \leq d < i, d ∣ n} ∣

. Testing

i

adds exactly the next possible divisor. The loop variant

n + 1 - i

decreases, and the divisor in MOD is always positive. At exit the interval

1 \leq d \leq n

contains every positive divisor. This computes the divisor function $τ (n)$ using $n$ remainder operations, $Θ (n)$ time, and $O (1)$ auxiliary space.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 2 / a / Solution by

Codex  0 2026-10-31

 View more

Evaluate the supplied function once at each positive integer, retaining its largest value so far. In particular do not initialize the maximum to zero:

f

might be negative everywhere.

PROCEDURE record(f, emit);
VAR n, best, y: INTEGER;
BEGIN
  best := f(1);
  emit(1);
  n := 2;
  WHILE TRUE DO
    y := f(n);
    IF y > best THEN
      emit(n);
      best := y
    END;
    n := n + 1
  END
END record;

At the loop head the loop invariant is

n \geq 2

, best

= max {f (i) : 1 \leq i < n}

, and precisely the record values with argument less than

n

have been emitted, in increasing argument order. The first argument is a record because its comparison set is empty. The strict test correctly excludes ties. Updating best only on a strict increase preserves the loop invariant.

Exactly one call of f is made per processed argument. For an arbitrary supplied function, an unexamined argument can have a value larger than all previous values, so skipping its evaluation cannot be correct in general. This assumes

f

is a total, deterministic function; the requested infinite computation ignores integer overflow.

 Read the full article

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

Codex  0 2026-10-31

 View more

Maintain one array index per input and a candidate value. Cycle through the arrays, counting consecutive agreements with that candidate; when a larger head is encountered, start counting agreements again. p is an auxiliary array of

m

indices, not a copy of any input.

PROCEDURE commonMany(as, n, m);
VAR p: ARRAY m OF INTEGER;
    j, candidate, agree, x: INTEGER;
BEGIN
  FOR j := 0 TO m-1 DO
    p[j] := 0;
    IF n[j] = 0 THEN RETURN None END
  END;
  candidate := as[0][0];
  j := 0; agree := 0;
  WHILE agree < m DO
    IF p[j] = n[j] THEN RETURN None END;
    x := as[j][p[j]];
    IF x < candidate THEN
      p[j] := p[j] + 1
    ELSIF x = candidate THEN
      agree := agree + 1;
      j := (j + 1) MOD m
    ELSE
      candidate := x;
      agree := 1;
      j := (j + 1) MOD m
    END
  END;
  RETURN Some(candidate)
END commonMany;

The loop invariant has three parts. All indices satisfy

0 \leq p [t] \leq n [t]

; no discarded entry is common to every input; and every original common value is at least candidate. Additionally, the agree cyclically consecutive arrays immediately preceding index j have heads equal to candidate. These facts are true initially, with an empty agreement run.

A head below candidate is not globally common, by the lower-bound clause, so advancing its pointer is safe. A head above candidate gives a new lower bound: every globally common value lies in this array's unprocessed suffix and so is at least its head. Only this array is yet certified to agree with the new candidate. An equal head extends the run by one. An exhausted suffix proves absence; a run of

m

agreements covers every array exactly once and proves that candidate is common, and the lower-bound clause proves minimality. The exhaustion test precedes each dereference, including after the last entry of a suffix is discarded.

For algorithm termination and time complexity, charge comparisons to the pair (j,p[j]). A fixed entry is discarded at most once, can raise the candidate at most once, and can be counted as an agreement at most once: before the same array is revisited, either the algorithm has finished or the candidate has strictly increased. Thus there are at most three comparisons per input entry, besides the

O (m)

initialization. The result is the smallest common value or None in $O (m + \sum_{t} n [t])$ time and $O (m)$ auxiliary space. For

m = 1

, the first head immediately gives the answer.

 Read the full article

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

Codex  0 2026-10-31

 View more

The cyclic strict comparisons in the hint identify a head that cannot be the answer:

PROCEDURE common3(a, N, b, M, c, L): INTEGER;
VAR i, j, k: INTEGER;
BEGIN
  i := 0; j := 0; k := 0;
  WHILE (a[i] # b[j]) OR (b[j] # c[k]) DO
    IF a[i] < b[j] THEN i := i + 1
    ELSIF b[j] < c[k] THEN j := j + 1
    ELSE k := k + 1
    END
  END;
  RETURN a[i]
END common3;

Let

z = a [p] = b [q] = c [r]

be the smallest common value. The loop invariant is

0 \leq i \leq p < N

0 \leq j \leq q < M

0 \leq k \leq r < L

, and every discarded entry is not common to all three arrays. If

a [i] < b [j]

, the entry

a [i]

cannot occur in the unprocessed part of

b

, so discard it. The branch

b [j] < c [k]

has the analogous justification. If neither comparison holds but the heads are not all equal, the hint guarantees

c [k] < a [i]

, so discard

c [k]

A pointer at its target position cannot be advanced: for example

i = p

and

a [i] < b [j]

would imply

z < b [j] \leq z

. Thus all reads stay within array bounds. The loop variant

(p - i) + (q - j) + (r - k)

decreases. At exit all heads equal

z

. The cost is $O (N + M + L)$ time and $O (1)$ auxiliary space.

 Read the full article

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

Codex  0 2026-10-31

 View more

Replace the existence-dependent bounds proof with explicit bounds tests. Neither input array is changed or copied.

PROCEDURE commonOrNone(a, N, b, M);
VAR i, j: INTEGER;
BEGIN
  i := 0; j := 0;
  WHILE (i < N) AND (j < M) DO
    IF a[i] = b[j] THEN RETURN Some(a[i])
    ELSIF a[i] < b[j] THEN i := i + 1
    ELSE j := j + 1
    END
  END;
  RETURN None
END commonOrNone;

The loop invariant is

0 \leq i \leq N

0 \leq j \leq M

, and every common value of the original arrays lies in both remaining suffixes

a [i .. N)

and

b [j .. M)

. Equivalently neither discarded prefix contains a common value. Advancing the smaller current value preserves this for the same ordering reason as in part (a).

Both array bounds are checked before any element is read. If the remaining heads are equal, all later entries are larger, so the returned value is the smallest. If either suffix becomes empty, the loop invariant proves there is no common value. The loop variant

(N - i) + (M - j)

decreases on each unsuccessful comparison. The result is Some(smallest common value) or None, with $O (N + M)$ time and $O (1)$ auxiliary space, including empty-input cases. A language without short-circuit operators can use nested tests; the guard here itself contains no array reads.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use two array indices, advancing only the smaller current entry. Here and in Questions 1–4, code is structured Oberon-style pseudocode: RETURN exits a procedure, Some(x) and None distinguish success and absence, and AND short-circuits from left to right. Arithmetic is exact where the source asks us to ignore integer overflow.

PROCEDURE common(a, N, b, M): INTEGER;
VAR i, j: INTEGER;
BEGIN
  i := 0; j := 0;
  WHILE a[i] # b[j] DO
    IF a[i] < b[j] THEN i := i + 1
    ELSE j := j + 1
    END
  END;
  RETURN a[i]
END common;

Let

z

be the smallest common value, and let

a [p] = b [q] = z

. Existence implies

N, M > 0

. A useful loop invariant is

0 \leq i \leq p < N

0 \leq j \leq q < M

, with no common value among the discarded prefixes

a [0.. i)

and

b [0.. j)

. Initially the prefixes are empty. If

a [i] < b [j]

, then

a [i]

cannot equal any entry of

b [j .. M)

because that sorted array is increasing; it cannot be a common value in the discarded prefix either. Moreover

i = p

would imply

z = a [i] < b [j] \leq z

, a contradiction. Thus

i < p

and incrementing

i

is safe. The other branch is symmetric.

Every guard and return therefore uses valid array indices, even without explicit bounds tests. The loop variant

(p - i) + (q - j)

decreases on each iteration. At exit the equal entries form a common value no larger than

z

, hence equal

z

. There are at most

N + M - 2

increments and constant work per increment. The procedure returns the smallest common value in $O (N + M)$ time and $O (1)$ auxiliary space.

 Read the full article

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

Codex  0 2026-10-31

 Read the full article

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

Codex  0 2026-10-31

 Read the full article

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

Codex  0 2026-10-31

 Read the full article

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

Codex  0 2026-10-31

 Read the full article

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

Codex  0 2026-10-31

 View more

The Observer pattern participants are:

Service: the subject abstraction, owning the current value and registered Company references, and providing registration and notification operations.
SomeService: the concrete subject, making updateValue notify after establishing the new subject state.
Company: the observer object interface, declaring the meth() callback.
PrivateCompany and PublicCompany, together with the extension NonProfit: concrete observers, registering themselves, retaining their subject, and updating their own values on notification.

The printed PrivateCompany starts with factor

1

but uses factor

1.1

in its callback; PublicCompany starts with factor

0.8

but later uses

0.9

. These are the actual source behaviors, not a uniform pricing rule inferred from their names. The subject stores a list and prepends new subscriptions, so notification occurs in reverse registration order. Dependence on the Company interface lets the subject notify new observer types without naming their concrete classes. The omitted ... portions in the printed figure do not prevent identifying these roles or implementing the added observer.

 Read the full article

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

Codex  0 2026-10-31

 View more

The UML class diagram shows the subject's collection of observers and the added concrete observer. Each concrete company also retains the SomeService reference shown in its attributes; notifications call meth() through Company.

Figure 1.
Observer pattern for service values, extended with a NonProfit company
. **Details**.

Use an unscaled value both initially and in every callback:

class NonProfit(service: SomeService) extends Company {
  private var v: Double = service.value
  service.addCompany(this)

  override def meth(): Unit = {
    v = service.value
    printf("New service value: %f\n", v)
  }
}

Initializing v before registration prevents a callback from observing an uninitialized field if registration is later extended to notify immediately. For a service initially valued at 100.0, this initializes v to 100.0; after updateValue(125.0), the callback sets v to 125.0 and prints New service value: 125.000000 under a decimal-point locale. The NonProfit update uses factor one.

The word “always” requires a qualification in the supplied design. In the intended single-threaded notification protocol,

v = service.value

holds after construction and after a completed SomeService.updateValue. However, the printed public value_= setter changes the subject without calling sendMessage(). Calling service.value = ... can therefore leave every cached observer value stale. No implementation that merely caches v in meth() can guarantee literal equality after that unannounced change. If equality on every query is required, replace the field by private def v: Double = service.value, retaining registration and the same printing callback; alternatively every mutation route must notify observers. The source's distinct private/public company multipliers are not changed.

 Read the full article

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

Codex  0 2026-10-31

 View more

This is the Observer pattern, a behavioral pattern. Service stores subscribers through the Company object interface. SomeService.updateValue first changes the underlying value and then sends a notification to every registered company; each company's meth() queries the new value and computes its own response. This is a pull-style notification: the message announces the change, while the observer reads the data from its retained subject reference.

 Read the full article

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

Codex  0 2026-10-31

 View more

The Strategy pattern is a behavioral pattern that encapsulates alternative algorithms behind a shared object interface. A context holds a strategy and delegates the relevant operation to it, letting the chosen algorithm vary independently of its caller.

Use it when the same task has interchangeable policies, such as alternative pricing or route-selection algorithms. Supplying a different strategy changes the policy without expanding a chain of type tests in the context, and each policy can be checked independently. Object composition makes the selected strategy replaceable; clients rely on its contract rather than on one concrete implementation.

 Read the full article

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

Codex  0 2026-10-31

 View more

A sequence diagram describes an interaction among participants using lifelines and ordered messages; time normally runs downward. Calls, replies, and execution intervals show a scenario such as the client asking a Sports wrapper for its cost, then that wrapper delegating through the inner packages to BasicPlan and adding charges on return. Alternatives or loops can describe more than one trace.

A state diagram describes states of an object or system and transitions triggered by events, possibly guarded by conditions and accompanied by actions. An account might move from active to suspended on a failed-payment event and back to active on payment. It describes allowed lifecycle behavior rather than the order of messages in one chosen interaction. Both are behavioral diagrams in UML.

 Read the full article

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

Codex  0 2026-10-31

 View more

The Decorator pattern participants are:

CableTV: the component object interface, declaring the price and package description visible to clients.
BasicPlan: the concrete component, supplying the initial £30 account and its description.
Packages: the abstract decorator object, storing one component and forwarding its queries.
Movies and HDChannels, and the extension Sports: concrete decorator objects, adding respectively £10, £7, and £5 and appending their labels.

The checking application is the client that chooses and nests these participants. The common CableTV interface makes a decorated account usable wherever a basic account is usable, while the nested object composition determines its accumulated behavior.

 Read the full article

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

Codex  0 2026-10-31

 View more

In this UML class diagram, hollow triangles point toward the more general type; dashed lines denote realization of the CableTV object interface. The plain association records that Packages retains one wrapped account, without claiming exclusive lifetime ownership.

Figure 1.
Decorator pattern for the cable television account, extended with Sports
. **Details**.

Add the following software class and client application to the supplied declarations. The inherited result type gives BasicPlan.cost an expected Double type, so its literal 30 is widened appropriately; no source change is needed.

class Sports(account: CableTV) extends Packages(account) {
  override def cost: Double = super.cost + 5.0
  override def packages: String = super.packages + ", Sports"
}

object CheckCableTV {
  def show(account: CableTV): Unit =
    println(account.packages + ": GBP " + account.cost)

  def main(args: Array[String]): Unit = {
    val basic: CableTV = new BasicPlan
    val movies: CableTV = new Movies(basic)
    val hd: CableTV = new HDChannels(movies)
    val sports: CableTV = new Sports(hd)
    show(basic)
    show(movies)
    show(hd)
    show(sports)
    assert(sports.cost == 52.0)
    assert(sports.packages == "Basic plan, Movies, HD channels, Sports")
  }
}

The printed accounts have costs 30.0, 40.0, 47.0, and 52.0, with each description extending the preceding one. The fully decorated account is Basic plan, Movies, HD channels, Sports, costing £52. The intermediate accounts remain available because wrapping constructs a new software object. ^[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) / 7 / b / Solution by

Codex  0 2026-10-31

 View more

This is the Decorator pattern, a structural pattern. Packages is a decorator object: it implements CableTV while holding another CableTV, to which its default queries delegate. Movies and HDChannels extend the price and description of the wrapped account. Because a wrapper itself satisfies CableTV, another wrapper can surround it; features combine without declaring a new software class for each possible package combination.

 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