MUST BE CORRECT ANSWERS

A small software company has the following simplified cashflow, funded by shareholders' equity of 20,000 and a bank overdraft of 5000: Invoiced money received 2 months after due date; paid after 1 month of receipt of invoice Cashflow: Month 1 2 3 4 5 6 7 Income 30, 000 30, 000 Expenditure Programmers 5, 000 5, 000 5, 000 5, 000 5, 000 5, 000 5, 000 Overheads 5, 000 5, 000 5, 000 5, 000 5, 000 5, 000 Total costs 5, 000 10, 000 10, 000 10, 000 10, 000 10, 000 10, 000 Cash at start 5, 000 15, 000 5, 000 25, 000 15, 000 5, 000 5, 000 Cash at end 15, 000 5, 000 25, 000 15, 000 5, 000 5, 000 15, 000 Draw up the balance sheet at the end of month 6. [5 marks] (d) What advice would you give the directors? [5 marks] 2 CST.2011.7.3 2 Artificial Intelligence II Consider the following propositional planning problem. Start state: A, B, C, D. Goal: A, B, C, D. Actions: Action 1 has preconditions A,B,C and effect D. Action 2 has preconditions A,B and effects A and B. Action 3 has preconditions B,C and effects B and C. Action 4 has precondition B and effect B. (a) Using an entire sheet of paper, draw the planning graph as far as state level S3, where the start state is at state level S0 and the first action level is A0. Do not add any mutex links at this point. [5 marks] (b) Describe each of the five kinds of mutex link that can be incorporated in a planning graph. Add one example of each to the graph you produced in part (a). Clearly label the links to make clear which type they are. [10 marks] (c) At which level in the planning graph will all goals first be present simultaneously? Will the GraphPlan algorithm be able to extract a working plan without extending it beyond this level? Explain your answer, adding further mutex links to your diagram if necessary. [5 marks] 3 (TURN OVER) CST.2011.7.4 3 Advanced Graphics (a) Describe the key features of B-splines that make them useful for representing curves in computer-aided design (CAD). [3 marks] (b) Derive and graph the quadratic Bezier basis functions using the standard B-spline method and the knot vector [0, 0, 0, 1, 1, 1]. [5 marks] (c) Describe Chaikin's corner-cutting subdivision method that produces the quadratic Bezier curve in the limit. [5 marks] (d) Describe the Doo-Sabin subdivision scheme, that is the generalisation of Chaikin's method to the bi-variate case able to represent surfaces with extraordinary vertices. [7 marks] 4 Comparative Architectures (a) What hardware and software techniques may be used to reduce the number of conflict misses experienced by a direct-mapped cache? [4 marks] (b) How might a hardware prefetcher that is capable of detecting and prefetching non-unit strides be implemented? [4 marks] (c) How can the MESI cache coherency protocol be exploited to ensure that a test-and-set instruction is performed atomically without the need to lock down the bus for multiple cycles? [4 marks] (d) Moore's law predicts we will be able to integrate a very large number of processor cores onto a single chip in the near future. What constraints and challenges may limit our ability to exploit these chip multiprocessors? [8 marks] 4 CST.2011.7.5 5 Denotational Semantics (a) Let be the domain 0 v 1 v v n v v (n N)

That is, = N {}, v with x v y in iff x y in N or y = . Indicate whether the following statements are true or false. Provide an argument for each answer. (i) Every monotone function from to is continuous. [5 marks] (ii) Every monotone function from to has a least pre-fixed point. [5 marks] (b) Let D and E be domains, and let f : D D and g : E E be continuous functions. (i) Define f g : D E D E to be the continuous function given by

f g (d, e) = f(d), g(e) , and let 1 : D E D and 2 : D E E respectively denote the first and second projection functions. Show that fix(f g) v

fix(f), fix(g) , and that fix(f) v 1

fix(f g) and fix(g) v 2

fix(f g) . [5 marks] (ii) It follows from part (i) that fix(f g) = fix(f), fix(g) . Use this and Scott's Fixed Point Induction Principle to show that, for all strict continuous functions h : D E, h f = g h = h

fix(f) = fix(g) [5 marks]Suppose that the random variable X has an exponential distribution with parameter > 0. (i) What are the probability density function, fX(x), and the probability distribution function, FX(x), for the random variable X? [2 marks] (ii) Derive the mean and variance of the random variable X and determine its coefficient of variation. [3 marks] (iii) Show that the random variable X obeys the memoryless property P(X > t + s|X > t) = P(X > s) for all s, t > 0. [2 marks] (iv) Use the inverse transform method to derive a method to simulate random variables, Xi , indexed by i = 1, 2, . . . from an exponential distribution with parameter > 0 given a sequence of pseudo-random values Ui from the uniform distribution U(0, 1). [3 marks] (b) Suppose that X1, X2, . . . is a sequence of independent and identically distributed random variables with each random variable Xi having a marginal distribution that is an exponential distribution with parameter > 0. Let Sn = Pn i=1 Xi where n is a positive integer and let the random variable N(t) for t > 0 be the number of events in a Poisson Process with parameter > 0 that occur in the time interval (0, t). (i) State the probability distribution of N(t). [2 marks] (ii) State a relation between Sn and N(t). [2 marks] (iii) Derive the probability density of the random variable Sn. [6 marks] 2 CST.2011.9.3 2 Computer Vision (a) Name four Gestalt laws of perceptual organisation. What is the main theme of Gestalt Psychology, and in what way is it relevant to automated object recognition in images and video sequences? [4 marks] (b) Many computer vision algorithms such as SIFT (scale-invariant feature transform) seek to detect and analyse features at multiple scales of analysis. (i) What is "scale-space" and what is a "scale-space fingerprint"? [2 marks] (ii) Briefly describe how SIFT achieves scale and rotation invariance. [3 marks] (iii) Show that the difference-of-Gaussian operation DoG given by DoG(x, y, ) = (G(x, y, k) G(x, y, )) I(x, y) G(x, y, ) = 1 22 e (x 2+y 2 )/2 2 on image data I as used by SIFT is an approximation of the scalenormalised Laplacian of Gaussian given by 22G. You may assume that G = 2G Comment on a good choice for the value of k for practical applications of SIFT. [6 marks] (c) The curvature map of a closed image contour is a bandlimited signal and can be described by its zero-crossings. Explain how this property can be exploited for 2D shape description. What properties make such a representation suitable for classification and recognition of shapes? [5 marks] 3 (TURN OVER) CST.2011.9.4 3 Denotational Semantics (a) A PCF type is said to be finite (resp. infinite) if the domain [[ ]] is finite (resp. infinite). An element d of the domain [[ ]] is said to be definable whenever there exists a closed PCF term M : such that [[M]] = d. Indicate whether the following statements are true or false. Provide an argument for each answer. You may use standard results provided that you state them clearly. (i) For all finite PCF types , every element of the domain [[ ]] is definable. [5 marks] (ii) For all infinite PCF types , every element of the domain [[ ]] is definable. [5 marks] (b) Consider the following two statements for PCF terms M1 and M2 for which the typings ` M1 : and ` M2 : hold for some type environment and type . (1) For all PCF contexts C[] for which C[M1] : bool and C[M2] : bool, C[M1]bool C[M2]bool where, for M : , the notation M stands for the existence of a value V : for which M V . (2) For all PCF contexts C[] for which C[M1] : bool and C[M2] : bool, C[M1]bool true C[M2]bool true (i) Show that (1) implies (2). [5 marks] (ii) Define the notion of contextual equivalence in PCF and show that (2) implies that M1 and M2 are contextually equivalent. [5 marks] 4 CST.2011.9.5 4 Digital Signal Processing (a) Make the following statements correct by changing one word or number. (Negating the sentence is not sufficient.) (i) A square-summable sequence is also called power signal. [1 mark] (ii) Adding together sine waves of the same frequency always results in another sine wave of the same phase. [1 mark] (iii) The Fourier transform of a Dirac comb is a Dirac impulse. [1 mark] (iv) 60 dBm = 1 W [1 mark] (b) Before resampling a digital image at a quarter of its original resolution, you want to apply an anti-aliasing low-pass filter. (i) If you apply a 1-dimensional filter with impulse response {hn} both horizontally and vertically to image pixels Ix,y, what are the resulting filtered pixel values Ix,y? [4 marks] (ii) What would be the discrete impulse response {hn} of an ideal low-pass filter for this application, if its length were of no concern? [4 marks] (iii) You decide to truncate the impulse response {hn} at its second zerocrossing on each side, resulting in a new impulse response {h n}. In the frequency domain, this results in H = H T for what function T? [4 marks] (iv) In order to make the frequency-domain response of your filter {h n} smoother, you convolve it in the frequency domain with a rectangular pulse, the width of which is twice the distance between the zero crossings of T. What does the resulting time-domain impulse response {h n} look like? [4 marks] 5 (TURN OVER) CST.2011.9.6 5 Information Retrieval Consider the following text, which gives the input to three different information extraction systems dealing with texts about job succession events. Last Monday Sunny Simmers resigned his position as CEO of Sparkling Inc., the well-known cleaning supply manufacturer, following recent corruption allegations. This move has been expected for some time now. He is succeeded by his brother, Sandy Simmers. The tasks of the three systems are as follows: System 1 determines all person and organisation names. System 2 determines the employed-by relationship, which holds between employees and employers. System 3 fills templates about job successions, in the style of MUC templates (as in the following figure). START-JOB-EVENT Person: Position: Company: Start Date: END-JOB-EVENT Person: Position: Company: End Date: (a) For each system, give a description of how it could plausibly solve its task. What is the most difficult problem each system will encounter? Use examples from the text. [4 marks per system] (b) Define each of the following concepts, giving an example in the context of the above text if applicable: (i) sure-fire rule; [2 marks] (ii) lexico-semantic template; [2 marks] (iii) inference rule; [2 marks] (iv) template learning. [2 marks] 6 CST.2011.9.7 6 Mobile and Sensor Systems This question concerns Wireless Sensor Networks (WSNs). (a) Explain the advantages of using event-based concurrency versus traditional concurrency through processes. Also explain how TinyOS implements event-based concurrency. [4 marks] (b) In most WSNs, devices are battery operated and the use of the radio interface needs to be limited to preserve energy. Describe the salient characteristics of duty cycling through basic preamble sampling. [2 marks] (c) Describe XMAC and how it optimises over basic preamble sampling approaches. [3 marks] (d) Consider the WSN depicted in the picture below. Assume MintRoute is used as the routing protocol. Describe how MintRoute works and explain how the numbers on the edges in the network depicted below are generated by the protocol. What is the path that the packets would follow from source S to destination D if MintRoute were applied? A B C D E S 0.3 0.4 0.2 0.5 0.7 0.1 0.2 [5 marks] (e) Explain why wireless reprogramming is important in WSNs. Describe the sensor network reprogramming described in the lectures and explain the role of the parameters which govern its behaviour. Also, what are the limitations of the approach when applied to mobile sensor networks? [6 marks] 7 (TURN OVER) CST.2011.9.8 7 Natural Language Processing (a) Explain what is meant by subsumption and unification when applied to feature structures. [5 marks] (b) The feature structures below represent a grammar rule and two lexical entries. The rule is intended to allow for adjectival and adverbial modification in phrases such as big dog and suddenly jumps. Give lexical entries for big and suddenly and show how the rule applies when these phrases are parsed. [7 marks] modifier-modified rule: MOTHER 1 DTR1 h MOD 1 i DTR2 1 h OBJ filled i dog: HEAD CAT noun AGR sg OBJ filled SUBJ filled MOD filled jumps: HEAD CAT verb AGR sg OBJ filled SUBJ HEAD h CAT noun i MOD filled (c) In the verb-object rule discussed in the lectures, the value of the HEAD feature of the mother is reentrant with the HEAD feature of DTR1, MOTHER SUBJ is reentrant with DTR1 SUBJ, and DTR1 OBJ is reentrant with DTR2. Explain why the pattern of reentrancies in the modifier-modified rule differs from that of the verb-object rule. [6 marks] (d) Why is the value of DTR2 OBJ specified as filled in the modifier-modified rule? [2 marks] 8 CST.2011.9.9 8 Optimising Compilers (a) Explain what is meant by "instruction scheduling" in a compiler. Indicate what properties of architectures make it beneficial. Are some architectures too simple, or too complex, for it to be useful? [3 marks] (b) Sketch an algorithm that schedules instructions within a basic block for an architecture of your choice on which scheduling is useful. Indicate its time complexity O(f(n)) stating to what 'n' refers. What additional complications arise in choosing which instruction to emit first from a basic block? [5 marks] (c) Indicate how your algorithm could be modified to deal with a static multipleissue VLIW-style architecture. The input basic block contains simple instructions, but the output basic block contains wide instructions consisting of two simple instructions (either of which may be NOP). These two instructions execute in parallel. Now explain how your algorithm can schedule the following sequence of instructions to execute in parallel, or detail any adjustments necessary to permit this. st r1,4(r8) ld r2,0(r8) Explain how alias analysis or points-to analysis might provide information to the instruction scheduler to enable a wider range of load/store pairs to be re-scheduled. [6 marks] (d) Briefly summarise a source-level approach to alias or points-to analysis, for example Andersen's algorithm. Your summary should emphasise key choices, for example any data-structures used; detailed algorithms are not required. [6 marks] 9 (TURN OVER) CST.2011.9.10 9 Principles of Communications (a) Control Theory allows us to find various useful properties of a system such as stability. Draw a picture of a generic control system, explaining the functions of feedback and the design goals for the controller. [5 marks] (b) The Transmission Control Protocol of the Internet uses a feedback controller and responds to absence or presence of congestion signals by Additive Increase Multiplicative Decrease of a sending window. (i) Describe the operation of this scheme. [10 marks] (ii) Explain qualitatively why the scheme is necessary, but perhaps not sufficient, to create a stable set of traffic flows in the Internet. [5 marks] 10 System-on-Chip Design (a) What is an instruction set simulator (ISS) and what is typically the best way for it to achieve high performance? [2 marks] (b) What performance bottleneck can typically arise when CPU-intensive software is run on a model of a complete system on chip (SoC)? How can this be avoided and at what costs to modelling accuracy? [4 marks] (c) What problems can arise when operating system device drivers are run on an ISS that has been optimised according to your answers to parts (a) and (b) above? [4 marks] (d) Two processors on a SoC have separate address spaces. What does this mean? Describe a simple hardware mechanism for sending non-trivial amounts of data between processors in separate address spaces. Interrupts should be used. [4 marks] (e) Briefly describe both a high-level and a mid-level model of your answer to part (d) where the mid-level model requires minimal or no modification to the device driver firmware but is not a net-level model and where the high-level model dispenses with much of the device driver code and many or all of the interrupts. [3 marks each] 10 CST.2011.9.11 11 Temporal Logic and Model Checking (a) Explain the difference between static and dynamic methods for property checking. Is LTL or CTL a better property language for dynamic checking? Justify your answer. [4 marks] (b) Outline an algorithm for model checking LTL properties of the form G p, where p is an atomic property. [4 marks] (c) What is the difference between explicit state and symbolic model checking? [4 marks] (d) Who is the person credited with introducing temporal logic as a property specification language? What were the main contributions of Clarke & Emerson, and of McMillan, to model checking? Why were they significant? [4 marks] (e) Briefly explain the terms Boolean layer, Temporal layer, Verification layer and Modelling layer in connection with PSL. [4 marks] 12 Topical Issues (a) Describe the Binary Exponential Backoff (BEB) procedure found in 802.11 (WiFi) and explain why it is necessary. Give two shortcomings of the BEB approach. [4 marks] (b) Describe two modifications to the BEB algorithm that could be made by a malicious user attempting to increase their chances of gaining access to the wireless channel. At least one of your modifications, if used by all wireless stations, should enable the provision of Quality of Service and you should explain how it would do so. [6 marks] (c) Discuss the behaviour of the BEB procedure in heavily congested networks. Propose an alternative procedure, which may be based on BEB, that has improved behaviour in such networks. Take care to explain how it outperforms the default technique. Discuss how your solution behaves in lightly congested networks. [10 marks] 11 (TURN OVER) CST.2011.9.12 13 Topics in Concurrency This question concerns CTL, a variant of CTL in which assertions are of the form: A := T | A0 A1 | A0 A1 | A | hi A | hi A | AG A | EG A where ranges over action names. Recall that a path from state s is a maximal sequence of states = (0, 1, 2, . . .) such that s = 0 and i i+1 for all i. The logical connectives have the standard interpretation and T represents "true". The interpretation of the modalities is: s |= hi A iff there exists s 0 such that s s 0 and s 0 |= A s |= hi A iff there exists s 0 such that s s 0 and s 0 |= A s |= EG A iff for some path from s, we have i |= A for all i s |= AG A iff for all paths from s, we have i |= A for all i (a) What is the interpretation of the CTL modality E[A0 U A1]? How can it be used to express the CTL modality AG A? [4 marks] (b) Consider the following three formulae: A1 : AG hai T A2 : AG hbi T A3 : EG hbi T (i) For each of the following two transition systems, state which of A1, A2 and A3 are satisfied in the initial state. '&%$ !"# a : '&%$ !"# a : b d P1 : P2 : [4 marks] (ii) Draw a transition system with an initial state that satisfies A1 A2 A3. [3 marks] (c) Give a modal- formula that corresponds to the CTL formula AG hai T. [2 marks] (d) Let the function on sets of states of a transition system be defined as: (X) def = hai T hi X Show by induction on n 1 that s |= n() iff there exists m n and states s1, . . . , sm, s0 such that s = s1 . . . sm a s 0 Deduce that s |= X.hAi T hi X in a finite-state transition system if, and only if, s |= AG hai T. [7 marks] 12 CST.2011.9.13 14 Types Let x range over a set of identifiers and range over a set of type variables. Now suppose we have a set of types, , and a set of type schemes, , given by ::= | | list ::= 1, . . . , n ( ) and a language of terms, M, given by M ::= x | x (M) | M M | let x = M in M | nil | M :: M | case M of nil => M | x :: x => M (a) Define the relation of specialisation, , between types and type schemes . [3 marks] (b) Give the ML-like type inference rules for judgements of the form ` M : , and explain why -bound variables cannot be used polymorphically within a function abstraction, while let-bound variables can within a local declaration. Hint: Consider the terms f(f f) and let f = x(x) in f f. [8 marks] (c) Briefly explain what is meant by capture-avoiding substitution for type schemes. [2 marks] Cracking RSA is NP-complete so nothing better than brute force is possible. Your task is to evaluate to what extent (if any) this statement is true. For full marks, you will consider the following questions. What would it mean, precisely, for "cracking RSA" to be NP-complete? In particular, what is the decision problem involved and what is meant by saying it is NP-complete? Is the problem, in fact, NP-complete? Why or why not? What is meant, precisely, by the conclusion, "nothing better than brute force is possible"? Assuming the premise is correct, i.e. "cracking RSA is NP-complete", does the conclusion follow? Why or why not? What is the relationship, more generally, between encryption systems and NP-completeness? [20 marks] 2 CST.2011.6.3 2 Complexity Theory (a) Recall that a Boolean formula is in 3-CNF if it is the conjunction of clauses, each of which is the disjunction of at most three literals. A literal is either a variable or a negated variable. Consider the following two decision problems: 3-SAT: given a Boolean formula in 3-CNF, decide whether or not it is satisfiable. 3-VAL: given a Boolean formula in 3-CNF, decide whether or not it is valid. (i) One of the two problems above is known to be in the complexity class P. Which one, and why? [2 marks] (ii) Describe a polynomial time algorithm for the problem you identified in part (i). [6 marks] (iii) What can you say about the complexity of the other problem? State precisely any standard results you use in your answer. [4 marks] (b) Say that a Boolean formula is in 3-DNF if it is the disjunction of terms, each of which is the conjunction of at most three literals. We now consider the following two decision problems: 3-DNF-SAT: given a Boolean formula in 3-DNF, decide whether or not it is satisfiable. 3-DNF-VAL: given a Boolean formula in 3-DNF, decide whether or not it is valid. What can you conclude about the complexity of these two problems? [8 marks] 3 (TURN OVER) CST.2011.6.4 3 Computation Theory (a) Explain how we can associate a unique number dPe to each register machine program P. [5 marks] (b) Consider the following two partial functions S : N * N and T : N * N on the natural numbers. S(dPe) = ( n if the program P when started with 0 in all registers halts after n steps; 0 otherwise. T(dPe) = ( n if the program P when started with 0 in all registers halts after n steps; undefined otherwise. (i) Which, if any, of S and T is computable and which is uncomputable? [4 marks] (ii) Give full justification for your answers above. State carefully any standard results that you use. [11 marks] 4 Computation Theory (a) State precisely what it means for a function f : N k N to be primitive recursive, giving exact definitions for all operations you use. [5 marks] (b) State precisely what it means for a function f : N k N to be -definable. [5 marks] (c) For each of the following functions, show (using the definitions you gave) that it is primitive recursive and -definable. (i) The function square : N N given by square(x) = x 2 . [4 marks] (ii) The function fact : N N given by fact(x) = x!. [4 marks] (d) Give a definition of a function that is -definable but not primitive recursive. [2 marks] 4 CST.2011.6.5 5 Logic and Proof (a) Recently, automated theorem provers based on the saturation algorithm have become very powerful tools. (i) Exhibit a proof by resolution of the following formula in first-order logic. Include the conversion into a set of clauses and provide brief justification for each step of the proof. x(P(x) Q(x)) (yP(y) zQ(z)) [6 marks] (ii) Prove P(s(s(s(0)))) by linear resolution from the following assumptions: x((P(x) Q(x)) P(s(x))) x(P(x) Q(x)) P(0) [7 marks] (b) Binary decision diagrams (BDDs) can be used to represent formulae in propositional logic. Show the steps in the recursive construction of a BDD, ordered alphabetically, for the following formula: ((P Q) R) (Q R) [7 marks] 5 (TURN OVER) CST.2011.6.6 6 Logic and Proof (a) Unification is used to find a common instance of two terms. (i) Briefly explain the unification algorithm, outlining non-trivial cases. [4 marks] (ii) What is the importance of the occurs check in the unification algorithm? [2 marks] (iii) Find a most general unifier for each of the following three pairs of terms or explain why none exists. Do not rename variables prior to unification. j(a, z, f(x)) j(y, f(y), z) f(g(x, y), a, h(z)) f(z, x, y) f(g(x), y, x) f(z, f(z), a) [6 marks] (b) Prove or disprove the following sequent of S4 modal logic: A, B (A B) [8 marks] 6(d) Prove that for all , all and all substitutions for type schemes S, if holds, then also S( ) S(). Hint: Use the following property of simultaneous substitution: ( [1/1, . . . , n/n])[~ 0 /~0 ] = [~ 0 /~0 ][1[~ 0 /~0 ]/1, . . . , n[~ 0 /~0 ]/n] which holds, provided that for each i, i is distinct from the type variables ~0 , and i does not occur in type schemes ~0 . [7 marks] 6 Hoare Logic (a) What does it mean for a logic to be sound and to be complete? [4 marks] (b) Outline how Hoare logic can be proved sound. [4 marks] (c) What does it mean for Hoare logic to be relatively complete? [4 marks] (d) State conditions under which Hoare logic is relatively complete and outline the proof of completeness under these conditions. [8 marks] 5 (T