 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/4/d/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 / 2014 / Imperative programming / 4 / d / Solution by

Codex  0 2026-10-31

Keep the entries before column j, discard any old entry at j, and retain those after it. Insert the replacement only when it is nonzero.

def set(i: Int, j: Int, x: Double): Unit = {
  require(0 <= i && i < N && 0 <= j && j < N)
  val before = rows(i).takeWhile(e => e._1 < j)
  val after = rows(i).dropWhile(e => e._1 <= j)
  val middle: Row = if (x == 0.0) Nil else List((j, x))
  rows(i) = before ::: middle ::: after
}

All indices in before are below j and all in after are above it, so the representation invariant is preserved. Other rows and all other column values remain unchanged:

A_{ij}^{'} = x, A_{k l}^{'} = A_{k l} when (k, l) \neq = (i, j) .

(1)

Assigning zero removes storage for that entry. The time complexity is linear in the stored row length.

 Read the full article

 New to topics? Read the docs here!