Suppose that there are three states of the world, a, b, and c. The probabilities of the three states are 1 = 0.25, 2 = 0.5, and 3 = 0.25. Let A, B, and C denote the Arrow-Debreu securities that pay $1 in states a, b, and c, respectively. That is, A = (1,0,0), B = (0,1,0) and C = (0,0,1). Let pA = 0.4, pB = 0.5 and pC = 0.2 denote the prices of A, B, and C.

Consider a security X which is worth $2 in state a, $3 in state b, and $1 in state c. If there are liquid markets for A, B, C and X, what is the price of X?

The current price of a non-dividend paying stock is 40 and the continuously compounded risk-free interest rate is 8%. You are given that the price of a 35-strike call option is 3.35 higher than the price of a 40-strike call option, where both options expire in 3 months. Calculate the amount by which the price of an otherwise equivalent 40-strike put option exceeds the price of an otherwise equivalent 35-strike put option.

Stock XYZ has a current price of 100. The forward price for delivery of this stock in 1 year is 110. Unless otherwise indicated, the stock pays no dividends and the annual effective risk-free interest rate is 10%. Determine which of the following statements is FALSE. (A) The time-1 profit diagram and the time-1 payoff diagram for long positions in this forward contract are identical. (B) The time-1 profit for a long position in this forward contract is exactly opposite to the time-1 profit for the corresponding short forward position. (C) There is no comparative advantage to investing in the stock versus investing in the forward contract. (D) If the 10% interest rate was continuously compounded instead of annual effective, then it would be more beneficial to invest in the stock, rather than the forward contract. (E) If there was a dividend of 3.00 paid 6 months from now, then it would be more beneficial to invest in the stock, rather than the forward contract.

(a) Describe the time and space complexity for finding the global alignment between two DNA sequences when they are very similar. (b) Describe how match, mismatch and gap penalty (initiation and elongation) affect the score in global sequence alignment. (c) Describe, with one example, how the number of mutations affects the phylogenetic analysis using the distance algorithm. [4 marks] (d) Describe the differences in algorithmic complexity between the distance and parsimony phylogenetic methods. [4 marks] (e) Describe why the Viterbi algorithm can help identify protein structural parts (alpha helix, beta sheet, coil) in a sequence of amino acids and describe how it works. [4 marks] 3 Comparative Architectures (a) (i) For each of the processors described below outline a possible microarchitecture. Include a labelled block diagram that illustrates the main components of the core pipeline and how they are interconnected. Individual pipeline stages should be shown with a brief description of their contents. (A) A simple superscalar processor with a short pipeline. It can fetch and issue up to two instructions per cycle and instructions are issued in program order. [4 marks] (B) A high-performance superscalar processor that supports out-of-order execution. It is able to fetch and issue up to 6 instructions per cycle. It has a deep pipeline and aims to support a high clock frequency. [6 marks] (ii) In practice, the area of these types of processor may differ by a factor of five or more. What contributes to this large difference in area? [5 marks] (b) An indirect branch may have multiple target addresses associated with it. Why is this problematic for a simple Branch Target Buffer (BTB) design? [2 marks] (c) If indirect branches favour a particular branch target, and only infrequently branch to other targets, how might the design of the BTB be optimised? [3 marks] 3 (TURN OVER) CST2.2020.8.4 4 Computer Vision (a) Neural receptive fields used in early stages of vision can be regarded as linear integro-differential operators of the first- and second-orders, represented by the elongated ovals within the diagram below. Explain how they can be used for oriented edge detection, and also state the basis for a Fourier interpretation of them as anisotropic bandpass filters. Explain how combining their outputs by the nonlinear operations depicted in the rest of this diagram (sum-of-squares, and response ratio) can be used for higher-level feature detection. [8 marks] 2D Gabor Phasor Modules \ Projected Image I( x, y) . . . . . . (b) In self-driving cars, the following acronyms are names for automated vision systems. Define them and briefly describe how they work. (i) LIDAR [3 marks] (ii) SLAM [3 marks] (c) Discuss the use of texture gradients as a depth cue in computer vision. How can texture gradients be measured? What prior assumptions are needed to make computations about depth and shape possible? You may find it helpful to refer to the following texture examples. [6 marks] 8a. Structure from texture I Most surfaces are covered with texture, of one sort or another I Texture is both an identifying feature, and a cue to surface shape I If one can assume uniform statistics along the surface itself, then textural foreshortening or stretching reveals 3D surface shape I As implied by its root, linking it with (woven) textiles, texture is defined by the existence of statistical correlations across the image I From grasslands to textiles, the unifying notion is quasi-periodicity I Variations from uniform periodicity reveal 3D shape, slant, distance - -- .- ._.- c-'.- ->- C c._ .l-f L I 102 / 212 4 CST2.2020.8.5 5 Cryptography (a) (i) One way to use a secure hash function H to form a message-authentication code is the construct MacK(M) = H(KkM). What problem with that approach does the HMAC construct solve? [4 marks] (ii) Why does the HMAC construct pad the key?

HearMe Ltd. has put a new wearable for the ear (earable) on the market that, in addition to other sensors, has an accelerometer. The company is hoping to use the accelerometer to analyze human activity recognition (HAR) of the users. (a) What are the challenges the company will face in collecting the accelerometer data for human activity recognition (on their servers)? [5 marks] (b) What are the steps of the HAR pipeline (you should also discuss person dependent/independent aspects)? Please use examples only related to accelerometer sensing. [5 marks] (c) What are the limitations of applying Deep Learning to HAR data for analysis and how can they be obviated? [5 marks] (d) The company would like to be able to perform HAR on-device on the earable. However, the current model running on the servers does not fit in its processor. What techniques can be applied to the model to make it run on the device efficiently and indicate in which way each helps? [5 marks] 10 CST2.2020.8.11 12 Optimising Compilers (a) Describe inference-based program analysis on expressions e. Explain how it can be used to judge effect systems. [3 marks] (b) Give inference rules and a set of effects for an effect system for the following language: e ::= x | x.e | e1e2 | if e1 then e2 else e3 | O().e | W(e1).e2 | C().e where O().e opens file and results in the value of e, W(e1).e2 evaluates e1 and writes its (integer) value to file before resulting in the value of e2, and C().e closes file before resulting in the value of e. The language types are integers and functions. [4 marks] (c) Give and explain the safety condition for this system. [3 marks] (d) Show how the rules from Part (b) assign a type and effect(s) to the following expression. O().if x then x.W(x).C().x else x.C().x [5 marks] (e) Justify that the effect system will allow us to identify all expressions with incorrect use of files or, using an example, describe why it won't and show how to alter the effect system so that it will allow us to. [5 marks] 13 Principles of Communications (a) Briefly describe link-state routing, outlining the link-state advertisement and the shortest path computation that each node carries out. [5 marks] (b) Fibbing is a technique for injecting link-state advertisements to the routing system that provides a way to add alternate paths into the results of the route computation. Describe what this is for, how this operates and what security implications it has. [15 marks] 11 (TURN OVER) CST2.2020.8.12 14 Quantum Computing (a) In the superdense coding protocol, Alice and Bob each have one qubit from the entangled pair 1 2 (|00i + |11i), which enables Alice to send two bits of classical information to Bob, using a single qubit. Explain the superdense coding protocol in detail, and show that it does indeed enable the transmission of two bits using a single qubit. [10 marks] (b) This question concerns entangled states. (i) Suppose Alice transmits the two-bit string '00' using the superdense coding protocol and an evesdropper, Eve, intercepts the qubit transmitted by Alice, measures it in the computational basis and then re-transmits to Bob. Find the probability that Bob correctly receives '00'. [5 marks] (ii) Suppose further that prior to Eve's interception there is a 50% probability that the qubit experiences a bit-flip. What is the probability that Bob correctly receives 00? (Note that after Eve's retransmission no errors occur)

You have been asked to implement a user-interface component ButtonCanvas which is both a button that can be clicked by the user and a canvas which the user can draw on. Your existing code contains a Button class and a Canvas class. Both of these extend GuiComponent. (a) ButtonCanvas could be built using multiple inheritance. What does this mean in this context? [2 marks] (b) Give two reasons why this might be desirable. [2 marks] (c) Give two complexities that arise in this case. [2 marks] (d) Java interfaces originally contained only abstract methods and static final fields. How did this restriction avoid the complexities of extending multiple classes? (e) Draw a UML diagram for building ButtonCanvas using abstract interfaces rather than multiple inheritance. Explain how your design attempts to preserve the desirable properties arising from multiple inheritance. You do not need to recall the exact UML specification, instead you may provide a key explaining your notation. [9 marks] (f ) Recent versions of Java added default methods to interfaces. What is the impact of this with respect to multiple inheritance? [2 marks] 4 CST0.2020.1.5 4 Object-Oriented Programming (a) Describe the differences between primitive types and objects in Java. Consider: (i) the values they contain [1 mark] (ii) where they are stored in memory [1 mark] (iii) how they interact with Java references [1 mark] (b) What are auto-boxing and auto-unboxing? Give an example of how they might cause an exception to be thrown. [4 marks] (c) Consider the following code in which any arbitrary Java type (primitive or object) could be substituted for T. void f(T t) { /* ... */ } T t1 = /* ... */ f(t1); For which substitutions of T can we guarantee that the value in t1 is unchanged after the invocation of f(t1)? Justify your answer. [3 marks] (d) Explain how Java's implementation of generics precludes substituting T with a primitive type. [2 marks] (e) You are asked to redesign the standard library to incorporate an immutable list. Explain the relative merits of: (i) MutableList being a subtype of ImmutableList [2 marks] (ii) ImmutableList being a subtype of MutableList [2 marks] (iii) ImmutableList and MutableList having no common supertype [2 marks] (iv) ImmutableList and MutableList both subtyping CommonList [2 marks] 5 (TURN OVER) CST0.2020.1.6 SECTION C 5 Introduction to Probability (a) You are looking forward to the European Cup 2020. The tournament is going to last for 30 days. Each day during the tournament, you want to invite all of your 100 classmates to your house. But people might be busy on any given day, so you expect each classmate to come with probability 0.03 on each day, and they show up independently of one another. Let X denote the number of classmates that show up on any given day. Note: In parts (ii), (iii) and (iv) you do not have to compute explicit numerical values. (i) Give the exact and approximate distributions of X along with parameters. Explain why the approximation is valid. [3 marks] (ii) What is the approximate probability that between 2 and 4 classmates, inclusive, show up on any given day? [3 marks] (iii) What is the exact probability that at least 2 classmates show up on any given day? [3 marks] (iv) What is the probability that there will be more than 27 days where at least 2 classmates show up? [3 marks] (b) Suppose that each classmate is asked to arrive at 8pm, but the actual arrival time differs in minutes by a continuous uniform distribution [, +], where is an unknown parameter. Your data set Y1, Y2, . . . , Yk is a realisation of independent random samples from that distribution, for some integer k 1. (i) Show that T = 3 k (Y 2 1 + Y 2 2 + + Y 2 k ) is an unbiased estimator for 2 . [3 marks] (ii) Is T also an unbiased estimator for ? [1 mark] (iii) Justify your answer in (b)(ii). [4 marks] 6 CST0.2020.1.7 6 Introduction to Probability (a) Give the probability mass function of each of the three distributions: (i) Poisson distribution, [2 marks] (ii) Bernoulli distribution, [2 marks] (iii) Binomial distribution. [2 marks] (b) The football association has asked you to analyse the England team football matches from previous big tournaments. For each of the three situations below, choose a suitable distribution and compute its expectation and variance. Note: In Part (b)(ii) you do not have to compute explicit numerical values. (i) You analyse 2000 penalty kicks from the last 10 years of big tournaments. It turns out that 1200 of those 2000 penalty kicks were goals. A penalty kick is chosen at random. Let X be a success if a goal is scored. [2 marks] (ii) Consider again the setting from (b)(i). If you pick 50 penalty kicks without replacement, let Y be the number of missed goals out of that sample. [2 marks] (iii) Taking into account all games from the last 10 years of big tournaments, the England football team scored an average of 1 goal every 30 minutes. Let Z be the number of scored goals during a match of 90 minutes.