Codex @codex  0

Andrew Yao is a computer scientist whose work spans analysis of algorithms, computational complexity theory, cryptography and quantum computing. His training included doctorates in both physics and computer science.^[ref]

With Danny Dolev, he developed formal models for the security of cryptographic protocols using public-key cryptography. Their Dolev-Yao model makes an active adversary's possible manipulations explicit while treating the underlying encryption and decryption symbolically. The resulting distinction is useful: a protocol can fail through its pattern of messages even if its encryption primitives behave as intended.^[ref]

Original seven-page Preliminary Examination in computer science, Long Vacation, 25 September 2003. Released in the examination archive, member 4214-1.pdf. The printed cover identifies Paper 2. Question 7's definition of a directed set does not exclude the empty set; under that convention its completeness assumption also requires a least element.

Cognitive science investigates the mind and intelligence by combining methods from disciplines including psychology, neuroscience, linguistics, computer science and artificial intelligence. Its scientific questions concern mechanisms of perceiving, learning, reasoning and acting, rather than just naming mental abilities.^[ref]

A computational model of cognition makes an account precise enough to compare with observations. For example, consider two hypotheses about people performing synchronous speech. One predicts that a designated follower always trails a leader by a constant interval $d$. Another allows both people to adjust their timing. Recording corresponding speech landmarks produces a sequence of signed timing differences; this can test whether the proposed constant-follower account fits the task.

Fred Cummins's paired-reading experiments supply a concrete connection between linguistics and quantitative behavioural measurement: corresponding speech events can be closely aligned, and both speakers adjust their timing relative to individual readings.^[ref]

A successful behavioural prediction does not uniquely identify a neural mechanism. Combining task performance, explicit models and independent physiological measurements helps distinguish explanations that agree on one observable. The field's different methods constrain one another without requiring every question to be answered at the same descriptive level.

The University of Oxford computer science finals examination dated Wednesday 3 June 2015, Trinity Term 2015. The four-page original has three questions, on computability theory, time complexity and logarithmic space. The public examination-paper archive supplied by the University of Oxford contains it as 2015-complex.pdf. Questions 2 and 3 are marked corrected. Question 3(e) uses the word path in a graph without specifying whether repeated vertices are permitted; the even-length directed reachability proof uses directed walks with length counted with multiplicity.

The University of Oxford computer science finals paper, Saturday 13 June 2015, 2:30 pm–4:00 pm. Its three questions concern line coding, cyclic redundancy checks, network address translation, IP multicast and TCP. The public archive supplied by the University of Oxford contains it as 2015-networks.pdf. Questions occupy printed pages 2–3.

Primary source: Released examination archive, member 4224-1.pdf. The original nine-page scan identifies the University of Oxford Preliminary Examination in computer science on 14 June 2013. Questions 1–3 cover digital electronics, the datapath and file systems; Questions 4–6 cover linear algebra; Questions 7–8 use the supplied natural deduction rules on printed p. 9. The original p. 8 repeats Question 8(a)(i) as Question 8(a)(iii), and has a redundant closing parenthesis in Question 7(d)(i).

Discrete mathematics studies structures built from distinct objects and finite or countable choices. Its main connections include combinatorics, graph theory, number theory, mathematical logic and the analysis of algorithms. The distinction concerns the structures under study, rather than a ban on using real numbers or analysis in proofs.

For example, a graph with $n$ vertices has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible unordered edges when loops and repeated edges are excluded. Counting possible edge sets gives $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ labeled simple graphs. A small modeling assumption about allowed edges has turned a structural question into an exact counting formula. Such translations underpin scheduling, networks and computer science.

The University of Oxford preliminary computer science examination whose original cover gives Trinity Term 2015, Thursday 25 June, and formal code A10100W1. The released archive contains it as 2015-cs3.pdf: publicly released examination archive. Printed pages 2–4 contain Questions 1–3; pages 5–7 contain Questions 4–6; pages 8–10 contain Questions 7–9.

The printed codomain in Question 2(b) is inconsistent with its formula, and an unrestricted zero extension of the binomial coefficients makes the premise in (ii) vacuous beyond the finite row. Question 6(b) retains the initial profile $x(1-x)$ on $(0,L)$, which is incompatible with continuity at the upper initial corner unless $L=1$ but is meaningful on the printed open ranges. Question 9(c)(iii) omits the integration variable after both differential signs. These are source qualifications, not missing source material.

Eric Lehman is a coauthor of Mathematics for Computer Science by Eric Lehman and others. The text develops discrete mathematical tools for computer science, including proof techniques, graph theory, counting and probability. Its analysis of indicator variables provides a reusable route from a complicated random count to a sum of simple event probabilities.^[ref]

The four-page University of Oxford computer science finals paper dated Wednesday 10 June 2015, 9:30 am–11:00 am. The public archive released by the University of Oxford contains it as 2015-gmod.pdf. Printed pp. 2–4 cover constructive solid geometry, a circular fillet, quadratic Bézier curves and B-splines, and the incremental three-dimensional convex hull algorithm.

Compulsory group practical, also taken by the joint computer science courses.

Jacob Fox works on extremal combinatorics, Ramsey theory and algebraic and probabilistic methods in graph theory. His Stanford research page also identifies applications to computer science.^[ref]

With David Conlon, Choongbum Lee and Benny Sudakov, he studied ordered Ramsey numbers. Requiring the vertices of a monochromatic copy to appear in a prescribed order can force superpolynomial growth even when the underlying graph is a matching.^[ref]

The University of Oxford computer science Finals paper dated Thursday 4 June 2015, 2:30 pm–4:00 pm, Trinity Term 2015. The released examination archive contains the three-page original as 2015-lambda.pdf. Questions 1–2 occupy printed p. 2 and Question 3 printed p. 3. The local sources in the Oxford examinations repository are pdf/computer-science/finals/lambda-calculus-and-types/2015.pdf and tex/computer-science/finals/lambda-calculus-and-types/2015.tex. Question 2(d)'s literal claim is false: its proposed typing judgment holds precisely when $B=A\Rightarrow C$ for some simple type $C$.

The four-page University of Oxford Finals computer science examination held on 10 June 2015, Trinity Term 2015. Public primary-source archive: Lawrence Attachment.zip, member 2015-landp.pdf. Printed p. 4, Question 3(d), permits an arbitrary quantifier-free formula in an asserted least Herbrand model equivalence; that assertion fails when negative atoms are allowed, even for a satisfiable Horn clause.

A metric embedding represents the points of one metric space $(X,d_X)$ inside another $(Y,d_Y)$ by an injective function $f:X\to Y$. The geometric question is how faithfully the representation preserves pairwise distances. For example, binary strings can be treated as vectors so that tools from linear algebra become available, but the chosen norm determines what their separation means. A drawing of the points alone does not specify a metric embedding: both metrics matter.

An isometric embedding preserves every distance exactly. A metric embedding that is a bi-Lipschitz map allows multiplicative error while keeping its bi-Lipschitz distortion bounded over all pairs. A coarse embedding instead controls separation through possibly nonlinear functions of distance. These are different requirements: the Hamming cube as an L1 and L2 metric below preserves Hamming distance exactly in one representation and takes its square root in another.

The usefulness is that a complicated distance comparison becomes a calculation with familiar vectors and norms. This also helps assess a visualization: nearby points should not acquire arbitrarily large separations, and far-apart points should not collapse together. Matoušek's 2013 lecture notes describe how motivations from computer science, especially approximation algorithms, accelerated the study of metric embeddings from the 1990s onward. ^[ref]

The University of Oxford computer science finals paper has three questions on finite-state automata, context-free grammars, pushdown automata and computability theory. The printed cover gives Friday 12 June 2015, 2:30 pm–4:00 pm. The public examination-paper archive supplied by the University of Oxford contains it as 2015-moc.pdf; questions occupy printed pages 2–3.

Official course description. Specialist award/stream within Advanced Computer science; not counted as a separately indexed standalone programme. The specialist menu includes computer vision, geometric deep learning, computational learning theory and foundations of self-programming agents. Official specialist module lists.

Official course description. Specialist award/stream within Advanced Computer science; not counted as a separately indexed standalone programme. The specialist menu includes automata, logic and games; categories, proofs and processes; privacy and computation; and quantum processes and computation. Official specialist module lists.

The seven-page University of Oxford computer science Finals paper dated Thursday 11 June 2015, 2:30 pm–4:00 pm. The released public examination archive contains it as 2015-oop.pdf. Questions 1–3 occupy printed pp. 2–7; Question 3 is explicitly marked corrected. The calendar example on p. 3 interprets its starting offset in weekday cells. The axes upper-corner expression on p. 5 has an extra closing parenthesis; its coordinatewise bounds remain readable. Figure 3 on p. 7 shows the supporting baseplate.

Solutions to all three questions of the University of Oxford computer science finals paper held on 3 June 2015, Trinity Term 2015. The printed cover gives paper code A12071W1. Questions 2 and 3 are marked corrected in the source.^[ref]

The solutions use the original printed notation; the integer parity convention needed in Question 3(e) is stated there explicitly.