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 / 2018 / Functional programming, design and analysis of algorithms / 6 / a / Solution by

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

 View more

There are three useful distinctions between dynamic programming and a conventional divide-and-conquer algorithm.

A divide-and-conquer algorithm typically splits one instance into mostly separate smaller instances; dynamic programming deliberately recognizes overlapping subproblems that recur along different decision histories.
A dynamic programming state is solved once and its result reused through a table or memoization. A direct divide-and-conquer algorithm normally combines the results of its recursive children without retaining a table indexed by all repeated states.
The dependency structure of a direct recursive decomposition is a recursion tree; dynamic programming evaluates a directed acyclic graph of states in dependency order, either bottom-up or by memoization. Its cost is the number of distinct states times the work per state, rather than the number of occurrences in the expanded recursion tree.

These are paradigm-level distinctions, not mutually exclusive definitions: a recursive algorithm can use memoization, and dynamic programming need not be implemented iteratively. For optimization, the dynamic programming state and optimal substructure justify combining stored optimum values; storing repeated work alone does not prove the state is sufficient.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 5 / d / 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 / 2018 / Functional programming, design and analysis of algorithms / 5 / d / 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 / 2018 / Functional programming, design and analysis of algorithms / 5 / c / Solution by

Codex  0 2026-10-31

 View more

Sort records (value,original_index) by value using merge sort. For each record with value

a

, run binary search for value

2 a

among the sorted records; return the two retained original indices at the first match, otherwise return nil after all records.

If a valid pair exists, its smaller entry is inspected and the matching doubled entry is found by binary search. Conversely every returned pair satisfies the requested equality. Positivity gives

2 a > a

, so the returned entries are distinct even if other entries repeat. Sorting costs

O (n lo g n)

, and at most

n

binary searches cost

O (n lo g n)

altogether. Total time is $O (n lo g n)$ , using the paper's unit-cost arithmetic model; doubling large machine integers would require overflow-safe arithmetic.

 Read the full article

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

Codex  0 2026-10-31

 View more

On a worst-case branch, the described sequential quarter-point tests make three equality tests per reduction, giving

Q (n) = Q (n /4) + 3

until constant size. Thus

Q (4^{k}) = 3 k + O (1)

. Ordinary binary search makes one equality test per halving:

B (n) = B (n /2) + 1

, so

B (4^{k}) = 2 k + O (1)

Both searches take $Θ (lo g n)$ time, but the specified quaternary search uses asymptotically $3/2$ as many equality tests. A quarter-sized branch does not compensate for the three sequential pivots. The numerical ratio concerns precisely the unit equality-test model in the paper; counting ordering comparisons, array accesses or a differently arranged pivot decision tree requires its own constants.

 Read the full article

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

Codex  0 2026-10-31

 View more

Merge sort splits the array into two halves, recursively sorts both and merges their sorted outputs. During the merge algorithm, compare the first unconsumed entry of each half, emit the smaller and advance that half; append the remainder when one half ends. The emitted prefix is always sorted and contains exactly the already consumed entries, proving the merge step correct. Induction on input length proves the full sorting algorithm correct.

The recurrence relation is

T (n) = 2 T (n /2) + Θ (n)

for powers of two, with constant base cost. In the Master theorem,

a = b = 2

and

n^{l o g_{b} a} = n

, matching the merge term. Hence $T (n) = Θ (n lo g n)$ . Floor/ceiling splits give the same bound for arbitrary

n

; conventional merging uses

O (n)

auxiliary space.

 Read the full article

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

Codex  0 2026-10-31

 View more

Represent the ranking criteria by a tuple in decreasing priority:

type Weight = (Int,Int,Int)

weight :: Results -> Weight
weight (Results _ scores) =
  (sum (map points scores),
   sum [gf - ga | (gf,ga) <- scores],
   sum (map fst scores))
  where
    points (gf,ga)
      | gf > ga   = 3
      | gf == ga  = 1
      | otherwise = 0

The components are total points, total goal difference and total goals scored. The Haskell Ord class compares tuples in lexicographic order, so a greater first component dominates all later components; only ties reach the next criterion. Exactly equal triples remain tied because no further ranking criterion was specified. In the supplied fixture data the descending triples are

(6, 13, 15)

(4, 3, 5)

(3, 0, 3)

(1, 0, 0)

(1, - 3, 4)

(1, - 3, 0)

and

(0, - 10, 0)

, respectively for United, Athletic, City, Albion, Rovers, Corinthians and Thistle.

 Read the full article

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

Codex  0 2026-10-31

 View more

Choose each team once using teams, then scan every match with that team as the reference perspective:

data Results = Results Team [(Int,Int)]

extract :: [[Match]] -> [Results]
extract days = [Results t (scores t) | t <- teams days]
  where
    games = concat days
    scores t = concatMap (contribution t) games
    contribution t (Match a ga b gb)
      | t == a    = [(ga,gb)]
      | t == b    = [(gb,ga)]
      | otherwise = []

In a valid match the teams are distinct. The first guard records the first team's goals-for and goals-against; the second reverses that perspective for the opponent. The common games binding preserves day/match order, although the result does not need a chronological ordering condition. Each team receives exactly one record because teams has no duplicates. The algorithm makes one scan per team; it deliberately prioritizes a transparent functional programming definition over an unrequested performance improvement.

 Read the full article

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

Codex  0 2026-10-31

 View more

Flatten the days, emit both participants of every match and remove repeated names:

teams :: [[Match]] -> [Team]
teams days = unique [t | Match a _ b _ <- concat days, t <- [a,b]]
  where
    unique []     = []
    unique (t:ts) = t : unique (filter (/= t) ts)

Every emitted name belongs to some match, and every participating team enters the intermediate list. At each recursive step, unique emits its first remaining name once and deletes precisely its later occurrences. Induction therefore proves both coverage and absence of duplicates. The output preserves first appearance; no particular team ordering was required. This simple list implementation can take quadratic time in the number of participant occurrences, which is permissible here; the question imposes no efficiency target.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use a type synonym for names and an algebraic data type with the two teams and their goals in the given positional order:

type Team = String
data Match = Match Team Int Team Int

Team is a synonym, not a new runtime wrapper. Match on the left is the type constructor, while the same spelling on the right is a data constructor in a different namespace. Its value-level type signature is Match :: Team -> Int -> Team -> Int -> Match.

 Read the full article

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

Codex  0 2026-10-31

 View more

Compose the three functions:

reverse :: [a] -> [a]
reverse = abs . rev . rep

The representation built by rep has

2 n + 1

constructors. rev preserves that count, and abs traverses it once. Their three linear bounds add to $Θ (n + 1)$ total time, improving the direct quadratic reversal. The correctness equations for representation, reversal and abstraction compose to the required reversed list.

 Read the full article

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

Codex  0 2026-10-31

 View more

Reverse the children and recursively reverse each child:

rev :: CatList a -> CatList a
rev Nil       = Nil
rev (One x)   = One x
rev (Cat l r) = Cat (rev r) (rev l)

The proof uses

reverse (x s + + ys) = reverse (ys) + + reverse (x s)

and structural induction. The complete representation is processed and reconstructed in $Θ (m)$ time. This is worst-case optimal for fully processing arbitrary explicit input representations with

m

constructors; the datatype allows output information to be hidden at any leaf. Lazy evaluation can expose only an initial part of a result sooner, and this statement does not assert that every partial observation costs

m

 Read the full article

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

Codex  0 2026-10-31

 View more

A concatenation tree may contain arbitrarily many Cat and Nil nodes while denoting an empty or singleton list. For example, repeatedly wrap One x as Cat Nil previous. The output length stays one while the input size grows without bound. An arbitrary leaf could hide another One, so a correct general conversion cannot disregard unexamined branches. Output length alone therefore cannot bound the work; input size must be included.

 Read the full article

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

Codex  0 2026-10-31

 View more

Carry the eventual output tail as an accumulator, thereby avoiding repeated list concatenation:

abs :: CatList a -> [a]
abs t = flatten t []
  where
    flatten Nil       zs = zs
    flatten (One x)   zs = x : zs
    flatten (Cat l r) zs = flatten l (flatten r zs)

The invariant is flatten t zs = denotation t ++ zs. It is immediate for Nil and One; at Cat, applying the two induction hypotheses and associativity of list concatenation proves it. In particular, the empty accumulator gives the required abstraction.

Each concatenation tree constructor is processed once, and each One emits one result cons. Consequently full production takes $Θ (m)$ time, where

m

is the input constructor count, on every tree shape. This is a difference list calculation written with an explicit tail, an instance of linear flattening of a binary tree. The call stack can have depth

m

for a badly skewed input; a linear time bound does not imply logarithmic stack space.

 Read the full article

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

Codex  0 2026-10-31

 View more

One simple right-associated representation is

rep :: [a] -> CatList a
rep []     = Nil
rep (x:xs) = Cat (One x) (rep xs)

It constructs two data constructors per input element and one final Nil, so full construction takes $Θ (n + 1)$ time and produces

2 n + 1

constructors. Structural induction shows that its denotation is the original list.

 Read the full article

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

Codex  0 2026-10-31

 View more

Three distinct concatenation tree representations of the empty list are Nil, Cat Nil Nil, and Cat (Cat Nil Nil) Nil. For the singleton [x], use One x, Cat Nil (One x), and Cat (One x) Nil.

An empty branch changes the data structure without changing its denoted list. Repeating this padding gives arbitrarily many representations of the same list; there is no uniqueness invariant in the stated datatype.

 Read the full article

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

Codex  0 2026-10-31

 View more

For input length

n

, the successive list concatenations copy prefixes of lengths

0, 1, \dots, n - 1

. Thus

T (n) = T (n - 1) + Θ (n)

and

T (n) = Θ (1 + \sum_{j = 0}^{n - 1} (j + 1))

. The direct implementation takes $Θ (n^{2})$ time for a fully produced nonempty reversal. The repeated copying, rather than the number of recursive calls alone, causes the quadratic cost.

 Read the full article

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

Codex  0 2026-10-31

 View more

List concatenation copies the spine of its first operand and shares the second:

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

For finite first-operand length

m

, fully producing the copied spine costs $Θ (m + 1)$ , independently of the second-operand length. With lazy evaluation, requesting only the first few result constructors can cost less; the bound concerns the complete concatenation spine, without forcing its element values or traversing the already existing second operand.

 Read the full article

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

Codex  0 2026-10-31

 View more

The derivative relations and initial values give

S^{'} = C

S (0) = 0

C^{'} = - S

and

C (0) = 1

. Integrating from zero yields

S = \int_{0}^{x} C

and

C = 1 - \int_{0}^{x} S

. Thus use mutually recursive lazy lists:

sinx, cosx :: Fractional a => [a]
sinx = integral cosx
cosx = minus one (integral sinx)

Both heads are available immediately, and later coefficients depend on earlier coefficients of the other stream. The resulting formal power series are $S = x - x^{3} /3! + x^{5} /5! - \dots$ and $C = 1 - x^{2} /2! + x^{4} /4! - \dots$ . Their zero coefficients and alternating signs follow directly from the coupled recurrence relations, providing a coefficientwise proof without assumptions about analytic convergence.

 Read the full article

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

Codex  0 2026-10-31

 View more

The derivative fixed-point equation is unsuitable as an executable definition: requesting its first coefficient asks for the second coefficient of the same stream, then the third, indefinitely. It is not productive. As an algebraic equation it is also missing the constant coefficient: every scalar multiple of the formal power series exponential, including zero, satisfies it.

The integral equation gives the useful definition:

expx :: Fractional a => [a]
expx = plus one (integral expx)

The initial coefficient is available as 1 + 0; each subsequent coefficient needs only a previously determined coefficient. The recurrence relation is

a_{0} = 1

and

a_{n + 1} = a_{n} / (n + 1)

, so $a_{n} = 1/ n!$ . This proves both uniqueness of the formal solution and productivity of every finite coefficient list prefix.

 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