Write about two of the following. Describe how each technique can be used in the solution of a natural language processing (sub)task and the problems which remain. (a) Active chart parsing (b) Part-of-speech disambiguation using finite-state machines (c) Probabilistic context-free grammar 

z Consider a noiseless analog communication channel whose bandwidth is 10,000 Hz. A signal of duration 1 second is received over such a channel. We wisgh toh represent this continuous signal exactly, at all points in its one-second duration, using just a finite list of real numbers obtained by sampling the values of the signal at discrete, periodic points in time. What is the length of the shortest list of such discrete samples required in order to guarantee that we capture all of the information in the signal and can recover it exactly from this list of samples? [5 marks] Name, define algebraically, and sketch a plot of the function you would need to use in order to recover completely the continuous signal transmitted, using just such a finite list of discrete periodic samples of it. [5 marks] Consider a noisy analog communication channel of bandwidth , which is perturbed by additive white Gaussian noise whose power spectral density is N0. Continuous signals are transmitted across such a channel, with average transmitted power P (defined by their expected variance). What is the channel capacity, in bits per second, of such a channel? [

You work for a large company where there are many meetings, both of internal staff and between staff and external clients. Meetings are recorded in formal minutes. The company's files of minutes are large, and the material has to be kept for many years since it may be necessary to check back on decisions taken early in large projects. You are asked to design a retrieval system so that company staff can locate minutes on a particular topic. Because of the legal implications that past discussions and decisions may have, the company is particularly concerned that the new retrieval system will be reliable and effective. Outline the design of your system, indicating the particular features it will have that are intended to meet the company's requirements (you can assume that minutes are always clearly dated and have explicit lists of participants). [10 marks] The company is willing to allow the installation of a pilot system so your approach can be evaluated under realistic conditions. Describe, in detail, your design for the evaluation: what data, operational conditions and aspects of your system would you consider, and why? What performance measures would you apply, and why? [10 marks] 5 Security "Robert Morris Senior was responsible for Unix security, Robert Morris Junior for the Internet worm. The father did much more damage to Internet security than the son" (Whitfield Diffie). Discuss. [20 marks] 4 CST.2000.7.5 6 Neural Computing Explain the key ideas of a Hopfield artificial neural network for content-addressable, associative memory. In explaining how memories are stored and retrieved, be sure to define the notions of: configuration space connectivity matrix stable attractor basin of attraction network capacity, and its dependence on the number of "neurones" [10 marks] Marshall as many lines of evidence as you can to support the view that in human vision "what you see is your own 'graphics', rather than the retinal image as faithfully recorded by photoreceptors in the eye". Explain the significance of this observation for vision theory and for machine vision. [8 marks] Suppose you were trying to design a machine vision system based as closely as possible upon human vision. Would you aim to design in the visual illusions that nearly all people "see" as well? (These include the distortions of geometrical form, angle and relative length illusions, etc.) If such properties emerged as unintended consequences of your vision design, would you consider them to be features, or bugs? [2 marks] 5 [TURN OVER CST.2000.7.6 7 Natural Language Processing The following context-free grammar and lexicon generates the examples below it with multiple derivations and therefore multiple associated interpretations. (a) S NP VP (b) NP Det N (c) NP NP PP (d) N N N (e) VP V NP (f ) VP V NP PP (g) VP VP PP (h) PP P NP N car | park | tree | boy | toy | morning | . . . V hit | . . . P in | with | . . . Det a | the | . . . a car hit the tree in the park the boy hit the toy car park with a toy car in the morning Describe how a probabilistic version of the context-free grammar (PCFG) can be created, defining the constraints which must hold for the resulting PCFG to be interpretable as a stochastic language model. [8 marks] How accurate would the resulting PCFG be at assigning the semantically appropriate derivations the highest probability for the examples and other structurally similar sentences? [6 marks] Define an improved probabilistic model for discriminating alternative derivations. What problems would arise in the implementation of this model? [6 marks] 6 Using appropriate mathematical expressions, define the following operations commonly used in computer vision and briefly explain their function and applications: (a) convolution [4 marks] (b) correlation

For a transaction model based on objects: (a) Define how conflict may be specified in terms of object operation semantics. Give an example of conflicting operations. Give an example of non-conflicting operations that would conflict with read-write semantics. [3 marks] (b) Define the necessary and sufficient condition for two transactions to be serializable. Give an example of a non-serializable pair of transactions. [2 marks] (c) Define the necessary and sufficient condition for a concurrent execution schedule of a number of transactions to be serializable. Give an example of a serialization graph for four transactions that are non-serializable. [2 marks] (d) Discuss how the three general approaches to providing concurrency control for transaction systems are designed to enforce the property you have defined in (c) above. [13 marks] 1 [TURN OVER CST.96.3.2 2 Further Modula-3 A Modula-3 library module is required to provide a buffered stream of characters between two threads, with appropriate synchronization. Write a Buffer interface defining an opaque object type, T, with the following methods: init: taking an argument specifying the buffer size and returning a suitably initialized object put: inserting a single character into the buffer get: extracting a single character from the buffer [4 marks] Sketch a corresponding implementation giving (a) the concrete revelation of the types