New articles - OurBigBook.com

Dynamic programming describes a problem by reusable subproblem states and a recurrence, computing each required state once through memoization or a bottom-up order. Its benefit comes from sharing answers to overlapping subproblems.

The principle of optimality says that, after the information needed by a state has been fixed, the remaining part of an optimal solution is optimal for that state. Otherwise replacing it by a better subsolution would improve the whole solution. A correct state must retain every constraint that can affect later choices.

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

Codex  0 2026-10-31

The balanced comparison tournament uses

C (n) = 2 C (n /2) + 1, C (1) = 0,

C (n) = n - 1

. The second-largest search compares

m = lo g_{2} n

direct losers, using

m - 1

comparisons. The record of

s

contains at most

m - 1

direct losers, because

s

loses before becoming the overall winner. Hence the third candidate set has size at most

2 m - 2

, requiring at most

2 m - 3

comparisons.

For

n = 2^{m} \geq 4

, the complete comparison count is therefore

(n - 1) + (m - 1) + (2 m - 3) = n + 3 lo g_{2} n - 5.

(2)

This is

n + O (lo g n)

and therefore meets the requested

O (n + lo g^{2} n)

bound. The defeat-record lists can be linked in constant local work per merge; flattening the final partition takes

O (n)

work. Thus the method also has linear overall running time under constant-cost key comparisons.

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

Codex  0 2026-10-31

The first value is the tournament winner

M

. Find the second value

s

by taking the maximum of the direct-loser set

second (S)

, retaining its associated tournament record.

The third-largest value must have lost directly to either

M

s

: any other value is smaller and could not defeat it. Therefore it belongs to

C = (second (S) ∖ {s}) \cup {r . key : r \in s . losers} .

Conversely, every value in

C

is distinct from

M, s

. Thus the third-largest value is $max C$ . This is tournament selection of the three largest elements; it uses the retained defeat records while computing the requested three-part partition.

Three largest elements exist only for

n \geq 3

. With the paper's power-of-two assumption this means

n \geq 4

. The partition in part (b) remains meaningful for

n = 2

, but a third output cannot be supplied in that case.

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

Codex  0 2026-10-31

Build a balanced comparison tournament, retaining the record of each value's direct defeats. A record stores a key and a list of records that it directly defeated:

tournament(S):
    if |S| = 1:
        return Node(the element of S, [])
    split S into equally sized L and R
    a = tournament(L)
    b = tournament(R)
    if a.key < b.key:
        exchange a and b
    prepend b to a.losers
    return a

There is one key comparison at each merge. Because

S

is a set, all keys are distinct, so the greater winner is unambiguous. Retaining the losing record also retains its own earlier comparison history; it does not merely retain the losing root's value.

Let the returned root have value

M

. Define

max (S) = M, second (S) = {r . key : r \in root.losers}, third (S) = S ∖ ({M} \cup second (S)) .

The second-largest value can only lose to

M

, so it occurs among those direct losers. This proves the required partition and the exclusion of the second-largest value from the third part. For

n = 2^{m}

, the winner participates in exactly

m

merges, so

∣ second (S)∣ = m

. The other part can be materialized by marking the original element identities in this list and scanning the original inputs, using

O (n)

additional operations without more comparisons between keys.

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

Codex  0 2026-10-31

The standard three-case master theorem concerns

T (n) = a T (n / b) + f (n), a \geq 1, b > 1,

with constant base-case cost and eventually nonnegative

f

. Put

d = lo g_{b} a

If $f (n) = O (n^{d - ϵ})$ for some $ϵ > 0$ , then $T (n) = Θ (n^{d})$ .
If $f (n) = Θ (n^{d})$ , then $T (n) = Θ (n^{d} lo g n)$ .
If $f (n) = Ω (n^{d + ϵ})$ for some $ϵ > 0$ and $a f (n / b) \leq c f (n)$ eventually for a constant $c < 1$ , then $T (n) = Θ (f (n))$ .

In a divide-and-conquer algorithm,

a

counts recursive subproblems,

n / b

is their size, and

f

accounts for splitting and combining. The comparison with

n^{l o g_{b} a}

identifies whether leaves, all levels, or the upper levels dominate the running time. The polynomial gap and the third case's regularity condition are part of this version of the theorem.

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

Codex  0 2026-10-31

Enumerate by the hypotenuse and test finitely many shorter legs:

primitiveTriples :: [(Integer, Integer, Integer)]
primitiveTriples =
  [(a, b, c) |
     c <- [1..],
     b <- [1..c-1],
     a <- [1..b-1],
     a*a + b*b == c*c,
     gcd a (gcd b c) == 1]

The equality selects Pythagorean triples, and the greatest common divisor test makes them primitive. The bounds enforce

0 < a < b < c

, removing the duplicate obtained by exchanging the legs. Each fixed

c

has a finite search, so the outer loop gives ascending hypotenuse order and reaches every qualifying triple. Infinite families supplied by Euclid's formula ensure that the stream has arbitrarily many outputs. Its first five entries are

[(3,4,5),(5,12,13),(8,15,17),(7,24,25),(20,21,29)]

Using Integer avoids overflow in the squared values. The construction prioritizes a direct correctness argument; it does not claim an optimal enumeration cost.

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

Codex  0 2026-10-31

For the requested Int-typed operation, remove the first element as well as its later multiples:

sieve :: [Int] -> [Int]
sieve [] = []
sieve (p:xs) = [x | x <- xs, x `rem` p /= 0]

On its intended input, p is positive, so the remainder is defined. An arbitrary list headed by zero lies outside this convention.

To enumerate literally all prime numbers, use unbounded Integer arithmetic:

primes :: [Integer]
primes = go [2..]
  where
    go :: [Integer] -> [Integer]
    go [] = []
    go (p:xs) =
      p : go [x | x <- xs, x `rem` p /= 0]

At each stage, the smallest remaining number has no smaller prime divisor and is therefore prime. Removing its larger multiples preserves every later prime and removes any composite number once its least prime divisor is processed. Lazy evaluation makes each requested finite prefix available. This implements the given repeated-filtering form of the sieve of Eratosthenes. A bounded Int stream can only cover representable values; Integer supplies the all-primes interpretation.

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

Codex  0 2026-10-31

Enumerate finite shells of constant coordinate sum:

triples :: [(Integer, Integer, Integer)]
triples =
  [(a, b, k-a-b) |
     k <- [0..],
     a <- [0..k],
     b <- [0..k-a]]

Here natural numbers include zero. Every generated coordinate is nonnegative. Conversely, a given triple

(a, b, c)

occurs in exactly the shell

k = a + b + c

and at exactly those loop indices

a, b

. Each shell contains only finitely many triples, so every triple is reached after finitely many earlier outputs. This is fair enumeration, unlike nesting three unrestricted infinite lists. For the positive-integer convention, add one to each generated coordinate.

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

Codex  0 2026-10-31

Lazy evaluation is evaluation by need: an expression is deferred until its value is demanded, and its computed value is shared for subsequent demands of the same suspended computation.

Its two key properties here are avoiding evaluation of unused expressions and sharing demanded computations. For example, the first component of (3, undefined) can be obtained without evaluating the second. A suspended expression is represented by a thunk; after evaluation its result can be reused. This supports productive infinite lists: take 5 [0..] demands only a finite prefix. It does not guarantee that a demanded computation terminates.

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

Codex  0 2026-10-31

Attach zero-based indices before filtering:

findStates :: [State] -> String -> [(State, Integer)]
findStates states str =
  [(state, i) |
     (state, i) <- zip states [0..],
     isPrefix str state]

The zip function pairs each state with its position in the original sequence. The list comprehension retains exactly those pairs satisfying the prefix test, preserving their order and their original indices. The declared result makes [0..] a stream of Integer indices. An empty search string matches every state, including an empty state, because the empty list is a prefix of every list.

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

Codex  0 2026-10-31

The principal type needs an equality type class constraint:

isPrefix :: Eq a => [a] -> [a] -> Bool
isPrefix [] _ = True
isPrefix (_:_) [] = False
isPrefix (x:xs) (y:ys) = x == y && isPrefix xs ys

The empty list is a prefix of every list, witnessed by the second list itself as the remaining suffix. A nonempty prefix cannot fit in the empty list. Otherwise the first elements must agree, and the remaining first list must be a prefix of the remaining second list. These cases prove correctness by structural induction on the candidate prefix. The Eq a constraint is required by x == y; no ordering constraint is needed.

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

Codex  0 2026-10-31

Generate successive states lazily and take exactly their initial nonempty segment:

runSystem :: (State, [Rule]) -> [State]
runSystem (state, rules) =
  takeWhile (not . null) (iterate (step rules) state)

The iterate function starts with state itself and repeatedly applies step rules. The takeWhile function excludes the first empty state and everything after it. If the initial state is empty, the result is []. If the process never reaches an empty state, the answer is a potentially infinite list whose finite prefixes can be observed through lazy evaluation. No artificial maximum number of rewriting steps is introduced.

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

Codex  0 2026-10-31

Apply one replacement to each original character and concatenate the results:

step :: [Rule] -> State -> State
step rules = concatMap (applyRule rules)

The concatMap operation combines a map function and list concatenation. Replacements occur in original-character order, so a character produced by a replacement is not processed again during the same step. This is parallel string rewriting. In particular step rules "" = "", with no rule lookup required for the empty state.

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

Codex  0 2026-10-31

Collect the matching replacements and distinguish all three possible multiplicities:

applyRule :: [Rule] -> Char -> String
applyRule rules c =
  case [replacement | (key, replacement) <- rules, key == c] of
    []          -> error ("no rule for " ++ [c])
    [result]    -> result
    (_:_:_)     -> error ("multiple rules for " ++ [c])

The list comprehension selects precisely the rules whose left-hand character is c. A singleton is the required unique match. The third branch also rejects duplicate rules with identical right-hand sides: there are still two matching rules. Finiteness of the rule list makes the uniqueness test decidable. The returned replacement may itself be empty.

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

Codex  0 2026-10-31

Maintain a stack of values of the complete subexpressions encountered so far, with the newest value at its head:

evalRP :: RPolish -> Int
evalRP = finish . foldl push []
  where
    push :: [Int] -> Elem -> [Int]
    push stack (Number n) = n : stack
    push (right:left:stack) (Operator op) =
      applyOp op left right : stack
    push _ (Operator _) = error "missing operand"

    finish :: [Int] -> Int
    finish [value] = value
    finish _       = error "malformed expression"

The left fold processes tokens in their order. A number pushes its own value; an operator replaces the two latest subexpression values by their combination. The top value is the right operand, so preserving the order in applyOp op left right is necessary for subtraction and division. Induction on the consumed token prefix proves this stack machine invariant. A complete valid expression finishes with exactly one value.

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

Codex  0 2026-10-31

Use an auxiliary parser that returns both a value and the unconsumed suffix. The arithmetic helper is:

applyOp :: Op -> Int -> Int -> Int
applyOp Add x y = x + y
applyOp Sub x y = x - y
applyOp Mul x y = x * y
applyOp Div x y = x `div` y

For the integer-valued expression language, this chooses integer division with div's rounding convention. The result is evaluated under the intended arithmetic model; bounded-Int overflow is separate from parsing.

evalP :: Polish -> Int
evalP input =
  case parse input of
    (value, []) -> value
    _           -> error "trailing tokens"
  where
    parse :: Polish -> (Int, Polish)
    parse [] = error "missing operand"
    parse (Number n : rest) = (n, rest)
    parse (Operator op : rest) =
      let (left, rest1)  = parse rest
          (right, rest2) = parse rest1
      in (applyOp op left right, rest2)

A number consumes one token. An operator consumes the two successive complete expressions that follow it, so nested operators are handled by recursion. Structural induction on the expression proves that parse consumes exactly its Polish notation and returns its value. Keeping the suffix is essential: neither operand has a fixed token count. Division by zero need not be treated separately under the stated input convention.

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

Codex  0 2026-10-31

Pass an already constructed suffix through the traversal:

convert :: Expr -> RPolish
convert e = go e []
  where
    go :: Expr -> RPolish -> RPolish
    go (Num n) rest = Number n : rest
    go (App op left right) rest =
      go left (go right (Operator op : rest))

The invariant is that go e rest is the reverse Polish notation of e followed by rest. It holds at a numeric leaf. At an application, the result is the left subtree's tokens, then the right subtree's tokens, then the operator, then rest, exactly as required.

Each vertex of the abstract syntax tree creates one output list cell and performs constant local work. Thus producing the complete result takes $O (n)$ time for an expression with

n

vertices. No repeated list concatenation copies a previously traversed subtree. This suffix-passing construction is a difference list traversal.

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

Codex  0 2026-10-31

Use a sum type whose two constructors distinguish a number from an operator:

data Elem = Number Int | Operator Op

Then the supplied Polish and RPolish aliases can both be lists of Elem. Constructor tags distinguish tokens without attempting to encode operators as special numeric values. The numeric type Int agrees with the supplied abstract syntax tree.

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

Codex  0 2026-10-31

The expression parses as g . (g x). Initially write g :: a -> r and x :: a. In the function composition, g x must itself be a function whose result can be passed to g. Hence r = b -> a for a fresh type b, so

g :: a -> b -> a
g x :: b -> a
g . g x :: b -> b -> a

Consequently the principal type is

f :: (a -> b -> a) -> a -> b -> b -> a

One can check the constraints by expanding the composition:

f g x y z = g (g x y) z

Here g x y has type a, and the second application accepts it and the final b-typed argument z. The two type variables remain independent; no Haskell type class constraints are required.

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

Codex  0 2026-10-31

Let x :: a and g :: a -> b, as required by the inner application g x. Using g x as the next argument of that same g forces b = a. Thus g (g x) :: a. Applying that result to x requires a function type a -> c, giving

a = a \to c .

This equation fails the occurs check: the type variable a occurs inside the type with which it would be unified. These constraints have no solution in the Hindley-Milner type system. Therefore the definition has no type in ordinary Haskell. The obstruction is to type inference, independently of which particular values might later be supplied.