Explain what these two functions does and why they may be useful. [4 marks] (a) Here is a typical use of map: fun mangle n = (n-2)*(n+7); fun manglelist x = map mangle x; Show how to express manglelist using one of the "fold" functions rather than map. [3 marks] (a) Given a set A, dene the following terms: (i) a relation on A; [1 mark] (ii) an equivalence relation on A; [1 mark] (iii) a partial order on A; [1 mark] (iv) a well-founded relation on A. [1 mark] (b) If two relations tr * unit->tr; (a) Write the function called ndeep such that if n is an integer and z is a tree (i.e. of type tr) the call ndeep n z will return an ordinary list of all the 2n integers at depth exactly n in the tree. Note that if n = 0 it will return a list of length 1, being just the top integer in the tree. Comment on its eciency. [8 marks] (b) You are given a tr, and told that it contains arbitrarily large values at least somewhere in it. You want to nd a value from it that is bigger than 100 (but if there are many big values it does not matter which one is returned). Because the tree is innite you cannot use simple depth-rst search: you decide to use iterative deepening. Thus you rst check all integers at depth 1, then at depth 2, depth 3,... and return when you rst nd a value that is greater than 100. Use exception handling to return the large value when you nd it. Present and explain code that searches the lazy tree. [12 marks] In ML it is possible to use functions as values: they can be passed as arguments and returned as results. Explain the notation used to write function without having to give it a name. [2 marks]

(i) Define the Discrete Fourier Transform (DFT) of f[n], a discrete sequence F[k], as a series using complex exponentials. In terms of N, how many complex multiplications would be required to compute F[k] explicitly? Then define W, the primitive Nth root of unity, and now re-express your series for F[k] in terms of W. [4 marks] (ii) Now express your DFT sequence F[k] using a series with only N/2 terms, by capturing the second half of the series within the first half, and show that fewer complex multiplications are required. [4 marks] (iii) Now show that separating F[k] into two new sequences of half-length, each of which computes only N/2 coefficients F[k], leads to a very efficient recursive form. How many times can this halving process be repeated? Ultimately how many complex multiplications are therefore required for this Fast Fourier Transform (FFT)? For 'big data' applications requiring a DFT on a billion data values, what speed-up factor can be expected by using an FFT instead of explicitly computing a DFT? [4 marks] (c) Piecewise continuous and absolutely integrable functions f(x), g(x) : R C have Fourier transforms F() and G(), respectively. Let h(x) = (f g)(x) be the convolution of f(x) and g(x): h(x) = Z f(x y)g(y)dy Prove that H(), the Fourier transform of h(x), is simply the product: H() = 2F() G() [4 marks] 7 (TURN O CST1.2017.6.8 8 Mathematical Methods for Computer Science (a) (i) State the central limit theorem. [2 marks] (ii) Consider a binomially distributed random variable T with parameters Bin(n,p) where n is a positive integer and 0 < p < 1. Using the central limit theorem derive an approximation to the probability P(T > d) where d (0, n) and where n is sufficiently large. [4 marks] (b) Let (Xn)n1 be a Markov chain on the states {0, 1, 2} with transition matrix P = 0 0 1 0 1 1 0 where 0 < < 1. (i) Draw the state space diagram for the Markov chain Xn. [2 marks] (ii) Explain why Xn is an irreducible, recurrent and aperiodic Markov chain. [6 marks] (iii) Define an equilibrium distribution = (0, 1, 2) for the Markov chain Xn and determine . [6 marks] 8 CST1.2017.6.9 9 Semantics of Programming Languages Consider a language with abstract syntax e ::= n | x | let x = e1 in e2 | alloc | free e | e1 := e2 | !e | e1; e2 | e1 + e2 This is intended to allow computation over data allocated in a concrete block of memory: n ranges over a set W = {0, . . . , 2 32 1} of machine words, used both as values and as addresses. A memory state is described by a total function m : W W , giving the value at each address, and a set a W , identifying the locations that are currently allocated. The term x ranges over a set of non-mutable variables, not allocated in memory. The expression e := e 0 , !e, alloc, and free e are respectively assignment, dereferencing, allocation, and free of single words. (a) Define a reasonable deterministic operational semantics for this language, as a transition relation he, m, ai he 0 , m 0 , a 0 i and a predicate he, m, ai error that identifies the configurations that are runtime errors. You can omit the rules for e1; e2 and e1 + e2 and the standard definition of substitution. Your definition should ensure (though you need not prove) that for any configuration he, m, ai, either e is a value n, or there is exactly one transition he, m, ai he 0 , m0 , a 0 i from that configuration, or there is exactly one derivation of a runtime error he, m, ai error. Note and explain your choices.