Have these java questions. solve all the questions.

Natural Language Processing A context free grammar for a fragment of English is shown below: S -> NP VP NP -> Det N N -> N N VP -> rumbles, rusts Det -> the, a, every N -> bus, car, train, park, airport, station (a) Show the parse trees for the two parses that the grammar assigns for sentence S1. S1: the train station bus rumbles [3 marks] (b) Give an algorithm for a bottom-up passive chart parser without packing. Illustrate your answer by showing the edges constructed when parsing sentence S1. [11 marks] (c) Describe how this algorithm could be modified so that edges may be packed, illustrating your answer by considering sentences S1 and S2. What effect does packing have on parsing efficiency? S2: the airport car park bus rumbles [6 marks] 11 [TURN OVER CST.2004.8.12 15 Denotational Semantics (a) The function fix is the least fixed point operator from (D D) to D, for a domain D. (i) Show that f. f n() is a continuous function from (D D) to D for any natural number n. [Hint: Use induction on n. You may assume the evaluation function (f, d) 7 f(d) and the function f 7 (f, f), where f (D D) and d D, are continuous.] [7 marks] (ii) Now argue briefly why fix = G n0 f. f n () , to deduce that fix is itself a continuous function. [3 marks] (b) In this part you are asked to consider a variant PCFrec of the programming language PCF in which there are terms rec x : . t, recursively defining x to be t, instead of terms fix . (i) Write down a typing rule for rec x : . t. [2 marks] (ii) Write down a rule for the evaluation of rec x : . t. [2 marks] (iii) Write down the clause in the denotational semantics which describes the denotation of rec x : . t. (This will involve the denotation of t which you may assume.) [3 marks] (iv) Write down a term in PCFrec whose denotation is the least fixed point operator of type ( ) .

11 Computer Vision (a) When defining and selecting which features to extract in a pattern classification problem, what is the goal for the statistical clustering behaviour of the data in terms of the variances within and amongst the different classes? [2 marks] (b) Consider the following pair of filter kernels: -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -3 -4 -4 -3 -1 -1 -2 -3 -3 -2 -1 2 4 5 5 4 2 -1 -3 -4 -4 -3 -1 2 4 5 5 4 2 1 3 4 4 3 1 -1 -3 -4 -4 -3 -1 1 2 3 3 2 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 (i) Why do these kernels form a quadrature pair? [2 marks] (ii) What is the "DC" response of each of the kernels, and what is the significance of this? [1 mark] (iii) To which orientations and to what kinds of image structure are these filters most sensitive? [1 mark] (iv) Mechanically how would these kernels be applied directly to an image for filtering or feature extraction? [1 mark] (v) How could their respective Fourier Transforms alternatively be applied to an image, to achieve the same effect as in (iv)? [1 mark] (vi) How could these kernels be combined to locate facial features? [2 marks] (c) Explain why inferring object surface properties from image properties is, in general, an ill-posed problem. In the case of inferring the colours of objects from images of the objects, how does knowledge of the properties of the illuminant affect the status of the problem and its solubility? [5 marks] (d) Explain and illustrate the "Paradox of Cognitive Penetrance" as it relates to computer vision algorithms that we know how to construct, compared with the algorithms underlying human visual competence. Discuss how human visual illusions may relate to this paradox. Comment on the significance of this paradox for computer vision research. [5 marks] 9 [TURN OVER CST.2004.8.10 12 Numerical Analysis II (a) State a recurrence formula for the sequence of Chebyshev polynomials, {Tk(x)}, and list these as far as T5(x). [4 marks] (b) What is the best L polynomial approximation over [1, 1] to x k using polynomials of lower degree, and what is its degree? Use this property to explain the method of economisation of a Taylor series. How can the error in one economisation step be estimated? [7 marks] (c) It is required to approximate the function f(x) = lim k Pk(x) over [1, 1] with an absolute accuracy of 2 decimal places, where Pk(x) = X k n=1 x n n n! . As this series converges faster than e x , a good estimate of the error ||f(x) Pk(x)|| in the truncated Taylor series is given by evaluating the next term x k+1 (k + 1)(k + 1)! at x = 1. Use the method of economisation to find a polynomial approximation of the required accuracy. [9 marks] 13 Specification and Verification I (a) Describe how to use Floyd-Hoare logic to specify that a program sorts an array A so that A(0), A(1), . . . , A(N) are in ascending order. [8 marks] (b) What is VDM notation? Use the sorting example to show how it can shorten specifications. Does the VDM specification of sorting have the same meaning as the Floyd-Hoare specification you gave in answer to part (a)? [6 marks] (c) Describe the concept of weakest preconditions and weakest liberal preconditions. How do they relate to Floyd-Hoare specifications?

Computer Systems Modelling Suppose that bus inter-arrival times, X, at a given bus stop have a probability density function fX(x) with mean = E(X) and variance 2 = Var(X) = E(X2 ) 2 . Suppose that a randomly arriving customer arrives during a bus inter-arrival interval of length Y and suppose that the probability density of Y is fY (y). It may be assumed that fY (y) = CyfX(y) for some constant C. (a) Derive an expression for the constant C in terms of and 2 . [7 marks] (b) Derive an expression for the average waiting time as seen by a randomly arriving customer. [7 marks] (c) For each of the following cases, calculate the average waiting time as seen by a randomly arriving customer. (i) X is deterministic taking a value of 10. [2 marks] (ii) X is exponentially distributed with mean = 10. [2 marks] (iii) X has a general distribution with mean = 10 and variance 2 = 500.