Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 6 b Solution Created 2026-09-24 Updated 2026-10-14
Carry the list as an immutable accumulator instead of storing it in a reference:For any initial accumulator
fun snackerPure m =
let
fun collect (Snack x, acc) = x :: acc
| collect (Lunch (a, b), acc) =
collect (b, collect (a, acc))
| collect (Feast (a, b, c), acc) =
collect (c, collect (b, collect (a, acc)))
in
collect (m, [])
end;acc, structural induction shows that collect(m,acc) equals the final reference content obtained by traversing m left to right and prepending each snack to a reference initially containing acc. At Lunch and Feast, the accumulator passed to each child is the result of all earlier children, exactly matching the imperative sequencing. Thus the result is the reverse of the left-to-right list of snack labels, just as for the original snacker; returning the ordinary left-to-right list would be incorrect. The code uses no mutable cells and is polymorphic, with type 'a meal -> 'a list. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 6 a Solution Created 2026-09-24 Updated 2026-10-14
An ML reference type Both dereferences now give one. A reference's stored type remains fixed; the value restriction prevents allocating one unrestricted polymorphic cell and then using incompatible instantiations.
'a ref describes a mutable cell holding a value of type 'a. The operations are ref : 'a -> 'a ref for allocation, ! : 'a ref -> 'a for dereferencing and := : 'a ref * 'a -> unit for assignment. An immutable variable binding can name a mutable cell; assigning to the cell does not change what the binding denotes. Two names may alias the same cell, so an update through either is visible through the other.val counter = ref 0;
val alias = counter;
counter := !counter + 1;Imperative programming uses sequencing References provide mutable state; sequencing, conditionals and loops control its updates.
(e1; e2; ...; en) to perform effects left to right, with the final expression supplying the result. Conditional expressions choose one branch. while condition do body repeatedly checks a Boolean condition and performs a unit-valued body, returning () on termination. Standard ML has no required primitive for loop, but recursion or a reference with while supplies one. For example:fun sumTo n =
let val i = ref 1
val total = ref 0
in
while !i <= n do
(total := !total + !i; i := !i + 1);
!total
end; Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 5 c Solution Created 2026-09-24 Updated 2026-10-14
If The zero comparison fixes the labels to type so the wrapper maps an integer tree to a packaged Boolean result or exception packet.
f : 'a -> 'b, then the success constructor applied to f x has type 'b result, and the exception alternative has that same type. Thereforewhat : ('a -> 'b) -> 'a -> 'b resultint, and tony with this predicate accepts an int tree and normally produces a Boolean. The requested expression consequently has typeint tree -> bool resultFor
ta, the packet Ian true means that a normal successful search occurred: ta has at least one root-to-Lf path all of whose branch labels are nonzero. It can be Lf; if nonempty, its root must be nonzero, but labels away from the successful path need not be. For example, Br(1,Lf,Br(0,Lf,Lf)) succeeds despite containing a zero.For
tb, Cherie Blair means that the search raised the designated exception. Every root-to-Lf path has a zero-labeled branch somewhere. Thus tb is nonempty, but its root need not be zero: Br(1,Br(0,Lf,Lf),Br(0,Lf,Lf)) fails. With the supplied total comparison predicate, tony can return only true or raise Blair, never return false. ta admits an all-nonzero path; tb admits none. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 5 b Solution Created 2026-09-24 Updated 2026-10-14
The ML exception type
exn contains exception packets and is an extensible datatype: an exception declaration introduces a fresh constructor, optionally with an argument. For example:exception Empty;
exception BadIndex of int;Empty has type exn, and BadIndex has type int -> exn. These packets are ordinary values which can be passed, returned or stored. raise propagates a packet; the resulting expression can have whatever result type its surrounding context requires, because normal evaluation does not return from the raise.In exception handling,
expression handle pattern => recovery evaluates the recovery for a matching exception packet and otherwise propagates the packet outward. The normal expression and recovery must have the same result type. Handlers are dynamically nested, and exceptions raised in the recovery are not handled again by that same handler. A variable pattern catches every packet, whereas a constructor pattern selects a particular exception. Separate fresh exception declarations create distinct identities even if their printed names coincide; exception rebinding instead aliases an existing constructor. exn packages exceptional information; raise and handle determine its control-flow effect. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 5 a ii Created 2026-09-24 Updated 2026-09-24
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 5 a i Created 2026-09-24 Updated 2026-09-24
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 3 c Solution Created 2026-09-24 Updated 2026-10-14
The inference is false in both directions. Although
String is a subtype of Object, generic type invariance means that neither Vector<String> nor Vector<Object> is a subtype of the other. If a string vector could be used as an object vector, an arbitrary object could be inserted into storage promised to contain strings. Conversely, an object vector may already contain an Integer, so it cannot satisfy the contract of a string vector.Both parameterizations are subtypes of the ordinary class
Object, but this does not create a subtype relation between their element parameterizations. For a view accepting vectors with different element types, Vector<?> is appropriate; a Vector<? extends Object> similarly allows retrieval as Object without arbitrary non-null insertion. A Vector<? super String> accepts insertion of strings but does not promise that retrieved elements are strings. The stated subclass relationship does not hold: mutable generic vectors are invariant. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 3 b Solution Created 2026-09-24 Updated 2026-10-14
Replace type parameters by their erasures, normally The two fragments are alternatives, not consecutive declarations in one scope. For a user-defined
Object or the first declared bound, and insert checked casts where an erased result is used as its former specific type. A simple generics in Java example becomes:// Generic version
Vector<String> names = new Vector<String>();
names.add("Ada");
String s = names.get(0);
// Non-generic version
Vector names = new Vector();
names.add("Ada");
String s = (String) names.get(0);Box<T>, replace fields, parameters and returns of type T by Object, and cast the retrieved result. Bounded parameters instead erase to their bound. A full translation must also preserve method dispatch where erasure changes overridden signatures, using suitable forwarding methods; this is the principle of type erasure, not simply deleting every pair of angle brackets.The raw collection permits accidental insertion of an unrelated object, which may fail much later at a cast. The generic collection rejects such insertion during compilation, documents its contract at the declaration, and eliminates repetitive casts at use sites. The generic version catches more errors earlier and expresses the programmer's intended element type directly. Generic types are largely erased at runtime, so their advantage is static checking rather than a new runtime vector representation. The translation mechanism is specified by the Java language specification.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 3 a Solution Created 2026-09-24 Updated 2026-10-14
A generic class, interface or method in Java is parameterized by one or more types. Generics in Java allow one implementation of a collection or algorithm to be reused with different reference types while checking the allowed values and results statically. For example:The type parameter is declared inside angle brackets, as in
Vector<String> names = new Vector<String>();
names.add("Ada");
String first = names.get(0);
class Box<T> {
private T value;
public void put(T x) { value = x; }
public T get() { return value; }
}Box<T>, and supplied as a type argument, as in Box<String>. A generic method places its parameter list before its return type, for example static <T> T identity(T x). Bounds such as <T extends Number> restrict type arguments, and wildcards such as ? extends Number or ? super Integer describe restricted views. Primitive values require wrapper types such as Integer rather than a type argument int. Generics provide reusable code with compile-time checking of element types. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 2 d Solution Created 2026-09-24 Updated 2026-10-14
Set-user-ID execution of a suitable executable makes its effective user identity that of the owner. When that owner is root, running it can give root privileges even to an otherwise unprivileged caller. World-write permission destroys the trust boundary: any user can alter the privileged executable, potentially substituting code which performs arbitrary privileged operations. World-execute permission then makes the compromised program available to everyone.
World-read access can reveal implementation details or embedded secrets, but reading alone is not the decisive privilege-escalation flaw; properly designed public set-user-ID utilities need not keep their code secret. Some Unix kernels clear the set-user-ID bit after an unprivileged modification. That is a mitigation, not a reason to maintain a world-writable privileged program: if the bit persists or is restored without validating the changed code, the privilege escalation remains. Root-owned privileged executables must not be writable by untrusted users.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 2 c Solution Created 2026-09-24 Updated 2026-10-14
First, suppressing kernel preemption simplifies protection of shared kernel data on a uniprocessor: another ordinary kernel execution cannot be scheduled in the middle of a short update which temporarily breaks an invariant. Fewer paths require preemption-specific locking and reentrancy handling, making the operating-system kernel easier to implement correctly.
Second, it avoids involuntary kernel context switches and their scheduler, register-save and cache-disruption costs, and can make the execution of short kernel operations more predictable. The tradeoff is greater scheduling latency if a kernel operation runs too long. Simpler synchronization and lower switching overhead are the two reasons. Non-preemptive kernel code can still receive interrupts or block voluntarily, and multiprocessor execution still requires synchronization; non-preemption is not a substitute for all locking.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 2 b Solution Created 2026-09-24 Updated 2026-10-14
Both kinds of context switch save and restore registers, a program counter, stack pointer and scheduler state. Switching between operating-system processes additionally changes the address-space and protection context, including the page-table root. Cached translations must be invalidated or distinguished by address-space identifiers, and the new process may have a different memory and cache locality.
Software threads of one process share its address space and most resources, so a thread switch normally preserves the page-table root and valid cached translations; only the execution context, stack and thread-specific state need change. Thus a process switch requires address-space management which a same-process thread switch usually avoids. Tagged translation caches can reduce the extra cost, so a complete translation lookaside buffer flush is not an inevitable feature of every process switch.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 2 a Solution Created 2026-09-24 Updated 2026-10-14
The working set is the set of virtual pages referenced by an operating-system process within a recent window of execution time or memory references. Its size estimates the number of frames needed for the process's current locality of execution. It is a set of recently used pages, not the entirety of the process's address space.
An operating system can estimate it from reference bits or fault history and try to keep those pages resident. Process scheduling and admission control should avoid simultaneously running processes whose combined working sets exceed physical memory; suspending some processes or reducing multiprogramming then allows the rest to make useful progress. If too many active pages compete for too few frames, repeated page faults produce memory thrashing. Working sets connect memory allocation to the choice of processes allowed to run.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 12 ii Solution Created 2026-09-24 Updated 2026-10-14
The Fermat-Euler theorem states that for integers and with ,where Euler's totient function counts the residue classes coprime to . The case is trivial. For , list a reduced residue system . Multiplication by permutes these classes: each is coprime to , and implies since has a multiplicative inverse modulo . Multiplying the permuted residues givesThe product is itself coprime to and can be cancelled using its inverse, proving the theorem.
The integer 359 is prime: none of the primes , all the primes not exceeding , divides it. Therefore and 60 is coprime to 359. Using the supplied congruence and the Fermat-Euler theorem,Now express the decimal expansion by long division. Put and for defineThus , and none of these remainders is zero. The congruence implies ; since both are the unique representatives between zero and 358, they are equal. A digit is determined by the preceding remainder, namely , soThis proves the required pure periodicity from the first digit. In fact its least period is 179: the multiplicative order of 10 modulo 359 divides the prime 179 and is not one, since . The connection between the remainder recurrence and the period is the decimal period from multiplicative order.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 12 i Solution Created 2026-09-24 Updated 2026-10-14
Suppose is a prime number, and . Since the only positive divisors of are one and , the greatest common divisor of and is one. By Bézout's identity, integers exist with . Multiplying by gives . Both terms on the left are divisible by , so . Thus Euclid lemma givesThe fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if is prime it already has a factorization; otherwise with , and the factorizations of combine to factor .
For uniqueness, suppose are two prime factorizations. Repeated application of Euclid lemma makes divide one of the , so primality forces . Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 10 c Solution Created 2026-09-24 Updated 2026-10-14
Add a public override of In Inherited dynamic dispatch selects the proper method at every node of the abstract syntax tree. Full parentheses distinguish the domain and codomain nesting without relying on a reader's precedence convention. Repeated occurrences of one type variable use the same identifier, and distinct factory variables have distinct identifiers. For example, with the first three factory variables, the type from part (b) prints as
toString in each concrete subclass. In TypeVar:public String toString() {
return "t" + id.toString();
}Arrow:public String toString() {
return "(" + from.toString() + " -> " + to.toString() + ")";
}((t1 -> t2) -> (t2 -> t3)). The recursive textual form preserves both arrow structure and variable identity. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 10 b Solution Created 2026-09-24 Updated 2026-10-14
Introduce a checked exception class, for example in its own source file:Declare the required abstract method in Within the nested Within the nested The parameter denotes an actual non-null type variable returned by the factory; checking object identity distinguishes different variables without confusing their printed names. Structural induction on the abstract syntax tree proves the occurs check: a variable node contains the queried variable exactly when the identities match, and an arrow contains it exactly when either component does. The first detected occurrence throws and propagates the checked exception; normal return proves absence. Both subclass methods must declare the exception, and callers must catch or declare it.
public final class ItDoesDependOn extends Exception {
private final MLType.TypeVar variable;
public ItDoesDependOn(MLType.TypeVar variable) {
this.variable = variable;
}
public MLType.TypeVar getVariable() { return variable; }
}MLType:public abstract void mustNotDependOn(TypeVar a)
throws ItDoesDependOn;TypeVar class implement it by an identity check:public void mustNotDependOn(TypeVar a) throws ItDoesDependOn {
if (this == a) throw new ItDoesDependOn(a);
}Arrow class implement it recursively:public void mustNotDependOn(TypeVar a) throws ItDoesDependOn {
from.mustNotDependOn(a);
to.mustNotDependOn(a);
}For , either recursive branch detects each of , whereas a distinct is absent and the call returns. A recursive identity-based occurs check throws exactly when the queried variable occurs.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 10 a Solution Created 2026-09-24 Updated 2026-10-14
Represent the two constructors of the type grammar by subclasses of The nested classes are public for use by clients, while their fields are private;
MLType: a TypeVar node and an Arrow node containing two types. Use immutable fields so a completed type expression cannot acquire cycles through later mutation. The static factory allocates a fresh object and gives it a fresh identifier shared across the whole hierarchy:import java.math.BigInteger;
public abstract class MLType {
private MLType() { }
private static BigInteger next = BigInteger.ONE;
public static synchronized TypeVar createNewTypeVar() {
TypeVar answer = new TypeVar(next);
next = next.add(BigInteger.ONE);
return answer;
}
public static final class TypeVar extends MLType {
private final BigInteger id;
private TypeVar(BigInteger id) { this.id = id; }
}
public static final class Arrow extends MLType {
private final MLType from, to;
public Arrow(MLType from, MLType to) {
if (from == null || to == null)
throw new IllegalArgumentException();
this.from = from; this.to = to;
}
}
}TypeVar can be created only through the factory. Client code uses MLType.TypeVar and MLType.Arrow. A type variable is identified by its unique node, and a function type by its domain and codomain nodes; repeated occurrences of one logical variable share the same TypeVar object.The monotonically increasing
BigInteger identifier avoids fixed-width counter overflow, and synchronization prevents two simultaneous calls from receiving the same identifier. Actual allocation remains subject to available memory. This is an abstract syntax tree representation, possibly sharing subexpressions. Fresh variable nodes and recursive arrow nodes represent every type in the given grammar. Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 1 c Solution Created 2026-09-24 Updated 2026-10-14
Assume head comparison and construction of one list cell take constant time. In the merge algorithm, every comparison removes one head from the recursive inputs, and evaluation stops as soon as either is empty. For lengths , at most comparisons and the same number of newly constructed cells are required; the untouched suffix is shared. Inputs which keep both lists nonempty until the last comparison attain this bound. ThusAn initially empty input makes this particular implementation constant-time; not every pair requires linear work.
The balanced merge sort spends time per call on list length, splitting and merging. Hence its time complexity satisfiesAt each recursion level the lengths of its disjoint subproblems sum to , so the work per level is , and balanced splitting gives levels. ConsequentlyThe length and splitting traversals change the constant factor, not this asymptotic order; repeatedly inserting elements into a sorted list would not give the same complexity.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 5 1 b Solution Created 2026-09-24 Updated 2026-10-14
Split the list into two contiguous halves, sort each recursively, and use the merge algorithm from part (a):
fun mergesort [] = []
| mergesort [x] = [x]
| mergesort xs =
let
val k = List.length xs div 2
val left = List.take (xs, k)
val right = List.drop (xs, k)
in
merge (mergesort left, mergesort right)
end;List.length counts elements, List.take(xs,k) returns the first elements and List.drop(xs,k) returns the remaining suffix. Since when , both recursive inputs are smaller and differ in length by at most one. Mathematical induction on length proves that each half is sorted without losing elements, and the correctness of the merge algorithm proves the same for the combined result. Contiguous splitting and left-biased equal-key merging preserve the original relative order of equal keys. This is a stable top-down merge sort. There are unlisted articles, also show them or only show them.