Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 5

Choose a fixed positive capacity

C

and represent the abstract state by a finite partial function

re p : Z ⇀ Z

. Its domain of a partial function

S

has at most

C

members; each

re p (x)

belongs to

S

and is a fixed point:

re p (re p (x)) = re p (x) (x \in S) .

(1)

The blocks of a set partition are the nonempty fibres of rep, and their shared values are their disjoint-set representatives. Initially $re p = \emptyset$ , so

S = \emptyset

. Representatives need not be the minimum members of their blocks.

trait DisjointSets {
  val capacity: Int
  // State: rep is a finite idempotent map, |dom rep| <= capacity.
  // Initially: rep is empty; capacity is fixed and positive.

  // Pre: x is absent and |dom rep| < capacity.
  // Post: add x -> x; leave every old mapping unchanged.
  def makeSet(x: Int): Unit

  // Pre: x belongs to dom rep.
  // Post: state unchanged; return rep(x).
  def find(x: Int): Int

  // Pre: x and y belong to dom rep.
  // Post: merge their blocks, retaining old rep(x).
  def union(x: Int, y: Int): Unit
}

Precisely, makeSet(x) extends the domain of a partial function by

x

with

re p^{'} (x) = x

. For union(x,y), snapshot

r_{x} = re p_{0} (x)

and

r_{y} = re p_{0} (y)

, keep

S

unchanged, and set

re p^{'} (z) = {r_{x} re p_{0} (z) re p_{0} (z) = r_{y}, otherwise .

(2)

This merges the two blocks and keeps the representative of the first argument's block. If

r_{x} = r_{y}

, it is an identity operation. This deterministic design choice satisfies disjoint set union without imposing minimum-element representatives. The capacity bound is explicit in the abstract data type so that the bounded implementation does not silently strengthen makeSet's precondition.

b

 0  0

Solution

 0  0

Use parallel arrays for keys and their representative values, with only a prefix active:

override val capacity: Int = 1000
private val elements = new Array[Int](capacity)
private val representatives = new Array[Int](capacity)
private var used = 0

The chosen bound is an explicit implementation parameter of the abstract data type; another a-priori positive bound works identically. The initial map is empty because used == 0. Zero-filled unused cells are not members of the map, so zero and negative keys remain valid integers. Use DisjointSets consistently as the trait name; the source's prose variation DisjointSubsets does not change the declared interface.

c

 0  0

Solution

 0  0

A sufficient representation invariant is:

Both arrays have length capacity, with $c a p a c i t y > 0$ and $0 \leq u se d \leq c a p a c i t y$ .
The active keys elements(0 until used) are pairwise distinct.
For each active index $k$ , representatives(k) equals some active key elements(j).
Every such representative is fixed: if representatives(k) == elements(j), then representatives(j) == elements(j).

The abstraction function is

re p = {e l e m e n t s (k) \mapsto re p rese n t a t i v es (k) ∣ 0 \leq k < u se d} .

(1)

The last two conditions ensure each representative is a genuine member of its own block and that the abstract function is idempotent function. Cells beyond used are unconstrained and ignored. When used == 0, these conditions hold vacuously and the abstraction function yields the empty map. This is an explicit-key version of quick-find, rather than a parent-pointer disjoint-set forest.

d

 0  0

Solution

 0  0

Return the key's active array index, or -1 if absent:

private def isInMap(x: Int): Int = {
  var i = 0
  while (i < used && elements(i) != x) i += 1
  if (i < used) i else -1
}

The loop invariant states that every index below i has a key different from x. The scan ignores all inactive cells, and short-circuit evaluation protects the array access at the end of the active prefix. Key uniqueness makes a successful index unambiguous. Its running time is

O (u se d)

e

 0  0

Solution

 0  0

Insert a singleton mapping, retrieve a stored representative, or relabel every occurrence of the second block's old representative:

def makeSet(x: Int): Unit = {
  require(isInMap(x) == -1, "element already present")
  require(used < capacity, "capacity exhausted")
  elements(used) = x
  representatives(used) = x
  used += 1
}

def find(x: Int): Int = {
  val i = isInMap(x)
  require(i >= 0, "unknown element")
  representatives(i)
}

def union(x: Int, y: Int): Unit = {
  val keep = find(x)
  val replace = find(y)
  if (keep != replace) {
    var i = 0
    while (i < used) {
      if (representatives(i) == replace) representatives(i) = keep
      i += 1
    }
  }
}

For makeSet, the new key is absent, its representative is itself, and old mappings are unchanged. find is a read-only linear search. In union, snapshot both representatives before changing any cell: recomputing the representative of y during the scan could change the criterion halfway through. The loop invariant says that every processed index already has its specified final representative and every unprocessed index still has its old representative. The cached labels make this assertion stable.

At exit the abstract postcondition in part (a) holds. The surviving representative was already a fixed point and belongs to its old block; every member of the replaced block, including its old representative key, now maps to it. Thus idempotence and key uniqueness are preserved. Duplicate insertions, absent-element operations and capacity overflow fail before changing the map. Each operation is

O (u se d)

in the worst case, except that a same-block union can skip the relabel scan after its lookups. Storage is

O (c a p a c i t y)

. These bounds follow from the chosen parallel-array quick-find representation; no parent-pointer optimization is being assumed.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 5

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

 Ancestors (10)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 5

 Discussion (0)  Subscribe (1)

 Discussion (0)