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 rumble

 

(a) If you were the HCI researcher on a speech interaction project intended to replace the WIMP interface, then (i) Which of the techniques described above would be most relevant to your work? Why? [3 marks] (ii) Explain how a modern analytic evaluation method could give design guidance to the team, including a description of how the analysis would be conducted, and two design improvements that might result from that analysis. [7 marks]

(a) The mid-point rule can be expressed in the form In =Z n+ 1 2 n1 2 f(x)dx = f(n) + en where en = f00(n)/24 for some n in the interval (n1 2,n+ 1 2). Assuming that a formula forRf(x)dxis known, and using the notation Sp,q = q X n=p f(n) , describe a method for estimating the sum of a slowly convergent series S1,, by summing only the rst N terms and estimating the remainder by integration. [5 marks] (b) Assuming that f00(x) is a positive decreasing function, derive an estimate of the error |EN| in the method. [5 marks] (c) Given Z dx (1 + x)x = 2tan1x illustrate the method by applying it to X n=1 1 (1 + n)n . Verify that f00(x) is positive decreasing for large x, and estimate the integral remainder to be added to S1,N. [6 marks] (d) How large should N be to achieve an absolute error of approximately 21015? [You may assume N + 1 ' N for this purpose.] [4 marks] (a) Prove Arden's Rule for events, that X = A*B is the least solution of the inequality X > B + AX. [6 marks] (b) Let M =A B C Dbe a (22) event matrix. Show that the matrix Y = (A + BD*C)* A*B(D + CA*B)* D*C(A + BD*C)* (D + CA*B)* satises the equation Y = I + MY . [4 marks] 5 Business Studies What is meant by a critical path? [5 marks] The village bakery has asked you to advise them about setting up a web site, including a trading function. Draw up a project plan, illustrated by a GANTT chart, and indicate the critical path. [5 marks] Make an estimate of the costs involved, and estimate how much working capital you would need. [5 marks] What other advice would you give them? [5 marks] 6 Security The owner of a banking system which previously used manually distributed shared keys to compute MACs on transactions decides to use public key cryptography to distribute MAC keys in future. The proposed protocol is A B : { {TA, KAB}K1 A KB } Explain the symbolism used in this description. [2 marks] What is wrong with this protocol? [6 marks] The protocol is changed to A B : { {A, TA, KAB}K1 A KB } What attacks might there be on the system now? [12 marks] 3 [TURN OVER CST.2000.9.4 7 Computer System Modelling A database system has a central processor and three (different) discs. Measurements are taken for 1000 transactions on a lightly loaded system and the following observations are made. The CPU scheduler initiated or resumed transaction processing 10,000 times. The total CPU usage was 25 seconds. Disc 1 made 5000 transfers with an average transfer time of 10 ms. Disc 2 made 2000 transfers with an average transfer time of 50 ms. Disc 3 made 2000 transfers with an average transfer time of 20 ms. Derive the visit counts, service times and transaction service demands. What is the bottleneck device? What is the maximum throughput of the system measured in transactions per second? [6 marks] Describe two balanced systems which bound the throughput of the system. What is the maximum throughput of these systems? [7 marks] Recall that the throughput of a balanced system with K devices, N customers and service demand D per device is X(N) = N (N + K 1) 1 D How many transactions do you expect to be in the system with a throughput of 7 transactions per second? [7 marks] 4 CST.2000.9.5 8 Neural Computing Give evidence supporting the view that the main computational load that has shaped the evolution of the human brain is "social computation", with sexual success being the ultimate measure of the value of an algorithm or neural design feature. Say what implications this has for: The cognitive skills and perceptual faculties that have been selected for in brain evolution, as contrasted with the goals which are the traditional focus of AI. The design of face recognition algorithms, which aim to interpret facial expression, gesture, and intent, as well as gender and identity. The construction of the theory that other persons have minds, too. Models of action, planning, and interaction between self and others. [8 marks] Comment on whether this "social computation" view of human brain evolution implies that brain science is less relevant to the goals of computer science than is usually thought. [2 marks] Answer any five of the following seven short questions: (a) Roughly what is the total number of neurones in the human brain? (b) Roughly what is the total number of synapses in the human brain? How does this compare with the total number of stars in our galaxy, and with the total number of galaxies in the known universe? (c) Why is nerve impulse propagation described as "saltatory", and what purposes are achieved by this method of signalling? (d) What is the approximate speed of nerve impulse propagation in warm-blooded animals, in metres/sec? (e) Why is "white matter" white, what cells are responsible for this, and what purpose do they serve? (f ) Name the three principal ions involved in nerve membrane current flows, and identify which two of them transit through voltage-dependent conductances. (g) What causes the refractory deadtime of about 1 msec after each nerve impulse? [2 marks each] 5 [TURN OVER CST.2000.9.6 9 Artificial Intelligence Consider the following story of the play Macbeth, by William Shakespeare: The characters are Macbeth, Lady-Macbeth, Duncan and Macduff. Macbeth is an evil noble. Lady-Macbeth is a greedy ambitious woman. Duncan is a king. Macduff is a loyal noble. Macbeth is weak because Macbeth married Lady-Macbeth and because Lady-Macbeth is greedy. Lady-Macbeth persuades Macbeth to want to be king. Macbeth murders Duncan using a knife because Macbeth wants to be king and because Macbeth is evil. Lady-Macbeth kills Lady-Macbeth. Macduff is angry because Macbeth murdered Duncan and because Macduff is loyal to Duncan. Macduff kills Macbeth. Construct a semantic network representing the above story. [8 marks] Show the chain of reasoning leading to Macduff killing Macbeth. [5 marks] It is possible to change the story so that Lady-Macbeth is unable to persuade Macbeth to want to be king. Augment the story to provide a reason for Lady-Macbeth's inability to persuade Macbeth to want to be king. Update the semantic network to reflect the new situation. [7 marks] 10 Numerical Analysis II Explain the terms (a) positive definite, (b) positive semi-definite for a symmetric matrix A. If a square matrix B is non-singular, which of the properties (a) or (b) most accurately describes BT B? What if B is singular? [4 marks] State Schwarz's inequality for the product AB. In what way is this modified for the product Ax, where x is a vector? What are the singular values of A, and how are they related to the l2 norm of A? In the singular value decomposition A = UWVT , what is W? [5 marks] Let x be an approximate solution of Ax = b, and write r = b Ax, e = x x. Find an expression which is an upper bound for the relative error ||e||/||x|| in terms of computable quantities. Explain how this result may be interpreted if the l2 norm is used. [8 marks] Suppose A is a 5 5 matrix and Ax = b is to be solved by singular value decomposition. If machine epsilon ' 1015 and the singular values of A are 1, 106 , 1010 , 1017 , 0 write down the generalised inverse W+ that you would use. [3 marks] 6 CST.2000.9.7 11 Information Theory and Coding (a) Prove that the information measure is additive: that the information gained from observing the combination of N independent events, whose probabilities are pi for i = 1 . . . N, is the sum of the information gained from observing each one of these events separately and in any order. [4 marks] (b) What is the shortest possible code length, in bits per average symbol, that could be achieved for a six-letter alphabet whose symbols have the following probability distribution? { 1 2 , 1 4 , 1 8 , 1 16 , 1 32 , 1 32 } [3 marks] (c) Suppose that ravens are black with probability 0.6, that they are male with probability 0.5 and female with probability 0.5, but that male ravens are 3 times more likely to be black than are female ravens. If you see a non-black raven, what is the probability that it is male? [4 marks] How many bits worth of information are contained in a report that a non-black raven is male? [1 mark] Rank-order for this problem, from greatest to least, the following uncertainties: (i) uncertainty about colour (ii) uncertainty about gender (iii) uncertainty about colour, given only that a raven is male (iv) uncertainty about gender, given only that a raven is non-black [3 marks] (d) If a continuous signal f(t) is modulated by multiplying it with a complex exponential wave exp(it) whose frequency is , what happens to the Fourier spectrum of the signal? Name a very important practical application of this principle, and explain why modulation is a useful operation. How can the original Fourier spectrum later be recovered? [3 marks] (e) Which part of the 2D Fourier Transform of an image, the amplitude spectrum or the phase spectrum, is indispensable in order for the image to be intelligible? Describe a demonstration that proves this. [2 marks] 12 Computer Vision Define the Correspondence Problem, detailing the different forms that it takes in stereo vision and in motion vision. (a) In each case, explain why the computation is necessary. [5 marks] (b) What are the roles of space and time in the two cases, and what symmetries exist between the stereo vision and the motion vision versions of the Correspondence Problem? [5 marks] (c) How does the complexity of the computation depend on the number of underlying features that constitute the data? [5 marks] (d) Briefly describe at least one general approach to an e

1 Distributed Systems In a distributed electronic conference application each participant has a replica of a shared whiteboard. Only one user at a time may write to the whiteboard, after which the user's update is propagated to all conference members. A dedicated process manages each whiteboard replica. Define and discuss a protocol that the replica managers could use to achieve this mutual exclusion. [10 marks] A service database is replicated within a widely distributed system to achieve high availability and low access latency. Within a hierarchy of replicas a set of top-level primary servers maintain strong consistency of their replicas. Describe how this strong consistency could be achieved. [10 marks] 2 VLSI Design Sketch a transistor-level design and give a brief description of the method of operation for each of the following memory cells: (a) a dual-ported, static memory cell [5 marks] (b) a dynamic memory cell using standard MOS logic [5 marks] (c) a dynamic memory cell for dense memory [5 marks] Explain the comparative merits of the three designs and explain where they might be used. [5 marks] 1 [TURN OVER CST.2000.9.2 3 Digital Communication II Consider the IntServ (RSVP based) and DiffServ QoS Architectures. (a) Compare the nature of "guarantee" that is made in each and the time scale on which these are altered. [6 marks] (b) Compare where state resides in each case, and how much state there is. [3 marks] (c) Compare the number of control interactions that a core router in each architecture would engage in. [3 marks] (d) Compare the resource efficiency of each scheme in terms of link bandwidth. [Hint: consider single-ended Service-Level Agreements (SLAs).] [3 marks] (e) Describe the architecture of a core router in a DiffServ environment, recalling that each packet will have a Type of Service field describing its designated Per Hop Behaviour. [5 marks] 4 Advanced Graphics and HCI (a) Show how you would calculate the first intersection point between an arbitrary ray and a finite length open cylinder of unit radius aligned along the x-axis. [Note: an open cylinder is one which has no end caps.] Having calculated the intersection point, how would you calculate the normal vector? [7 marks] (b) A non-rational B-spline has knot vector [1, 2, 4, 7, 8, 10, 12]. Derive the first of the third order (second degree) basis functions, N1,3(t), and graph it. If this knot vector were used to draw a third order B-spline, how many control points would be required? [7 marks] (c) Describe how an object built using constructive solid geometry (CSG) can be represented using a binary tree. Given the intersection points of a ray with each primitive in the tree, show how to calculate the first intersection point of the ray with the entire CSG object. [6 marks] 2

5 Business Studies What is meant by a critical path? [5 marks] The village bakery has asked you to advise them about setting up a web site, including a trading function. Draw up a project plan, illustrated by a GANTT chart, and indicate the critical path. [5 marks] Make an estimate of the costs involved, and estimate how much working capital you would need. [5 marks] What other advice would you give them? [5 marks] 6 Security The owner of a banking system which previously used manually distributed shared keys to compute MACs on transactions decides to use public key cryptography to distribute MAC keys in future. The proposed protocol is A B : { {TA, KAB}K1 A KB } Explain the symbolism used in this description. [2 marks] What is wrong with this protocol? [6 marks] The protocol is changed to A B : { {A, TA, KAB}K1 A KB } What attacks might there be on the system now? [12 marks]

7 Computer System Modelling A database system has a central processor and three (different) discs. Measurements are taken for 1000 transactions on a lightly loaded system and the following observations are made. The CPU scheduler initiated or resumed transaction processing 10,000 times. The total CPU usage was 25 seconds. Disc 1 made 5000 transfers with an average transfer time of 10 ms. Disc 2 made 2000 transfers with an average transfer time of 50 ms. Disc 3 made 2000 transfers with an average transfer time of 20 ms. Derive the visit counts, service times and transaction service demands. What is the bottleneck device? What is the maximum throughput of the system measured in transactions per second? [6 marks] Describe two balanced systems which bound the throughput of the system. What is the maximum throughput of these systems? [7 marks] Recall that the throughput of a balanced system with K devices, N customers and service demand D per device is X(N) = N (N + K 1) 1 D How many transactions do you expect to be in the system with a throughput of 7 transactions per second? [7 marks] 4 CST.2000.9.5 8 Neural Computing Give evidence supporting the view that the main computational load that has shaped the evolution of the human brain is "social computation", with sexual success being the ultimate measure of the value of an algorithm or neural design feature. Say what implications this has for: The cognitive skills and perceptual faculties that have been selected for in brain evolution, as contrasted with the goals which are the traditional focus of AI. The design of face recognition algorithms, which aim to interpret facial expression, gesture, and intent, as well as gender and identity. The construction of the theory that other persons have minds, too. Models of action, planning, and interaction between self and others. [8 marks] Comment on whether this "social computation" view of human brain evolution implies that brain science is less relevant to the goals of computer science than is usually thought. [2 marks] Answer any five of the following seven short questions: (a) Roughly what is the total number of neurones in the human brain? (b) Roughly what is the total number of synapses in the human brain? How does this compare with the total number of stars in our galaxy, and with the total number of galaxies in the known universe? (c) Why is nerve impulse propagation described as "saltatory", and what purposes are achieved by this method of signalling? (d) What is the approximate speed of nerve impulse propagation in warm-blooded animals, in metres/sec? (e) Why is "white matter" white, what cells are responsible for this, and what purpose do they serve? (f ) Name the three principal ions involved in nerve membrane current flows, and identify which two of them transit through voltage-dependent conductances. (g) What causes the refractory deadtime of about 1 msec after each nerve impulse? [2 marks each] 5 [TURN OVER CST.2000.9.6 9 Artificial Intelligence Consider the following story of the play Macbeth, by William Shakespeare: The characters are Macbeth, Lady-Macbeth, Duncan and Macduff. Macbeth is an evil noble. Lady-Macbeth is a greedy ambitious woman. Duncan is a king. Macduff is a loyal noble. Macbeth is weak because Macbeth married Lady-Macbeth and because Lady-Macbeth is greedy. Lady-Macbeth persuades Macbeth to want to be king. Macbeth murders Duncan using a knife because Macbeth wants to be king and because Macbeth is evil. Lady-Macbeth kills Lady-Macbeth. Macduff is angry because Macbeth murdered Duncan and because Macduff is loyal to Duncan. Macduff kills Macbeth. Construct a semantic network representing the above story. [8 marks] Show the chain of reasoning leading to Macduff killing Macbeth. [5 marks] It is possible to change the story so that Lady-Macbeth is unable to persuade Macbeth to want to be king. Augment the story to provide a reason for Lady-Macbeth's inability to persuade Macbeth to want to be king. Update the semantic network to reflect the new situation. [7 marks] 10 Numerical Analysis II Explain the terms (a) positive definite, (b) positive semi-definite for a symmetric matrix A. If a square matrix B is non-singular, which of the properties (a) or (b) most accurately describes BT B? What if B is singular? [4 marks] State Schwarz's inequality for the product AB. In what way is this modified for the product Ax, where x is a vector? What are the singular values of A, and how are they related to the l2 norm of A? In the singular value decomposition A = UWVT , what is W? [5 marks] Let x be an approximate solution of Ax = b, and write r = b Ax, e = x x. Find an expression which is an upper bound for the relative error ||e||/||x|| in terms of computable quantities. Explain how this result may be interpreted if the l2 norm is used. [8 marks] Suppose A is a 5 5 matrix and Ax = b is to be solved by singular value decomposition. If machine epsilon ' 1015 and the singular values of A are 1, 106 , 1010 , 1017 , 0 write down the generalized inverse W+ that you would use. [3 marks]

Information Theory and Coding

(a) Prove that the information measure is additive: that the information gained from observing the combination of N independent events, whose probabilities are pi for i = 1 . . . N, is the sum of the information gained from observing each one of these events separately and in any order. [4 marks] (b) What is the shortest possible code length, in bits per average symbol, that could be achieved for a six-letter alphabet whose symbols have the following probability distribution? { 1 2 , 1 4 , 1 8 , 1 16 , 1 32 , 1 32 }

c) Suppose that ravens are black with probability 0.6, that they are male with probability 0.5 and female with probability 0.5, but that male ravens are 3 times more likely to be black than are female ravens. If you see a non-black raven, what is the probability that it is male?