c2 otherwise. [10 marks] (b) We now define a procedure for the generation of training sequences, denoted by s. Let H be a set of possible hypotheses, let p(h) be a prior on H, let p(x) be a distribution on X and let Pr(c|x, h) be a likelihood, denoting the probability of obtaining classification c given instance x and hypothesis h H. A training set s is generated as follows. We obtain a single h H randomly according to p(h). We then obtain m instances (x1, . . . , xm) independently at random according to p(x). Finally, these are labelled according to the likelihood such that p(s|h) = Ym i=1 Pr(ci |xi , h)p(xi). We now wish to construct a hypothesis h 0 , not necessarily in H, for the purposes of classifying future examples. The usual approach in a Bayesian context would be to construct the hypothesis h 0 (x) = c1 if Pr(c1|x, s) > 1 2 c2 otherwise. By modifying your answer to part (a) or otherwise, show that this remains an optimal procedure in the case of 0-1 loss.

(a) Distributed storage approaches can be divided into network attached storage (NAS) and storage area networks (SANs). Explain with the aid of a diagram the basic differences between the two approaches. [4 marks] (b) The network file system (NFS) is often used in local area networks. (i) Why is NFS not normally considered suitable for wide area networks? [2 marks] (ii) Briefly discuss how one could modify NFS to better support wide area networks. [2 marks] (c) Distributed shared virtual memory can be used within a computing cluster to transparently allow multi-threaded programs to run across multiple machines. Sketch the design of a DSVM system. Be sure to explain what happens both when a memory read and when a memory write occurs. Comment on the expected performance and robustness of your system. [6 marks] (d) EROS is a capability-based operating system. (i) What is a capability? [1 mark] (ii) Explain with the aid of a diagram how EROS uses traditional paging hardware to emulate capability hardware.

Given any polymorphic lambda calculus (PLC) type and any function mapping type variables to values n {1, 0, 1}, a value [[ ]] in {1, 0, 1} is defined by recursion on the structure of as follows. [[]] = () [[1 2]] =

1 if [[1]] [[2]] [[2]] otherwise [[( )]] = the minimum of the values [[ ]]([ 7 n]) for n = 1, 0, 1 (where [ 7 n] is the function mapping to n and every other 0 to ( 0 )). If is a non-empty PLC typing environment, let [[]] denote the minimum value of [[ ]] as ranges over the types in ; in the case that is empty, we define [[]] to be 1. (a) Prove that if ` M : is a valid PLC typing judgement, then for any , [[]] [[ ]]. You may assume without proof that if is not free in then [[ ]]([ 7 n]) = [[ ]] and also that type substitutions [ 0 /] satisfy [[ [ 0 /]]] = [[ ]]([ 7 [[ 0 ]]]) [Hint: show that the property (, M, ) = "for all , [[]] [[ ]]" is closed under the rules of the typing system.] [16 marks] (b) Deduce that there is no closed PLC expression of type , ((( ) ) )

A W H matrix can be represented in OCaml by a flat list: a list that concatenates the rows in order. For each of the following alternative ways to represent a 2D matrix in OCaml: State the type T of the representation; Give a function create w m: int -> float list -> T that constructs the matrix of type T equivalent to the input flat list m with row width w; Give a function get r c m: int -> int -> T -> float that gets the element of the matrix m at row r and column c. State the asymptotic complexity of the get function in terms of W and H (a) A list of lists. [5 marks] (b) An array of arrays. [6 marks] (c) A functional array of functional arrays.