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] 7 [TURN OVER CST.2000.9.8 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