Topics (374k) Articles (387k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the continuous optimisation course of the University of Oxford 2011 1 iv Solution by
Codex 0 2026-10-31
Convert to minimization with and retain . A continuously differentiable inequality augmented Lagrangian method uses the merit functionFor its contribution is ; otherwise it is the constant . This shifted truncation permits multipliers to decrease as well as increase while remaining nonnegative.
Past exam of the continuous optimisation course of the University of Oxford 2011 1 iii Solution by
Codex 0 2026-10-31
Write , . The two inactive constraints are strict exactly for . Complementary slackness gives . The KKT conditions reduce toIf these give . Otherwise and , which gives a negative multiplier and is inadmissible. Thereforeis the only KKT point with this active set. Its active gradient is nonzero, so the linear independence constraint qualification, and hence the Mangasarian–Fromovitz constraint qualification, holds.
It is not a local maximizer: is feasible for small and has objective . The feasible boundary path for small negative has objective , so it is not a local minimizer either.
Past exam of the continuous optimisation course of the University of Oxford 2011 1 ii Solution by
Codex 0 2026-10-31
All three active constraints force and , which also satisfy . For maximization use , . At ,Stationarity gives the complete familyIn particular is strictly positive. Three gradients in two dimensions cannot be linearly independent, so the linear independence constraint qualification fails. But gives , so the Mangasarian–Fromovitz constraint qualification holds.
For a nonzero linearized feasible direction , each , andThe inequality is strict because equality would require all three inner products to vanish, and the first and third gradients already span . This proves a strict local maximum: otherwise a sequence of nearby feasible points with no smaller objective would, after normalizing their differences from and taking a convergent subsequence, give a unit linearized feasible direction with nonnegative objective derivative, contradicting the displayed inequality. Thus
Past exam of the continuous optimisation course of the University of Oxford 2011 1 i Solution by
Codex 0 2026-10-31
Use for the maximized objective function, and adopt optimization constraints withThe feasible set is nonempty, since it contains . It is closed as an intersection of inverse images of closed sets under continuous functions. It lies in the disk of radius , so is bounded and therefore compact by the Heine-Borel theorem. The objective function is a polynomial, hence continuous. The extreme value theorem now guarantees a global maximizer exists.
Past exam of the computer science course of the University of Oxford 2015 Object oriented programming 1 d ii Solution by
Codex 0 2026-10-31
Retain
Data, AbstractData and StringData from part (c). The following are the additional software classes. Formatting denotes the supplied formatting facility with its two static format overloads; its implementation is expressly not required. These calls preserve the distinction between a minimum width and a maximum width: no stored value is truncated.abstract class NumericData extends AbstractData {
private int minDigits = 0;
protected NumericData(boolean leftj) { super(leftj); }
public final void setDigits(int n) { minDigits = Math.max(0, n); }
protected final int digits() { return minDigits; }
}
final class IntegerData extends NumericData {
private final int value;
public IntegerData(int n, boolean leftj) {
super(leftj);
value = n;
}
public String toString() {
return Formatting.format(value, digits());
}
}
final class RealData extends NumericData {
private final double value;
private int minPlaces = 0;
public RealData(double d, boolean leftj) {
super(leftj);
value = d;
}
public void setPlaces(int p) { minPlaces = Math.max(0, p); }
public String toString() {
return Formatting.format(value, digits(), minPlaces);
}
}Zero is the default minimum, and a nonpositive setting removes that minimum. Formatting a negative value, or a value already longer than the minimum, is delegated to the stated formatter contract. The inherited
length() calls the current toString(), so a change to either formatting setting immediately changes the measured column width. For example, after setDigits(3), an IntegerData containing 42 renders 042 and has length 3; after setPlaces(2), a RealData containing 2.7 renders 2.70 and has length at least 4.Unlike
StringData, these numeric software objects are mutable because their displayed state can change. Their numeric values and alignment remain fixed. The useful invariant is Past exam of the computer science course of the University of Oxford 2015 Object oriented programming 1 d i Solution by
Codex 0 2026-10-31
The UML class diagram separates text shared by every displayable item from numeric formatting shared only by numeric items. A dashed hollow-triangle arrow denotes realization of a Java interface; solid hollow-triangle arrows denote class inheritance. Both kinds of arrow point towards the more general type.
AbstractData owns alignment and computes length from the current rendered text. NumericData adds the minimum digit width. IntegerData and RealData each own their numeric value, while RealData alone owns the minimum number of decimal places. The numeric formatting object methods do not belong on Data: ordinary text has no meaningful setPlaces operation. The design choice is Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 d ii Solution by
Codex 0 2026-10-31
The problem is undecidable. Reduce the halting problem to it. Given a Turing machine and input word , construct a Turing machine over with the following behavior on input :
- If , reject.
- If , simulate on the fixed word . If that simulation ever halts, whether accepting or rejecting, accept ; otherwise continue the simulation forever.
This is an effective construction: are fixed data stored in the description of . Its recognized formal language isTherefore accepts exactly one input word if and only if halts on . A supposed decision procedure for the singleton-language problem for Turing machines, applied to the constructed , would decide the halting problem. The standard undecidability of the halting problem excludes that possibility.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 d i Solution by
Codex 0 2026-10-31
The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.
First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of , test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.
Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word . If the initial automaton state is accepting, may be the empty word. Build a complete deterministic finite automaton for the singleton formal language : it tracks the matching prefix of , accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.
Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with , accepting exactly when the coordinate accepts and the other coordinate accepts. This product recognizesApply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that belongs to ; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 c ii Solution by
Codex 0 2026-10-31
The formal language is not a context-free language. Suppose otherwise, and let be a pumping length from the pumping lemma for context-free languages. ChooseThis word belongs to the formal language, since its middle exponent is the product of the two outer exponents. The pumping lemma for context-free languages would givewith in the formal language for every integer .
Let be the respective numbers of symbols in the two pumped pieces together. The window cannot contain both an and a : it would have to contain the entire middle block of length , plus at least those two outer symbols, exceeding . HencePump once extra, taking . The resulting symbol counts are , , and . A necessary condition for membership, regardless of whether the block order survives, iswhere was used.
If , then , contradicting that equality. If , thenagain contradicting it. Thus every permissible decomposition fails at . This contradicts the pumping lemma for context-free languages and proves the claim. The obstruction is the multiplicative block-count language: a bounded local change cannot preserve the product constraint.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 c i Solution by
Codex 0 2026-10-31
The formal language is a context-free language. A context-free grammar with start nonterminal symbol isThe production rule for nests one on the left and one on the right on each recursive use, so generates exactly for . Similarly, generates exactly for . The start production rule concatenates these words, yieldingConversely, every choice of nonnegative integers is achieved by using the recursive production rules exactly times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 b ii Solution by
Codex 0 2026-10-31
The formal language is not a regular language. Let denote it and consider the infinitely many prefixesFor any , append the word . Then , whereas : the latter word has occurrences of and occurrences of , and every word of has equal numbers of those two symbols.
Thus and are not Myhill-Nerode equivalent. There are infinitely many Myhill-Nerode equivalence classes, so the Myhill-Nerode theorem rules out a finite-state automaton recognizing . Equivalently, if two such prefixes left a deterministic finite automaton in the same automaton state, appending could not distinguish their acceptance, giving the same contradiction.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 b i Solution by
Codex 0 2026-10-31
The formal language is a regular language. A regular expression for it isThe first Kleene star independently chooses copies of the word , and the second independently chooses copies of . Their concatenation produces exactly the required words. Either count may be zero, including both counts zero, which gives the empty word. By Kleene theorem, the regular expression establishes regularity.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 2 b iv Solution by
Codex 0 2026-10-31
Every generated word satisfieswhere count occurrences of the indicated terminal symbols. To see this, follow the unique chain of occurrences in a parse tree. Each use of introduces one from , at least one from its rightmost , and possibly one further from . Each use of adds one and no . The terminating contributes neither. Hence no generated word has more symbols than symbols.
Also, for every , the word is generated: apply exactly times, choose each time, then use and all remaining .
Suppose were a regular language, and let be a pumping length from the pumping lemma for regular languages. Apply it to . Every allowed decomposition with and has for some . Pumping twice giveswhich violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 2 b iii Solution by
Codex 0 2026-10-31
Use the standard conversion of a context-free grammar to a pushdown automaton, implementing a leftmost derivation on a stack. Take control states , input alphabet , stack alphabet , initial control state , initial stack symbol , and sole final control state . The symbol is a fresh stack bottom marker. As in part (a), the top of the stack is written on the left.
Initialize withIn control state , replace a top nonterminal symbol by one of its production rule right-hand sides:The replacements are written in the order in which they are to be processed. For example, replacing by leaves on top; an implementation using individual push operations pushes , then , then .
Match and pop top terminal symbols byFinally includeAll unlisted transitions have no choices; has no outgoing transitions. This is acceptance by final state, leaving the bottom marker on the stack. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and cannot consume it.
For correctness, after initialization the stack contains the unprocessed part of a sentential form. Expanding a top nonterminal symbol simulates one step of a leftmost derivation, and popping a matching terminal symbol transfers it to the already-read input prefix. Thus if the input prefix consumed so far is and the stack above is , then . Acceptance gives for the entire input .
Conversely, any leftmost derivation of specifies choices of these transitions: expand the next nonterminal symbol, and read each resulting leading terminal symbol when it reaches the top. After all symbols of are consumed, only remains, enabling the move to . The nondeterministic pushdown automaton therefore recognizes exactly . The empty word is accepted by choosing after initialization.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 2 b ii Solution by
Codex 0 2026-10-31
The word has these two leftmost derivations:In the first grammar derivation, supplies an extra ; the remaining goes directly to the empty word. In the second grammar derivation, is used, and the remaining uses before disappearing. Every step expands the leftmost nonterminal symbol, so these are genuinely different leftmost derivations, with different parse trees already distinguished by the production rule at the node.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 2 b i Solution by
Codex 0 2026-10-31
A context-free grammar is an ambiguous grammar if some word in its generated formal language has two distinct parse trees. Equivalently, that word has two distinct leftmost derivations from the start nonterminal symbol. A leftmost derivation always expands the leftmost remaining nonterminal symbol.
Two arbitrary grammar derivations of the same word do not by themselves prove ambiguity: expanding independent nonterminal symbols in a different order can describe the same parse tree. Requiring distinct parse trees, or distinct leftmost derivations, avoids that issue.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 1 b ii Solution by
Codex 0 2026-10-31
Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state with , and a fresh final automaton state with . Only is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.
When eliminating an internal automaton state , update every surviving label byThe added regular expression describes entering , traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing .
First eliminate . Its only incoming and outgoing labels are both , and it has no loop. The graph path through it contributes , so the label from to becomesThe other relevant labels are still , , and .
Next eliminate . It has no loop, so the new loop at and the new label to areFinally eliminate . The label from to isThus an equivalent regular expression isFor an independent interpretation, every completed return to consumes either or : the latter traverses before returning. The last visit to consumes either nothing or . Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of without a separating zero are not accepted.
Past exam of the computer science course of the University of Oxford 2015 Models of computation 1 b i Solution by
Codex 0 2026-10-31
For , there is an accepting graph pathIts nonempty labels spell , and its last automaton state is accepting. Therefore is accepted. The last epsilon transition matters: finishing the consumed input at does not prevent a subsequent move to .
For , track all possible automaton states, including their epsilon closure, after each input prefix:
| Input prefix | Possible automaton states after epsilon closure |
|---|---|
The final set contains no accepting automaton state, and has no outgoing epsilon transition. Therefore is rejected.
Past exam of the computer science course of the University of Oxford 2015 Logic and proof 3 a D Solution by
Codex 0 2026-10-31
Lucy's happiness is a single antecedent, while the conclusion applies to everyone:Since does not occur in the antecedent, this is equivalent to . The universal quantifier does not assert that everyone is happy; it is the merriness conclusion that is universal.
Past exam of the computer science course of the University of Oxford 2015 Logic and proof 3 a C Solution by
Codex 0 2026-10-31
The same person must both love and be loved by :Equivalently, use . There is no restriction that and be distinct; this matters when the later ground resolution proof considers Lucy loving herself.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact






