Search for the predecessor of the matching linked list node, or for the last linked list node if there is no match. This helper makes deletion uniform:The search loop invariant says that
class LinkedBook extends Book {
private val header = new Node("", "", null)
// Pre: name != null.
// Post: result is header or a real node.
// All real nodes through result have names different from name.
// result.next is null or has name equal to name.
// No state is changed.
private def findPrev(name: String): Node = {
require(name != null)
var p = header
while (p.next != null && p.next.name != name) {
p = p.next
}
p
}
def store(name: String, number: String): Unit = {
require(name != null && number != null)
val p = findPrev(name)
if (p.next == null)
p.next = new Node(name, number, null)
else
p.next.number = number
}
def recall(name: String): String = {
require(name != null)
val p = findPrev(name)
require(p.next != null, "Name is not in the book")
p.next.number
}
def isInBook(name: String): Boolean = {
require(name != null)
findPrev(name).next != null
}
def delete(name: String): Boolean = {
require(name != null)
val p = findPrev(name)
if (p.next == null) false
else {
p.next = p.next.next
true
}
}
}p is the header or a reachable real linked list node, and every real linked list node from the start through p has a name different from the requested name. The linked list has not been changed. Short-circuit evaluation protects p.next.name when the end is reached. The loop variant is the number of real linked list nodes strictly after p; finiteness and acyclicity make it a nonnegative decreasing integer. Consequently the helper's stated postcondition holds.For
store, a found name changes only its number; an absent name adds exactly one fresh binding at the end, maintaining uniqueness. For delete, unlinking the found linked list node removes exactly the requested binding; absence returns false without mutation. Both query operations preserve the abstraction function. Non-null preconditions are checked at entry; recall additionally checks membership using the one completed search, avoiding a redundant whole-list membership scan. The helper is the only additional operation and its complete behavioral contract is stated above.Start with a private permanent header whose
next is null. Its two string fields are ignored. For a concrete state satisfying the representation invariant, define the abstraction functionThe representation invariant says that the header exists, the reachable real linked list is finite and acyclic, the header is not a real reachable linked list node, all real name/number fields are non-null strings, and real names are pairwise distinct. The real linked list nodes are owned by the book, so clients cannot mutate their fields through exposed references. Distinct names ensure that the displayed relation is a partial function. The initial empty linked list has abstraction . Reordering real linked list nodes changes the representation but not the abstract book.A permanent dummy header node gives even the first real linked list node a predecessor. Insertion into an empty linked list and deletion or movement of its first real linked list node then use the same link updates as internal cases. The header itself represents no contact, so it also removes the need to use a real name as a special end marker. A search still needs a null-end check.
The linked list node needs mutable fields for changing a stored number and rearranging links:The implementation will keep its real linked list nodes private to the
class Node(var name: String, var number: String, var next: Node)Book object and will not return linked list node references to clients.The abstract state is a finite partial function from strings to strings, initially empty. Names and numbers below are non-null mathematical strings. These preconditions and postconditions specify an abstract data type, independently of any linked list. In particular, a failed deletion leaves the abstract state unchanged, and recalling a missing name is outside the operation's specified domain.
store replaces an old binding if present; delete reports whether a binding existed.trait Book {
// Abstract state B: finite partial map String -> String; initially empty.
// Pre: name != null && number != null.
// Post: B' = B updated at name with number.
def store(name: String, number: String): Unit
// Pre: name != null && name is in dom(B).
// Post: result = B(name), and B' = B.
def recall(name: String): String
// Pre: name != null.
// Post: result iff name is in dom(B), and B' = B.
def isInBook(name: String): Boolean
// Pre: name != null.
// Post: result iff name was in dom(B); B' = B with name removed.
def delete(name: String): Boolean
}Keep a deficient interval of possible values and only the array segment containing occurrences from that interval. This is missing-value search by deficient value intervals:The precondition is that every original entry lies in . The loop invariant istogether with: every active entry lies in , and every original occurrence with a value in that interval is in the active segment. The whole array remains a permutation of its initial contents. Initially these assertions follow from the precondition and .
def missing(): Int = {
val n = a.length
var lo = 0L
var hi = n.toLong + 1L
var l = 0
var r = n
while (hi - lo > 1L) {
val p = lo + (hi - lo) / 2L
val k = partition(l, r, p.toInt)
if ((k - l).toLong < p - lo) {
hi = p
r = k
} else {
lo = p
l = k
}
}
lo.toInt
}After array partitioning, the low subinterval has occurrences and possible values. If it is deficient, retaining it preserves the loop invariant. Otherwise , while the original active count is strictly less than ; subtraction givesThus the high subinterval is deficient and retaining it also preserves the loop invariant. Discarded occurrences lie outside the new candidate interval. The loop variant is the positive integer , which strictly decreases because the midpoint is strictly internal. At exit the interval has one possible value and fewer than one occurrence, so
lo is absent from the entire original array. For the loop is skipped and zero is returned. The Long value bounds avoid overflowing ; every internal pivot is at most , so its checked mathematical range fits Int.For the time complexity, let be the interval width and its active occurrence count before iteration . The loop invariant gives , and binary search gives . Each two-way array partition costs . Until the width reaches one, the widths are bounded by , so the total scan work is bounded by a geometric series plus loop overhead: overall, hence for positive . Partitioning the full array again at every iteration would instead lose this bound. Auxiliary space complexity is .
Let The loop invariant is , every entry of is less than , every entry of is at least , and the segment's multiset is unchanged. Entries outside are unchanged. When
a be the given enclosing array. A two-way array partition needs only one scan, and does not require the pivot to occur in the array:def partition(l: Int, r: Int, p: Int): Int = {
require(0 <= l && l <= r && r <= a.length)
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
}a(j)<p, swapping it into position k extends the low part; if k<j, the displaced entry was in the high part and remains there after j advances. If k==j, the self-swap is harmless. The other branch simply extends the high part. The loop variant is . At exit , so the returned has the required separation property, including empty segments and arbitrarily many duplicate entries. The time complexity is and auxiliary space complexity is .Print separators before all but the first term, so there is neither a leading nor a trailing plus sign:The loop invariant says that exactly the first unit fractions have been printed in order, separated by
def printRat(num: Int, den: Int): Unit = {
print(num.toString + "/" + den.toString)
}
def printEgypt(e: Array[Int]): Unit = {
if (e.isEmpty) print("0")
var i = 0
while (i < e.length) {
if (i > 0) print(" + ")
print("1/" + e(i).toString)
i += 1
}
} + , with no trailing separator. The loop variant is . The empty array is displayed as zero. Since and , the output is 5/7 = 1/2 + 1/5 + 1/70. The source's earlier example with middle denominator and final denominator contains the arithmetic typo; its final printing example is correct. Indeed , so no positive final term could repair that particular prefix. The printing routine reports the generated terms rather than imposing a particular expansion.An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only The loop invariant is , , , , andWriting , the fraction for the extended prefix has numerator and denominator . These are the
Reduce on every intermediate value. First define an exact helper:def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
var n = BigInt(0)
var d = BigInt(1)
var i = 0
while (i < e.length) {
require(e(i) > 0)
val x = BigInt(e(i))
val g = d.gcd(x)
val nextN = n * (x / g) + d / g
val nextD = d * (x / g)
val h = nextN.gcd(nextD)
n = nextN / h
d = nextD / h
i += 1
}
(n, d)
}
def toRat(e: Array[Int]): (Int, Int) = {
val result = toRatExact(e)
require(result._1.isValidInt && result._2.isValidInt,
"Reduced result does not fit (Int, Int)")
(result._1.toInt, result._2.toInt)
}nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is . At exit the helper returns the exact sum in lowest terms, including for the empty array.There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits
(Int, Int). For example, the sum is in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.[ref]Scala 2.12 BigInt API documentation. Checked representability with isValidInt before the potentially truncating toInt conversion
Maintain an accumulated array of denominators and an exact remaining fraction. The usual greedy algorithm can require a denominator larger than The loop invariant is , , all entries of
Int.MaxValue, even for an input with Int components. The following implementation uses arbitrary-precision integers internally. If that representational limit is reached, it returns the always-valid alternative consisting of num copies of . Repeated denominators are permitted by the given Egyptian fraction representation.def fromRat(num: Int, den: Int): Array[Int] = {
require(0 <= num && num < den)
val start = Reduce(num, den)
var n = BigInt(start._1)
var d = BigInt(start._2)
var e = Array.empty[Int]
while (n > 0) {
val q = (d + n - 1) / n
if (!q.isValidInt) return Array.fill(num)(den)
e = e :+ q.toInt
val nextN = n * q - d
val nextD = d * q
val g = nextN.gcd(nextD)
n = nextN / g
d = nextD / g
}
e
}e are positive, andAppending and replacing the residual by preserves this equality; division by the greatest common divisor preserves the residual's value. The loop variant is , by the proof in part (b). If nextN is zero, its greatest common divisor with nextD is nextD, giving residual . On normal exit the residual is zero and the returned array has exactly the required value. On the early-return branch, num copies of have that same value directly; the partial greedy Egyptian fraction expansion is discarded. num=0 returns an empty array.The fallback is a correctness provision for the fixed result type, not an efficiency claim: a large repeated-term array can be impractical. An array of arbitrary-precision integers would retain the greedy Egyptian fraction expansion without this fallback. Allocation, as with any output-producing program, requires enough available memory. The
BigInt remainder, greatest common divisor and checked conversion operations are documented in [ref]Scala 2.12 BigInt API documentation. Methods gcd, isValidInt and toInt
.For a positive remaining fraction , the condition is equivalent to . Since decreases as the positive integer increases, choose . The zero fraction needs no term. This is the greedy Egyptian fraction expansion.
The remaining fraction isThe defining inequalities give . Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.
Use the remainder form of the Euclidean algorithm to compute the greatest common divisor, then divide both components of the fraction by it:The loop invariant is , , and . Initially it holds by symmetry of the greatest common divisor. For , the integer division identity , with , shows that and have exactly the same common integer divisors. Thus the update preserves the loop invariant. The loop variant is the nonnegative integer , which strictly decreases on each iteration. At exit , so . Dividing by preserves the rational number and makes the returned components coprime. In particular, zero is returned as . No multiplication is needed, and all remainders remain within the original nonnegative
def Reduce(num: Int, den: Int): (Int, Int) = {
require(0 <= num && num < den)
var a = den
var b = num
while (b != 0) {
val r = a % b
a = b
b = r
}
(num / a, den / a)
}Int range.All edge lengths are positive, so run the Dijkstra algorithm from every source , retaining distances and a shortest-path tree of its reachable component. Each run takes with a binary heap. The following scans after each run use only additional work.
For a directed graph, inspect every closing edge and consider when is reachable. The tree route from to followed by this edge is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its vertices as ; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is the shortest directed-cycle length.
For an undirected graph, do not combine an edge with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only edges absent from the current shortest-path tree, with both endpoints reachable, and considerThe two tree routes and this non-tree edge contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.
To prove equality is attained, take a shortest cycle and a source on it. If either cycle edge incident to is absent from the tree, its candidate uses a shortest route no longer than the rest of , so it is at most the length of . Otherwise both incident edges are in the tree, and their other endpoints lie in different branches below . Along the remaining segment of , some edge crosses between different branches. Such an edge is not a tree edge. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of from ; their sum plus the crossing edge is at most the length of . Thus some candidate is no greater than the optimum, completing the proof.
Return the smallest finite candidate, or report acyclicity if none exists. The total running time is , as required. The ordinary convention is a simple graph; if parallel edges are allowed, track actual edge identities when excluding tree edges, and treat a self-loop as its own cycle rather than discarding it. This is shortest cycle by repeated shortest-path trees.
Initialize and elsewhere. Perform full passes over the directed edges, applying edge relaxation whenever is finite. For an undirected graph, process each edge in both directions. Stop early if a pass makes no change.
Each finite label records the cost of a discovered directed walk, so it never understates the true infimum. After passes, relaxation has propagated along every route of at most edges, so the label is no greater than the cost of any such route. If no reachable negative-cost closed walk exists, an optimal route can be chosen without repeated vertices and has at most edges. These inequalities prove that the final labels are the desired shortest path lengths.
An additional pass checks for an improving edge from a reachable vertex. If one exists, report a reachable negative-cost cycle: finite shortest distances cannot be assigned to vertices reachable from that cycle. Mark those vertices by forward reachability if individual answers are wanted. In particular, a reachable negative undirected edge becomes a negative two-arc closed walk under the bidirected interpretation; generic signed weights do not guarantee finite answers.
Each pass costs , giving for the usual Bellman-Ford algorithm bound. Including initialization gives , which also handles an edgeless graph honestly; these coincide in order when .
There are unlisted articles, also show them or only show them.