PLEASE GIVE CORRECT ANSWERS

Prove that the number of comparators in any sorting network is (n log n). [4 marks] (ii) What does Part (d)(i) imply in terms of the depth of any sorting network? [1 mark] 3 (TURN OVER) CST.2016.7.4 2 Advanced Graphics A force function F : R 3 R takes a 3D point and returns a scalar representing a value of force. Force functions are the fundamental building blocks of metaball modelling. We will build an implicit surface renderer which takes as input a set of force functions {F1(P), . . . , Fn(P)} and renders the set of all points P in space where the forces of the functions sum to a threshold: the 3D isosurface such that PFi(P) = 0.5. (a) Using pseudocode, give a force function Sphere(P) which will render a unit sphere centred on (0, 0, 0). [Figure 1] [2 marks] (b) Using pseudocode, give a force function Cube(P) which will render an axisaligned cube of edge length 2 centred on (1, 1, 1). [Figure 2] [4 marks] (c) You now pass both Sphere(P) and Cube(P) to your implicit surface renderer. Depending on your choice of force functions, the seam between the cube and the sphere may be a sharp edge (to within the tolerance of your polygonalization) or a smooth blend which merges gradually from one form into the other. Which will it be, and (briefly) why? [Figures 3 and 4] [2 marks] (d) Provide alternate formulations of Sphere(P) and/or Cube(P) such that if you answered 'smooth' to Part (c) then your answer would now be 'sharp', or vice-versa. [4 marks] A spatial distortion function S : R 3 R 3 transforms one 3D point to another. If the points passed into the force function are modified by a spatial distortion functionthat is, if we render F(S(P))then the rendered isosurface will have a different shape. For example, if we define S(P) as function Point S(P) { return new Point(P.x * 2, P.y / 2, P.z * 2); } then rendering the implicit surface of Sphere(S(P)) will yield a tall, narrow ellipsoid along the Y axis. [Figure 5] (e) Give a spatial distortion function S(P) such that rendering the isosurface of Cube(S(P)) would render the cube centred at the origin and rotated 45 degrees around the X axis. [Figure 6] Hint: a standard rotation matrix is cos(t) sin(t) sin(t) cos(t) . [3 marks] 4 CST.2016.7.5 (f ) Define S(P) as function Point S(P) { return new Point( P.x / 4, P.y * 2 / sin(P.x * PI), P.z * 2); } Describe and draw a sketch of the isosurface defined by Sphere(S(P)). [5 marks] Figures: Figure 1: A sphere centred at (0, 0, 0) Figure 2: A cube of edge length 2 centred at (1, 1, 1) Figure 3: A sharp join between sphere and cube Figure 4: A smooth blending between sphere and cube Figure 5: A vertical elipsoid Figure 6: A tilted cube centred at (0, 0, 0) 5 (TURN OVER) CST.2016.7.6 3 Artificial Intelligence II Let X, Y and Z be random variables. Denote by X Y | Z that X and Y are conditionally independent given Z. (a) Give two definitions of what it means to say that X Y | Z, and prove that they are equivalent. [4 marks] (b) Prove that if X1, X2 Y1, Y2 | Z then X1, X2 Y1 | Z. [3 marks] (c) For each of the following Bayesian networks, state whether X Y | Z and justify your answer. [7 marks] Y Z X Y Z X Y Z X (d) Give a detailed explanation of how a Markov chain Monte Carlo algorithm might be used to estimate an arbitrary inference for the following Bayesian network. [6 marks] V1 V2 V3 V4 V5 V6 6 CST.2016.7.7 4 Bioinformatics (a) Explain the uses of Eulerian and Hamiltonian graphs in the context of genome assembly. [4 marks] (b) Discuss, giving an example, how to apply de Bruijn graphs to genome assembly. [6 marks] (c) Discuss how the choice of different K-mer length affects the accuracy of genome reconstruction. [3 marks] (d) Discuss the additive property in phylogeny. [3 marks] (e) Show one example of additive and one of non-additive matrices. [4 marks] 5 Business Studies (a) A small software company accepts a contract to supply some specialist software. Draw up an outline cashflow for this project. [5 marks] (b) How profitable is this project if all goes to plan? [2 marks] (c) At a project beer night towards the end of Month 3, your lead programmer punches the project manager in the face, during a heated argument. The project manager comes to you on the following day to complain to you in your role as CEO. How will you handle this affair and what is the likely effect on the project's progress? [8 marks] (d) How would the resulting loss of progress affect the project's profitability? [5 marks] 7 (TURN OVER) CST.2016.7.8 6 Comparative Architectures A large Last Level Cache (LLC) is necessary to achieve good performance in many applications. Recent server class processors have included LLCs with capacities of 40 MBytes or more. Large caches such as this are constructed from numerous smaller SRAM banks. (a) Describe an appropriate on-chip network to interconnect 32 SRAM banks to create a large LLC. The delay to access a bank should increase as we move further away from the cache controller and bus interface. The SRAM banks are square and the time taken for a signal to travel along the edge of a SRAM bank is much less than your network's clock cycle time. [5 marks] (b) To implement a set-associative LLC we may spread each set across multiple banks, i.e. each "way" of the set will be in a different bank. The different associative ways will have different access latencies depending on their distance from the cache controllerExplain the difference between PTAS and FPTAS, and give one example of a problem for which a FPTAS is known, and one example of a problem for which a PTAS is known but no FPTAS. [4 marks] (b) We consider an extension of the MAX-3-CNF problem, called MAX-4-CNF problem, where we are given a 4-CNF formula with m clauses, e.g., (x1 x3 x4 x5) (x1 x2 x3 x5) , and the goal is to find an assignment of the variables x1, x2, . . . , xn that satisfies as many clauses as possible. (i) Design a randomised approximation algorithm and analyse its approximation ratio. (For full marks, the approximation ratio must be smaller than 10/9.) [4 marks] (ii) Express the MAX-4-CNF problem as an integer program. [4 marks] (iii) Based on the construction from Part (b)(ii) or otherwise, describe an algorithm that performs randomised rounding on the solution of a linear relaxation. [3 marks] (iv) Analyse the expected approximation ratio of the algorithm from Part (b)(iii). Hint: You may want to use the following two inequalities. Firstly, for any non-negative numbers a1, a2, . . . , ak, we have Y k i=1 ai !1/k Pk i=1 ai k . Secondly, for any integer k 2 and 0 a 1, 1 1 a k k 1

1 1 k k a. [5 marks] . How might we optimise the placement of lines in particular banks (or ways) to minimise the cache's average access latency? Remember to consider the cost of moving lines. [6 marks] (c) How might the SRAM banks be efficiently interconnected so that the cache's access time is constant regardless of which bank is accessed? [4 marks] (d) Why might it be advantageous to be able to manage the amount of LLC used by each co-scheduled thread in a chip multiprocessor? [5 marks] 8 CST.2016.7.9 7 Denotational Semantics (a) (i) Define the notion of continuous function between domains. [2 marks] (ii) Let P(N 2 ) be the domain of all subsets of pairs of natural numbers ordered by inclusion. Show that the function f : P(N 2 ) P(N 2 ) given by f(S) = { (1, 1) } { (x + 1, x y) N 2 | (x, y) S } (S N 2 ) is continuous. [3 marks] (b) (i) State Tarski's fixed point theorem for a continuous endofunction on a domain. [2 marks] (ii) Give a concrete explicit description of the fixed point fix (f) N 2 of the continuous function f in Part (a)(ii). Briefly justify your answer. [3 marks] (c) (i) Define the notion of an admissible subset of a domain. [2 marks] (ii) Let P P(N 2 ) be defined as P = { S N 2 | (x, y) S. log y xlog x }. Show that P is an admissible subset of the domain P(N 2 ). [3 marks] (d) (i) State Scott's fixed point induction principle. [2 marks] (ii) Use Scott's fixed point induction principle to show that fix (f) P for f the continuous function in Part (a)(ii) and P the admissible subset of the domain P(N 2 ) in Part (c)(ii). [3 marks] 9 (TURN OVER) CST.2016.7.10 8 Hoare Logic and Model Checking This question considers a language L which has integer variables V , arithmetic expressions E and boolean expressions B, along with commands C of the forms V :=E (assignment), C; C 0 (sequencing), IF B THEN C ELSE C 0 (conditional) and WHILE B DO C (iteration). (a) Explain the syntax of the Hoare-logic partial-correctness formula {P} C {Q} and give a careful definition in English of when it is valid, that is, when |= {P} C {Q}. [2 marks] (b) How does the definition of validity for the total-correctness formula [P] C [Q] differ? [1 mark] (c) Preconditions and postconditions in {P} C {Q} often make use of logical or auxiliary variables v in addition to program variables V . Explain why this is useful illustrating your answer with a command C which satisfies {T} C {R = X + Y} but not {X = x Y = y} C {R = x + y}. [3 marks] (d) Give the axioms and rules of an inference system ` {P} C {Q} for Hoare logic. [4 marks] (e) Are your rules sound? To what extent are they complete? [2 marks] (f ) Give a formal proof, using your inference system, of {X = x Y = 3} X:=X+1 {X 1 = x Y < 10}. [2 marks] (g) Consider the command C given by WHILE X>0 DO (X:=X-1; Y:=Y+3), and let P be the precondition X = x Y = y x 0. Give the strongest postcondition Q that you can establish. Give any invariant necessary to prove {P} C {Q} for your Q. Explain briefly how the structure of the proof relates to the structure of C. [6 marks] 10 CST.2016.7.11 9 Human-Computer Interaction This question is concerned with methods that might contribute to the design of a novel wearable device, which can provide unobtrusive cues to the user, helping them to negotiate social situations. The device is configured by the user with a web interface to an XML database that specifies many different types of social obligations and challenges that the user wishes to deal with. It also uses artificial intelligence techniques to predict appropriate actions based on the user's social media history. (a) Explain the difference between formative and summative HCI research methods. [2 marks] (b) Describe two formative empirical research methods that could contribute to the development of the novel wearable device, one that results in qualitative data, and one that results in quantitative data. For each method, describe what attributes would be expected of good quality data. [6 marks] (c) Describe two summative empirical research methods that could contribute to the development of the novel wearable device, one that results in qualitative data, and one that results in quantitative data. For each method, describe what attributes would be expected of good quality data. [6 marks] (d) Describe two analytic research methods that could be used to compare specific options in the design of the novel wearable device, one that expresses those options in qualitative terms, and one that expresses options in quantitative terms. [6 marks] 11 (TURN OVER) CST.2016.7.12 10) Define the following terms: (i) the Voronoi diagram of a set of points Pi ; [1 mark] (ii) the Delaunay triangulation of a set of points Pi ; [1 mark] (iii) the equiangularity of a triangulation of a set of points Pi ; [1 mark] (iv) the empty circle property of a Voronoi diagram. [1 mark] (b) Photon mapping is a two-phase algorithm consisting of photon scattering followed by rendering. (i) Describe photon mapping's scattering phase. [4 marks] (ii) Describe photon mapping's rendering phase. [4 marks] (iii) Explain why photon mapping is considered to be a Monte Carlo algorithm. [2 marks] (c) Compare and contrast vertex and fragment shaders. Explain where each fits in the modern graphics pipeline. [6 marks] 2 Hoare Logic The programming language L consists of commands C composed from assignments V :=E (where E is an expression) using sequences C1;C2, conditionals IF S THEN C1 ELSE C2 (where S is statement) and while-loops WHILE S DO C. (a) Devise a command SKIP in L that has no effect and, for arbitrary P, prove using the Hoare logic axioms and rules for the constructs of L that ` {P}SKIP{P}. [4 marks] (b) Devise a one-armed conditional IF S THEN C built only from S, C and constructs of L and show using the Hoare logic for L that if ` {P S}C{Q} and ` P S Q then ` {P}IF S THEN C{Q}. [6 marks] (c) Define a command MAGIC in L that has the property ` {P}MAGIC{Q} for any precondition P and postcondition Q. Prove that your definition of MAGIC has this property using the Hoare logic for L. [10 marks] 2 CST.2011.8.3 3 Comparative Architectures (a) Why might a branch target buffer provide a poor prediction of procedure return addresses and what hardware solution may be employed to improve the accuracy of such predictions? [4 marks] (b) What challenges must be overcome in order to achieve high instruction fetch rates for wide-issue superscalar processors? [6 marks] (c) Embedded processors often allow both 16-bit and 32-bit instructions to be used in the same program. Why might this be advantageous? [4 marks] (d) Branch prediction and speculative execution are often used to expose greater amounts of instruction-level parallelism in superscalar processors. A reorder buffer or unified register file may be used to help recover after mispredicted branches are detected. (i) How are an instruction's operands located when a reorder buffer is used? [3 marks] (ii) What actions are taken to recover from a mispredicted branch when a unified register file is used? [3 marks] 4 System-on-Chip Design (a) Define the terms interface, protocol and flow control with respect to the electrical connections between sub-circuits or instantiated components in a SoC (system on chip). [2 marks each] (b) Why is it critical that a protocol embodies the concept of being idle when an interface joins two different clock domains? [2 marks] (c) When a pair of components are modelled using separate classes in an objectoriented language, describe two techniques for modelling the data transferred between them and emphasise how each technique incorporates flow control. One technique should use shared variables to model wires. [3 marks each] (d) Describe and compare two methods for modelling the delays experienced when a pair of components communicate over a resource that may become congested (such as a SoC bus or network on chip). [3 marks each] 3 (TURN OVER) CST.2011.8.4 5 Computer Vision (a) Define the notion of the "semantic gap" in the context of systems for contentbased image retrieval. [2 marks] (b) Many systems for optical character recognition make use of convolutional neural networks. (i) In what sense are such networks "convolutional", and to what extent do they recognise features independent of position? [3 marks] (ii) Outline how such a network could be used to recognise the characters in a high resolution digital image of this examination question, and highlight which aspects of convolutional neural networks allow for efficient detection and recognition. Assume that the network was trained to recognise only isolated instances of each of the characters. [4 marks] (iii) Consider a convolutional neural network with input image size 29 29 pixels where the first stage is a convolutional layer whose feature maps each have 37 weights. The second stage of the network implements spatial subsampling by a factor of 2 in each dimension, and this is followed by another convolutional layer (third stage) whose feature maps have 26 weights each. How many neurons are there in each of the feature maps of the third stage? [3 marks] (iv) Why is handwriting recognition a more difficult problem than the recognition of printed text? [1 mark] (c) A template-based face detector with a basic detector size of 20 20 pixels is to be applied to an image using a multi-scale sliding window approach. The detector has a hit rate of 99.99% and a false positive rate of 0.1%. (i) Explain whether this detector is likely to yield good recognition performance and give a lower bound estimate of the likely number of false positives if the image has a resolution of 4 megapixels. [2 marks] (ii) Briefly describe the detection mechanism of the Viola-Jones approach to face detection, and highlight two aspects of this approach that make it efficient as a sliding-window detector. [5 marks] 4 CST.2011.8.5 6 Digital Signal Processing (a) What can you say about the Fourier transform X(f) if (i) x(t) is real; [2 marks] (ii) x(t) = x(t)? [2 marks] (b) Give the result of the Fourier transform X(f) = R x(t) e2jf t dt, using Dirac's delta where appropriate, of (i) x(t) = 1; [1 mark] (ii) x(t) = cos(2t); [2 marks] (iii) x(t) = rect(t); [2 marks] (iv) x(t) = [ 1 2 + 1 2 cos(2t)] rect(t). [3 marks] (c) When is a random sequence {xn} called a "white noise" signal? [2 marks] (d) Consider an n-dimensional random vector variable X. (i) How is its covariance matrix defined? [2 marks] (ii) How can you change its representation without loss of information into a random vector of equal dimensionality in which all elements are mutually uncorrelated? [4 marks] 5 (TURN OVER) CST.2011.8.6 7 E-Commerce (a) What is meant by the abbreviations CPC, CTR, CPA, ARPU, CLV in relation to online marketing? [5 marks] (b) You decide to offer an online ecommerce course. The target sales price is 995. (i) How will you market and promote the course online? [5 marks] (ii) How will you monitor your marketing campaigns? [5 marks] (iii) The table below gives Google estimates of typical keywords. Should you bid for any of these? Justify your answer. [5 marks] Keyword Global Local Estimated Estimated Estimated Estimated Monthly Monthly Avg. Ad Daily Daily Searches Searches CPC Position Clicks Cost ecommerce 1,500,000 201,000 3.02 1.64 62 191.94 business 110,000 18,100 2.63 1.32 8 21.95 course marketing 60,500 8,100 2.92 1.3 2 8.81 course 6 CST.2011.8.7 8 Artificial Intelligence II (a) Give a definition of expected utility and explain why the concept is useful in the context of decision-making. [2 marks] (b) Give a definition of the value of perfect information and explain why the concept is useful in the context of decision-making. [4 marks] (c) A talented, but nervous, student has to sit a difficult and important examination. There are only two possible outcomes: pass or fail and the student attaches to these utilities of U(pass) = 106 and U(fail) = 108 . Lacking in confidence, his beliefs are that Pr(pass|revise) = 0.55 and Pr(pass|revise) = 0.2. Calculate the expected utility of the situation described. [4 marks] (d) The student finds what he believes might be a copy of this year's examination paper, discarded by a careless examiner. He believes that Pr(pass|revise, thisYearsPaper) = 0.75 However, should he be wrong then Pr(pass|revise, thisYearsPaper) = 0.1 as he will waste time learning to answer the wrong questions, because he will revise from the wrong paper. Not revising implies Pr(pass|revise, thisYearsPaper) = 0.7 However, should he be wrong then Pr(pass|revise, thisYearsPaper) = 0.08 He considers bribing somebody to tell him whether he has this year's paper or not; however, he thinks it is unlikely that he in fact has this year's paper, and therefore believes that Pr(thisYearsPaper) = 0.7 Compute the value of perfect information associated with finding out whether the paper is the right one. [10 marks] 7 (TURN OVER) CST.2011.8.8 9 Information Retrieval The figure below shows the output of two information retrieval systems on the same two queries in a competitive evaluation. The top 15 ranks are shown. Crosses correspond to a document which has been judged relevant by a human judge; dashes correspond to irrelevant documents. There are no relevant documents in lower ranks. System 1 Rank Q1 Q2 1 - X 2 X - 3 X - 4 X - 5 - - 6 - - 7 - - 8 X - 9 X - 10 X - 11 X - 12 - - 13 - X 14 - X 15 X - System 2 Rank Q1 Q2 1 X X 2 X - 3 X - 4 - X 5 X X 6 X - 7 - - 8 - - 9 - - 10 - - 11 X - 12 X - 13 - - 14 - - 15 X - (a) Explain the following evaluation metrics and give results for query Q1 for both systems. (i) Precision at rank 10. [2 marks] (ii) Recall at precision 0.5. [2 marks] (b) The metrics in part (a) above are not adequate measures of system performance for arbitrary queries. Why not? What other disadvantages do these metrics have? [3 marks] (c) Give the formula for mean average precision (MAP), and illustrate the metric by calculating System 1's MAP. [6 marks] (d) For each system, draw a precision-recall curve. Explain how you arrived at your result. How could one create more informative curves? [7 marks] 8 CST.2011.8.9 10 Principles of Communications (a) Draw the transition rate diagram for an M/M/1 queueing system, explaining each type of label, symbol and transition you have used. [5 marks] (b) Suppose an M/M/1 server is being designed with the following business in mind: Each customer arrival earns the service 5 Euros. However, for each unit of time the customer waits in the system, there is a refund of 1 Euro. (i) What is the range of arrival rates for which the system makes a net profit? [10 marks] [Hint: You may wish to use the result that Pj = j (1 ), and (hence) P0 = 1 , where Pi is the probability of i customers being in the service and = / is the utilisation of the service, for the mean arrival rate of a Poisson process, and a mean service time .] (ii) Imagine that a priority queue is made available for an additional fee. Discuss qualitatively the relationship between the customers' willingness to pay, and the appropriate setting of the fee to continue to maximise profit. [5 marks] 11 Security II You are consulting for a large online services company which stores personal information on millions of customers. Your client's directors are alarmed by the Wikileaks saga and are concerned about damage to their company's reputation should a disaffected member of staff steal and publish personal information on a large number of customers. Discuss the security policy options available to your client to minimise the damage that a member of staff could do. [20 marks] 9 (TURN OVER) CST.2011.8.10 12 Computer Systems Modelling (a) Consider an open Jackson queueing network. (i) Give a description of an open Jackson network. Explain the parameters that specify the network and the state space that you would use to model its behaviour. [2 marks] (ii) Derive the traffic equations for the arrival rates i at each node i in the network. [2 marks] (iii) What is the condition for the existence of an equilibrium distribution? [2 marks] (iv) State Jackson's Theorem for an open Jackson network. [2 marks] (b) Now consider the M/M/m/m loss system with traffic intensity . (i) Show that the steady state loss probability, E(, m), that all servers are occupied is given by E(, m) = m/m! Pm i=0 i/i! [6 marks] (ii) Show that E(, m) solves the recurrence relation E(, m) = E(, m 1) m + E(, m 1) with the boundary condition E(, 0) = 1 and comment on why the recurrence relation is useful in practice. [6 marks] 10 CST.2011.8.11 13 Topics in Concurrency (a) Draw the transition systems of the following two pure CCS terms: P1 def = (a.(b + c) k b) \ {b} P2 def = a.(c + ) [3 marks] (b) Write down pure CCS terms for the following two transition systems: '&%$ !"# a / b q a @ @ @ @ @ @ @ b a @ @ @ @ @ @ @ '&%$ !"# a ? a @ @ @ @ @ @ @ @ a ? P3 : P4 : [3 marks] (c) Carefully justify your answers to the following two questions either by exhibiting a bisimulation or by providing a Hennessy-Milner logic formula satisfied by one process and not by the other: (i) Are P1 and P2 bisimilar? [3 marks] (ii) Are P3 and P4 bisimilar? [3 marks] (d) A trace of a process p0 is a finite sequence of action labels = (1, . . . , k) for which, if is nonempty, there exist p1, . . . , pk such that pi1 i pi for all 0 < i k. Two processes p and p 0 are said to be trace-equivalent if, for all sequences of action labels , is a trace of p if, and only if, is a trace of p 0 (i) Are trace-equivalent processes always bisimilar? (ii) Are bisimilar processes always trace-equivalent? In each case, provide either a proof or a counterexample. [8 marks] 11 (TURN OVER) CST.2011.8.12 14 Types Terms in the polymorphic lambda calculus (PLC) are given by the grammar M ::= x | x : (M) | M M | (M) | M where is a type, a type variable and x a variable. (a) Give the rules for the type system in PLC. [2 marks] (b) Give the rules for the relation, , of beta-reduction in PLC. Explain what it means for a term to be beta-normal. [3 marks] (c) Terms in head-normal form, H, can be described in PLC by the grammar A ::= x | A H | A H ::= A | x : (H) | (H) Arguing by induction on the structure of terms, or otherwise, prove that every term in PLC that is both typable and beta-normal is of head-normal form. [8 marks] (d) Natural numbers can be encoded into PLC using the type nat defined as nat def = ( ( ) ) The encoding uses the Church-numerals defined as n def = (x:(y : (y(y(y . . .(y | {z } n occurrences x). . .))))) Prove that the Church-numerals are the only closed, beta-normal terms of type nat. Hint: Use the result proved in part (c) and do a case analysis over the form of terms in head-normal form. You may assume without proof that if ` M : is provable in the PLC type system, then the free variables of the term M are contained in the domain of the typing environment . Information Theory (a) Consider a discrete memoryless channel whose input symbol source is a random variable X {x1, . . . , xJ } having probability distribution p(xj ), and whose output symbol (possibly corrupted) is a random variable Y {y1, . . . , yK} (see figure below). X Channel Y Symbols Source encoder Symbols Decoder (i) Provide its channel matrix. [3 marks] (ii) Give the average probability of correct reception, meaning the probability that the same symbol is emitted as was injected into the channel, averaged over all the cases. [3 marks] (b) Show that convolution of any continuous signal with a Dirac delta function reproduces the signal. [4 marks] (c) A frequency-shifting modulation of signals into different channels of a shared medium multiplies the baseband signal f(t) by a complex exponential carrier wave e ict of some (channel-specific) frequency c to produce a passband f(t) e ict (see figure below). Upon reception of such a passband, what process of demodulation would recover the original baseband? baseband carrier signal AM passband FM passband [5 marks] (d) Explain the "information diagram" of Gabor, and why the Uncertainty Principle gives it a quantal structure with an irreducible representation of the data. [5 marks] 12 CST.2016.7.13 11 Natural Language Processing The distributional hypothesis states that the meaning of a word can be defined by its use and, therefore, it can be represented as a distribution of contexts in which the word occurs in a large text corpus. (a) Describe four different types of context that can be used for this purpose. [4 marks] (b) The contexts can be weighted using Pointwise Mutual Information (PMI). Explain, giving formulae, how PMI is calculated and how individual probabilities are estimated from a text corpus. [5 marks] (c) Some words occur very rarely in the corpus. How does this affect their PMI scores as contexts? [4 marks] (d) The goal of distributional word clustering is to obtain clusters of words with similar or related meanings. The following clusters have been produced in two different noun clustering experiments: Experiment 1: carriage bike vehicle train truck lorry coach taxi official officer inspector journalist detective constable policeman reporter sister daughter parent relative lover cousin friend wife mother husband brother father Experiment 2: car engine petrol road driver wheel trip steering seat highway sign speed concert singer stage light music show audience performance ticket experiment research scientist paper result publication laboratory finding (i) How are the clusters produced in the two experiments different with respect to the similarity they capture? What lexico-semantic relations do the clusters exhibit? [3 marks] (ii) The same clustering algorithm, K-means, was used in both experiments. What was different in the setup of the two experiments that resulted in the different kinds of similarity captured by the clusters? [4 marks] 13 (TURN OVER) CST.2016.7.14 12 Optimising Compilers The following C-like program reads a List of integers by making calls to external procedures readint() to read and return an integer and cons() to construct a List: struct List { int hd; List *tl; }; List *readlist() { L0: List *p = 0, *q, *t; int v; L1: // comment for Part (e) L2: v = readint(); L3: if (v < 0) return p; L4: t = cons(v, 0); L5: if (p == 0) { L6: p = t; q = t; } else { L7: q->tl = t; q = t; } L8: goto L2; } (a) Define the concept of a variable being live at a program point, distinguishing a semantic notion from one which is more practically computable. Sketch an algorithm to compute the set of variables live at each program point. [5 marks] (b) Give the sets of live variables your algorithm would compute for the program points L0 . . . L8. Also indicate any discrepancies between these and sets derived from your semantic notion of liveness. [5 marks] (c) Does the above code have any data-flow anomalies? If so explain what they are and what action a helpful compiler might take. [2 marks] (d) Suppose the above code were compiled for an ARM-like processor which assumes registers 0-3 are corrupted by procedure call and registers 4-7 are preserved by procedure call; register 0 is also used for the first argument to and result from a procedure call. Assuming a register allocator operating by graph colouring, which registers might be allocated to variables p, q, t and v? Indicate when there is a choice between equivalent allocations and when there is a benefit of using one register over another. What, if anything, would be wrong with simply allocating p, q, t and v respectively to r4, r5, r6 and r7? [5 marks] (e) Now suppose that the commented line L1 were replaced with some more complex code (which does not use p, q, t or v) and the register allocator found that 9 registers were now required for readlist() when only r0 . . . r7 are available. How would an allocator proceed for the code as written? Can you suggest an adjustment to the source code (respecting your company's coding requirement that all declarations, but not necessarily initialisation, occur at the very start of a procedure) to allow all variables to be allocated a register? [3 marks] 14 CST.2016.7.15 13 Principles of Communications (a) Distributed link-state routing algorithms can be enhanced by a central controller, such as the fibbing scheme, to modify the results of the computation. Explain by an example, starting from the topology below, how a specific path can be added from router C to host D2 via nodes A, B and X, by the introduction of virtual nodes in the topology, and their advertisement via the routing protocol. requirement (C,A,B,X,D2 ) A B C X D1 D2 3 1 10 1 [10 marks] (b) Dynamic Alternative Routing (DAR), also known as Sticky Random Tandem, is a way to shed load from the most direct path in a circuit switched network to other, slightly longer paths. It depends on properties of the backbone topology of the telephone network, and, to some extent, on the properties of telephone call statistics. Describe the basic algorithm and give an overview of why it works well. [10 marks] 15 (TURN OVER) CST.2016.7.16 14 Security II A taxpayer, whose total wealth is 300 Galactic Credits (GC), is having her tax return investigated under suspicion of irregularity. The tax inspector offers her a choice: either the investigation goes ahead as normal, which may result in her being cleared or in her having to pay a hefty fine, or she pays a fixed settlement upfront and the investigation is closed. We formalize these options respectively as the contest choice (40% chance of being cleared and 60% chance of paying 10 GC) and the settle choice (paying a fixed settlement of s = 5 GC). Pretend, for simplicity, that the utility of wealth in Expected Utility Theory is U(w) = ln(1+w) and that the Prospect Theory diagram has V (x) = ln(1 + x) in the first quadrant and V (x) = 2 ln(1 + |x|) in the fourth quadrant, with w, x R expressed in GC. (a) Answer the following two questions separately for each of the three cases of (1) straightforward probabilistic computation, (2) Expected Utility Theory and (3) Prospect Theory. Compute any numerical values to three decimal digits using a calculator. (i) Will the taxpayer prefer settle or contest in each of the three cases? Justify your answer. [5 marks] (ii) What should the value of s be for the taxpayer to be indifferent between the settle and contest choices in each of the three cases? [5 marks] (b) For what range of values of s would the preferences of the taxpayer in the three cases of part (a) be settle, contest, contest respectively? [5 marks] (c) For the case of Expected Utility Theory, draw a full-page diagram and explain in detail how to derive graphically the value of s for which the choice between contest and settle does not matter. [5 marks]