H4

class C is derived from class B (which is derived from base class A).

The obj object of class C is defined in the main() function.

When the display() function is called, display() in class A is executed. It's because there is no display() function in class C and class B.

The compiler first looks for the display() function in class C. Since the function doesn't exist there, it looks for the function in class B (as C is derived from B).

The function also doesn't exist in class B, so the compiler looks for it in class A (as B is derived from A).

If display() function exists in C, the compiler overrides display() of class A (because of member function overriding).

) In early stages of machine vision systems, the isotropic operator shown on the right is often applied to an image I(x, y) in the following way: [2G(x, y)] I(x, y). What is the purpose of this operation? Which class of neurones in the retina does it mimic? How would the results differ if instead this operation: G(x, y) 2 I(x, y) were performed; or alternatively if this operation: 2 [G(x, y) I(x, y)] were performed? [6 marks] (b) Computer vision colour space is usually three-dimensional, just because human vision is tri-chromatic and therefore cameras are designed with three colour planes. But suppose we added a fourth colour plane, say yellow (Y), to the standard red, green, and blue (RGB) bands. Considering that these are linearly independent but not orthogonal vectors, what would be the added capability of RGBY space? What tests would reveal it? Present a version of the Retinex algorithm for RGBY space, explaining the purpose of each step in the algorithm. [8 marks] (c) Visual inference of surface shape depends on assumptions and prior knowledge, such as "faces are mostly convex". Explain the "rotating hollow mask illusion". Why does a face mask (as pictured below) appear to reverse its direction of rotation, once it is seen from the inside instead of the outside? What is the role of Bayesian inference when interpreting a face-like surface that is actually concave in presentation instead of convex? Should visual illusions like this be considered "features" or "bugs", and should one try to design them in to a computer vision system? [6 marks] Cryptography (a) (i) Choose and briefly describe one major application of elliptic-curve group operations in cryptography. [4 marks] (ii) What other group operation was previously (and still is) widely used for the same purpose? [2 marks] (iii) What is a major advantage of elliptic curve group operations over the group operation you named in Part (a)(ii)? [4 marks] (b) In the Galois field GF(28 ) modulo x 8 + x 4 + x 3 + x 2 + 1, calculate (i) the sum 0011 1001 plus 0110 1100; [2 marks] (ii) the product 0100 1011 times 0000 1001. [4 marks] (c) In Lamport's one-time password scheme, the user is given a list of passwords Rn, . . . , R0 generated using the following algorithm: R0 random for i := 1 to n Ri := h(Ri1) (i) State two properties required of function h. [2 marks] (ii) Complete the password verification algorithm implemented in the server by filling in the ellipses (...) below: Q := . . . while true P := read password if . . . . . . grant access else deny access [2 marks] Denotational Semantics (a) Suppose that (D, v) is a poset which is chain-complete but does not have a least element, and that f : D D is a continuous function. (i) Give an example of such (D, v) and f for which f has no fixed point. [1 mark] (ii) If d D satisfies d v f(d), prove that there is a least element e D satisfying d v e = f(e). [Hint: consider the method used to prove Tarski's fixed point theorem.] [7 marks] (b) (i) Define the notion of contextual equivalence for the language PCF. (You need not describe the syntax and semantics of PCF.) [2 marks] (ii) State the compositionality, soundness and adequacy properties of the denotational semantics of PCF. Explain why they imply that any two closed PCF terms of the same type with equal denotations are contextually equivalent. [8 marks] (iii) Give, without proof, an example of two contextually equivalent PCF terms that have unequal denotation. [2 marks] Hoare Logic and Model Checking This question is about modelling a program, defined below, consisting of two threads and a single (mathematical) integer variable X, initially set to 0. Each thread t has its own program counter given by pct , initially set to 0, which describes the current line for that thread. Thread 1 Thread 2 0: X := X+1 0: IF IS ODD(X) THEN STOP ALL 1: GOTO 0 1: GOTO 0 The program is executed by repeatedly carrying out execution steps, where one thread is non-deterministically selected, its entire current line is run, and its program counter is then updated appropriately. This continues until STOP ALL is executed, which immediately terminates the whole program. (a) The program state can be described by (pc1, pc2, X, stopped), where pc1, pc2, and X are mathematical integers, and stopped is a boolean which is true iff STOP ALL has been executed. Let S be the set of all such states. (i) Define S0, the set of initial states of the program, such that S0 S. [1 mark] (ii) Define a transition relation R S S describing the program's execution. [2 marks] (iii) Define a labelling function L that labels all states where the program has terminated with the atomic property term. [2 marks] (b) Explain why, taking the definitions from (a), the model Ma = (S, S0, R, L) is not a (finite) Kripke structure. [2 marks] (c) Draw the finite state automaton for a model Mb which is a Kripke structure, such that Ma and Mb are bisimilar. Justify your answer briefly. [Note: A full formal proof of bisimilarity is not required.] [5 marks] (d) (i) Give an LTL formula such that the judgement Mb corresponds to the statement "every execution of the program will eventually terminate". [2 marks] (ii) Either prove that Mb holds, or describe a counter-example trace. [2 marks] (e) Consider the CTL formula = AG(EF term). Determine whether this is equivalent to your definition of from Part (d). and are equivalent iff, for all Kripke structures M, (M ) iff (M ). Justify your answer. [4 marks] Information Theory (a) If I pick a number n that can be any integer from 1 to whose probability distribution of being selected is ( 1 2 ) n , and you ask a series of 'yes/no' questions which I will answer truthfully, how many such 'yes/no' questions should you expect to ask before discovering which number I have picked? Justify your answer by invoking a known series limit. What sequence of questions would be the most efficient to ask, and why? [4 marks] (b) An inner product space containing complex functions f(x) and g(x) is spanned by a set of orthonormal basis functions {ei}. Complex coefficients {i} and {i} therefore exist such that f(x) = X i iei(x) and g(x) = X i iei(x). Show that the inner product hf, gi = X i ii . [4 marks] (c) Consider a data sequence f[n] (n = 0, 1, . . . , 15) having Fourier coefficients F[k] (k = 0, 1, . . . , 15). Using the 16th roots of unity labelled around the unit circle as powers of w1

(e) A continuous signal f(t) has Fourier transform F(). Explain why computing derivatives of f(t) such as f 0 (t) or f 00(t) amounts simply to high-pass filtering. For the n th derivative f (n) (t), what exactly is this filtering operation when expressed in terms of F()? Show how this operation could be used to define derivatives of non-integer order (for example the 1.5 th derivative). [4 marks] Mobile and Sensor Systems A mobile phone software developer is programming her own behaviour tracking app and she wants to make it suitable for use in areas with intermittent and low bandwidth cellular connectivity. (a) Explain the precautions the developer can take to make the app work well in this environment. Describe examples of mechanisms which can help with this. [5 marks] (b) The app uses various sensors to monitor user activity and its surrounding environment. In particular, it uses the microphone to monitor location ambience (surrounding sounds). Describe a suitable machine learning approach and discuss system considerations. [6 marks] (c) Describe how the developer can use location data to provide mobility prediction and how mutual information can improve the mobility prediction algorithm. [4 marks] (d) A very able user wants to test the app for privacy leaks before using it on their own phone. What techniques can be used? Illustrate each technique's specific purpose and the assumptions it is predicated on. [5 marks] 11 Optimising Compilers (a) Describe the phase-order problem in a compiler and illustrate your answer with some example code. [4 marks] (b) You are advising a semiconductor design company on building a compiler for their latest processor. The processor has the following features: Sixteen 64-bit registers (r0-r15) and sixteen 32-bit registers (s0-s15), the latter corresponding to the lower 32 bits of each of the 64-bit registers. A one-cycle branch delay slot after each control-transfer instruction (i.e. the instruction after a branch is executed before the branch takes effect). Complex arithmetic instructions that implicitly use r15 as their first source operand. What are the challenges of code generation for this processor, given these features and how can they be addressed within the compiler? [8 marks] (c) To ease compilation, the chief designer suggests that the processor's instructions could be executed directly in SSA form (i.e. all destination registers unique). This would use a small cache to provide fast access to the most recently used virtual registers. Discuss the advantages and disadvantages of such an approach from the compiler writer's viewpoint. [8 marks]