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 CST.2000.9.3 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 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 efficient algorithm for solving the Correspondence Problem. [5 marks] 8 CST.2000.9.9 13 Types Give the axiom and rules of the type system for polymorphic lambda calculus (PLC). [6 marks] Given any function mapping type variables to boolean values b {true,false}, we extend to a function on all PLC types by defining ( 0 ) = ( ) ( 0 ) (( )) = [ 7 true]( ) & [ 7 false]( ) where and & are the usual boolean operations of implication and conjunction, and where [ 7 b] is the function mapping to b and otherwise acting like . For example, show that for any we have (( )) = true and (()) = false. [2 marks] Let (, M, ) be the following property of PLC typing judgements ` M : . "For all , if ( ) = false then contains a type assignment xi : i with (i) = false." Show that (, M, ) is closed under the axiom and rules of the PLC type system. (You may assume without proof that if is not free in then [ 7 b]( ) = ( ); and also that type substitutions 0 [ /] satisfy ( 0 [ /]) = [ 7 ( )]( 0 ).) [10 marks] Deduce that there is no closed PLC expression of type (). [2 marks) What are the first and second theorems of welfare economics? [5 marks] (b) Give three examples of ways in which markets can fail to reach competitive equilibrium when the assumptions of the first theorem do not hold, discussing the implications for the information goods and services industries in each case. [15 marks] (a) Write down the values for the following C expressions: **i p->c[2] &(*pps)[1] ++p->i [8 marks] (b) Explain why the code shown below, when executed, will print the value 420. #include #define init_employee(X,Y) {(X),(Y),wage_emp} typedef struct Employee Em; struct Employee {int hours,salary;int (*wage)(Em*);}; int wage_emp(Em *ths) {return ths->hours*ths->salary;} #define init_manager(X,Y,Z) {(X),(Y),wage_man,(Z)} typedef struct Manager Mn; struct Manager {int hours,salary;int (*wage)(Mn*);int bonus;}; int wage_man(Mn *ths) {return ths->hours*ths->salary+ths->bonus;} int main(void) { Mn m = init_manager(40,10,20); Em *e= (Em *) &m; printf("%d ",e->wage(e)); return 0; } [4 marks] (c) Rewrite the C code shown in part (b) using C++ primitives and give four reasons why your C++ solution is better than the C one. [8 marks] 4 CST.2007.3.5 5 Computer Graphics and Image Processing (a) In image compression we use three different mechanisms to compress pixel data: (i) mapping the pixel values to some other set of values; (ii) quantizing those values; (iii) symbol encoding the resulting values. Explain each mechanism, describe the way in which it helps us to compress the image, and describe how the mechanism is implemented in the baseline JPEG compression method. [10 marks] (b) Describe the limitations of human vision in terms of: (i) spatial resolution, (ii) luminance, (iii) color, and explain the implications that each of these has on the design of display devices, including numerical estimates of the limits beyond which a human cannot discriminate