/\As part of the derivation of the full learning algorithm we find that the function f might be expressible in terms of m new parameters i as f1,...,m,w0 (x) = Xm i=1 yiiK(xi , x) + w0. (2) Explain the purpose of K in Equation 2 and explain why its use might be beneficial. [3 marks] (e) Your boss can not afford to provide you with a solver capable of training your system using the algorithm in Parts (c) and (d). Your boss does however provide you with a solver for linear programs. For a matrix A and vectors b and c, this solves problems of the form Find x minimizing b T x with constraints Ax c and x 0. Suggest a way in which you could use this optimizer to (approximately) train your system. [8 marks] 11 (TURN OVER) CST2.2018.7.12 11 Natural Language Processing (a) The following text is from a children's story by Beatrix Potter (with slight? modifications): Mr Jeremy put on a macintosh, and a pair of shiny shoes; he took his fishing rod and basket, and set off with enormous hops to the place where he kept his boat. The boat was round and green, and very like the other lily-leaves. It was tied to a water-plant in the middle of the pond. Describe six features that are used in pronoun resolution algorithms using classifiers. For each feature, explain the range of values it can take, giving illustrative examples from the text above, and list any resources or systems necessary to derive the feature. [8 marks] (b) Describe the data you would need to train and test a classifier for pronoun resolution that made use of these features.?

Consider a chip-multiprocessor where each core supports simultaneous multithreading (SMT). Furthermore, each processor core has a write-through L1 data cache. Could multicopy atomicity be supported in such a design? [6 marks] (e) Consider a chip-multiprocessor with two cores P1 and P2. Coherence is maintained using a MESI protocol with support for Bus Upgrade (BusUpgr) transactions to avoid unnecessary data transfers (i.e. when moving from state S to M). Why might a processor that initially makes a BusUpgr request have to change the request to a Read-Exclusive (BusRdX) before it even wins access to the shared bus? [3 marks] 3 (TURN OVER) CST2.2018.8.4 3 Computer Systems Modelling This question deals with stochastic processes {N(t), t 0} where N(t) represents the number of events in the time interval [0, t]. (a) (i) Define a Poisson process {N(t), t 0} of rate > 0. [2 marks] (ii) Show that N(t) Pois(t) for each fixed t > 0. You may use the result that limn(1 x/n) n = e x without proof. [4 marks] (iii) Let X1 be the time of the first event of the Poisson process N(t). Show that X1 Exp(). [2 marks] (iv) Now given that N(t) = 1 derive the distribution of the time of the single event in [0, t]. [4 marks] (b) Suppose that events of a Poisson process of rate are independently selected at random with probability p > 0. Show that the process of selected events is also a Poisson process and establish its rate. [2 marks] (c) Describe how your result from part (b) can be used to simulate a nonhomogeneous Poisson process whose rate function (t) is such that (t) ? for all t 0. [6 marks] 4 CST2.2018.8.5 4 Computer Vision (a) Explain how each of the following equations or expressions can be used for detecting and estimating visual motion in a spatio-temporal image sequence I(x, y, t). Include in your answer the name used to describe each of these general classes of motion extraction models: (i) I(x, y, t) t = ~v ~ I(x, y, t) [2 marks] (ii) t

2G(x, y) I(x, y, t)?

[2 marks] (iii) argmax(vx,vy) Z x Z y Z t I(x, y, t) I(x vx, y vy, t ) dx dy dt [2 marks] (iv) F(x, y, t) = e i(xvx + yvy + t)F(x, y, t) where F(x, y, t) = Z x Z y Z t I(x, y, t) e i(xx+yy+tt) dx dy dt [2 marks]? (b) Colour perception is not about measuring wavelengths, because they vary with illumination. Explain why it is difficult to assign intrinsic spectral reflectance properties of surfaces. Explain all steps in the Retinex Algorithm intended to solve this, relating these steps where possible to neurobiology. [7 marks] (c) Sketch out an algorithm for shape classification and the construction of shape grammars, involving active contours, codon strings, and indexing. Explain how codon constraints enable a shape grammar to define broad equivalence classes such as "cashew shaped" objects, with invariance to irrelevant transformations such as planar rotations or dilations. [5 marks] 5 (TURN OVER)What are the three possible cases for the solution of a linear program? For each of them, give an example of a linear program in standard form exhibiting this case. [6 marks] (b) What is the set of optimal solutions for the following linear program? Minimize x1 x2 x2 3 2x1 + x2 8 x1, x2 0 [6 marks] (c) For a given linear program LP1 Maximize Xn j=1 cjxj Xn j=1 aijxj bi (1 i m) xj 0 (1 j n), consider a new linear program LP2: Minimize Xm i=1 biyi Xm i=1 aijyi cj (1 j n) yi 0 (1 i m). (i) Prove that if x is a feasible solution for LP1 and y is a feasible solution for LP2, then c T x b T y. [6 marks] (ii) Using your answer in Part (c)(i), what can we conclude about LP2 if we know that LP1 is unbounded? [2 marks] 2 CST2.2018.7.3 2 Advanced Graphics (a) Given two signed distance field functions f and g, give the formula for their . . . (i) Union (fg) (ii) Intersection (fg) (iii) Difference (fg) [3 marks] (b) Give clear definitions for the Virtual Reality industry's principles of immersion and presence. Compare the two concepts and explain the difference between them with examples demonstrating each. [5 marks] (c) The Doo-Sabin subdivision scheme has kernel (1/4)[. . . , 0, 0, 1, 3, 3, 1, 0, 0, . . .], defining a scheme in which each face is replaced by four new vertices. (i) Give an expression for computing the position of a new vertex given the positions of the four old vertices of a face. [2 marks] (ii) If the face does not have 4 vertices then you must weight each parent vertex differently to find the position of the child. Suggest possible weights for the vertices of faces with 3, 5, and n vertices, and justify your answer. [3 marks] (d) There are several ray-tracing-friendly acceleration structures. (i) Explain the BSP tree data structure. Explain how it is constructed and traversed. [3 marks] (ii) Explain the kd-tree data structure. Explain how it is constructed and traversed. [3 marks] (iii) Which of the two data structures is best-suited to ray-tracing a game of chess in real time? [1 mark] 3 (TURN OVER) CST2.2018.7.4 3 Bioinformatics (a) Explain with one example the difference between local and global alignment. [3 marks] (b) Give one example why the multiple alignment, as implemented in the software Clustal, described in the course, needs a guide tree. [4 marks] (c) What is the scope of phylogeny? [2 marks] (d) Describe the UPGMA algorithm. [4 marks] (e) Explain with one example what the ultrametric property of a phylogenetic tree tells us about the evolutionary process. [3 marks] (f ) Explain the steps and the complexity of the divide and conquer approach to sequence analysis. [4 marks] 4 CST2.2018.7.5 4 Business Studies (a) Describe the characterists of debt and equity financing, highlighting the differences between them. [4 marks] (b) What is the difference between a loan and an overdraft? [1 mark] Your software company is contracted to create a new control system for chocolate bar delivery in Cambridge. The contract is for a 6 month period, with payment of 400k against milestones in months 1, 3 and 6. (c) form an outline cashflow for the project assuming staff costs of 75k per month and overheads of 60k per month. [5 marks] (d) What is your working capital requirement for the project allowing a contingency of a two month delay to one of either the second or third delivery milestones? [5 marks] (e) How would you suggest to finance this working capital requirement, justifying your answer? [5 marks] 5 (TURN OVER) CST2.2018.7.6 5 Comparative Architectures (a) Briefly describe three microarchitectural techniques or elements that can be used to improve the performance of a scalar pipelined processor. You are unable to fetch more than a single instruction per clock cycle or make any changes to the Instruction Set Architecture (ISA). [4 marks] (b) Imagine two processor implementations with equal performance. One is a superscalar design with support for out-of-order execution. The other is an in-order scalar processor. In what circumstances might the superscalar design be more power efficient? [6 marks] (c) Loads and stores are often reordered in a superscalar processor. Describe how some loads can be issued speculatively before the addresses of older stores are known and how mispredictions are detected and handled. [6 marks] (d) How can memory reference speculation be supported in a VLIW processor? [4 marks] 6 CST2.2018.7.7 6 Denotational Semantics Consider the concocted language PCF obtained from the language PCF by extending it with: Types ::= | Expressions M ::= | pair(M, M) | left(M) | right(M) Typing rules ` M1 : 1 ` M2 : 2 ` pair(M1, M2) : 1 2 ` M : 1 2 ` left(M) : 1 ` M : 1 2 ` right(M) : 2 Values V ::= | pair(V, V ) Operational semantics M1 1 V1 M2 2 V2 pair(M1, M2) 12 pair(V1, V2) M 12 pair(V1, V2) left(M) 1 V1 M 12 pair(V1, V2) right(M) 2 V2 (a) Give a denotational semantics for the above extension of PCF. [3 marks] (b) Show that the denotation of types are domains and that the denotation of terms are continuous functions. You may use any standard results provided that you state them clearly. [5 marks] (c) State the soundness property for a denotational semantics of PCF. [2 marks] (d) Show that your denotational semantics of PCF is sound. You may use any standard results provided that you state them clearly. [4 marks] (e) State the adequacy property for a denotational semantics of PCF. [2 marks] (f ) Establish whether or not your denotational semantics of PCF is adequate. You may use any standard results provided that you state them clearly. [4 marks] 7 (TURN OVER) CST2.2018.7.8 7 Hoare Logic and Model Checking (a) Give a formal definition of a Kripke structure, as a 3- or 4-tuple, briefly explaining the roles of its components. What might a Kripke structure model? [4 marks] (b) A lift controller manages a lift moving between floors 0, 1 and 2. There are three 'call' input buttons (C0 , C1 , C2 ) within the lift requesting the lift to move to the corresponding floor. These are duplicated at each floor to avoid the need for a separate 'call' button. They are internally latched as usuala call button-press stays active until reaching the associated floor, but can be immediately reactivated (e.g. useful when one realises the lift is setting off in the wrong direction!). The controller is (rather informally) specified by a hardware-style state transition diagram with three inputs and three states as in the diagram: 0 C1 C2 C0 1 C2 C0 C1 2 Give a Kripke-structure model for the controller, explaining any necessary changes or clarifications you make. You need not model the internal structure of the call buttons, it suffices to treat them as (a) non-deterministically becoming active and (b) deactivated on arrival at the corresponding floor.