Tripos 2021 Paper 1 Question 2 — Worked Solution

Question: A W × H matrix can be represented by a flat list concatenating the rows in order. For three alternative representations, state the type T, give create and get, and state asymptotic complexity of get.

Given functional array code:

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree
exception Subscript

let rec sub = function
  | Lf, _ -> raise Subscript
  | Br (v, t1, t2), 1 -> v
  | Br (v, t1, t2), k when k mod 2 = 0 -> sub (t1, k / 2)
  | Br (v, t1, t2), k -> sub (t2, k / 2)

let rec update = function
  | Lf, k, w ->
      if k = 1 then Br (w, Lf, Lf)
      else raise Subscript
  | Br (v, t1, t2), k, w ->
      if k = 1 then Br (w, t1, t2)
      else if k mod 2 = 0 then Br (v, update (t1, k / 2, w), t2)
      else Br (v, t1, update (t2, k / 2, w))

(a) A list of lists [5 marks]

Type T: float list list

create:

let rec create w = function
  | [] -> []
  | m ->
      let row = take w m in
      let rest = drop w m in
      row :: create w rest

This uses take and drop (as defined in the course) to partition the flat list into rows of width w. Each recursive step extracts one row. This is O(W × H) time since we must process every element of the flat list.

get:

let rec get r c m =
  match m with
  | [] -> raise (Invalid_argument "index out of bounds")
  | row :: rest ->
      if r = 0 then
        let rec nth i = function
          | [] -> raise (Invalid_argument "index out of bounds")
          | x :: _ when i = 0 -> x
          | _ :: xs -> nth (i - 1) xs
        in
        nth c row
      else
        get (r - 1) c rest

Asymptotic complexity of get: O(r + W) in the worst case. We scan r rows (skipping r × W elements), then scan c elements in the target row. Since r < H and c < W, this is O(H + W).

(b) An array of arrays [6 marks]

Type T: float array array

create:

let create w m =
  let flat = Array.of_list m in
  let h = Array.length flat / w in
  Array.init h (fun i ->
    Array.init w (fun j ->
      flat.(i * w + j)
    )
  )

Explanation: We first convert the input list to a flat array for O(1) indexed access. Then we allocate an h × w array of arrays, computing each element’s index in the flat array as i * w + j. This is O(W × H) time.

get:

let get r c m =
  m.(r).(c)

Asymptotic complexity of get: O(1). Array indexing is constant-time: the outer array lookup m.(r) and the inner array lookup .(c) are both direct indexed accesses.

(c) A functional array of functional arrays [9 marks]

Type T: float tree tree

A functional array of functional arrays: the outer tree maps row index r+1 to the inner tree (where indices in functional arrays start at 1), and the inner tree maps column index c+1 to the float value. The element at matrix position (r, c) corresponds to index (r+1) in the outer tree and (c+1) in the inner tree.

create:

let create w m =
  let n = List.length m in
  let h = n / w in
  let rec build_rows i rows acc =
    if i >= h then acc
    else
      let row_start = i * w in
      let rec build_row j acc_row =
        if j >= w then acc_row
        else
          let v = List.nth m (row_start + j) in
          build_row (j + 1) (update (acc_row, j + 1, v))
      in
      let row = build_row 0 Lf in
      build_rows (i + 1) rows (update (acc, i + 1, row))
  in
  build_rows 0 h Lf

Explanation (more efficient version): Rather than repeatedly calling update (which copies the path each time, giving O(n log n) overall), we can construct the functional array directly using a more efficient approach. The coursework version using update is acceptable but expensive. Here is a cleaner version:

let create w m =
  let n = List.length m in
  let h = n / w in
  let rec of_list start len =
    if len = 0 then Lf
    else if len = 1 then Br (List.nth m start, Lf, Lf)
    else
      let mid = len / 2 in
      let left = of_list start mid in
      let right = of_list (start + mid + 1) (len - mid - 1) in
      Br (List.nth m (start + mid), left, right)
  in
  let rec make_rows i =
    if i >= h then Lf
    else
      let row = of_list (i * w) w in
      update (make_rows (i + 1), i + 1, row)
  in
  make_rows 0

But the simplest approach building row-by-row with update is:

let create w m =
  let n = List.length m in
  let h = n / w in
  let rec loop i acc =
    if i = h then acc
    else
      let rec build_row j row_acc =
        if j = w then row_acc
        else
          let idx = i * w + j in
          let v = List.nth m idx in
          build_row (j + 1) (update (row_acc, j + 1, v))
      in
      let row = build_row 0 Lf in
      loop (i + 1) (update (acc, i + 1, row))
  in
  loop 0 Lf

Building the outer functional array takes O(H × log H) time (each of H row updates copies O(log H) path nodes). Building each inner row takes O(W × log W) time for each of H rows. Total: O(H × W × log W + H × log H).

get:

let get r c m =
  let row = sub (m, r + 1) in
  sub (row, c + 1)

Asymptotic complexity of get: O(log H + log W). We first look up the row tree at index r+1, which takes O(log H) time following the binary path. Then we look up the inner tree at index c+1, taking O(log W) time. Both sub operations follow paths proportional to the depth of balanced trees, giving O(log H + log W) total. Since H × W = n, this is O(log n) where n is the total number of elements.