Consider the following context-free grammar of expressions E ::= n | (E, E) where n ranges over integers. (a) Present a right-most derivation of the expression ((21, 18), 17). [2 marks] (b) List the LR(0) items for this grammar. [2 marks] (c) Describe the states of the deterministic finite automata associated with an LR(0) parser for the grammar presented above. Explain your method of constructing these states. [4 marks] (d) Describe the calculation of the goto function associated with an LR(0) parser for the grammar above. How is the goto function used by the parser? [4 marks] (e) Carefully describe the LR(0) parsing associated with your derivation in (a). That is, show each transition of the parser and how it performs shift and reduce operations

A company wishes to have a camera in a video-conferencing suite to track the current speaker at any time. To do so they propose distributing a set of microphones around the room, each connected to a single computer via a set of sound cards. They intend to use a Time Difference of Arrival (TDOA) procedure to locate the speaker. (i) What is the minimum number of microphones needed, and how would you distribute them spatially to get the best results? [2 marks] (ii) Each microphone input is sampled simultaneously for a time window of length T. Give two factors that affect the choice of T. [3 marks] (iii) Given matching windows of samples for two microphones, how would you compute the time differences of the signals? [2 marks] (iv) How does the sampling rate for the signals affect the accuracy of each TDOA estimate? Assuming the audio signal of interest has a frequency of 22kHz, estimate the largest error that could be associated with a single TDOA estimate. [5 marks] (v) Suggest two other error sources likely to contribute to the ultimate error in position. What would you expect to be the dominant error source? [3 marks] 2 CST.2009.9.3 2 Advanced Systems Topics (a) Distributed storage systems can typically be divided into network attached storage (NAS) and storage area networks (SAN). (i) Describe with the aid of a diagram the operation of a typical NAS system. Use as an example the access of a file by a client system. [3 marks] (ii) Describe with the aid of a diagram the operation of a typical SAN system. Use as an example the access of a file by a client system. [3 marks] (iii) Which would be more suitable for a high-performance database system? Justify your answer. [2 marks] (b) Database systems often use indexes in order to accelerate certain operations. (i) What exactly is an index used for? [1 mark] (ii) Sequential indexes can be either sparse or dense. Give two advantages of sparse indexes and two advantages of dense indexes. [4 marks] (iii) The B+ -tree is a commonly used data-structure for implementing indexes. Sketch the structure of a B+ -tree, and describe how lookup and insertion occur. [4 marks] (iv) A related data-structure is the B-tree. What are the differences between B-trees and B+ -trees? [2 marks] (v) Why are B+ -trees typically preferred over B-trees in database systems? [1 mark] 3 (TURN OVER) CST.2009.9.4 3 Bioinformatics (a) Compute the global alignment between the two strings s1 = ACCGTT and s2 = AGTTCA, considering the following scoring parameters: +1 for match, 1 for mismatch, and 1 for a gap. (i) What is the maximum similarity score between the two sequences s1 and s2? [2 marks] (ii) Find an alignment with this similarity score. [2 marks] (iii) Is the alignment you found unique, or are there multiple alignments achieving the maximum similarity score? [1 mark] (b) Discuss the complexity of the Sankoff parsimony algorithm. [4 marks] (c) Discuss the main differences between K-means, Superparamagnetic and Markov clustering algorithms. [7 marks] (d) Discuss the utility of the Gillespie algorithm in system biology. [4 marks] 4 Computer Systems Modelling Consider the birth death process model for a M/M/1 queue with arrival rate > 0, service rate > 0 such that the traffic intensity = / < 1. Let pk for k = 0, 1, 2, . . . be the equilibrium distribution for the number of jobs, k, in the queue. (a) By considering transitions into and out of a given state i construct the global balance conditions for the equilibrium distribution. [5 marks] (b) By considering the transitions between a pair of adjacent states i and i + 1 construct the detailed balance conditions for the equilibrium distribution. [5 marks] (c) Solve the detailed balance conditions to derive the equilibrium distribution when < 1. [5 marks] (d) Show that your solution for the equilibrium distribution derived in part (c) also solves your global balance conditions given in part (a). [5 marks] 4 CST.2009.9.5 5 Computer Vision (a) Consider the following two contrasting kinds of filter kernels, A and B: 0 -1 -1 -1 -1 0 A B 1 1 1 1 1 1 -1 -2 -3 -3 -2 -1 -1 -2 -3 -3 -2 -1 -1 -3 12 12 -3 -1 -1 -3 -4 -4 -3 -1 -1 -3 12 12 -3 -1 1 3 4 4 3 1 -1 -2 -3 -3 -2 -1 1 2 3 3 2 1 0 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 (i) Given that the sum of all taps in each kernel is zero, how will each filter respond to an image region having only uniform brightness? [1 mark] (ii) Which filter has much broader bandwidth in spatial frequency? [1 mark] (iii) Categorise each filter as being either essentially isotropic or anisotropic, and explain the significance of these terms. [2 marks] (iv) Which filter is better described as an oriented edge detector? What orientation of edges is it best able to detect? [2 marks] (v) Apply the terms "2G(x, y)" or "Imaginary part of a 2D Gabor wavelet" as you think most appropriate to each filter. [2 marks] (b) What is accomplished by the lateral signal flows within both plexiform layers of the mammalian retina, in terms of image processing and coding? [4 marks] (c) Consider the task of "anti-spoofing" in the automated visual recognition of iris patterns: how to confirm that an image is acquired from a living iris instead of from a spoofing artefact like a photograph or a fake printed contact lens. How would you implement strategies (i)-(ii), and detect properties (iii)-(iv)? (i) 3D shape description using inferences from stereo, shading information, or structured light and the fact that a real iris is planar whereas a printed contact lens on the cornea floats on a spherical surface. [2 marks] (ii) Motion detection tuned for radial changes in pupil size with iris pattern stretching and light-driven deformations. [2 marks] (iii) Lambertian properties and dynamic specular reflections. [2 marks] (iv) Photonic properties of living tissue compared with artificial objects, including reflectance maps and wavelength-dependent absorption spectra. [2 marks] 5 (TURN OVER) CST.2009.9.6 6 Denotational Semantics (a) (i) Define the notion of contextual equivalence in PCF. [2 marks] (ii) Consider the following two closed PCF terms of type nat nat nat. F def = fix fn f : nat nat nat. fn x : nat. fn y : nat. if zero(x) then 0 else if zero(y) then 0 else succ f (pred x) (pred y) G def = fix fn g : nat nat nat. fn x : nat. fn y : nat. if zero(y) then 0 else if zero(x) then 0 else succ g (pred x) (pred y) Are F and G contextually equivalent? Justify your answer. [5 marks] (b) (i) Define a closed PCF term H : (nat nat nat) nat nat nat such that [[fix(H)]] N (N N) satisfies [[fix(H)]] (i) (j) = max(i, j) for all i, j N. [4 marks] (ii) Let S def = { f N (N N) | f(x)(y) = f(y)(x) for all x, y N } Show that the subset S N (N N) is admissible. [4 marks] (iii) Show that [[fix(H)]] (x) (y) = [[fix(H)]] (y) (x) for all x, y N. [5 marks] [Hint: Use Scott's Fixed-Point Induction Princip

Some RFID manufacturers now produce semi-active RFID tags, where a battery is used to power the microelectronics but backscattering is used for all radio communications. Give two advantages and two disadvantages of such tags. [4 marks] (c) Consider a typical binary tree search applied to identify all RFID tags within range of a transmitter. Each request takes the form [ REQ | F | X ], where REQ is a c-bit command ID, F is the f < K filter bits and X is a (K f) bit sequence of 1s. Any response then has the form [ RESP | F | I ], where RESP is a c-bit command ID, F is the first f bits of the replying tag's ID and I represents the remaining (K f) bits of that ID. In an attempt to increase efficiency, a manufacturer proposes that the reader just send [ REQ | F ] and the tags immediately respond with [ I ]. (i) What addition would you have to make to the communications protocol for this to work? What would its overhead be in bits? [3 marks] (ii) Derive an expression for the proportional reduction in search time that this new scheme would provide. Estimate the value of the ratio for a typical tag on the market today. [5 marks] (d) In a probabilistic RFID scheme, the reader transmits the number of slots in a round, N. RFID tags choose a slot uniformly at random and transmit their ID in it. Suggest how to estimate the number of tags in range based only on one round at the reader. [Hint: Consider the expected number of slots with a given property such as being empty or containing a collision.] [6 marks] 2 CST.2009.7.3 2 Advanced Graphics (a) State the Jordan curve theorem. [1 mark] (b) Given point V and simple convex planar polygon P={v0, v1, . . . , vn1} in R 3 , express: (i) A test for whether V is coplanar with P. [1 mark] (ii) A test for whether V lies strictly inside P. [2 marks] (iii) A test for whether V lies on the border of P. [1 mark] (c) (i) Describe an algorithm for ray-tracing a complex CSG (Constructive Solid Geometry) shape. How could your algorithm be represented by a state machine? [4 marks] (ii) Identify three Boolean operations that your algorithm would support between primitives. [1 mark] (iii) Would your algorithm perform ray-primitive intersections in local, eye, screen, or world co-ordinates? Why? [2 marks] (d) (i) Show that the closed uniform B-Spline of degree 2 and with knot vector {0, 0, 0, 1, 1, 1} is a quadratic Bezier curve. [6 marks] (ii) Sketch the basis functions of the curve's coefficient polynomials. Accuracy is not critical. [2 marks] 3 (TURN OVER) CST.2009.7.4 3 Advanced Systems Topics (a) The size and rate of growth of routing tables is an issue of considerable concern for inter-domain routing in the Internet. (i) Describe at least three factors that contribute to this problem. [3 marks] (ii) How might a distinction between Locators and Identifiers help address this problem? [4 marks] (iii) What are the costs and risks of implementing a Loc/ID split? [4 marks] (b) BGP employs a mechanism called Route Flap Damping (RFD) to reduce route instabilities. (i) Describe how RFD works. [4 marks] (ii) Describe some problems with RFD. [2 marks] (iii) Describe another approach to reducing the number of BGP updates. [3 marks] 4 CST.2009.7.5 4 Artificial Intelligence II Evil Robot has almost completed his Evil Plan for the total destruction of the human race. He has two nasty chemicals, which he has imaginatively called A and B and which are currently stored in containers 1 and 2 respectively. All he has to do now is mix them together in container 3. His designeran equally evil computer scientisthas equipped Evil Robot with a propositional planning system that allows him to reason about the locations of particular things and about moving a thing from one place to another. (a) Explain how this problem might be represented within a propositional planning system. Give specific examples of the way in which the start state and goal can be represented. [5 marks] (b) Describe in detail an algorithm that can be used to find a plan using this form of representation. [5 marks] (c) Give a specific example of a successor-state axiom using the representation you suggested in part (a). [2 marks] (d) Explain why in this particular planning problem it might be necessary to include one or more precondition axioms and give an example of such an axiom using your representation. [2 marks] (e) Explain why in this particular planning problem it might be necessary to include one or more action exclusion axioms and give an example of such an axiom using your representation. Suggest why it might be unwise to include too many axioms of this type, and explain how a reasonable collection of such axioms might be chosen in a systematic way. [4 marks] (f ) Explain how in this problem it might be possible to include state constraints as an alternative to action exclusion axioms, and give a specific example of such a constraint using your representation. [2 marks] 5 (TURN OVER) CST.2009.7.6 5 Bioinformatics (a) Discuss, with one example, the complexity of the Nussinov algorithm for RNA folding. [5 marks] (b) In the context of algorithms on strings, what is the advantage of using spaced seeds in database sedels (HMM) are used to identify genes in genome sequencing projects. (i) Describe how you would build a hidden Markov model to identify genes in a genome sequence. [7 marks] (ii) How would you assess the sensitivity and specificity performance of the HMM? [5 marks] 6 Business Studies (a) Distinguish between debt and equity financing for a young company. [5 marks] (b) You have won a contract to write and supply some software and set up a company to do so. The contract is worth 100,000, with 30% payable at start, 20% at a milestone expected to be completed in month 3 after starting, 40% on delivery expected in month 6 and 10% 1 month after delivery. You will need to employ two contract programmers at a rate of 2,500 each per month (plus overheads) for the duration of the contract. (i) Draw up an outline cash flow budget. What is the working capital requirement? [5 marks] (ii) You raise investment of 15,000 in the company and arrange a bank loan facility up to another 15,000 (ignore bank charges and loan interest for this question). You purchase 10,000 of capital equipment initially (computers etc). Draw up the balance sheet at the end of month 6. [5 marks] (iii) The project unfortunately takes an additional two months before passing the milestone. Draw up a revised cash-flow budget including the funds raised and purchases made as specified in part (b)(ii). What effect does this have on the working capital requirement? What options do the Directors have if the bank refuses to extend the loan? [5 marks] 6 CST.2009.7.7 7 Comparative Architectures (a) What dependencies exist between the instructions in the code fragment below? Identify both true data dependencies and name dependencies, and for each name dependence indicate whether it is an antidependence or an output dependence. [4 marks] LI R1, 25 /* R1=25 */ LI R2, 8 /* R2=8 */ ADD R1, R1, R2 /* R1=R1+R2 */ LD R2, 0(R1) /* R2=mem[R1] */ (b) How would a hardware register renaming mechanism remove the name dependencies? Illustrate your answer by providing a version of the code showing the destination and source registers for each instruction after renaming has taken place. Clearly state what free physical registers you assume are available prior to renaming. [4 marks] (c) Why is the removal of name dependencies beneficial within a superscalar processor? [4 marks] (d) In addition to removing name dependencies, for what other purposes may register renaming hardware be used in a superscalar processor? [4 marks] (e) The out-of-order execution of ALU instructions in a superscalar processor is only constrained by the availability of functional units and true data dependencies. Why must the out-of-order execution of memory instructions (e.g. load and store instructions) be constrained further?

) the relationship between YCrCb and RGB colour coordinates. [4 marks] (c) A 300 Hz sine wave is sampled at 1000 Hz. This discrete sequence is then multiplied, sample by sample, with the discrete sequence . . . , 0, +1, 0, 1, 0, +1, 0, 1, 0, +1, 0, 1, . . . Which frequencies appear in the Fourier transform of the result? [5 marks] 11 (TURN OVER) CST.2009.9.12 13 Specification and Verification II (a) What is the "false-implies-everything" problem? [2 marks] (b) What is the difference between temporal and data abstraction? [2 marks] (c) How do models of combinational and sequential devices differ? [2 marks] (d) How is the rising edge of a signal modelled in higher order logic? [2 marks] (e) Write down a formula that asserts that if a signal s has the value a then at all later times it also has the value a. [2 marks] (f ) Give two properties of transistors that are not modelled by the simple switch model. [2 marks] (g) What are advantages of using binary decision diagrams to represent Boolean formulae? [2 marks] (h) What is the difference between linear and branching time? [2 marks] (i) What are the relative expressive powers of LTL and CTL? [2 marks] (j) How do the Verilog and VHDL simulation cycles differ? [2 marks] 12 CST.2009.9.13 14 Topics in Concurrency (a) (i) Describe the modal -calculus and its semantics. [4 marks] (ii) Describe how to express maximum fixed points Y.A in terms of minimum fixed points. [1 mark] (b) (i) Describe an algorithm to determine whether a state in a finite-state transition system satisfies an assertion in the modal -calculus. [4 marks] (ii) Explain briefly why the algorithm always terminates. [3 marks] (iii) Use the algorithm to determine whether or not the state s in the labelled transition system below satisfies the assertion [a]Y.(hbiT [b]Y ), where T stands for "true". s u t a a b b [6 marks] (iv) Describe, without proof, the meaning of the assertion from the modal -calculus in part (b)(iii) above. [2 marks] 13 (TURN OVER) CST.2009.9.14 15 Types (a) What is meant by beta-reduction, beta-conversion and beta-normal forms for the polymorphic lambda calculus (PLC)? Explain why typeable PLC expressions are beta-convertible to beta-normal forms that are unique up to alpha-conversion. Is the same true for untypeable PLC expressions? (Any general properties of PLC you use should be clearly stated, but need not be proved.) [10 marks] (b) Let be the PLC type (( ) ), where and are distinct type variables. Give closed PLC beta-normal forms I and J with the following properties: (i) I has type ( ) (ii) J has type ( ) (iii) (x : (J (I x))) has beta-normal form (x : (x)) Justify your answers by giving proofs of typing and beta-conversion. [8 marks] What is the beta-normal form of (y : (I (J y)))?