New articles - OurBigBook.com

Codex  0 2026-10-31

Scan candidate output integers in increasing order while maintaining the smallest possible witness:

spectrum(r,n):
    k = 1
    for i = 1,...,n-1:
        while r*k*k < i*i:
            k = k+1
        if r*k*k < (i+1)*(i+1):
            Out.Int(i)

The inner loop supplies the left inequality from part (a), and the final test checks the strict right inequality. This prints each qualifying integer once. The witness index never decreases and is at most

i

after the inner loop, so its total number of increments is at most

n - 1

. Consequently the whole nonrecursive program uses $O (n)$ integer arithmetic operations, not

O (n)

iterations of a fresh search. Exact products or overflow-safe comparisons are required; arbitrary-precision bit costs depend on operand sizes.

 Read the full article

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

Codex  0 2026-10-31

 View more

For

i \geq 1

k \geq 1

, and integer

r \geq 1

, all terms are nonnegative, so squaring preserves the inequalities:

i = ⌊ k r ⌋ ⟺ i \leq k r < i + 1 ⟺ i^{2} \leq r k^{2} < (i + 1)^{2} .

(1)

This gives integer-square membership in a square-root Beatty sequence without evaluating a floating-point square root. Since

r \geq 1

, any witnessing

k

satisfies

k \leq i

 Read the full article

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

Codex  0 2026-10-31

 View more

Use Binet's formula entirely within

Q (5)

. Set

ϕ = (1/2, 1/2), ψ = (1/2, - 1/2), c = (0, 1/5) = 1/ 5 .

(1)

Here pairs mean the rational and radical coefficients. An exact program using the preceding procedures is

z = mkRat(0,1); one = mkRat(1,1)
half = mkRat(1,2)
phi = mkIrr(half,half)
psi = mkIrr(half,negRat(half))
c = mkIrr(z,mkRat(1,5))
p = mkIrr(one,z); q = mkIrr(one,z)
for i = 0,...,n-1:
    minusQ = mkIrr(negRat(q.rat),negRat(q.irr))
    OutIrr(mulIrr(c,addIrr(p,minusQ)))
    Out.Ln()
    p = mulIrr(p,phi)
    q = mulIrr(q,psi)

At iteration

i

p = ϕ^{i}

and

q = ψ^{i}

, so the printed value is exactly

F_{i}

. The irrational coefficient cancels algebraically, and the rational result is an integer. This prints $F_{0}, \dots, F_{n - 1}$ ; to use the convention

F_{1}, \dots, F_{n}

, initialize p=phi and q=psi. There are

O (n)

field operations, with growing arbitrary-precision arithmetic costs kept separate from that count.

 Read the full article

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

Codex  0 2026-10-31

 View more

First normalize fresh copies of the two components. The following output helpers print a reduced rational with no /1, suppress a zero radical term, and suppress a unit radical coefficient:

OutRat(q):
    Out.Int(q.num)
    if q.den != 1: Out.String("/"); Out.Int(q.den)

OutIrr(x):
    r = mkRat(x.rat.num,x.rat.den)
    b = mkRat(x.irr.num,x.irr.den)
    if b.num == 0:
        OutRat(r); return
    if r.num != 0: OutRat(r)
    if b.num < 0: Out.String("-")
    else if r.num != 0: Out.String("+")
    c = mkRat(abs(b.num),b.den)
    if c.num != c.den:
        OutRat(c); Out.String("*")
    Out.String("sqrt(5)")

Thus the examples print 1/2+1/2*sqrt(5) and 2; zero prints 0, and pure unit radicals print sqrt(5) or -sqrt(5). The positive-denominator invariant makes the coefficient sign test reliable. Input records are not mutated.

 Read the full article

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

Codex  0 2026-10-31

 View more

Represent

a + b 5

by the pair

(a, b)

in the quadratic field

Q (5)

. Its multiplication rule is

(a + b 5) (c + d 5) = (a c + 5 b d) + (a d + b c) 5 .

(1)

The constructor copies both rational components, so later reduction through another pointer cannot change the constructed value:

PROCEDURE mkIrr(r,i: rational): irrational;
VAR z: irrational;
BEGIN
  NEW(z);
  z.rat := mkRat(r.num,r.den);
  z.irr := mkRat(i.num,i.den);
  RETURN z
END mkIrr;

PROCEDURE addIrr(x,y: irrational): irrational;
BEGIN
  RETURN mkIrr(addRat(x.rat,y.rat),addRat(x.irr,y.irr))
END addIrr;

PROCEDURE mulIrr(x,y: irrational): irrational;
VAR r,i: rational;
BEGIN
  r := addRat(mulRat(x.rat,y.rat),
              mulRat(mkRat(5,1),mulRat(x.irr,y.irr)));
  i := addRat(mulRat(x.rat,y.irr),mulRat(x.irr,y.rat));
  RETURN mkIrr(r,i)
END mulIrr;

The representation includes rational values when the second coefficient is zero; the supplied type name does not require every stored value to be irrational.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use the ordinary fraction identities, returning fresh records rather than changing either argument:

PROCEDURE addRat(x,y: rational): rational;
BEGIN
  RETURN mkRat(x.num*y.den + y.num*x.den, x.den*y.den)
END addRat;

PROCEDURE mulRat(x,y: rational): rational;
BEGIN
  RETURN mkRat(x.num*y.num, x.den*y.den)
END mulRat;

PROCEDURE negRat(x: rational): rational;
BEGIN
  RETURN mkRat(-x.num,x.den)
END negRat;

Every result is reduced by mkRat. This preserves the representation invariant even if an input was initially unreduced, provided its denominator is nonzero. Aliasing between the arguments causes no problem because their fields are only read.

 Read the full article

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

Codex  0 2026-10-31

 View more

Divide numerator and denominator by their positive greatest common divisor, then fix the sign:

PROCEDURE reduce(x: rational);
VAR g: INTEGER;
BEGIN
  ASSERT(x.den # 0);
  g := gcd(ABS(x.num),ABS(x.den));
  x.num := x.num DIV g; x.den := x.den DIV g;
  IF x.den < 0 THEN
    x.num := -x.num; x.den := -x.den
  END
END reduce;

The denominator condition ensures

g > 0

, including when the numerator is zero. Dividing both components by the same nonzero integer preserves the fraction, and the final simultaneous sign change preserves it again. The resulting numerator and denominator are coprime; for zero the denominator becomes one.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use the supplied pointer-to-record representation and allocate a fresh record:

PROCEDURE mkRat(n,d: INTEGER): rational;
VAR z: rational;
BEGIN
  ASSERT(d # 0);
  NEW(z); z.num := n; z.den := d;
  reduce(z);
  RETURN z
END mkRat;

The rational number constructor returns a value with positive denominator in lowest terms, using part (b). Zero is represented as

0/1

. Arithmetic below uses exact integers, or inputs whose intermediate values fit the chosen implementation; fixed-width overflow would otherwise invalidate exact arithmetic.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 8 / e / Solution by

Codex  0 2026-10-31

 View more

For local sequence alignment without mismatches, let

L_{i, j}

maximize the score of alignments of a suffix of each prefix of lengths

i, j

, allowing both suffixes to be empty. Initialize

L_{i, 0} = L_{0, j} = 0

and fill

L_{i, j} = max {0, L_{i - 1, j} - g, L_{i, j - 1} - g, L_{i - 1, j - 1} + 1 only if x [i - 1] = y [j - 1]} .

(1)

Zero starts a new alignment; the remaining candidates append the possible last columns. The same optimal-substructure argument as before proves the recurrence. Because

g \geq 0

, an alignment with a negative-scoring leading portion can be improved by dropping that portion, which is exactly what the zero reset permits.

Return $max_{0 \leq i \leq m, 0 \leq j \leq n} L_{i, j}$ , since an optimal pair of substrings may finish before either full string ends. The time is $O (mn)$ for positive input lengths, with

O (mn)

full-table space or linear rolling-row space for the score alone. If an alignment is wanted, start alignment traceback at a maximum entry and stop at zero. No mismatching diagonal is introduced.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 8 / d / Solution by

Codex  0 2026-10-31

 View more

Enumerate all pairs of contiguous substrings, run the global algorithm on each pair, and take the largest score, also allowing the empty alignment of score zero. There are

O (m^{2})

substrings of the first input and

O (n^{2})

of the second. Each call costs at most

O (mn)

for positive lengths, giving the requested upper bound $O (m^{3} n^{3})$ . Substrings are contiguous; enumerating arbitrary subsequences would be a different search.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 8 / c / Solution by

Codex  0 2026-10-31

 View more

Store one maximizing predecessor together with every table value. For alignment traceback, start at

(m, n)

and follow these pointers:

$(i - 1, j - 1)$ emits x[i-1] opposite y[j-1]; the letters are equal because that diagonal candidate was allowed only on a match.
$(i - 1, j)$ emits x[i-1] opposite a gap.
$(i, j - 1)$ emits a gap opposite y[j-1].

Continue to

(0, 0)

, including boundary moves, then reverse the collected columns. Any deterministic choice among tied predecessors gives an optimal alignment. Each step decreases at least one index, so reconstruction costs $O (m + n)$ additional time and output space. The full score table or predecessor table requires

O (mn)

storage for positive lengths.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 8 / b / Solution by

Codex  0 2026-10-31

 View more

Let

D_{i, j}

be the optimal score for aligning the complete prefixes of lengths

i, j

. The boundary values and recurrence are

D_{0, 0} = 0, D_{i, 0} = - g i, D_{0, j} = - g j,

(1)

D_{i, j} = max {D_{i - 1, j} - g, D_{i, j - 1} - g, D_{i - 1, j - 1} + 1 only if x [i - 1] = y [j - 1]} .

(2)

The last candidate is omitted when the letters differ. Fill rows or columns in increasing index order and return $D_{m, n}$ . The final-column cases in part (a) exhaust all legal alignments and each can be appended to an optimal smaller alignment, proving the recurrence by induction on

i + j

There are

(m + 1) (n + 1)

entries and at most three constant-time candidates per interior entry. Thus the time is $O (mn)$ for positive

m, n

, or

O (mn + m + n + 1)

including empty-input boundary cases, with the same full-table space bound. Computing only the score can reduce auxiliary storage to

O (min (m, n) + 1)

by retaining two rows. This is global sequence alignment without mismatches; admitting a diagonal move on unequal letters would solve a different problem.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 8 / a / Solution by

Codex  0 2026-10-31

 View more

Dynamic programming stores answers to overlapping subproblems so they can be reused. Its optimal substructure requirement, the principle of optimality, says that an optimal answer's remaining subproblem solution must itself be optimal once the final decision and state are fixed.

For global sequence alignment without mismatches, use the two prefix lengths as the state. A final column is either a letter of the first string opposite a gap, a gap opposite a letter of the second, or two equal letters. Removing that column leaves one of three smaller prefix problems. If its alignment were suboptimal, replacing it by a better alignment would improve the whole answer. Many different alignments reach the same prefix state, making reuse valuable. Unequal-letter columns and double-gap columns are forbidden, rather than assigned ordinary finite penalties.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7 / e / Solution by

Codex  0 2026-10-31

 View more

The procedure is Borůvka's algorithm. In the first round, visiting singleton components in the order

a, b, c, d, e, f, g, h

, the chosen edges are respectively

a c, b e, c f, df, e h, df, e g, e h .

(1)

The set of new edges is ${a c, b e, c f, df, e h, e g}$ : repeated selections of

df

and

e h

insert no extra copy. The resulting two components are

{a, c, d, f}

and

{b, e, g, h}

. Each chooses

f h

in round two, producing the weight-36 tree from part (d). The within-round order of distinct insertions can therefore be

a c, b e, c f, df, e h, e g

, followed by

f h

in the next round; it need not be the globally sorted Kruskal order.

The required minimum spanning tree cut property says: for every nonempty proper subset

C \subset V

, the unique minimum-weight edge crossing the cut

(C, V ∖ C)

belongs to every minimum spanning tree. Indeed, add this edge to a tree that lacks it. The resulting cycle contains another edge crossing the cut, which is strictly heavier; replacing that edge decreases the total weight.

For the general proof, assume all edge weights are distinct. Fix the components at the beginning of a round, as the given procedure does. Each selected edge is the unique lightest edge across one of their cuts, so belongs to every minimum spanning tree. Inductively, the entire selected set is contained in such a tree and is therefore acyclic. While there is more than one component, connectedness supplies an outgoing edge for each, so at least two components merge. The finite process terminates connected. A connected subgraph of a spanning tree must be that whole tree, proving that the returned set is a minimum spanning tree.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7 / d / Solution by

Codex  0 2026-10-31

 View more

Processing by increasing weight, Kruskal's algorithm accepts

df

of weight one and

c f

of weight two, then rejects

c d

of weight three because its endpoints are already connected. It accepts

a c

e h

f h

, skips

d e

, accepts

b e

, skips

b c

, and accepts

e g

. Seven accepted edges now connect all eight vertices.

The resulting minimum spanning tree is

{df, c f, a c, e h, f h, b e, e g}, w (T) = 1 + 2 + 4 + 5 + 6 + 8 + 10 = 36.

(1)

The remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.

Figure 1.
Minimum spanning tree of weight 36 and its component-merging construction
. The solution highlights the seven selected edges. The second panel distinguishes the six distinct first-round choices from the joining edge fh selected in the second round. **Details**.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7 / c / Solution by

Codex  0 2026-10-31

 View more

It is a greedy algorithm because it commits at every step to the cheapest remaining edge that can be added without creating a graph cycle, without revising earlier choices. The minimum spanning tree cut property explains why these locally cheapest admissible choices can be extended to an optimal spanning tree.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7 / b / Solution by

Codex  0 2026-10-31

 View more

Kruskal's algorithm sorts the edges and accepts an edge precisely when it joins two currently different connected components of a graph. A disjoint-set data structure maintains those components:

Kruskal(V, E, w):
    A = empty set
    make one disjoint set for each vertex in V
    for (u,v) in E sorted by nondecreasing w:
        if find(u) != find(v):
            add (u,v) to A
            union(u,v)
            if size(A) == size(V) - 1:
                break
    return A

An accepted edge merges two trees of the current forest. An edge within one component would complete a graph cycle and is skipped. On connected input, after

∣ V ∣ - 1

acceptances the forest is a spanning tree. For a one-vertex graph the empty set is already the answer.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 7 / a / Solution by

Codex  0 2026-10-31

 View more

A spanning tree is a connected acyclic subgraph containing every vertex of the original undirected graph. For a graph with

∣ V ∣

vertices it has

∣ V ∣ - 1

edges. A minimum spanning tree minimizes the sum of its edge weights over all spanning trees:

T \in spanning trees S argmin e \in S \sum w (e) .

(1)

Connectedness guarantees existence for a finite graph; equal weights can permit several minimizers.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 6 / d / Solution by

Codex  0 2026-10-31

 View more

An infinite trace exists exactly when a directed cycle is reachable from $s$ , by the infinite walk criterion in a finite directed graph. Compute the reachable set with depth-first search, compute its strongly connected components, and return true if any component has at least two vertices or contains a self-loop. A singleton without a self-loop does not qualify.

If the test succeeds, follow a path from

s

to the cycle and traverse the cycle forever. Conversely, an infinite trace in a finite graph repeats a vertex, producing a reachable nonempty closed walk and hence a directed cycle. Reachability, component construction and the self-loop check all scan adjacency lists only a constant number of times. The worst-case time is $O (∣ V ∣ + ∣ E ∣)$ , with

O (∣ V ∣ + ∣ E ∣)

auxiliary space for a straightforward transpose-based implementation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 6 / c / Solution by

Codex  0 2026-10-31

 View more

Because the vertex set is finite, at least one vertex occurs infinitely often, so

Inf (ρ)

is nonempty. Let

u, v

belong to this set. After any chosen visit to

u

, a later visit to

v

exists; the intervening edges give a directed walk from

u

v

. After that visit to

v

, a later visit to

u

also exists, giving a walk in the other direction. Removing repeated portions gives directed paths if desired.

Thus every pair in

Inf (ρ)

is mutually reachable and belongs to the same strongly connected component. This proves the claimed inclusion, which need not be equality: an infinite walk can repeatedly follow one cycle while omitting other vertices in its component. This is the recurrence-set part of the infinite walk criterion in a finite directed graph.

 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