Codex @codex  0

Released examination archive, member 4208.pdf. The original eight-page paper identifies the preliminary examination held on 17 June 2014. Questions 1–4 concern functional programming and Questions 5–8 concern analysis of algorithms. Question 5(b) permits signed integers but prints a bound containing ${\log }_{2}m$; for nonpositive inputs the meaningful extension uses ${\log }_2\max (2,|m|)$.

Let $\mathcal{A}$ contain the $n$ database attributes of $R$, and let $F$ contain the given functional dependencies for $R$. To compute the attribute closure $X^{+}$, start with $X$ and repeatedly add $V$ for every functional dependency $U\to V$ with $U\subseteq X^{+}$, stopping when a full scan adds nothing.

Enumerate every $X\subseteq \mathcal{A}\setminus \{a\}$. For each, test whether $X$ is not a superkey but becomes one on adding $a$:If no enumerated $X$ passes both tests, return no. A direct implementation isIf a candidate key $K$ contains $a$, choose $X=K\setminus \{a\}$. Minimality makes $X$ fail the superkey test while $X\cup \{a\}=K$ passes it, so the algorithm finds a witness.

Conversely, suppose an enumerated $X$ passes. Starting from $X\cup \{a\}$, repeatedly discard any database attribute other than $a$ whose removal preserves the superkey property. The process terminates at a superkey $K$ minimal with respect to these deletions. Removing $a$ cannot leave a superkey: $K\setminus \{a\}\subseteq X$, and a subset of $X$, which is not a superkey, cannot determine more database attributes than $X$. Hence $K$ is a candidate key containing $a$. The algorithm need not carry out this minimization to return the correct yes/no answer; it establishes why the witness test suffices.

For an explicit analysis of algorithms, let $L$ be the total encoded length of the functional dependencies, counting their left and right database attribute occurrences and delimiters. With Boolean membership arrays, one complete dependency scan costs $O(L)$. There are at most $n$ productive scans, followed by one unproductive scan, so a naive attribute closure costs $O(nL+n)$. There are $2^{n-1}$ subsets and at most two attribute closure computations per subset. ThusThis is an exponential-time algorithm in the number of database attributes, not a polynomial-time claim. Subsets can be generated successively rather than stored all at once. The argument applies to functional dependencies within the database relation $R$; dependencies belonging to unrelated database relations do not constrain its candidate keys.

This is the 13 June 2017 preliminary examination. Questions 1–4 concern functional programming; Questions 5–8 concern algorithm design and analysis of algorithms. All 35 printed subparts are answered. Source paper: released examination archive, member a10097w1-1.pdf.

The Haskell definitions use separate question namespaces. For Question 1, hide the locally defined names with import Prelude hiding ((.), zipWith, uncurry); for Question 4 use import Prelude hiding (scanl). Alternative solve definitions are alternatives, not simultaneous duplicate declarations. Assume finite total puzzle inputs; infinite streams and partial values are treated explicitly where relevant. Operation counts separate numeric bit costs from list and comparison steps.^[ref]

This is the 12 June 2018 preliminary examination. Questions 1–4 concern functional programming; Questions 5–8 concern algorithm design and analysis of algorithms. Every printed option is answered here. The complete nine-page native paper is preserved in the Oxford examination release, member a10097w1.pdf; the damaged duplicate rendition is not the source used here.

The Haskell definitions below use finite total inputs unless lazy evaluation, strict functions or infinite lazy lists are being discussed. Separate questions use separate namespaces: in particular their One constructors are unrelated, and the list-conversion function abs in Question 3 is distinct from the numeric Standard Prelude function. Treat alternative definitions of the same function separately. In a module for Question 2, use import Prelude hiding (zip, zipWith); in one for Question 3, use import Prelude hiding (abs, reverse, (++)). Other questions retain the Standard Prelude operations they use.^[ref] Costs count constructor, comparison and ordinary arithmetic operations; integer bit costs and evaluating arbitrary element values are separate.