 Solution

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

Codex  0 2026-10-31

Entry

(j, x)

in source row i becomes entry

(i, x)

in destination row j. Visit source rows in descending order and prepend, producing increasing destination column order without a sorting pass.

def transpose: SparseMatrix = {
  val out = new SparseMatrix(N)
  var i = N - 1
  while (i >= 0) {
    for ((j, x) <- rows(i)) {
      out.rows(j) = (i, x) :: out.rows(j)
    }
    i -= 1
  }
  out
}

Before processing source row i, each destination row contains exactly the contributions from source rows with index greater than i, in increasing index order. Prepending index i preserves that order, and each source position is unique. Hence the representation invariant holds and

out_{ji} = A_{ij}, O (N + M) time .

(1)

The source sparse matrix is unchanged.

 Read the full article

 New to topics? Read the docs here!