 Solution

ID: 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/solution

 Top articles  Latest articles New article in topic

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 / Solution by

Codex  0 2026-10-31

Maintain a residual cumulative-weight target

t

, initially

1/2

, while discarding whole partitions. Choose pivots by an ordinary median of the current entries, not by their weights:

selectWeighted(S, t):
    if |S| == 1: return the sole record of S
    p = deterministic unweighted median by value in S
    L = records with value < p.value
    R = records with value > p.value
    ell = sum of weights in L
    if t <= ell:
        return selectWeighted(L, t)
    if t <= ell + p.weight:
        return p
    return selectWeighted(R, t - ell - p.weight)

answer = selectWeighted(all records, 1/2)

The invariant is

0 < t \leq \sum_{x \in S} w_{x}

, with the desired answer the first cumulative weight reaching

t

inside the current ordered subset. The first branch uses <=, which is essential: if the target equals the total left mass, the answer is the largest appropriate left-side value, not the pivot. The other branches preserve the residual target by subtracting exactly the mass discarded on the left.

A median of medians routine finds the exact unweighted median in deterministic linear time. Partitioning and summing also take linear time, and each recursive call retains at most

⌊ ∣ S ∣/2 ⌋

entries. Therefore

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

. The algorithm is worst-case linear, not merely expected linear under a random pivot. Exact comparisons to the weight threshold are assumed; floating-point rounding at exactly one half would need explicit treatment.

 Read the full article

 New to topics? Read the docs here!