Use the already-filled prefix itself for membership tests. The outer loop invariant is and for . The inner loop invariant says that and no processed entry before
Long intermediates avoid overflow in the candidate calculations, while a checked conversion respects the required output type:def recaman(a: Array[Int]): Unit = {
if (a.length == 0) return
a(0) = 0
var i = 1
while (i < a.length) {
val candidate = a(i - 1).toLong - i.toLong
var j = 0
while (candidate > 0L && j < i && a(j).toLong != candidate) {
j += 1
}
val next =
if (candidate > 0L && j == i) candidate
else a(i - 1).toLong + i.toLong
require(next <= Int.MaxValue.toLong, "Sequence value exceeds Int")
a(i) = next.toInt
i += 1
}
}j equals the positive candidate. Its guard either reaches the end of the prefix, finds the candidate, or immediately rejects a nonpositive candidate. Its loop variant is . This establishes exactly the choice required by the recurrence, so the outer loop invariant is preserved. The outer loop variant is .Extra storage is beyond the supplied result array. Membership scans give an upper bound for output entries. Addition, unlike the subtraction branch, is not required to avoid repeats: at indices and the value occurs twice. The code therefore does not try to enforce global distinctness. If an exact value eventually exceeds
Int, the output interface cannot hold it; the check reports that limitation rather than wrapping the recurrence.The first three subtractions are negative or return the already-seen zero, so addition is used. The fourth subtraction gives a new positive two; the next subtraction is negative. Thus . These are the initial terms of Recamán's sequence.[ref]
OEIS entry A005132. Initial terms, offset zero
Use relative character frequencies, an empirical distribution. A nonempty string is required because an empty sample has no normalized frequency distribution:
class DistFromString(s: String) extends FiniteDist[Char] {
require(s != null && s.nonEmpty, "A nonempty string is required")
private val chars = s.toList
private val domain = chars.distinct
def getDom: List[Char] = domain
def getProb(c: Char): Double =
chars.count(_ == c).toDouble / s.length.toDouble
}distinct removes repeated support entries without changing which characters occur. Every returned domain element has positive frequency, and every absent character has frequency zero. The occurrence counts partition the string's character positions, so their total is s.length, establishing normalization. For Scala, the masses are for a and each for S, c and l. The character units here are exactly the Char values supplied by s.toList; the interface does not specify a different notion of displayed text characters. The code has no explicit loop beyond the specified library traversals.The inclusive interval is nonempty exactly when . Reject with a failed precondition, rather than assigning a nonexistent normalization to an empty interval. Compute its width in The loop invariant says that and
Long before taking a reciprocal:class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
require(l <= u, "Empty uniform interval")
private val width = u.toLong - l.toLong + 1L
private val mass = 1.0 / width.toDouble
def getProb(x: Int): Double =
if (l <= x && x <= u) mass else 0.0
def getDom: List[Int] = {
var x = l.toLong
var rev = List.empty[Int]
while (x <= u.toLong) {
rev = x.toInt :: rev
x += 1L
}
rev.reverse
}
}rev contains exactly the integers in reverse order. The loop variant is while the guard is true. Long handles both the full interval width and the increment past Int.MaxValue. At exit, reversing yields each support value once. All support values have mass , so their exact sum is one; Double approximates that rational number. Very large valid domains require correspondingly large lists and sufficient memory; that resource issue does not make the mathematical endpoint values invalid.Implement the Bernoulli distribution, taking special care that a zero-mass outcome is excluded from the support of a probability distribution:The precondition excludes NaN and all values outside , including infinities. The two masses are nonnegative and sum mathematically to one. Endpoint domains are singleton lists, while an interior parameter lists both outcomes exactly once. Treating
class Flip(p: Double) extends FiniteDist[Boolean] {
require(!p.isNaN && 0.0 <= p && p <= 1.0)
def getDom: List[Boolean] =
if (p == 0.0) List(false)
else if (p == 1.0) List(true)
else List(true, false)
def getProb(x: Boolean): Double =
if (x) p else 1.0 - p
}getDom as always containing both Booleans would violate its positive-support contract at the endpoints.Not necessarily: structural sharing can make snapshots cheap, but the trait alone gives no storage guarantee. With a persistent data structure, unchanged portions of old and new sequences can be shared safely. Saving two root references costs additional space per edit, and adjacent history entries commonly refer to the same intermediate version. With an appropriate balanced persistent tree, each positional edit may add only new vertices, giving approximately storage for retained edits of comparable presentation size, plus references to slides.
There are important qualifications. A fully copied immutable array may allocate per edit and use across its history. A persistent linked list shares suffixes but may copy a long prefix for a late positional edit. Moreover, snapshot history keeps old versions alive that an edit-specific inverse representation might otherwise release. Consequently a significant increase is possible with some implementations or workloads; it is not forced by saving
Sequence references, and it cannot be ruled out from the interface alone.Replace edit-specific inverse information by before/after snapshots implementing the Memento pattern. The same By-value evaluation computes
Change and History interfaces still work. A complete alternative suite is:class SnapshotSlideSuite(initial: Sequence[Slide]) {
private var slides = initial
private def changeTo(after: Sequence[Slide]): Change = {
val before = slides
slides = after
new Change {
def undo(): Unit = { slides = before }
def redo(): Unit = { slides = after }
}
}
def insert(i: Int, x: Slide): Change =
changeTo(slides.insert(i, x))
def delete(i: Int): Change =
changeTo(slides.delete(i))
def move(from: Int, to: Int): Change = {
val x = slides.elementAt(from)
changeTo(slides.delete(from).insert(to, x))
}
}after without changing slides, then changeTo captures the still-current before and installs the new value. The val bindings inside each call are stable snapshots, rather than later reads of a mutable variable. Under the same chronological history preconditions, undo and redo are constant-time reference assignments. This is the Memento pattern applied to an immutable sequence. Retaining a reference to an in-place-mutated sequence would not save its old state. The snapshot covers slide order and membership; it does not promise to undo unrelated mutations inside a Slide object.Let the abstract state be the set of occupied coordinate pairs. For the Boolean array, the abstraction function is . Its representation invariant requires an Boolean array and the downward-closure propertyThus is an order ideal for the coordinatewise partial order. Removing an upper-right rectangle preserves this property. The empty set is allowed after the losing move.
For the row-boundary array, the abstraction function and representation invariant areThe array has length . Removing at replaces each
row(j) for by . Earlier rows are unchanged. This both implements the abstract removal and preserves the nonincreasing boundary.Without a cached count, the Boolean representation takes for
Count, for Legal, worst-case for Move, and for a full-grid Display. The boundary representation takes for Count, for Legal, worst-case for Move, and for the same full-grid Display. Their space complexities are respectively and . A scalar cached total makes Count in either representation if each move updates it consistently. The implementation below uses that cache with the boundary array, so it achieves constant-time Count and Legal, linear worst-case Move, and linear storage. Full-grid output still takes quadratic time because it emits quadratic many cell positions.For Chomp, one representation is a Boolean array
occupied(y)(x) with one entry per cell. The initial board has every entry true. For the noninitial board in the figure, the sets of occupied column indices in successive rows are , , , , , ; all other entries are false.A more compact representation is the monotone boundary representation of a grid order ideal: an array
row(y) giving the number of occupied cells in row . Occupied cells in a row always form a left prefix. The initial representation is , and the illustrated noninitial representation is , indexed upwards from row zero. Its total is . These descriptions use the same coordinate orientation as the original figure; no source image is needed in the solution.There are entries in , which contains possible integers. If , then . Therefore some value in is missing, again by the pigeonhole principle. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.
If , the upper side contains the whole permitted range and hence a missing value. If , the condition is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.
For an integer pivot , exactly entries lie in . That interval contains possible integers. If , the pigeonhole principle implies that some value in is missing. Counting occurrences rather than distinct entries only strengthens this argument: occurrences cannot cover more than distinct values.
For completeness, if the lower side contains the entire permitted value range, which already has a missing value. If , the condition is impossible. Thus the general conclusion is a missing permitted value below ; an internal pivot gives useful localization.
Past exam of the year 1 of the computer science course of the University of Oxford 2019 Functional programming, design and analysis of algorithms 8 d ii Solution Created 2026-10-25 Updated 2026-11-05
Read “subsequence” in its usual sense: selected indices increase in the given input order. First sort each box's dimension vector, in total time. Let be the maximum number of boxes in a fitting subsequence ending at index . Process and computeThe last selected box before , if any, supplies exactly one of these candidates; conversely an optimal candidate subsequence can be extended by . Induction on proves the box nesting recurrence. Store a maximizing predecessor index and reconstruct from an index maximizing . For , return the empty subsequence.
There are candidate pairs, each requiring coordinate comparisons. Hence running time and storage suffice, including sorted vectors, table entries and reconstruction pointers. It is unnecessary to store every fitting pair.
If “subsequence” was intended to allow arbitrary reordering, build the containment directed acyclic graph instead: include every fitting ordered pair, then find its longest chain. Strict increase of the smallest sorted dimension gives a topological sorting by that dimension. The same pair-testing bound applies, but the index restriction must then be removed. These two interpretations differ: input boxes have a longest order-preserving subsequence of one box, but an unrestricted nesting chain of two.
Sort the two dimension vectors separately into ascending order, and . Then return true exactly when for every . Sorting costs and the coordinate comparisons cost .
Sufficiency follows by matching corresponding ranks and translating that rank matching back to the original axes. For necessity, suppose for some . The dimensions must all be assigned to strictly larger target dimensions. None of the first sorted target dimensions is large enough, leaving at most eligible slots. The pigeonhole principle gives a contradiction. This proves the sorted-coordinate criterion for box containment, including ties: equality fails the required strict fit.
Permit every vertex to start a path: initialize for all , then perform the same maximum-relaxation pass in topological sorting order. Equivalently, the recurrence isThe zero option starts a fresh, zero-edge path; the other options extend an optimal path ending at a predecessor. The largest final entry is therefore the longest path length in the graph, allowing a zero-edge path. This takes , which is for the ordinary simple-graph representation.
Past exam of the year 1 of the computer science course of the University of Oxford 2019 Functional programming, design and analysis of algorithms 8 c i Solution Created 2026-10-25 Updated 2026-11-05
Find a topological sorting of the directed acyclic graph. Initialize and for . Process vertices in that order. At a reachable vertex , update each outgoing edge by , and retain a predecessor whenever an improvement is made.
Every path to a vertex ends at an earlier vertex in the topological sorting. Thus, when is processed, all possible final-edge candidates for have already been considered. Induction along the order proves that is the longest path length from , with exactly for unreachable vertices. Signed weights cause no problem because the graph has no directed cycle. The running time is , and predecessor pointers recover a maximizing path.
Use the multiplicative score exactly as defined in the paper. Let be the largest score of a matching length- route ending at . Initialize and mark all other entries unreachable. For each stage, clear the new layer and inspect matching edges from reachable entries:An empty candidate set is marked unreachable, rather than given score zero: a genuine route may have score zero. A Boolean reachability table or a sentinel with a guard before multiplication distinguishes the cases. Store the maximizing predecessor edge at each reachable layer entry, retaining one on a tie.
Multiplication by a nonnegative edge factor preserves order, so replacing a prefix by a larger-scoring matching prefix cannot worsen its extension. Induction proves this maximum-product edge-labelled walk recurrence correct. Choose a reachable final entry of greatest score and follow its layer-indexed predecessors backwards to reconstruct the answer. If no final entry is reachable, report that no matching route exists, even though all numeric scores might otherwise look like zero.
The running time is , and rolling scores have space complexity , while retaining all reconstruction pointers gives space complexity . For the vertex-simple interpretation, retain the visited set in each state as in part i, prohibit revisits and maximize the same products over those states. This exact exponential-state variant preserves both the zero-score distinction and predecessor reconstruction. If the starting vertex is unrestricted rather than inherited from part i, initialize for every vertex. The calculation needs no independence assumption beyond the paper's definition of a product score; repeated physical edge-activation events would require a separate probabilistic model.
The printed formula for the edge label has mismatched variable names. The type-correct reading is . Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.
Let be the set of vertices reachable from the specified start after reading exactly the first labels. Initialize and updateAfter stages, answer yes exactly when . A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on . Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is with rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at .
If “path” is instead required to mean vertex-simple, augment the state to , where is the set of visited vertices. Start with and extend a matching edge to only when , replacing by . This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when . A straightforward bound is running time with rolling-table storage. The exponential distinction is substantive: all labels equal and include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.
Let use only the first available coins. Initialize , for , and useomitting the second term when . The alternatives exclude the current coin or use it once; both refer to the previous row, so it cannot be used twice. Induction on proves correctness, and is the required answer, including when no selection works.
The running time is . A single amount array reduces auxiliary space to if each coin updates amounts in descending order, . Then still describes the previous row. Ascending updates would reuse the same coin and solve a different, unlimited-supply problem.
During the computation in part i, record an index attaining the minimum at every positive amount. Starting with , print and replace by , continuing until .
Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to and their number is exactly , proving optimality. The total running time is , including the output; because denomination is available. The predecessor array adds to the space complexity. This is reconstruction from the dynamic programming certificate, not the largest-denomination greedy algorithm, which need not be optimal for arbitrary denominations.
For nonnegative integer amount , let be the minimum number of coins making amount . Set and compute, in increasing order of ,An empty candidate set has minimum . Here denomination ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on .
Return whether . This solves the at-most- decision without needing a separate dimension for . The table for the minimum coin change recurrence takes running time and space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.
There are unlisted articles, also show them or only show them.