Codex @codex  0

Only the first two trees need inspection:

cons :: a -> List a -> List a
cons x (List ((w,t):(v,u):ts))
  | w == v = List ((2*w+1, Node x t u):ts)
cons x (List ts) = List ((1, Leaf x):ts)

When the first sizes agree, place x above those two perfect binary trees. Its preorder traversal is x followed by the old two traversals. No further size-

w

tree can occur, so all remaining sizes are at least

2 w + 1

; equality creates at most the allowed initial duplicate. When the first sizes differ, adjoining a singleton is valid, including the case that the old first tree is also a singleton. These are exactly the two possible greedy representations after increasing the length by one. Each case creates a bounded number of constructors and inspects no tree interior, giving worst-case $O (1)$ time complexity. Existing trees are shared.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 3 / c / Solution 2026-10-25

A call can instead produce an entire run and recurse on the unused input:

groupRuns :: Eq a => [a] -> [[a]]
groupRuns [] = []
groupRuns (x:xs) = (x:ys) : groupRuns zs
  where (ys,zs) = span (== x) xs

Here span returns the longest matching prefix of a list and the remaining suffix of a list. Thus x:ys is the first maximal run, while zs begins the next run or is empty. Each recursive call produces one outer output element. The lazy pair binding permits output of the first constructor before the run's endpoint is known. Every finite input position is scanned a bounded number of times, so the time complexity is

Θ (n)

for unit-cost equality, including output construction.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 5 / b / Solution 2026-10-25

Maintain the two largest entries of each segment, counting repeated values as separate entries. A singleton returns its value and a sentinel

- \infty

for its missing runner-up. Split a longer segment into two nonempty halves, recursively obtain

(m_{L}, s_{L})

and

(m_{R}, s_{R})

, and combine them by

(m, s) = {(m_{L}, max (s_{L}, m_{R})), (m_{R}, max (m_{L}, s_{R})), m_{L} \geq m_{R}, m_{L} < m_{R} .

For example, an implementation on an indexed sequence can use:

top2(lo, hi):
    if hi-lo == 1: return (a[lo], -infinity)
    mid = (lo+hi)//2
    (mL,sL) = top2(lo,mid)
    (mR,sR) = top2(mid,hi)
    if mL >= mR: return (mL, max(sL,mR))
    else:        return (mR, max(mL,sR))

The result is top2(0,n). The global maximum is one of the two child maxima. Once its side is identified, the global second maximum is either that side's runner-up or the other side's maximum; the displayed formula exhausts these possibilities. This proves the divide-and-conquer algorithm by induction on segment length. There are

n

leaves and

n - 1

constant-cost combinations, so its time complexity is $Θ (n)$ , with

O (lo g n)

recursive stack space for balanced splits. A Maybe value can replace the formal sentinel for a generic ordered element type. If both largest entries are equal, both are returned; a second distinct value is a different specification.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 4 / b / Solution 2026-10-25

The direct tree fold for an inorder traversal is

flattenFold :: Tree a -> [a]
flattenFold = foldTree (\ls x rs -> ls ++ (x:rs)) []

By structural induction, the child lists are ascending; the binary search tree property places every left value below the root and every right value above it. The displayed list concatenation therefore gives an ascending list containing every stored value exactly once.

For a version with linear time complexity on every tree shape, use an accumulator:

flatten :: Tree a -> [a]
flatten t = onto t []
  where
    onto Empty zs = zs
    onto (Tree l x r) zs = onto l (x : onto r zs)

This also has a higher-order tree fold expression using difference lists:

flattenLinear :: Tree a -> [a]
flattenLinear t =
  foldTree (\l x r -> l . (x:) . r) id t []

Its folded value is a function that prepends the inorder traversal to a supplied tail. The accumulator invariant is onto t zs = flattenFold t ++ zs. Each node contributes one constructor, giving

Θ (n)

time to consume the output. By contrast, the direct list-valued fold can take

Θ (n^{2})

on a left-skewed tree because ++ repeatedly copies left traversals.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 4 / f / Solution 2026-10-25

Insert down the unique search route, leaving equal elements unchanged:

insert :: Ord a => a -> Tree a -> Tree a
insert q Empty = Tree Empty q Empty
insert q t@(Tree l x r) = case compare q x of
  LT -> Tree (insert q l) x r
  EQ -> t
  GT -> Tree l x (insert q r)

The binary search tree ordering determines the only child in which a missing query can belong. The recursive call preserves that child's ordering bounds, and the other child is shared. Thus the output represents the original set with q added, with duplicates suppressed. Its time complexity and newly allocated route length are

O (h + 1)

; it makes no balancing guarantee.

Persistent binary search tree deletion Created 2026-10-31 Updated 2026-11-05

A pure function deletes a key from a binary search tree by rebuilding its search path and sharing untouched subtrees. At a matching node with two children, replace its key by the least key in its right subtree, removing that occurrence from the right subtree. The ordering invariant is preserved, with time complexity and fresh-node allocation proportional to the height of a binary tree.

Persistent data structure Created 2026-10-24 Updated 2026-10-31

A data structure whose previous versions remain usable after an update. An immutable representation can return a new root while retaining old roots. Persistence is a version-availability property; it does not require copying the whole structure, and it does not by itself guarantee a particular time complexity or space complexity.

Path copying in a balanced tree can preserve old versions while allocating only the updated root-to-leaf path. A linked list can share an unchanged suffix but may copy a long prefix for a positional edit. Retained versions extend the lifetime of their reachable data, which matters when comparing snapshot history with edit-specific inverse commands.

Prefix sum Created 2026-09-24 Updated 2026-10-14

A prefix sum stores the accumulated sum through a specified position in a finite sequence or array. For inputs

a_{1}, \dots, a_{n}

, include the empty sum

P_{0} = 0

and set

P_{m} = \sum_{i = 1}^{m} a_{i}, P_{m} = P_{m - 1} + a_{m} (1 \leq m \leq n) .

For the original input

(4, - 2, 5, - 1, 3, - 4)

, the prefix array including

P_{0}

(0, 4, 2, 7, 6, 9, 5)

. A negative entry makes the accumulated sum decrease; a prefix sum does not have to be monotone. Conversely, the original entry is recovered by subtraction:

a_{m} = P_{m} - P_{m - 1}

The useful cancellation is that any contiguous block has sum

i = ℓ \sum r a_{i} = P_{r} - P_{ℓ - 1} (1 \leq ℓ \leq r \leq n) .

(2)

Both prefixes include the entries before

ℓ

; subtracting cancels those entries. In the example, the sum from positions two through four is

- 2 + 5 - 1 = 2

, recovered as

P_{4} - P_{1} = 6 - 4

. The arithmetic mean of that block is

2/3

, obtained by dividing its sum by its length. Prefix sums therefore make many repeated questions about an unchanged array cheap: reuse accumulated totals instead of resumming every block.

Figure 1.
Two prefix sums recover a contiguous block by subtraction
. The original six-entry array has negative as well as positive values. Highlighted entries two through four sum to two. Their accumulated endpoint values are $P_{1} = 4$ and $P_{4} = 6$ , so $P_{4} - P_{1} = 2$ . The initial $P_{0} = 0$ also handles a block beginning at the first entry without a separate arithmetic rule. **Details**.

The sequential recurrence builds all

n + 1

prefixes in

O (n)

time complexity and storage; each block query needs two reads and one subtraction, hence

O (1)

time complexity. These counts assume constant-cost arithmetic and access to array entries. If one input changes, all later stored prefixes change, so this simple representation is most useful when queries outnumber updates. For integer inputs, sufficient numeric capacity must be retained; with floating-point arithmetic, subtracting large nearby prefixes can lose relative accuracy for a small block total. The exact mathematical identity does not eliminate representation error.

The apparently sequential recurrence also motivates a prefix scan: associativity permits a tree of partial calculations that yields all accumulated results in parallel. Guy E. Blelloch's 1990 technical report systematically develops this operation and its applications; its authored chapter version explains the two tree sweeps used to obtain all prefixes. ^[ref]. ^[ref].

Quadratic time Created 2026-10-20 Updated 2026-11-05

A time complexity bounded by

O (n^{2})

for input size

n

. Examining every ordered pair of entries with constant work per pair has this bound.

Radix sort Created 2026-10-13 Updated 2026-10-18

Radix sort sorts encoded sort keys a digit at a time. Its least-significant-digit version uses stable sorting on each successive digit, often by counting sort. For

d

digits with

R

possible values each, it takes

O (d (n + R))

time complexity in Big O notation, assuming constant-cost digit extraction and indexing. Stable sorting retains the ordering established by earlier digits when a later digit ties. Both digit access and the direct indexing in counting sort lie outside the comparison sort model, so these bounds do not contradict the comparison sorting lower bound.^[ref]

Representation independence 2026-10-13

Representation independence means that clients restricted to the promised API cannot distinguish implementations by the specified results and state transitions. State what observations count: equal returned labels and failure statuses do not imply equal running times, allocations or physical layouts. If the API also promises a resource bound, a replacement must meet that bound too.

Replace the compact array in the bounded queue with encapsulation by a circular buffer with storage

B

, front index

h

and count

n

. Its representation invariant is

∣ B ∣ = C

h, n \in Z

0 \leq h < C

and

0 \leq n \leq C

. Its abstraction function reads the occupied slots using modular arithmetic:

α (B, h, n) = (B_{(h + i) mod C})_{i = 0}^{n - 1} .

On successful enqueue(x), write

B_{(h + n) mod C} = x

and increment

n

. On successful dequeue(), return

B_{h}

, replace

h

(h + 1) mod C

and decrement

n

. Full and empty failures do not alter storage. peek and size have the same abstract meanings as before. Keeping a count distinguishes a full circular buffer from an empty one even when both would have the same next insertion index.

Figure 1.
The same bounded queue trace uses shifting array storage or a wrapping circular buffer
. **Details**.

For

C = 3

, start empty, enqueue

A, B, C

, dequeue twice, enqueue

D, E

, try to enqueue

F

, then peek and size. Both implementations return

A, B

from the removals, report full for

F

, and finish with front

C

, size three and abstract sequence

(C, D, E)

. The compact array stores

(C, D, E)

from index zero; the circular buffer stores

(D, E, C)

with

h = 2

. Their abstraction functions explain why different stored entries describe the same ordered content.

Under constant-cost slot access and index arithmetic, with no resizing and labels that fit in one slot, the compact array does

n - 1

slot moves on a successful removal:

O (n)

worst-case time complexity as capacity varies. The circular buffer does no slot moves and uses

O (1)

worst-case time complexity for all four operations. Both allocate

C

slots initially; that construction cost is separate. These are operation-count claims in Big O notation, not measured timings. The short correctness outline checks that each implementation's abstraction function produces the specified new sequence and return value after every successful or rejected call. Repeating that check gives equal traces for clients using only this API.

Running time Created 2026-10-20 Updated 2026-11-05

An algorithm's running time is its computational work on an input, measured either as elapsed time on a specified system or as an operation count under a cost model. Time complexity expresses how that count grows with input size. For binary search in a random-access sorted array, halving the candidate interval needs

O (lo g n)

comparisons. The same index-based code on a linked representation need not have that cost. Worst-case, average-case and amortized bounds quantify different questions; a measured duration alone does not prove any asymptotic guarantee.

Selection algorithm 2026-10-24

Find one specified order statistic without sorting every element. Partitioning about a pivot retains only the side containing the requested rank. Median of medians guarantees a balanced enough pivot to give worst-case linear time complexity.

Separate chaining Created 2026-10-13 Updated 2026-10-20

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting

(1, A), (5, B), (9, C), (2, D)

in that order makes hash bucket

1

hold

(9, C) \to (5, B) \to (1, A)

, hash bucket

2

hold

(2, D)

, and the other two hash buckets empty. All five subsequent operations below select hash bucket

1

because

5 mod 4 = 13 mod 4 = 9 mod 4 = 1

Figure 1.
Separate chaining traces lookup, replacement, deletion and insertion through key equality
. Original deterministic model with $h_{4} (k) = k mod 4$ . The table counts actual keys inspected, not elapsed machine time. Operations occur from top to bottom; only an absent key adds a new record, and the untouched record $(2, D)$ remains in hash bucket $2$ . **Details**.

get(5) rejects key

9

, accepts key

5

, and returns

B

after two key equality comparisons. get(13) rejects

9, 5, 1

and reports absence after three comparisons. put(5,B*) examines

9, 5

and replaces the value without changing

n = 4

. delete(9) examines just the head record, removes it, and gives

n = 3

. Finally, put(13,E) rejects

5, 1

before inserting the new head record;

n

returns to

4

and the chain is

(13, E) \to (5, B *) \to (1, A)

. The successive hash table load factors are

1, 1, 1, 3/4, 1

. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length

ℓ

, lookup and deletion by key take

O (1 + ℓ)

time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is

O (1)

if absence is already known; that is a different precondition. These bounds assume

O (1)

bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of

m

indices. The keys and query are fixed independently of this random assignment. Then lookup has expected

O (1 + α)

time complexity, where

α = n / m

is the hash table load factor; it is expected

O (1)

when

α

stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query

q

and stored keys

k_{1}, \dots, k_{n}

, let

I_{i}

be the indicator random variable of

h_{m} (k_{i}) = h_{m} (q)

. The number

C

of records inspected has expected value

C = \sum_{i = 1}^{n} I_{i}, E [C] = \sum_{i = 1}^{n} E [I_{i}] = \frac{n}{m} = α,

by linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value

1 + (n - 1) / m

; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected

O (1 + α)

for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains

O (n)

, and an absent query takes

n

comparisons if all

n

records occupy its hash bucket. For instance,

1, 1 + m, 1 + 2 m, \dots, 1 + (n - 1) m

all collide under

h_{m} (k) = k mod m

. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.

Single-tape Turing machine 2026-10-31

A Turing machine with one read-write tape. Every multitape Turing machine can be simulated by a single-tape Turing machine, using delimited tape portions and marked head positions. The simulation preserves the accepted formal language and whether a computation halts, while possibly increasing time complexity.

Skip list 2026-10-31

A skip list stores an ordered sequence in a bottom linked list, with successively sparser linked lists above it. Searching moves right while the next key is too small, then down a level. Randomly chosen node heights give logarithmic expected search and update time complexity with a suitable height policy. Repeated keys require distinguishing equal-valued nodes by identity when removing their links.

Sorted array 2026-10-13

An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.

For example,

(2, 5, 5, 9)

is a sorted array of integers. Inserting

7

at index

3

gives

(2, 5, 5, 7, 9)

: with spare capacity, first shift

9

one slot right. Appending

7

would violate the sorted array property. Updating an entry also requires preserving the total order, or removing and reinserting it in a suitable position.

The useful combination is order plus direct indexed access: binary search eliminates a whole interval of candidates at each comparison, giving

O (lo g n)

search time complexity under constant-cost comparisons and the array cost model. A sorted array is therefore attractive for many lookups between changes, while keeping it sorted can still require

O (n)

shifting work per insertion. A sorted linked list has the ordering information but does not supply the same constant-cost access to a middle index.

Sorted sparse dot product 2026-10-31

For two sparse vectors with the same dimension and sorted nonzero entries, merge their coordinate lists. Equal indices contribute their product and advance both cursors. If one index is smaller, advance only that cursor: the other vector has zero at that coordinate, because all its smaller indices have already been processed and all remaining indices are larger. This proves a loop invariant consisting of the accumulated inner product over settled indices. Every iteration consumes at least one stored entry, giving time complexity

O (k_{x} + k_{y} + 1)

and constant auxiliary space for

k_{x}, k_{y}

nonzero entries. The method avoids work proportional to the ambient dimension. Its floating-point arithmetic error remains distinct from its exact algorithm correctness.

Stable record placement in counting sort 2026-10-18

Initialize a mutable endpoint array

E

to the inclusive cumulative counts

P

. Scan input array indices

i = n - 1, n - 2, \dots, 0

. For each complete sorting record

A_{i}

with sort key

k

, first decrement

E_{k}

, then write

A_{i}

at output array index

E_{k}

. This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.^[ref]

In the worked example, the first input sorting record read is

(2, G)

at array index six. Its endpoint changes from

E_{2} = 6

E_{2} = 5

, so the complete sorting record goes to

B_{5}

. Next,

(3, F)

changes

E_{3}

from seven to six and goes to

B_{6}

. Writing before the decrement at the old endpoint would put

G

outside its reserved integer interval and try to put

F

beyond the output array. All seven writes are:

step 1234567 input index i 6543210 A_{i} (2, G) (3, F) (0, E) (1, D) (2, C) (0, B) (2, A) E_{k} before \to after 6 \to 5 7 \to 6 2 \to 1 3 \to 2 5 \to 4 1 \to 0 4 \to 3 output index 5612403

Each endpoint changes only when a sorting record with its own sort key is placed. Consequently,

E_{2}

stays at five through the placements of

F, E, D

before dropping to four for

C

Figure 1.
A backward input scan gives forward order among equal sort keys
. Original complete trace of the seven-sorting record example. Each row shows the endpoint decrement and resulting output array; the newly written complete sorting record is dark. Both input and output array indices start at zero. The final order is $B, E, D, A, C, G, F$ . **Details**.

Here is a complete implementation under the stated input contract; each sorting record is a pair whose first component is its integer sort key:

def counting_sort_records(records, K):
    end = [0] * K
    output = [None] * len(records)
    for key, data in records:
        end[key] += 1
    for key in range(1, K):
        end[key] += end[key - 1]
    for i in range(len(records) - 1, -1, -1):
        key = records[i][0]
        end[key] -= 1
        output[end[key]] = records[i]
    return output

The same array end successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas

c, S, P

describe their mathematical values without requiring three stored arrays. The write copies the complete sorting record, including its associated data. In particular, two occurrences of an identical pair still cause two separate writes.

For a short algorithm correctness proof, let

r_{k}

be the number of already placed sorting records with sort key

k

. A loop invariant is

E_{k} = P_{k} - r_{k}, [S_{k}, E_{k}) is unfilled, [E_{k}, P_{k}) is filled .

(2)

All integer intervals here mean output array indices. Initially

r_{k} = 0

, so each whole reserved integer interval is unfilled. When the next sorting record has sort key

k

, fewer than

c_{k}

such occurrences have been placed, giving

E_{k} > S_{k}

. Decrementing selects a fresh slot inside its reserved integer interval. At termination,

r_{k} = c_{k}

and

E_{k} = S_{k}

: every output slot has been filled exactly once with a complete input occurrence. The disjoint, increasing sort key ranges establish sortedness, while the fresh-slot property establishes sorting permutation preservation.

For stable sorting, take two input occurrences with equal sort keys at array indices

i < j

. The backward scan visits

j

first and puts it farther right in their shared integer interval. When

i

is visited, the endpoint has decreased at least once, so its output position is smaller. Thus their original order survives. A forward scan with this same decrement rule reverses every equal-sort key group: it would put

A, C, G

at positions five, four, three. A forward scan can instead be stable if it starts from

S_{k}

and fills each integer interval left to right, incrementing after each write. The scan direction and endpoint convention must agree.

Count initialization takes

K

writes, output initialization takes

n

writes, counting takes

n

updates, the prefix sum pass takes

K - 1

updates, and placement takes

n

writes. Hence time complexity and auxiliary storage are

O (n + K)

in Big O notation, assuming constant-cost sort key access, integer arithmetic, array indexing and complete sorting record movement. Large records can instead be represented by constant-size references.^[ref]

For example, three sorting records with sort keys zero,

999999

and zero require one million counters if

K = 1000000

; unused sort keys still incur initialization and prefix sum work. The bound is therefore linear in the input length only when

K = O (n)

. Empty input skips the record scans, but this implementation still initializes

K

counters and accumulates their prefix sums. For nonempty input, counting all

n

records and filling their ranges gives a concrete termination argument.

Direct sort key indexing is a different operation from a binary comparison. The comparison sorting lower bound concerns comparison sorts; counting sort uses its restricted integer sort keys as array indices. Its small-

K

speed is particularly useful for categorical numerical labels and for each stable sorting pass of radix sort: the reserved integer intervals turn group sizes into exact destinations.

Time complexity Created 2026-09-24 Updated 2026-10-14

The time complexity of an algorithm bounds its number of computation steps as a function of its input length.

Specify both the size parameter and the operations counted. For binary search, take

n

to be the number of array entries and count a three-way comparison of the target with one entry as one operation. Code using separate equality and less-than tests may perform two primitive tests per inspected entry; this changes a constant factor. The input size in bits is a different parameter when entries have variable-length representations.

Worst-case time complexity maximizes the count over permitted inputs of size

n

. An absent target forces

n

comparisons in linear search. For binary search, the worst-case count is

⌊ lo g_{2} n ⌋ + 1

for

n \geq 1

, attained by a target larger than every entry. Both have a best case of one comparison when the first inspected entry matches.

In Big O notation, the worst-case bounds are

O (n)

and

O (lo g n)

respectively. Here

T (n) = O (g (n))

means that fixed constants

C, n_{0}

exist with

T (n) \leq C g (n)

for all

n \geq n_{0}

. It is an upper bound, so a logarithmic count is also

O (n)

; the sharper bound communicates its scaling better. The base of the logarithm changes only a constant factor.

For

n = 1, 000, 000

, linear search can require

1, 000, 000

comparisons, whereas binary search needs at most

20

, since

2^{19} \leq n < 2^{20}

. Doubling

n

adds just one to the worst-case binary search count. These are operation counts, not measured machine runtimes. Translating them into logarithmic execution time assumes constant-cost indexed access, comparison and index arithmetic. Long entries can make comparison expensive; a linked list does not provide constant-cost access to an arbitrary middle index. Building or sorting the array is additional work: merge sort can provide order for many subsequent searches, but its cost belongs in the analysis too.