(a) How does the use of condition codes complicate the implementation of a superscalar processor that supports out-of-order execution? [4 marks] (b) A branch predictor with a high prediction accuracy is often employed to enable deeply pipelined processors to be exploited. What limits the complexity and size of such a branch predictor? [4 marks] (c) In the best case, how can a branch predictor and branch target buffer enable a branch instruction and the instruction at the branch's target address to be fetched in consecutive clock cycles? [6 marks] (d) Loop unrolling and predicated execution are two techniques that may be used to improve the performance of loops. (i) How do these techniques improve performance? [3 marks] (ii) What costs or disadvantages are associated with each technique? [3 marks] 3 (TURN OVER) CST.2009.8.4 3 Computer Systems Modelling (a) Suppose that X is a random variable having the Binomial distribution with parameters n and p and that > 0 is a constant. (i) Write down the expression for P(X = k) where k {0, 1, 2, . . . , n} [2 marks] (ii) Now suppose that n and p is chosen so that p = /n. Show that under this limit P(X = k) e k /k!, that is, to a Poisson distribution with parameter . [4 marks] (b) Suppose that N(t) is the random number of events in the time interval [0, t] of a Poisson process with parameter . (i) State the conditions that define the Poisson process N(t). [2 marks] (ii) Show that for all t > 0 the random variable N(t) has the Poisson distribution with parameter t. [4 marks] (c) Given a Poisson process of rate let X1 be the time of the first event and for n > 1 let Xn denote the time between the events (n 1) and n. Thus the sequence X1, X2, . . . gives us the sequence of inter-event times between the events in a Poisson process. (i) Show that P(X1 > t) = P(N(t) = 0) for t > 0. [4 marks] (ii) Show that the inter-event times X1, X2, . . . are independent, identically distributed random variables each of whose marginal distribution is an Exponential with rate parameteat mammalian brains send almost ten times as many neural fibres back down the visual pathway (from cortex to thalamus), as there are ascending neural fibres bringing visual data from the retina up to the thalamus and cortex. Does this massive neural feedback projection support the thesis of "vision as hypothesis testing," and if so, how? Try to marshall other evidence supporting the view that in human vision "what you see is your own graphics" rather than the retinal image as faithfully recorded by photoreceptors in the eye. [5 marks] (b) Write a block of pseudo-code for convolving an image with a feature-detecting kernel. (You may ignore out-of-bounds issues at the image array boundaries.) [3 marks] (c) The Differentiation Theorem of Fourier analysis asserts that, for an image f(x, y) whose 2D Fourier Transform (2DFT) is F(, ), taking derivatives of various orders m, n has the following spectral consequence: xm y n f(x, y) 2DF T = (i) m(i) n F(, ) In particular when the 2nd-derivative Laplacian operator 2 is applied to an image, its action is to multiply the Fourier transform of the image by a paraboloid: 2 f(x, y) 2 x2 + 2 y2 f(x, y) 2DF T = ( 2 + 2 )F(, ) What therefore best describes the filtering operation that corresponds to taking derivatives of an image: lowpass, bandpass, or highpass? If noise in an image resides mainly in the higher spatial frequencies, should you use higher or lower order derivatives for edge detection to be less sensitive to the noise? What else could you do with differentiating filters to reduce their noise sensitivity? [3 marks] (d) In pattern classification with two classes, explain how an ROC curve is derived from the underlying distributions. Define a threshold-independent performance metric based on the distributions' moments. [4 marks] (e) When visually inferring a 3D representation of a face, it is useful to extract separately both a shape model, and a texture model. Explain the purposes of these steps, their use in morphable models for pose-invariant face recognition, and how the shape and texture models are extracted and later re-combined. [5 marks] 5 (TURN OVER) CST.2009.8.6 5 Digital Communication II (a) Shared media networks make use of Media Access Control protocols to allocate resources. (i) Outline the use of CSMA/CD on Ethernets. [5 marks] (ii) Outline the use of CSMA/CA on Wireless Ethernets. [5 marks] (b) Discuss the trade-offs between network resource pre-allocation and network resource contention-based schemes in terms of delays and throughput under varying traffic loads. [10 marks] 6 Digital Signal Processing While reverse-engineering a radio receiver, you find in its firmware the following two discrete systems implemented: yn := xne jn/2 zn := 4000 X k=4000 ynk4000 103 sinc(k/103 ) 0.54 0.46 cos 2 k + 4000 8000 The discrete sequence {xn} emerges from an analog-to-digital converter operating at sampling frequency fs = 240 kHz, whose input is connected via a 100 kHz low-pass filter and linear amplifier directly to a radio antenna. (a) Explain the function of both discrete systems in the frequency domain and their main parameters (e.g. type of filter, cutoff frequency, type of window). [12 marks] (b) In approximately which frequency range will antenna signals substantially influence the resulting sequence {zn}? [4 marks] (c) Will the subsequent application of the discrete system bn := z500n cause aliasing, and why? [4 marks] 6 CST.2009.8.7 7 Types (a) Explain what is meant by a solution for a Mini-ML typing problem ` M : ? and what it means for a solution to be principal. [4 marks] (b) Consider the following typing problems (where and are distinct type variables). (i) x : {}( ) ` x (x nil) : ? (ii) x : {}( ) ` x (x nil) : ? (iii) x : {}( list) ` x :: (x nil) : ? (iv) x : {}( list) ` x :: (x nil) : ? For each typing problem, either give a solution together with a proof of typing, or show that no solution exists. [16 marks] 8 E-Commerce It is said that the Internet played a significant role in the US presidential election. You are asked by a major UK political party to advise them on their Internet policy and associated website. The party has about 200,000 members, each paying a fee of 25 per annum. Its total annual income, mainly from donations, is about 20M. The UK has about 46 million people registered to vote. There are about 646 parliamentary constituencies. (a) Describe in brief bullet points the key elements of your proposed Internet strategy. [5 marks] (b) Draw an outline block diagram of the architecture that would be needed. [5 marks] (c) Make and justify some estimates of the size and cost for its implementation. [5 marks] (d) Outline relevant regulations. [5 marks] 7 (TURN OVER) CST.2009.8.8 9 Information Retrieval The PageRank R of a webpage u is defined as: R(u) = (1 q) + q X vBu R(v) Nv Here, Bu is the set of pages that points to u, Nu is the number of pages that u points to, and q is the probability of staying locally on the webpage. (a) Explain the concept of PageRank, and how it is calculated. [4 marks] (b) Why is it relevant for web search? [3 marks] (c) Give, and briefly explain, the corresponding matrix notation of the PageRank computation. [3 marks] (d) Give the linkage matrix A of the network given in the diagram below. [5 marks] V W X Y Z (e) Show the final matrix that will be subjected to the PageRank calculation, if q = 0.8 is used. [5 marks] 8 CST.2009.8.9 10 Natural Language Processing (a) Give brief definitions of the following terms. Illustrate the definitions with examples. (i) hyponymy (ii) meronymy (iii) antonymy [2 marks each] (b) Describe Yarowsky's (1995) technique for word sense disambiguation and illustrate how it would disambiguate the following two senses of "sake": Sense 1: sake, interest (a reason for wanting something done: "for your sake", "died for the sake of his country") Sense 2: sake, saki, rice beer (Japanese alcoholic beverage made from fermented rice, usually served hot) [14 marks] 11 Security (a) Give four uses of anonymous communications other than censorship resistance. [4 marks] (b) Explain the role of latency in anonymous communications. What limits or costs does low latency impose? [4 marks] (c) Imagine you are a government censor, trying to identify which of your citizens are viewing forbidden websites through Tor.

(a) Define the Church numerals giving the encodings of zero 0, one 1 and an arbitrary number n. [3 marks] (b) Define -terms to perform the following operations on Church numerals. You may assume standard definitions for Booleans (true, false, if, and, and or) and pairs (pair, fst, and snd). For each part, you may assume solutions to the previous parts of the question. You may not use a fixed-point combinator. (i) Test for zero. [2 marks] (ii) Successor. [2 marks] (iii) Predecessor (where predecessor of zero is zero). [4 marks] (iv) Less than or equal. [3 marks] (v) Equality. [2 marks] (vi) Successor modulus n (where succn n m = 0 if n = m + 1, and succn n m = m + 1 otherwise). [2 marks] (vii)Modulus (e.g mod n m = m mod n). [2 marks] 5 (TURN OVER) CST.2009.6.6 6 Foundations of Functional Programming (a) Define what it means for a -calculus term to be in normal form. Is it possible for a -term to have two normal forms that are not -equivalent? Provide justification for your answer. [3 marks] (b) For each of the following, give an example of a -term that (i) is in normal form; (ii) is not in normal form but has a normal form; and (iii) does not have a normal form. For (ii), you should also present the term's normal form, and for (iii) you should show that the term does not have a normal form. [4 marks] We define a -term N to be non-trivial iff there exist A and B such that N A true and N B false, where true and false encode the Booleans. (c) Give an example of a -term that is non-trivial, and show that it is non-trivial. [2 marks] We define a -term N as total iff for each -term M, either N M true or N M false (d) Give an example of a -term that is total, and show that it is total. [2 marks] (e) Prove that there is no non-trivial and total -term. [Hint: Suppose N is non-trivial and total where N A true and N B false, and consider the term N(Y L) where L (x. if (N x) B A) and where Y is the fixed-point operator.] [7 marks] (f ) What consequences does this have for defining a general equality -term such that equal A B true if A = B equal A B false otherwise [2 marks] 6 CST.2009.6.7 7 Logic and Proof (a) What is an S4 modal frame? [2 marks] (b) For each of the following formulae of S4 modal logic, present either a sequent calculus proof or a falsifying interpretation. (i) ((P Q) P) Q [6 marks] (ii) (P Q) (P Q) [6 marks] (iii) (P Q) (P Q) [6 marks] 8 Logic and Proof (a) Briefly indicate the differences between the tableau calculus and the sequent calculus. [2 marks] (b) Prove the formula [x (P(x) R(x, x))] [x y (R(x, y)P(y))] using the tableau calculus, or exhibit a falsifying interpretation. [8 marks] (c) Give a model for the following set of clauses, or prove that none exists. Here a is a constant, while x and y are variables. Explain your reasoning clearly. {R(x, a), R(x, x)} {R(x, x), R(x, a)} {R(y, f(x)), R(y, x)} {R(y, x), R(y, f(x))} [10 marks] 7 (TURN OVER)

Compute the latency of the shortest path between each pair of end-nodes: A to B, A to C, and C to B. [3 marks] (iii) Without changing the network propose a solution to decrease the delay between A and B. [2 marks] 7 (TURN OVER) CST.2014.5.8 6 Computer Networking (a) Consider an unreliable message service where messages of a fixed size are sent between known endpoints. Outline the minimum set of additional features offered by a reliable byte-stream delivery service. [3 marks] (b) A researcher notes that the message service, fritter, resembles a datagram service. It is prone to delivery delays of up to 1 second, message re-ordering and message loss. Fritter permits a 140-byte message to be relayed between any two users and each message is delivered without data-corruption. You are asked to implement a Stop-and-wait ARQ to provide a unidirectional reliable byte-stream delivery service between two fritter users. Assume this is the only service between the two fritter users. (i) Provide a labelled diagram illustrating the format for a fritter message that could be used by a reliable, byte-stream, delivery service. Justify your answer. [3 marks] (ii) Draw and label the Finite State Machine that implements the sender portion of the Stop-and-wait ARQ. Your function will be called as reliable send() while the fritter message receive and message send functions are fritter rcv() and fritter send() respectively. You may assume that the argument to the reliable send() function does not exceed 100 bytes per function call. [8 marks] (iii) Users assert that the performance using your Stop-and-wait ARQ is terrible for large transfers. Explain why they are correct. [2 marks] (iv) Describe an appropriate enhancement to the ARQ that will improve performance. Given the constraints of a small fritter message size, justify why your particular ARQ enhancement is best suited to the fritter application. [4 marks] 8 CST.2014.5.9 7 Concurrent and Distributed Systems Correct handling of time is critical to the correctness (and performance) of distributed systems such as network file systems and databases. Consider the following two approaches. (a) Physical clock synchronisation (i) Define clock skew and clock drift. [2 marks] (ii) A client running Cristian's Algorithm observes a local clock time of 1399157100.00s at the start of its RPC, and 1399157100.10s at the end of its RPC. The RPC returns a server timestamp of 1399157100.05s. What client-server clock skew will the algorithm calculate? Justify your answer. [2 marks] (iii) Using Cristian's Algorithm as the underlying primitive, propose a time synchronisation algorithm that measures and compensates for clock drift. [2 marks] (b) Distributed logical clocks The make build tool relies on file-system timestamps to determine whether an object file is older than a source file: if so, the object file is rebuilt; if not, then a rebuild is avoided. However, it is common practice to store source code in a distributed file system and object files in a local temporary directory. The Network File System (NFS) stores file creation and modification times based on the server clock, whereas the local file system uses a local clock. (i) Describe the two failure modes make may experience if client and server clocks are out of sync. [2 marks] (ii) One solution is to use NTP to synchronise client and server clocks. Describe two reasons why this might work poorly in practice. [2 marks] (iii) The NFS developers decide that Lamport Clocks may be able to solve the problem, as they track the happens-before relationship. During a particular run, make finds a source logical timestamp s is less than the object logical timestamp o. Explain why it is problematic to use Lamport Clocks to conclude that the object file should not be recompiled. [4 marks] (iv) Explain why Vector Clocks might be more suitable than Lamport Clocks for this problem. [2 marks] (v) Explain what a Vector-Clock-based make should do if there is no defined happens-before relationship between source vector s and object vector o. [4 marks] 9 (TURN OVER) CST.2014.5.10 8 Concurrent and Distributed Systems (a) Monitors are a programming primitive linking data with two synchronization types: mutual exclusion and condition synchronisation. Which is provided implicitly; which is provided explicitly? [1 mark] (b) Describe two ways in which Monitors and Conditional Critical Regions differ. [2 marks] (c) The object-oriented programming style encouraged by Monitors has many benefits as the number of data types and locks increases in the system. (i) Placing all data in a single Monitor may improve program correctness. Explain why this might have undesirable performance effects. [1 mark] (ii) One problem that can arise when using multiple locks is deadlock, which can be prevented by imposing a partial order on locks. Describe the implications this has for code structure when using Monitors. [2 marks] (iii) Explain why Java's Monitor feature does not necessarily impose this code structure. [2 marks] (d) Condition variables allow condition satisfaction to be signalled between threads. Explain the difference between Hoare's signal-and-wait and Mesa's signal-andcontinue in terms of mutual exclusion and scheduling. [4 marks] (e) Consider the (incorrect) pseudocode on the next page: (i) Describe and justify minimal modifications to this code, referencing line numbers, in order to make it correct in the presence of Hoare signal-and-wait semantics. [4 marks] (ii) Describe and justify minimal modifications to this code, referencing line numbers, in order to make it correct in the presence of Mesa signal-and-continue semantics