Tripos 2024 Paper 1 Question 1 — Worked Solution

Question: Statistical analysis of 150 students’ exam results. Each student answered 6 of 10 questions. Zero indicates not attempted.

type marks = int list
let results : marks list = [
  [ 30; 25; 20; 0; 0; 18; 30; 0; 0; 8 ];
  [ 27; 0; 18; 9; 0; 30; 28; 0; 0; 17 ];
  (* ... 147 more rows ... *)
]

Mean and standard deviation formulas:

$\bar{x} = \frac{1}{n}\sum_{i=0}^{n-1} x_i \qquad s = \sqrt{\frac{1}{n-1}\sum_{i=0}^{n-1} (x_i - \bar{x})^2}$

(a) fold, map, filter [6 marks]

let rec fold f acc = function
  | [] -> acc
  | x :: xs -> fold f (f acc x) xs

let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

let rec filter p = function
  | [] -> []
  | x :: xs ->
      if p x then x :: filter p xs
      else filter p xs

Explanation: These are the standard list functionals from Lecture 8. fold (left fold) processes the list from left to right, accumulating a result. map applies f to each element. filter keeps elements satisfying p. Note that fold as defined here is not tail-recursive — the recursive call is the last operation syntactically but the accumulator is passed as argument. For a tail-recursive version:

let rec fold f acc = function
  | [] -> acc
  | x :: xs -> fold f (f acc x) xs

This is actually tail-recursive because the result of the recursive call is returned directly (no further computation). So O(n) time, O(1) space. map is not tail-recursive but can be made so with an accumulator (at the cost of reversing). filter is also not tail-recursive.

(b) Mean and standard deviation [8 marks]

type stats_result = Stats of float * float | NoAttempts

let analyse marks =
  let attempted = filter (fun x -> x <> 0) marks in
  let n = List.length attempted in
  if n < 2 then NoAttempts
  else
    let sum = fold (fun acc x -> acc +. float_of_int x) 0.0 attempted in
    let mean = sum /. float_of_int n in
    let sq_diffs = map (fun x ->
      let diff = float_of_int x -. mean in
      diff *. diff
    ) attempted in
    let sum_sq = fold (fun acc x -> acc +. x) 0.0 sq_diffs in
    let std = sqrt (sum_sq /. float_of_int (n - 1)) in
    Stats (mean, std)

Explanation: We:

1. Filter out zeros (unattempted questions) from the marks list.
2. Count how many marks remain. If fewer than 2, the standard deviation is undefined (division by n-1 would be division by zero or meaningless), so we return NoAttempts.
3. Compute the sum of marks using fold, converting to float for the calculation.
4. Compute the mean: sum / n.
5. Compute the sum of squared differences from the mean using map and fold.
6. Compute standard deviation: sqrt(sum_sq / (n - 1)) (sample standard deviation, as per the formula using n-1).

The stats_result type captures the possibility of an undefined result (fewer than 2 attempts). The function handles edge cases gracefully rather than raising an exception.

Time complexity: O(m) where m is the number of marks (filter is O(m), length is O(m), fold is O(m), map is O(m), second fold is O(m) — each pass is linear, giving O(m) overall with a constant factor of about 5). Space: O(m) for attempted and sq_diffs lists. Could be reduced to O(1) by combining passes, but clarity matters more here.

(c) Per-question statistics [6 marks]

let nth n xs =
  let rec go i = function
    | [] -> None
    | x :: rest ->
        if i = n then Some x
        else go (i + 1) rest
  in
  go 0 xs

let qmean q results =
  let q_marks = filter (fun x -> x <> 0)
    (map (fun row ->
      match nth q row with
      | None -> 0
      | Some v -> v
    ) results) in
  let n = List.length q_marks in
  if n = 0 then 0.0
  else
    let sum = fold (fun acc x -> acc +. float_of_int x) 0.0 q_marks in
    sum /. float_of_int n

let qstd q results =
  let q_marks = filter (fun x -> x <> 0)
    (map (fun row ->
      match nth q row with
      | None -> 0
      | Some v -> v
    ) results) in
  let n = List.length q_marks in
  if n < 2 then 0.0
  else
    let sum = fold (fun acc x -> acc +. float_of_int x) 0.0 q_marks in
    let mean = sum /. float_of_int n in
    let sq_diffs = map (fun x ->
      let diff = float_of_int x -. mean in
      diff *. diff
    ) q_marks in
    let sum_sq = fold (fun acc x -> acc +. x) 0.0 sq_diffs in
    sqrt (sum_sq /. float_of_int (n - 1))

Explanation: nth n xs returns Some v if the list has an element at zero-based index n, or None if the list is too short. We use option rather than raising an exception, which is safer and more idiomatic.

For qmean q results:

1. Extract the qth mark from each student’s row using map with nth. If a student’s row is shorter than q+1 (shouldn’t happen with 10 questions, but defensive), we treat it as 0.
2. Filter out zeros (unattempted).
3. Compute the mean, handling the empty case.

For qstd q results, the same pattern but with the standard deviation formula.

The type val nth : int -> 'a list -> 'a option returns None for out-of-bounds access, which is more idiomatic OCaml than raising an exception. The question functions have types val qmean : int -> marks list -> float and val qstd : int -> marks list -> float.

Time complexity for each: O(S) where S is the number of students (150), since we process each student’s row once for extraction and once for computation. The nth function is O(q) in the worst case per call, so total extraction is O(S × Q) where Q = 10.