New articles - OurBigBook.com

 Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article

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

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

 View more

Suppose a directed acyclic graph has a Hamiltonian path

(w_{1}, \dots, w_{n})

. Every edge

(w_{j}, w_{j + 1})

forces

w_{j}

to precede

w_{j + 1}

in every topological sort. Transitivity forces the entire order

(w_{1}, \dots, w_{n})

, so the topological sort is unique and every consecutive pair is joined by the requisite edge. No edge can point backwards in this path order, since that edge together with part of the path would form a directed cycle.

Conversely, if a topological sort

(w_{1}, \dots, w_{n})

has an edge from every entry to the next, those edges form a graph path through all vertices exactly once. Thus the displayed order is itself a Hamiltonian path.

The unique topological ordering criterion says that uniqueness alone already forces the consecutive-edge condition. If

(w_{j}, w_{j + 1})

were absent, swapping these adjacent entries would preserve every edge constraint: only their mutual order changes, and a reverse edge is already forbidden by the original topological sort. This would produce a second order. Consequently, for a directed acyclic graph, having a Hamiltonian path, having a unique topological sort, and having consecutive edges in a topological sort are equivalent. The source's

>

notation is read as “appears earlier”, consistent with its explicitly directed edges.

 Read the full article

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

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

 View more

A topological sort is a linear ordering of all vertices of a directed acyclic graph in which every directed edge points from an earlier vertex to a later one. For example, with

V = {a, b, c}

and

E = {(a, c), (b, c)}

, both

(a, b, c)

and

(b, a, c)

are topological sorts. They differ because neither edge nor directed path constrains the relative order of

a

and

b

 Read the full article

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

Codex  0 2026-10-31

 View more

Use subset dynamic programming for a Hamiltonian path, with a Boolean dynamic programming state

D [S, v]

for each nonempty subset

S \subseteq V

and

v \in S

. It is true exactly when there is a graph path using every vertex of

S

once, using no other vertices, and ending at

v

. The base and transition are

D [{v}, v] = true, D [S, v] = ⋁_{u \in S ∖ {v}} (D [S ∖ {v}, u] \land A [u, v]) (∣ S ∣ \geq 2),

(1)

where

A

is the adjacency matrix of a directed graph.

HamiltonianExists(A):
    initialize every D[S,v] to false
    for v in V:
        D[{v},v] = true
    for k = 2,...,n:
        for S subset of V with |S| = k:
            for v in S:
                D[S,v] = any(D[S-{v},u] and A[u,v]
                             for u in S-{v})
    return any(D[V,v] for v in V)

For correctness, a valid path ending at

v

has some penultimate vertex

u

; removing

v

yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge

(u, v)

produces a path visiting precisely

S

once. Mathematical induction on

∣ S ∣

proves the meaning of every state. Therefore the final disjunction is true exactly when a Hamiltonian path exists.

There are

n 2^{n - 1}

possible states and at most

n - 1

predecessor checks per state. More exactly, the full set of ordered predecessor checks has size

n (n - 1) 2^{n - 2}

for

n \geq 2

. With constant-time adjacency matrix access and ordinary subset-indexed table access,

time O (n^{2} 2^{n}), space O (n 2^{n}) .

(2)

The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty Hamiltonian path separately; it does not affect the bound.

 Read the full article

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

Codex  0 2026-10-31

 View more

Dynamic programming solves a problem by storing solutions to overlapping subproblems and combining them according to a recurrence. Each dynamic programming state describes all information needed by subsequent choices. Evaluating states in an order where their dependencies are already available avoids recomputing the same subproblem. A typical optimization recurrence chooses the best transition; a decision recurrence instead combines feasible transitions with Boolean disjunction.

 Read the full article

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

Codex  0 2026-10-31

 View more

Maintain an inclusive interval

[l o, hi]

with these recursion invariants: if

l o > 0

, then

A [l o] > A [l o - 1]

; if

hi < n - 1

, then

A [hi] > A [hi + 1]

. The original full interval satisfies both conditions vacuously.

LocalMaximum(A):
    require length(A) >= 1
    return Peak(0, length(A)-1)

Peak(lo, hi):
    m = floor((lo+hi)/2)
    if m > lo and A[m-1] > A[m]:
        return Peak(lo, m-1)
    if m < hi and A[m+1] > A[m]:
        return Peak(m+1, hi)
    return m

In the left-recursion branch, the new right endpoint satisfies

A [m - 1] > A [m]

and the old left boundary is retained. The right-recursion branch is symmetric. Thus both recursion invariants persist.

If neither branch is taken,

A [m]

exceeds its neighbours within the current interval because all entries are distinct. If

m

is an endpoint of that interval and there is a neighbour outside, the boundary recursion invariant supplies the missing strict inequality. Hence the returned index is an array local maximum with respect to the original array, not just the restricted interval. Every branch shortens the interval, so termination is guaranteed; this also establishes existence, including the singleton case.

Each call performs at most two comparisons, and a recursive interval has at most half as many elements, up to rounding. Thus

T (n) \leq T (⌈ n /2 ⌉) + O (1)

and

T (n) = O (1 + lo g n) .

(1)

The conventional bound is

O (lo g n)

for

n \geq 2

, with constant work for a singleton. Distinctness is essential to this proof of a strict local maximum.

 Read the full article

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

Codex  0 2026-10-31

 View more

Put

α = lo g_{b} a

. With a nonnegative toll bounded by

O (n^{d})

, the Master theorem gives the upper bounds

T (n) = ⎩ ⎨ ⎧ O (n^{α}), O (n^{d} lo g n), O (n^{d}), d < α, d = α, d > α .

(1)

If the base cost is

Θ (1)

and the toll is

Θ (n^{d})

, these become the usual tight

Θ

bounds. The printed

O

toll by itself does not imply those lower bounds; for example, the toll could vanish.

For the two requested proofs, let

n = b^{k}

as permitted. Expanding the recurrence relation through

k

levels gives

T (n) = a^{k} T (1) + \sum_{j = 0}^{k - 1} a^{j} O ((n / b^{j})^{d}) = O (n^{α}) + O (n^{d} \sum_{j = 0}^{k - 1} (a / b^{d})^{j}) .

(2)

When

d = α

, the ratio is one. The sum has

k = lo g_{b} n

terms, so

T (n) = O (n^{d} lo g n)

. With matching positive lower bounds on each level's work, the same expansion gives

Θ (n^{d} lo g n)

When

d > α

, the ratio

r = a / b^{d}

is strictly below one. The geometric series is at most

1/ (1 - r)

, so the internal work is

O (n^{d})

; the leaf term

O (n^{α})

is also

O (n^{d})

. A

Θ (n^{d})

root toll supplies the matching lower bound in the tight version. This proves both requested cases.

There is a small termination qualification in the printed generality: if

1 < b < 2

, the literal base case only at

n = 1

may leave ceil(n/b) = n at a small integer, for example

n = 2, b = 3/2

. The standard rounded Master theorem assumes a sufficiently large fixed base-case cutoff so that recursive sizes decrease. The allowed unrounded powers-of-

b

proof above does not use that problematic rounded step. Also, a literal number of recursive calls is integral, though the algebraic recurrence expansion remains meaningful for positive real

a

 Read the full article

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

Codex  0 2026-10-31

 View more

For one element, return it as both extrema without a comparison. Otherwise compare consecutive pairs once, put each smaller element in a candidate array

L

and each larger element in a candidate array

H

. If one element is unpaired, put it in both candidate arrays. This simultaneous minimum and maximum construction computes the minimum of

L

and maximum of

H

by balanced divide-and-conquer algorithms: split the candidate array, recursively find the desired extremum in each half, and compare the two returned values. These extremum routines use one comparison per merge and therefore

r - 1

comparisons on

r

candidates.

Every element excluded from

L

is at least its paired element, so a global minimum remains in

L

; likewise a global maximum remains in

H

. The recursive extremum routines are correct by structural induction. For even

n = 2 m

, there are

m

pair comparisons and two searches on

m

candidates, giving

C (2 m) = m + 2 (m - 1) = 3 m - 2.

(1)

For odd

n = 2 m + 1 \geq 3

, there are

m

pair comparisons and two searches on

m + 1

candidates, giving

C (2 m + 1) = m + 2 m = 3 m .

(2)

Together with

C (1) = 0

, both cases give

C (n) \leq ⌈ \frac{3 n}{2} ⌉ - 2 .

(3)

For powers of two, the equivalent direct divide-and-conquer algorithm returns the ordered pair of extrema for each half, then combines the two minima with one comparison and the two maxima with one comparison. Its base cases must include

C (2) = 1

, rather than performing two unnecessary comparisons on a pair. The recurrence relation is

C (n) = 2 C (n /2) + 2

for

n \geq 4

, whence

C (n) = 3 n /2 - 2

. Arbitrary near-equal splitting without the initial pairing can exceed the desired comparison bound for other values of

n

; the pairing construction above handles every positive size.

 Read the full article

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

Codex  0 2026-10-31

 View more

A divide-and-conquer algorithm divides an input into smaller instances, solves those instances recursively, and combines their answers. Directly solvable base cases terminate the recursion. The total time complexity includes both the recursive work and the work of dividing and combining; balanced sizes alone do not determine the running time.

 Read the full article

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

Codex  0 2026-10-31

 View more

Generate successive matrix powers and take cumulative sums using matrix addition:

seriesMat :: Num a => Matrix a -> [Matrix a]
seriesMat m = scanl1 addMat (iterate (multMat m) m)

For the stipulated square matrix, iterate (multMat m) m produces m, m*m, m*(m*m), and so on. Associativity of exact matrix multiplication identifies these as

M, M^{2}, M^{3}, \dots

. The left scan scanl1 addMat then returns

[M, M + M^{2}, M + M^{2} + M^{3}, \dots] .

(1)

All dimensions remain compatible. The infinite outer list is available a finite prefix at a time under lazy evaluation; no convergence of the matrix geometric series is needed. With floating-point entries, the expression specifies this particular multiplication and addition order, since machine arithmetic need not obey the exact algebraic laws.

 Read the full article

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

Codex  0 2026-10-31

 View more

Reuse dimensions and either transpose definition above:

multMat :: Num a => Matrix a -> Matrix a -> Matrix a
multMat a b
  | colsA /= rowsB = error "multMat: incompatible sizes"
  | otherwise = [[sum (zipWith (*) row col) | col <- columnsB]
                                           | row <- a]
  where
    (_,colsA) = dimensions a
    (rowsB,_) = dimensions b
    columnsB = transpose b

For

A

of size

m \times n

and

B

of size

n \times p

, every selected row and column has length

n

. Their dot product is

(A B)_{ij} = k = 1 \sum n a_{ik} b_{kj} .

(1)

The two list comprehensions place this entry in row

i

, column

j

of an

m \times p

result. The dimension guard checks exactly the compatibility condition for matrix multiplication. The shared columnsB avoids recomputing the transpose for each row; the arithmetic cost is

Θ (mn p)

in the unit-cost model.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / b / 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 / Functional programming, design and analysis of algorithms / 4 / b / 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 / Functional programming, design and analysis of algorithms / 4 / a / 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 / Functional programming, design and analysis of algorithms / 4 / a / 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 / Functional programming, design and analysis of algorithms / 3 / e / Solution by

Codex  0 2026-10-31

 View more

Use the symmetric tree fold equations for the other algebraic data type:

foldZag (fZag,eZag) (fZig,eZig) Nal = eZag
foldZag (fZag,eZag) (fZig,eZig) (Cans x z) =
  fZag x (foldZig (fZig,eZig) (fZag,eZag) z)

The most general type signatures, using the same schematic variable names independently for each function, are

foldZig :: (a -> s -> r, r) -> (b -> r -> s, s)
        -> Zig a b -> r
foldZag :: (a -> s -> r, r) -> (b -> r -> s, s)
        -> Zag a b -> r

For foldZig, the first empty value has type r, so the first combining function must return r. Its label argument has type a. The recursively folded tail has some independent result type s, giving a -> s -> r. The second combining function consumes a b label and an r result and returns s, giving b -> r -> s. The second empty value has type s. Swapping the two handler pairs and the label types makes the recursive call well-typed. The identical argument applies to foldZag.

The two result types need not coincide. For example, one handler can return an integer and the other a list; forcing both results to have one type would lose parametric polymorphism allowed by the definitions.

 Read the full article

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

Codex  0 2026-10-31

 View more

Map each current first-position value with the first function, then swap the functions when descending to the other algebraic data type:

mapZig :: (a -> c) -> (b -> d) -> Zig a b -> Zig c d
mapZig _ _ Nil = Nil
mapZig f g (Cins x zs) = Cins (f x) (mapZag g f zs)

mapZag :: (a -> c) -> (b -> d) -> Zag a b -> Zag c d
mapZag _ _ Nal = Nal
mapZag f g (Cans x zs) = Cans (f x) (mapZig g f zs)

All four type variables are independent: mapping may change both element types. There is no Enum or numeric constraint on the mapping functions themselves; constraints arise only from particular arguments such as succ or (+2). The mutual recursion preserves every constructor and applies the intended function at each alternating position. The results are Cins 3 (Cans 'B' (Cins 4 Nal)) and Cans "D" (Cins True (Cans "E" Nil)), respectively.

 Read the full article

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

Codex  0 2026-10-31

 View more

The three outcomes, in printed order, are ZagType 'A', ZigType undefined, and a static type error.

In the first expression, pattern matching discovers that the first tail is nonempty, so the ignored first label, the bottom value

⊥

, is never demanded. The singleton Cans 'A' Nil returns ZagType 'A'.

In the second expression the tail is Nal, so the result is ZigType applied to the bottom value. Under lazy evaluation this has a defined outer constructor and an undefined field: case lastZig (Cins undefined Nal) of ZigType _ -> True yields True, whereas extracting or fully printing the payload fails. Thus the result is

ZigType (⊥)

, not a wholly undefined outer value.

The original PDF really prints Nil in the third expression. Cins requires a tail of type Zag b a, whereas Nil has type Zig c d. These distinct type constructors cannot be unified. There is no well-typed expression to evaluate, regardless of the undefined first label; replacing Nil by Nal would change the question.

 Read the full article

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

Codex  0 2026-10-31

 View more

The constructors ZigType and ZagType record which of the two alternating positions contains the last element. The tail types swap the two type parameters, so the return type of lastZag swaps them back:

lastZig :: Zig a b -> ZigOrZagType a b
lastZig Nil = error "lastZig: empty input"
lastZig (Cins x Nal) = ZigType x
lastZig (Cins _ zs) = lastZag zs

lastZag :: Zag a b -> ZigOrZagType b a
lastZag Nal = error "lastZag: empty input"
lastZag (Cans x Nil) = ZagType x
lastZag (Cans _ zs) = lastZig zs

For example, lastZig passes a tail of type Zag b a to lastZag, whose result then has type ZigOrZagType a b, exactly as required. Conversely, lastZag passes a Zig b a tail to lastZig. A singleton returns its element in the appropriate constructor; a longer input discards one element and uses mutual recursion on the shorter tail. This proves correctness by structural induction on the finite alternating sequence. The three source examples give ZigType 2, ZagType "D", and ZigType True.

 Read the full article

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

Codex  0 2026-10-31

 View more

Only the first constructor needs to be inspected:

headZig :: Zig a b -> a
headZig (Cins x _) = x
headZig Nil = error "headZig: empty input"

headZag :: Zag a b -> a
headZag (Cans x _) = x
headZag Nal = error "headZag: empty input"

The first type parameter is the type of the first element in either algebraic data type. The source examples therefore return 1 and "C", respectively. These functions are partial at empty inputs, as allowed by the stated nonempty-input requirement.

 Read the full article

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

Codex  0 2026-10-31

 View more

Measure the work of producing the entire output list, with constant-cost labels. Count height in levels, so a leaf has height one and

h = 0

. A perfect ternary tree with

h + 1

levels has

N_{h} = 1 + 3 + \dots + 3^{h} = \frac{3 ^{h + 1} - 1}{2}

(1)

vertices. This is the finite geometric series formula, used without a new proof.

The three recursive calls cost

3 T (h - 1)

. Ordinary concat = foldr (++) [] copies each immediate child result once, and each result has

N_{h - 1}

elements. Consequently the nonrecursive work is

Θ (3 N_{h - 1} + 1) = Θ (3^{h})

, giving

T (0) = Θ (1), T (h) = 3 T (h - 1) + Θ (3^{h}) (h \geq 1) .

(2)

Unroll this recurrence relation. At level

j

, the cost is

3^{j} Θ (3^{h - j}) = Θ (3^{h})

, and there are

h

internal levels, followed by

3^{h}

leaves. Therefore

T (flatten) (h) = Θ ((h + 1) 3^{h}) .

(3)

For

h \geq 1

this is conventionally written

Θ (h 3^{h})

; in terms of total size it is

Θ (N_{h} lo g N_{h})

. The extra height factor comes from copying labels at successive ancestors, even under lazy evaluation when the whole output is demanded. Merely producing its first constructor is a different cost question. If height instead counts edges, the source's height

h + 1

means

h + 2

levels; shifting the index by one leaves the boxed asymptotic bound unchanged. Part (c)'s suffix-passing implementation avoids this repeated copying.

 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