 Functional programming, design and analysis of algorithms

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.