Imperative programming (4216)

a

Solution

Maintain a processed prefix split into values below the pivot and values at least the pivot. The remaining suffix has not yet been classified. Here a and N are the given array and its length.

def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= N)
  var k = l
  var j = l
  while (j < r) {
    if (a(j) < p) {
      val t = a(k); a(k) = a(j); a(j) = t
      k += 1
    }
    j += 1
  }
  k
}

The loop invariant is

l \leq k \leq j \leq r, a [l .. k) < p, a [k .. j) \geq p .

In addition, the active segment remains a permutation of its original contents, and every entry outside it remains unchanged. If a(j) < p, swapping it with a(k) extends the first region; the displaced entry, when the two positions differ, already belongs in the second region. Otherwise only the second region grows. The loop variant is

r - j

. At termination

j = r

, so

a [l .. k) < p \leq a [k .. r), return k .

There are exactly

r - l

iterations, giving

O (r - l + 1)

time complexity and constant auxiliary space.

b

i

Solution

Take an integer pivot

0 \leq p \leq N + 1

. There are

p

possible values in

[0, p)

but only

k

occurrences of such values in the whole array. When

k < p

, the pigeonhole principle gives

Some value in [0, p) is missing.

Repeated values do not invalidate the argument: they can only reduce the number of distinct values represented by those

k

occurrences. The other side might also contain a missing value.

ii

Solution

There are

N + 1 - p

candidate values in

[p, N + 1)

and exactly

N - k

occurrences there. If

k \geq p

, then

N - k \leq N - p < N + 1 - p .

Thus the pigeonhole principle gives

Some value in [p, N + 1) is missing.

This conclusion does not assert that every value on the lower side is present; duplicates may leave both sides deficient.

c

Solution

Use missing-value search by deficient value intervals: halve the candidate value interval, and apply array partitioning only to the array segment whose entries lie in that interval.

def missing(): Int = {
  require(N < Int.MaxValue)
  var lo = 0; var hi = N + 1
  var l = 0; var r = N
  while (hi - lo > 1) {
    val p = lo + (hi - lo) / 2
    val k = partition(l, r, p)
    if (k - l < p - lo) {
      hi = p; r = k
    } else {
      lo = p; l = k
    }
  }
  lo
}

The loop invariant is

0 \leq l \leq r \leq N

0 \leq l o < hi \leq N + 1

, and

a [l .. r) \subseteq [l o, hi), r - l < hi - l o .

More precisely, the segment contains all occurrences of original values in

[l o, hi)

, and the complete array remains a permutation of its original state. The occurrences statement is essential: absence from the final segment must imply absence from the original array.

After array partitioning, let

m = r - l

W = hi - l o

m_{L} = k - l

, and

W_{L} = p - l o

. If

m_{L} < W_{L}

, retain the left side. Otherwise the right side has

m_{R} = m - m_{L} < W - W_{L} = W_{R}

occurrences. Either choice preserves the strict deficiency and the all-occurrences condition. The positive integer width

hi - l o

decreases, proving termination. At width one, the active segment has fewer than one entry and is empty. Therefore

return l o, l o \in [0, N + 1), l o is absent from the original array .

(3)

For the time complexity, after

t

splits the width is at most

⌈(N + 1) / 2^{t} ⌉

, and the scan length is smaller than that width. Summing over the

O (lo g (N + 1))

levels gives a geometric series plus logarithmic overhead, hence

O (N + 1)

overall, conventionally

O (N)

for

N \geq 1

. This proof bounds the retained occurrence count by the retained value width; it does not assume that each array partitioning splits the number of occurrences in half. The

N = 0

case returns zero immediately.

2

a

Solution

For each row, keep the row run length of the processed prefix. A false entry resets the length to zero; a true entry extends it by one.

val rowCount = Array.ofDim[Int](N, N)
var i = 0
while (i < N) {
  var j = 0
  var run = 0
  while (j < N) {
    if (a(i)(j)) run += 1 else run = 0
    rowCount(i)(j) = run
    j += 1
  }
  i += 1
}

The outer loop invariant states that rows before i have all their correct row run lengths. The inner loop invariant states that columns before j in row i are correct and that run is the length of the all-true suffix of a(i)[0..j). Initially this suffix is empty. Updating run gives exactly the suffix length ending at column j, proving the required formula, including zero at a false entry. Every cell is visited once:

rowCount (i) (j) = {0, 1 + rowCount (i) (j - 1), \neg a (i) (j), a (i) (j), O (N^{2}),

where the fictitious value at column

- 1

is zero. The table itself uses

O (N^{2})

storage.

b

Solution

Fix the top-right corner

(i, j)

and a bottom boundary

k

. A width

w

is feasible precisely when every row

m \in [i, k)

has at least

w

consecutive true entries ending at column

j

. Thus the largest feasible width is the minimum of those row run lengths, and the area is that width times

k - i

def maxRectangleAt(i: Int, j: Int): Int = {
  var k = i
  var width = j + 1
  var best = 0
  while (k < N) {
    width = math.min(width, rowCount(k)(j))
    k += 1
    best = math.max(best, (k - i) * width)
  }
  best
}

At the loop head, the loop invariant is

i \leq k \leq N

width best = min ({j + 1} \cup {rowCount (m) (j) : i \leq m < k}), = max ({0} \cup {(h - i) i \leq m < h min rowCount (m) (j) : i < h \leq k}) .

The initial cap

j + 1

makes the empty-prefix case well-defined and cannot restrict any actual run. Each iteration incorporates one new row and tests its corresponding bottom boundary. The loop variant is

N - k

, so

best = i < k \leq N max (k - i) i \leq m < k min rowCount (m) (j), O (N) .

A zero width contributes area zero, covering the case where no nonempty all-true rectangle starts at that corner.

c

Solution

Every nonempty axis-aligned rectangle has a top-right corner. Enumerate all such corners and retain the greatest area from part (b).

var best = 0
var i = 0
while (i < N) {
  var j = 0
  while (j < N) {
    best = math.max(best, maxRectangleAt(i, j))
    j += 1
  }
  i += 1
}

The loop invariant is that best is the greatest area obtained from the corners processed so far, or zero if there are none. Consequently

maximum area = best, O (N^{3}) time, O (N^{2}) storage .

The preprocessing cost from part (a) is included. An entirely false matrix, or an empty one, returns zero. In the printed example, rows

5

through

9

and columns

6

through

8

give area

5 \times 3 = 15

; exhaustive corner enumeration confirms that no larger all-true rectangle exists.^[ref]

Figure 1.
An area-15 rectangle and the row run lengths that certify its width
. **Details**.

3

a

Solution

Assume NumLevels >= 1. Both sentinel nodes occur on every level; the tail ends every linked list.

val head = new Node(Int.MinValue)
val tail = new Node(Int.MaxValue)
for (level <- 0 until NumLevels) {
  head.nexts(level) = tail
  tail.nexts(level) = null
}

The empty skip list therefore has

head ⟶ tail ⟶ null at every level .

The forbidden data values distinguish the sentinel nodes from genuine entries.

b

Solution

Follow the next reference for the desired level, stopping at the tail. This returns the genuine nodes in their linked list order, excluding both sentinel nodes.

def nodesAt(level: Int): List[Node] = {
  require(0 <= level && level < NumLevels)
  val out = scala.collection.mutable.ListBuffer.empty[Node]
  var n = head.nexts(level)
  while (n ne tail) {
    out += n
    n = n.nexts(level)
  }
  out.toList
}

Write

L_{h}

for the resulting sequence of nodes at level

h

. The abstraction function is

α = map (datum, L_{0}) .

It preserves repetitions, because distinct nodes may carry equal values. A suitable representation invariant requires the following:

head and tail are distinct sentinel nodes with the specified extreme values; every node has a nexts array of length NumLevels.
For each level, following references from head gives a finite acyclic chain ending at tail, then null; the data along that chain are nondecreasing. Genuine values lie strictly between the sentinel values.
Each $L_{h + 1}$ is a subsequence of $L_{h}$ by node identity, so the relative order of equal-valued nodes agrees across levels. Every genuine node occurs in $L_{0}$ and on a contiguous initial collection of levels.
A genuine node absent from a level has null in that level's slot. Tail slots are all null; every other slot on a chain points to the next member of that chain.

These structural requirements make the traversal terminate and make descending through levels valid. A probabilistic height distribution is a performance policy, rather than a condition needed for the abstraction function to describe an ordered sequence.

c

Solution

Start at the highest level. Move right only while the next key is strictly smaller than x, then descend without returning to head.

def findPreds(x: Int): Array[Node] = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = new Array[Node](NumLevels)
  var n = head
  var level = NumLevels - 1
  while (level >= 0) {
    while (n.nexts(level).datum < x) {
      n = n.nexts(level)
    }
    preds(level) = n
    level -= 1
  }
  preds
}

At each inner loop head, n belongs to the current level and has key below x. Every node already passed has key below x. The representation invariant ensures that n also belongs to the next lower level. Stopping just before a key at least x therefore gives

preds (h) . datum < x \leq preds (h) . nexts (h) . datum .

The tail prevents a null dereference during the comparison. Strict comparison makes the predecessor lie before the first occurrence of x, including duplicates. On the source diagram, findPreds(14) yields data

[11, 9, 9, - \infty]

, in increasing level order.^[ref]

With the customary random-level policy this has expected logarithmic time complexity for a suitably sized level cap; an unlucky skip list can require a linear scan. No deterministic logarithmic guarantee is claimed.

d

Solution

The level-zero successor of the predecessor is the first node whose value is at least x. Thus only one equality test remains.

def contains(x: Int): Boolean = {
  if (x == Int.MinValue || x == Int.MaxValue) false
  else {
    val n = findPreds(x)(0).nexts(0)
    (n ne tail) && n.datum == x
  }
}

In particular, the tail is never reported as a genuine member:

x occurs ⟺ preds (0) . nexts (0) \neq = tail \land datum = x .

The additional work after the skip list search is constant.

e

Solution

Pick the new node's highest level once, and splice the same node into every level up to that height. pickLevel must return a value in 0 until NumLevels.

def add(x: Int): Unit = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = findPreds(x)
  val highest = pickLevel
  require(0 <= highest && highest < NumLevels)
  val n = new Node(x)
  for (level <- 0 to highest) {
    n.nexts(level) = preds(level).nexts(level)
    preds(level).nexts(level) = n
  }
}

The fresh array contains null above the chosen height. At each changed level the new node lies after a smaller value and before a value at least x. Every new occurrence is placed before all previous equal-valued nodes, consistently across levels. Therefore the representation invariant is preserved and

α_{new} = α_{old} with one extra occurrence of x .

The splice work is

O (highest + 1)

in addition to one skip list search.

f

Solution

Identify the first matching node at level zero, then bypass that node wherever it appears. Comparing keys alone at higher levels could accidentally remove links to a different occurrence with the same key.

def delete(x: Int): Unit = {
  if (x != Int.MinValue && x != Int.MaxValue) {
    val preds = findPreds(x)
    val victim = preds(0).nexts(0)
    if ((victim ne tail) && victim.datum == x) {
      for (level <- 0 until NumLevels) {
        if (preds(level).nexts(level) eq victim) {
          preds(level).nexts(level) = victim.nexts(level)
        }
      }
    }
  }
}

Because higher-level chains are subsequences of level zero, the predecessor found for any level containing victim points directly to it: no earlier equal-valued node can intervene before the first level-zero occurrence. Bypassing it preserves the order and nesting of all the linked lists. Levels lacking it are unchanged. Thus

Delete exactly one occurrence of x if present; otherwise leave the list unchanged .

The additional work is

O (NumLevels)

. With the usual level cap and random heights, updates have the expected logarithmic time complexity associated with a skip list.

4

a

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.

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

b

Solution

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 .

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.

c

Solution

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} .

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.

d

Solution

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) .

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

e

Solution

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} .

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

Solution

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 .

The source sparse matrix is unchanged.

g

Solution

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} .

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) ∣),

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.

5

a

Solution

Interpret step as a positive increment, consistent with the increasing sequence and exclusive upper bound. State this precondition explicitly; a zero increment would not define the intended finite progression. Use a wider cursor to avoid integer overflow on the update after the last valid Int result.

class RangeIter(lower: Int, upper: Int, step: Int) extends Iter[Int] {
  require(step > 0)
  private var current = lower.toLong
  def hasNext: Boolean = current < upper.toLong
  def next(): Int = {
    require(hasNext)
    val answer = current.toInt
    current += step.toLong
    answer
  }
}

After

q

calls to next, the abstraction function is the sequence of values

lower + t step < upper

with

t \geq q

, in increasing order. Repeated calls to hasNext do not change it; next removes precisely its first value. Therefore

1, 3, 5, 7, 9, 11 for RangeIter (1, 13, 2) .

If lower >= upper, the represented sequence is empty immediately. The paper does not specify a descending-range convention; this implementation exposes its positive-step precondition rather than assigning one implicitly.

b

Solution

A demand-driven filtering iterator needs one cached accepted value. Otherwise hasNext would either lose an element or consume another accepted value every time it is queried.

def filterIter[T](p: T => Boolean, it: Iter[T]): Iter[T] =
  new Iter[T] {
    private var buffered: Option[T] = None
    private var finished = false
    private def fill(): Unit = {
      while (buffered.isEmpty && !finished) {
        if (!it.hasNext) finished = true
        else {
          val x = it.next()
          if (p(x)) buffered = Some(x)
        }
      }
    }
    def hasNext: Boolean = {
      fill()
      buffered.nonEmpty
    }
    def next(): T = {
      fill()
      require(buffered.nonEmpty)
      val answer = buffered.get
      buffered = None
      answer
    }
  }

The representation invariant says that buffered holds at most one accepted value. The represented sequence is the buffered value, if present, followed by the subsequence of the underlying remainder satisfying the predicate. Filling moves the next accepted value into the cache and discards only rejected values, so this abstract sequence is unchanged by hasNext. Clearing the cache in next removes its head. Thus

α (filterIter (p, i t)) = filter (p, α (i t)) .

next works even when the client has not first called hasNext; exhaustion violates its stated precondition. As with ordinary iterator adapters, clients should give this wrapper exclusive consumption of it, and the predicate should give a stable answer for each element. One call may scan several rejected elements, but across a complete traversal each source element is consumed once. Cache storage is constant.

c

Solution

Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.

def primeIter(upperBound: Int): Iter[Int] = {
  def isPrime(n: Int): Boolean = {
    if (n < 2) false
    else {
      var d = 2
      while (d <= n / d && n % d != 0) d += 1
      d > n / d
    }
  }
  filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}

Before each trial division iteration, no integer in

[2, d)

divides n. If division succeeds, the condition becomes false with

d \leq n / d

, and isPrime returns false. Otherwise the loop ends with

d > n / d

, so every possible small divisor has been excluded. The quotient comparison is equivalent to

d^{2} \leq n

for positive values and avoids integer overflow in d*d.

primeIter (23) : 2, 3, 5, 7, 11, 13, 17, 19.

Bounds at most two give an empty iterator. This method tests candidates lazily and uses

O (n)

trial divisions for candidate

n

; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.

6

a

Solution

Apply overload selection followed by dynamic dispatch: the receiver's static type determines visible signatures, and argument static types choose the overload. The receiver's runtime type then selects its override. A super call starts at the inherited implementation instead of redispatching to the override just entered.

For c.f1(y), the Y overload is visible on C, so its body in C runs. For a.f2(x), the X signature is selected and its override in C calls C.f1(X). For a.f2(y), the Y signature is selected; its body in C calls super.f1(y). The superclass B has only f1(X), so that call uses B.f1(X).

For b.f3(y), the static type B exposes only f3(X). Its override in C calls super.f2(x), entering B.f2(X). The unqualified f1(x) inside that body still uses dynamic dispatch on the original C instance, so it calls C.f1(X).

Finally c.f4(x) invokes the companion object C, which is a separate receiver extending B. Its f3(X) calls inherited B.f2(X), whose f1 call dispatches to ObjC.f1(X).^[ref]

The exact five output lines, including the final comma and space on each line, are:

f1(y:Y) in C, 
f1(x:X) in C, f2(x:X) in C, 
f1(x:X) in B, f2(y:Y) in C, 
f1(x:X) in C, f2(x:X) in B, f3(x:X) in C, 
f1(x:X) in ObjC, f2(x:X) in B, f3(x:X) in ObjC, f4(x:X) in C,

Select the signature statically, then dispatch that signature dynamically .

b

Solution

In Scala trait linearization, the rightmost mixed-in trait takes priority. Merge inherited linearizations while retaining a shared ancestor only at its final position; super advances to the next implementation in the resulting chain. Ignoring predefined bases, the lookup orders are

Life1, Exercise, Work, Life
Life2, Dance, Exercise, Program, Study, Work, Fun, Life
Life3, Program, Study, Work, Dance, Fun, Exercise, Life

For example, Dance alone has order Dance, Fun, Exercise, Life. In Life2, the additional Program branch already contains Fun before Life; keeping that shared ancestry in its later position moves Fun after Work, while Dance still takes priority. Reversing the mixins yields the third chain above.

Each describe first delegates and then prints, so the lines appear in the reverse of the method lookup order. The exact output, including the two blank lines, is

I live.
I work.
I exercise.

I live.
I have fun.
I work.
I study.
I program.
I exercise.
I dance.

I live.
I exercise.
I have fun.
I dance.
I work.
I study.
I program.

Lookup follows the linearization; these prints occur while the calls return .

The super inside a trait therefore need not call that trait's isolated textual parent; the receiving object's full Scala trait linearization controls the next body.

7

a

Solution

Store characters in a mutable dynamic array. Its length is maintained by the collection, giving constant-time size.

class DocImpl extends Doc {
  private val text = scala.collection.mutable.ArrayBuffer.empty[Char]
  def insert(x: Char, pos: Int): Unit = {
    require(0 <= pos && pos <= text.length)
    text.insert(pos, x)
  }
  def delete(pos: Int): Char = {
    require(0 <= pos && pos < text.length)
    text.remove(pos)
  }
  def read(pos: Int): Char = {
    require(0 <= pos && pos < text.length)
    text(pos)
  }
  def size: Int = text.length
}

The representation invariant requires a nonnull private dynamic array containing a finite sequence of characters, with its internal collection invariant maintained by the library. The abstraction function is

α (text) = ⟨ text (0), \dots, text (length - 1)⟩ .

Insertion allows the end position and shifts the suffix right; deletion returns exactly the removed character and shifts the suffix left. read leaves the abstract state unchanged. size equals the abstract sequence length in

O (1)

time complexity. Indexed reads are also constant time; insertion and deletion may take linear time, which the question permits.

b

Solution

Keep 26 cached counts, updating them after a successful delegated edit. Count exactly lowercase letters; the query alphabet does not make uppercase letters the same character.

trait CharTrackPlugIn extends Doc {
  private val counts = Array.fill[Int](26)(0)
  private def lower(x: Char): Boolean = 'a' <= x && x <= 'z'
  abstract override def insert(x: Char, pos: Int): Unit = {
    super.insert(x, pos)
    if (lower(x)) counts(x - 'a') += 1
  }
  abstract override def delete(pos: Int): Char = {
    val x = super.delete(pos)
    if (lower(x)) counts(x - 'a') -= 1
    x
  }
  def getCount(x: Char): Int = {
    assert(lower(x))
    counts(x - 'a')
  }
}

For an initially empty underlying document that stores inserted arguments unchanged, the representation invariant is

counts (c - ’a’) = # {i : read (i) = c} (c = ’a’, \dots, ’z’) .

Insertion increments precisely the inserted lowercase character's count. Deletion uses the returned character, avoiding an extra indexed read and decrementing the character actually removed. Updating after super means a rejected edit leaves the counts unchanged. Both the added update work and getCount use

O (1)

time complexity and fixed storage.

The abstract override methods implement a stackable trait modification: they require a concrete document implementation further along the delegation chain. The invariant above depends on subsequent layers preserving inserted characters. Part (d) deliberately composes a transforming layer that can break this assumption; that is the transform-sensitive trait frequency counter phenomenon.

c

Solution

Convert lowercase alphabet letters before passing them to the next implementation. Already uppercase letters and other characters pass through unchanged.

trait CapitalisePlugIn extends Doc {
  abstract override def insert(x: Char, pos: Int): Unit = {
    val y = if ('a' <= x && x <= 'z') ('A' + (x - 'a')).toChar else x
    super.insert(y, pos)
  }
}

The character conversion uses the paper's contiguous lowercase and uppercase Latin ranges. Thus

insert(’a’,pos) delegates as insert(’A’,pos) .

Deletion, reading, and size need no overrides.

d

Solution

The rightmost trait intercepts insertion first. In A, capitalization runs before counting, so the counter receives uppercase A and does not increment the lowercase count. In B, counting receives lowercase a, delegates to capitalization, and then increments the original lowercase argument's counter. Both concrete documents store uppercase A.

The exact output is

0
1

d 1. getCount (’a’) = 0, d 2. getCount (’a’) = 1.

This illustrates an order-sensitive stackable trait modification. In the second composition the cached count describes intercepted insertion arguments, and no longer the actual lowercase characters in the stored document. For example, deleting its uppercase A would not decrement the lowercase counter. A counter required to track actual contents under arbitrary transforming mixins would need a stronger composition contract or would inspect the stored character after insertion; such a change would alter the intended behavior of this example.

8

a

Solution

The interval containment order compares the lower endpoints in reverse and the upper endpoints in their ordinary order. The smallest containing integer interval uses the smaller lower endpoint and the larger upper endpoint.

class Interval(val l: Int, val u: Int) extends Ordered[Interval] {
  require(l <= u)
  def <=(that: Interval): Boolean = that.l <= l && u <= that.u
  def lub(that: Interval): Interval =
    new Interval(math.min(l, that.l), math.max(u, that.u))
}

Endpoint comparison immediately proves reflexivity, transitivity, and antisymmetry on interval values. If two separately allocated instances have the same endpoints, they denote the same abstract interval; object identity is not the mathematical equality used by this partial order.

The returned interval contains both operands. Every other containing interval has a lower endpoint at most both original lower endpoints and an upper endpoint at least both original upper endpoints, so it also contains the returned hull. Hence

[l, u] \lor [l^{'}, u^{'}] = [min (l, l^{'}), max (u, u^{'})] .

This least upper bound need not equal the ordinary union: the hull of

[1, 2]

and

[5, 6]

[1, 6]

, including the gap.

b

Solution

Keep precisely those elements with no strictly smaller element in the input. Express strictness using the partial order itself, avoiding reliance on Scala reference equality.

def minimal[T <: Ordered[T]](xs: Set[T]): Set[T] =
  xs.filter { x =>
    !xs.exists(y => (y <= x) && !(x <= y))
  }

In a partial order,

y < x

means

y \leq x

and

x \neq \leq y

. Therefore

minimal (X) = {x \in X : ∄ y \in X, y < x} .

The empty set produces the empty set. An incomparable pair is retained in full; a minimal element need not be a least element. At most

O (∣ X ∣^{2})

order comparisons are needed, and only the supplied F-bounded generic interface is required.

c

Solution

Store the minimal elements of the finite generating set. The represented upper set itself may be infinite; the code manipulates its finite basis.

class UpSet[T <: Ordered[T]](c: Set[T]) extends Ordered[UpSet[T]] {
  private val basis: Set[T] = minimal(c)
  def contains(x: T): Boolean = basis.exists(a => a <= x)
  def intersection(that: UpSet[T]): UpSet[T] = {
    val generators: Set[T] =
      for (a <- basis; b <- that.basis) yield a.lub(b)
    new UpSet[T](generators)
  }
  def <=(that: UpSet[T]): Boolean = basis.forall(a => that.contains(a))
  def lub(that: UpSet[T]): UpSet[T] =
    new UpSet[T](basis union that.basis)
}

The abstraction function and representation invariant are

α (B) =↑ B = {x : \exists b \in B, b \leq x}, B finite with no strictly comparable distinct values .

Removing nonminimal generators preserves the upward closure: in a finite generating set, repeatedly descending below any discarded element must reach a retained minimal element. Thus the constructor represents exactly the required finitely generated upper set.

Membership follows directly from the abstraction function. For intersection, an element

x

lies above some

a \in B

and some

b \in C

exactly when it lies above their least upper bound:

(a \leq x \land b \leq x) ⟺ a \lor b \leq x .