Let denote the matrix unit with one at position and zero elsewhere. The five inverses are
Thus each is the identity matrix with only the indicated off-diagonal matrix entry altered. These inverses reverse the corresponding row additions; no row scaling or permutation is involved.
The second pivot is two. Row three has second entry two, so subtract row two; row four has second entry minus two, so add row two. Therefore , . Their trailing row pairs become and , respectively; the zero in the third pivot position is why a later row interchange is needed.
Left multiplication by an elementary matrix adds a multiple of row one to its designated target row. The first-column entries below the pivot are , so , , . The corresponding row operations are , , and . Since none changes row one, their sequential application gives the required three eliminated first-column entries and the displayed remaining entries.
Repeatedly applying the previous product rule gives
Formally, the result holds for ; multiplication by preserves the zero off-diagonal matrix entries and multiplies each diagonal matrix entry by , proving the induction step.
By matrix multiplication, . A potentially nonzero term requires because is a diagonal matrix, and because is a diagonal matrix. For these requirements cannot both hold. Thus every summand is zero and whenever .
One base-class implementation changes the private fields directly:
def flip(): Unit = {
  val oldH = _h
  _h = _w
  _w = oldH
}
The completed operation leaves the area unchanged. It calls no overriding setters, so the logging subclass's count stays unchanged and does not need an override. The invariant is about completed public updates, not transient internal states between the two assignments.
A second implementation uses public setters:
def flip(): Unit = {
  val oldH = height
  val oldW = width
  height = oldW
  width = oldH
}
These setter calls use dynamic dispatch on a logging receiver. Starting at height two and width three, the first call increases the temporary area from six to nine and wrongly increments the count, while the final area returns to six. This version needs a subclass override. With the counter name from part (i), the following override discards the internal setter contributions:
override def flip(): Unit = {
  val before = increases
  super.flip()
  increases = before
}
For this specified base implementation the two assignments complete normally and the final area equals the initial area, so restoring the saved count is correct. Another design could suppress logging during the compound operation. The difference between the two base implementations illustrates the fragile base class problem: an internal refactoring can change subclass behavior through newly introduced virtual calls.
Compare areas before and after each completed setter call. Widen before multiplication so all products of two Int dimensions are represented exactly:
class LoggedResizableFrame(h: Int, w: Int) extends ResizableFrame(h, w) {
  private var increases = BigInt(0)

  private def actualArea: Long = height.toLong * width.toLong

  override def height_=(h: Int): Unit = {
    val before = actualArea
    super.height_=(h)
    if (actualArea > before) increases += 1
  }

  override def width_=(w: Int): Unit = {
    val before = actualArea
    super.width_=(w)
    if (actualArea > before) increases += 1
  }

  def getIncreases: BigInt = increases
}
The history invariant is that increases counts exactly the completed dimension updates whose new area strictly exceeds their immediately preceding area. The constructor's starting area is a baseline, not an increase. Each overriding setter invokes the superclass setter once and increments precisely when its comparison succeeds. Equal-area changes do not count. The comparison is on area, not merely on which dimension increased; this also handles zero or signed dimensions without adding an unstated input restriction. An arbitrary-precision integer avoids eventual counter overflow.
Make defensive copies on both entry and exit, while keeping the supplied Dimension class unchanged:
class Frame(d: Dimension) {
  require(d != null)
  private val saved = new Dimension(d.width, d.height)
  private val savedArea = saved.width * saved.height

  def area: Int = savedArea
  def dimension: Dimension = new Dimension(saved.width, saved.height)
  def isPortrait: Boolean = saved.height >= saved.width
}
The private stored dimensions have no aliases exposed to the caller and are never changed. Mutating the constructor argument affects only the caller's object; mutating a returned Dimension affects only a fresh copy. Consequently the stored area is calculated once and stays equal to the stored dimensions' product. This defensive copying is sufficient because Dimension contains only primitive fields; a more deeply nested mutable structure could require a deep copy or an immutable representation.
The multiplication above deliberately retains the supplied class's Int arithmetic and accessor type. If an exact mathematical area outside that range is required, compute once with saved.width.toLong * saved.height.toLong and expose Long instead; avoiding aliases and avoiding integer overflow are separate concerns.
The constructor stores a reference, not a copy:
val d = new Dimension(3, 4)
val f = new Frame(d)
d.width = 10
Now f.area is still , but the product of its stored dimension fields is . Even without retaining d, a client can break the same invariant through f.dimension.height = 9, because the accessor exposes the same mutable object. This is representation exposure through reference aliasing. A val prevents reassigning the reference; it does not freeze the referenced object.
Class inheritance defines a subclass by extending another class's behavior, often with method overriding and subtyping. An editor might have an abstract Command type with execute, and subclasses for insertion and deletion. The controller keeps commands through the common type and dynamic dispatch chooses each command's actual operation. Alternatively, a specialized document can extend a base document's documented behavior. An inheritance relationship used for substitution must preserve the superclass contract; borrowing its code alone does not justify exposing incompatible behavior. Commands exemplify the Command pattern without exposing document storage to the controller.
Encapsulation exposes operations with contracts while hiding representation details and controlling changes to state. In a text editor, a document object can privately store text and cursor position and expose insert, delete and moveCursor. Clients cannot directly splice internal storage or set a cursor outside the document. The document's methods enforce its representation invariant, and the implementation can later replace a character array by a different text representation without changing the public editing interface. Merely declaring a field private is insufficient if an accessor returns the mutable representation itself.
A minimum-oriented binary heap is an appropriate alternative. Store a complete binary tree in an array and maintain heap order. Insertion appends a value and moves it upward; removing the root replaces it by the last value and moves that value downward. Each path has levels, and equal values can be stored in separate slots. Both operations therefore take time when capacity is available.
Unlike a binary search tree, the heap does not maintain a complete search order, so finding an arbitrary specified value can require inspections. A simple array implementation also has a capacity issue: a fixed array can fill, and resizing a growable array occasionally costs , giving an amortized insertion guarantee unless allocation is otherwise managed. This capacity cost is an implementation tradeoff, not an inherent inability of heaps to represent the priority queue abstraction.
Not automatically: the duplicate-value policy must implement a multiset. A strict binary search tree storing one entry per distinct key represents a set; inserting a second equal value then loses a required occurrence. A fixed rule that puts all equal values on one side also needs care, because ordinary balancing rotations need not preserve that one-sided equality rule.
One valid refinement stores a multiplicity at each distinct key. Inserting an equal key increments its count; delMin decrements the minimum key's count and removes that node only at zero. Alternatively, use distinct internal keys such as (value, uniqueSerial) while ordering primarily by value and returning only the value. With an appropriate balanced representation either approach preserves every occurrence and the required operation bounds. A bare claim about balanced search trees, with no treatment of duplicates, does not establish the abstract specification.
Yes, provided balancing guarantees logarithmic height. In a suitably maintained balanced binary tree of height , insertion searches one root-to-leaf path and deletion of the minimum follows the leftmost path. Reconnecting the tree and performing the required rebalancing also costs at most a constant amount per level for the standard logarithmic-time schemes. Thus both operations take time, conventionally written for nontrivial sizes. Merely calling a tree approximately balanced would not prove that height bound; it is the balancing guarantee that matters. Without it, a binary search tree can have linear height.
A fixed array containing the distinct seen integers needs capacity at most , because at most one new distinct value is introduced per result entry. Its auxiliary space is therefore , rather than the bitmap's universe storage. A size field identifies the occupied prefix; insertion first checks membership, and appends only when absent.
An unsorted occupied prefix needs linear membership scans, giving total work by the same summation as in the original version. Keeping it sorted permits binary search membership in , but inserting a new value can shift entries, so the overall worst-case upper bound remains quadratic. Unlike a bitmap, the space cost depends on the number of stored values rather than their largest possible numerical magnitude. Compared with part (a)(ii), this extra set array also duplicates information already present in the output prefix; its principal benefit is a separate set interface, not an automatic asymptotic speedup.
The original routine uses auxiliary space and at most membership work. A bitmap with universe size uses extra storage and work in the sequence-generation loop because membership and insertion each take constant time. Here the safe universal bound chooses , so extra storage is for growing .
Initialization must be accounted for separately: creating and clearing a Boolean array of length takes work in the usual array-initialization model. Consequently the complete one-shot routine takes , which is with this conservative universe bound. The faster lookup does not make that quadratic setup disappear. If the bitmap is already initialized, or the analysis explicitly charges only the generation phase, the remaining phase is linear. A tighter known bound on values can reduce the universe cost, but no unproved growth bound is needed here.
For result entries the largest required index is , so the bound in part (a)(iii) permits universe size . Check that the chosen universe can itself be expressed as an array length:
def recamanBitmap(a: Array[Int]): Unit = {
  val n = a.length
  if (n == 0) return
  val capacity = n.toLong * (n.toLong - 1L) / 2L + 1L
  require(capacity <= Int.MaxValue.toLong, "Bitmap universe too large")
  val seen = new BitMapSet(capacity.toInt)
  a(0) = 0
  seen.add(0)
  var i = 1
  while (i < n) {
    val candidate = a(i - 1).toLong - i.toLong
    val next =
      if (candidate > 0L && !seen.contains(candidate.toInt)) candidate
      else a(i - 1).toLong + i.toLong
    a(i) = next.toInt
    seen.add(a(i))
    i += 1
  }
}
The loop invariant is that the result prefix contains exactly and the abstraction function of seen is their set of values. The universe bound ensures that each positive candidate being queried and each actual next value is less than capacity; values are nonnegative. Thus the conversions and the restricted add precondition are justified, rather than merely hoped to succeed. At a repeated addition, add returning false is harmless: the set of previously seen values is still updated correctly. The loop variant is . At return every result entry agrees with the original recurrence.
Regardless of which branch is taken, . Starting from zero and applying induction gives
For the inductive step, add to the bound for the previous value. The subtraction branch gives an even smaller result, and positivity is checked there. This bound need not describe the actual growth sharply; it is sufficient to size a finite membership representation for a requested prefix.

There are unlisted articles, also show them or only show them.