Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4

Table of contents
- a 4
  - Solution a
- b 4
  - Solution b
- c 4
  - Solution c
- d 4
  - Solution d
- e 4
  - Solution e
- f 4
  - Solution f
- g 4
  - Solution g

Solution

The fresh array initially holds null references, whereas a zero row must be an empty list. Initialize every slot explicitly:

for (i <- 0 until N) rows(i) = List.empty[Entry]

Then

rows (i) = Nil for every i, A_{ij} = 0.

(1)

The following methods belong inside SparseMatrix, using the supplied Entry and Row type aliases.

Solution

 0  0

The representation invariant is

N \geq 0

, rows.length == N, and every rows(i) is a nonnull finite list of entries

(j, x)

satisfying

0 \leq j < N, x \neq = 0.0, column indices strictly increase along each row .

(1)

Strict increase excludes repeated columns. The abstraction function gives

A_{ij} = x

when the unique entry

(j, x)

occurs in rows(i), and

A_{ij} = 0

otherwise. Thus omitted positions represent zero; omission does not mean an unknown matrix entry.

Solution

 0  0

Select entries having the requested column. The representation invariant ensures that the selected list has length at most one.

def get(i: Int, j: Int): Double = {
  require(0 <= i && i < N && 0 <= j && j < N)
  val entries = rows(i).filter(e => e._1 == j)
  if (entries.isEmpty) 0.0 else entries.head._2
}

Consequently

get (i, j) = A_{ij} .

(1)

This version follows the hint and has time complexity linear in the number of stored entries in row i. An ordered early-exit scan is also possible.

Solution

 0  0

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.

Solution

 0  0

Construct a fresh sparse matrix, transform each stored value, and omit products that become zero.

def scale(s: Double): SparseMatrix = {
  val out = new SparseMatrix(N)
  for (i <- 0 until N) {
    out.rows(i) = rows(i).map { case (j, x) => (j, s * x) }
      .filter(e => e._2 != 0.0)
  }
  out
}

Filtering preserves column order. It handles s == 0.0 and any floating point underflow producing zero. Sharing immutable list structure elsewhere would be safe; this code constructs new transformed rows. Within the class, Scala's ordinary private permits access to out.rows. The result is

out_{ij} = s A_{ij} .

(1)

The time complexity is

O (N + M)

for

M

stored entries. As usual for the supplied Double model, arithmetic means machine arithmetic; for a finite-real interpretation assume finite operands and products, excluding infinities and NaNs.

f

 0  0

Solution

 0  0

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.

g

 0  0

Solution

 0  0

For each source row, use a temporary dense array to accumulate contributions from nonzero pairs. For every stored

A_{ik}

, traverse stored entries in row

k

of the other sparse matrix.

def mult(that: SparseMatrix): SparseMatrix = {
  require(N == that.N)
  val out = new SparseMatrix(N)
  for (i <- 0 until N) {
    val acc = Array.fill[Double](N)(0.0)
    for ((k, x) <- rows(i)) {
      for ((j, y) <- that.rows(k)) {
        acc(j) += x * y
      }
    }
    var j = N - 1
    var result: Row = Nil
    while (j >= 0) {
      if (acc(j) != 0.0) result = (j, acc(j)) :: result
      j -= 1
    }
    out.rows(i) = result
  }
  out
}

During accumulation, acc(j) is the sum of the already processed terms contributing to position

(i, j)

. Missing entries multiply to zero, so ignoring them loses no contribution under the finite arithmetic convention of part (e). At completion,

out_{ij} = k = 0 \sum N - 1 A_{ik} that_{kj} .

(1)

Descending j and prepending produce strictly increasing stored indices. Omitting zero also handles cancellation. The temporary array uses

O (N)

auxiliary space beyond the output. The time complexity is

O (N^{2} + \sum_{i} \sum_{(k, x) \in rows (i)} ∣ that.rows (k) ∣),

(2)

at worst

O (N^{3})

, but potentially much smaller when the matrices are sparse. The

N^{2}

term covers clearing and scanning the row accumulators. Finite-precision rounding can affect the numerical result, as in any Double matrix multiplication.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

f

Solution

g

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion