MUST ANSWER CORRECTLY We often use Hidden Markov Models (HMM) to…

Question Answered step-by-step MUST ANSWER CORRECTLY We often use Hidden Markov Models (HMM) to…  MUST ANSWER CORRECTLY We often use Hidden Markov Models (HMM) to predict a pattern (for instancethe exons). How can you compute the number of True Positives, True Negatives,False Positives and False Negatives and use them to evaluate your HMM?[6 marks](c) How can you evaluate the results obtained (number of clusters and their relativeposition) using the K means algorithm for clustering? [5 marks](d) What is the difference between the adjacency list and the accessibility list?[3 marks]2CST.2013.9.32 Computer Systems Modelling(a) Define a Poisson process of rate ? > 0. [3 marks](b) Show that the number of events, N(t), of a Poisson process that occur in thefixed time interval [0, t] is a random variable that has a Poisson distribution withparameter ?t. [3 marks](c) Show that the inter-event times of a Poisson process form a sequence ofindependent random variables each distributed with an exponential distributionwith parameter ?. [3 marks](d) Describe how to use the inverse transform method to simulate exponentialrandom variables with parameter ?. [3 marks](e) Show how your simulated exponential random variables can be used to simulatePoisson random variables with parameter ?. [3 marks](f ) Consider positive numbers ?1, ?2, . . . , ?n and weight factors ?1, ?2, . . . , ?n suchthat ?i ? 0 for i = 1, 2, . . . , n and Pni=1 ?i = 1. Show thatf(x) = (Pni=1 ?i?ie??ix x > 00 x ? 0is a density for a random variable and describe a procedure to simulate valuesfrom this density. [5 marks]3 (TURN OVER)CST.2013.9.43 Computer Vision(a) Explain why inferring object surface properties from image properties is anill-posed problem in general. In the case of inferring the colours of objects fromimages of the objects, how does knowledge of the properties of the illuminantaffect the status of the problem and its solubility? [4 marks](b) What surface properties can cause a human face to form either a Lambertianimage or a specular image, or an image lying anywhere on a continuum betweenthose two extremes? In terms of geometry and angles, what defines these twoextremes of image formation? What difficulties do these factors create forefforts to extract facial structure from facial images using “shape-from-shading”inference techniques? [4 marks](c) Explain and illustrate the “Paradox of Cognitive Penetrance” as it relates tocomputer vision algorithms that we know how to construct, compared withthe algorithms underlying human visual competence. Discuss how human visualillusions may relate to this paradox. Comment on the significance of this paradoxfor computer vision research. [4 marks](d) Define the “Correspondence Problem”, detailing the different forms that it takesin stereo vision and in motion vision, and discuss its complexity. In both cases,explain why the computation is necessary. What are the roles of space and timein the two cases, and what symmetries exist between the stereo and motionvision versions of the Correspondence Problem? [4 marks](e) When defining and selecting which features to extract in a pattern classificationsystem, what is the goal for the statistical clustering behaviour of the data interms of the variances within and amongst the different classes? [4 marks]4CST.2013.9.54 Denotational SemanticsA general piecewise curve definition, whether B´ezier, B-spline, or NURBS, can be written as a sum of products of basis functions, Ai(t), and control points, Pi : P(t) = XAi(t)Pi , tmin ? t < tmax Give the conditions on the functions Ai that are needed to ensure that: (i) Translation of all of the points by some vector, P0 i = Pi + ?P, causes a translation of the curve by the same vector, P0 (t) = P(t) + ?P. [2 marks] (ii) The curve lies within the convex hull of the control points. [2 marks] (iii) The curve passes through one of the control points, Pj . [2 marks] (b) The knot vector [0, 0, 0, 1, 1, 1] defines a quadratic B-spline with three control points. Derive the equations of and graph the three basis functions from this knot vector. [6 marks] (c) The basis functions derived in part (b) can be used, in a NURBS curve, to reproduce exactly a quarter-circle. Recall that a NURBS curve can be written as: P(t) = Pn+1 i=1 Ni,k(t)Pihi Pn+1 i=1 Ni,k(t)hi , tmin ? t < tmax where hi is the homogeneous co-ordinate associated with point Pi . Place the three control points at P1 = (1, 0), P2 = (1, 1), P3 = (0, 1). (i) Sketch the NURBS curve for the case h1 = h2 = h3 = 1 [1 mark] (ii) Calculate the magnitude of the maximum error between the curve in (c)(i) and a perfect circle of radius 1 centred at (0, 0). [2 marks] (iii) Sketch the NURBS curve for the case h1 = h3 = 1, h2 = 0. [1 mark] (iv) Sketch the NURBS curve for the limit case h1 = h3 = 1, h2 ? ?. [1 mark] (v) Derive the value for h2 that makes the NURBS curve perfectly match a quarter circle of radius 1 centred at (0, 0). [3 marks] 2 CST.2013.7.3 2 Artificial Intelligence II Princess Precious is a very light sleeper, and insists that every night she must sleep on brand new silk sheets. Her younger brother, however, is in the habit of secretly scattering toast crumbs in her bed, to make sure she sleeps badly. In order to get the week started well, he does this every Sunday with probability 0.9. For the rest of the week, he tends to relent on any given night if he placed crumbs in her bed the previous night, and hence leaves them with a probability of 0.1. On the other hand, if he did not leave crumbs on a given night, his mischievous nature compels him to leave crumbs the next night with probability 0.6. Precious, being a true princess, tends to be grumpy in the morning if she has not slept well. Consequently, if she has slept with crumbs in her bed she is grumpy with probability 0.95. Being a light sleeper, even if there are no crumbs she is grumpy with probability 0.55. (a) Give a detailed definition of a Hidden Markov Model (HMM) and show how the scenario described can be modelled as an HMM. [4 marks] (b) Give a detailed description of the Viterbi algorithm for computing the most probable sequence of states, given that an HMM produces a given sequence of observations. [8 marks] (c) It is observed that Princess Precious is grumpy on Monday and Tuesday. However on Wednesday she is radiantly happy. Use the Viterbi algorithm to compute the most likely sequence of activities performed by her brother. [8 marks] 3 (TURN OVER) CST.2013.7.4 3 Bioinformatics Given the two DNA sequences: GCACTT and CCCAAT (a) Compute the alignment (using the edit graph) and the final score with the following rules: match score = +1, mismatch = ?1, gap penalty = ?1. [4 marks] (b) Discuss how the alignment score and the quality of the result depend on the match score, mismatch, and gap penalty. [6 marks] (c) Generate four, short DNA sequences (a,b,c,d) such that their relations as a tree are approximately the following: ((a,b),(c,d)). [5 marks] (d) How is the score matrix used in phylogenetic tree building techniques? [5 marks] 4 CST.2013.7.5 4 Business Studies This question is about Intellectual Property and Copyright. (a) List 5 types of Intellectual Property. Comment on their use to protect a software program. [5 marks] (b) Explain what Intellectual Property Rights (IPR) an employee has on their inventions. Does this differ if the invention is made in their own time? [5 marks] (c) Professor Elbowpatch, a professor of ancient languages and keen amateur gardener, invents a new sort of lawnmower. What are his IPR options? [5 marks] (d) Discuss what actions Professor Elbowpatch should take to exploit his invention. [5 marks] 5 (TURN OVER) CST.2013.7.6 5 Comparative Architectures (a) Why might a heterogeneous or asymmetric chip-multiprocessor be preferable to a homogeneous or symmetric one? [5 marks] (b) You are a computer architect working on the design of a new processor for the mobile phone market. An initial analysis of applications suggests that there would be worthwhile gains in producing a processor that could offer two different power-performance tradeoffs. The first configuration would maximise the exploitation of ILP and consume the most power. The second would on average perform less well, but would consume less power. (i) Describe how the microarchitecture of a single processor could be modified in order to offer the ability to switch between the two configurations described at run-time. [9 marks] (ii) How might one determine when to switch from one configuration to the other in order to reduce overall power consumption while minimising the impact on the user experience? [6 marks] 6 CST.2013.7.7 6 Denotational Semantics (a) Let D be a poset and let f : D ? D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that whenever D is a domain and f is a continuous function, fix (f) exists. [5 marks] (b) A poset (P, v) has binary meets if for every pair of elements x, y ? P there is a necessarily unique element (x u y) ? P such that • (x u y) v x and (x u y) v y, and • for all z ? P, z v x and z v y imply z v (x u y). (i) Let (P, v) be a poset with binary meets. Show that the function meet : P × P ? P given by meet(x, y) = x u y is monotone. [5 marks] (ii) Exhibit a domain with binary meets for which the function meet is not continuous. Justify your answer. [5 marks] 7 (TURN OVER) CST.2013.7.8 7 Hoare Logic (a) Briefly explain the concepts: mechanised program verification and verification conditions (VCs). [4 marks] (b) Consider three consecutive assignments: { P } V1 := E1; V2 := E2; V3 := E3 { Q } Write down the VCs that are generated for such a program. Give a detailed proof which shows that, if the VCs are true, then the specification above is provable in Hoare Logic. [6 marks] (c) Write down the VCs for the following annotated program. For this part, do not attempt to define Inv. [4 marks] { T } I := 0; X := 0; Y := 1; WHILE (I 6= N) DO { Inv } I := I + 1; X := X + Y; Y := X + Y OD { X = fib(2 × N) } Here fib(0) = 0, fib(1) = 1 and fib(n + 2) = fib(n) + fib(n + 1) for n ? N. (d) Provide a definition of Inv such that the VCs are provable. Sketch a proof of the VCs. [6 marks] 8 CST.2013.7.9 8 Human-Computer Interaction Imagine you have been commissioned to design the user interface for a head-up display (e.g. based on Google Project Glass) that can be used while riding a bicycle, as a reminder of appointments around Cambridge. (a) In order to be safe while riding, the visual design of appointment reminders and instructions should be as simple as possible. Describe three specific ways this can be achieved, using formal elements of visual design. [6 marks] (b) Consider the possibility that users might wish to modify their appointment schedules while riding. Choose three different Cognitive Dimensions of Notations, and discuss their implications. [6 marks] (c) Describe ways that features of the bicycle itself might form the basis for (i) a tangible user interface; and (ii) an augmented reality interface to this system. For each of these, explain what sensor processing would be involved. [4 marks] (d) How might these two alternative interfaces be compared experimentally? Describe the structure of the experimental design and procedure for analysis of the results. [4 marks] 9 (TURN OVER) CST.2013.7.10 9 Information Theory and Coding (a) Consider an alphabet of 5 symbols whose probabilities are as follows: A B C D E 1 16 1 4 1 8 1 16 1 2 One of these symbols has been selected at random and you need to discover which symbol it is by asking 'yes/no' questions that will be truthfully answered. (i) What would be the most efficient sequence of such questions that you could ask in order to discover the selected symbol? [2 marks] (ii) By what principle can you claim that each of your proposed questions in the sequence is maximally informative? [2 marks] (iii) On average, how many such questions will need to be asked before the symbol is discovered? What is the entropy of the symbol set? [2 marks] (iv) Construct a uniquely decodable prefix code for the symbols. Explain why it is uniquely decodable and why it has the prefix property. [2 marks] (v) Relate the bits in the code words forming your prefix code to the 'yes/no' questions that you proposed in (i). [2 marks] (b) Explain how the bits in an IrisCode are set by phase sequencing. Discuss how quantisation of the complex plane into phase quadrants sets each pair of bits; why it is beneficial for quadrant codes to form a Gray Code; how much entropy is thereby typically extracted from iris images; and why such bit sequences enable extremely efficient identity searches and matching. [5 marks] (c) Consider a noisy analog communication channel of bandwidth ? = 1 MHz, which is perturbed by additive white Gaussian noise whose total spectral power is N0? = 1. Continuous signals are transmitted across such a channel, with average transmitted power P = 1,000. Give a numerical estimate for the channel capacity, in bits per second, of this noisy channel. Then, for a channel having the same bandwidth ? but whose signal-to-noise ratio P N0? is four times better, repeat your numerical estimate of capacity in bits per second. [5 marks] 10 CST.2013.7.11 10 Natural Language Processing Consider the following context-free grammar: S -> NP VP N -> dog V -> sees NP -> Det N N ->cat V -> hates VP -> V N -> mouse V -> sneezes VP -> V NP Det -> the (a) Which of the following sentences are recognised by this grammar, and why? [4 marks] (i) the dog sneezes the cat (ii) the mouse hates (iii) the cat the mouse hates (iv) the mouse hates the mouse (b) Modify the grammar so that the following sentence is now accepted in addition: the dog the cat the mouse sees hates sneezes Your modification should express the linguistic phenomenon as efficiently and elegantly as possible. Justify your choice. [6 marks] (c) The semantics of natural language expressions can be expressed in first order predicate logic (FOPL). For instance, “the dog sneezes” can be approximately expressed as ?x dog(x) ? sneeze(x) Following this pattern, express the semantics of the sentence in part (b) in FOPL. [4 marks] (d) Consider the following sentence: the mouse that sees the cat that hates the dog that sneezes Contrast this construction to the one in part (b) in terms of semantics and syntax. How would you modify the original grammar in part (a) to account for this construction? [6 marks] 11 (TURN OVER) CST.2013.7.12 11 Optimising Compilers (a) Give a semantic notion of a variable being live at a program point, explaining why this is problematic to calculate. Now give a simpler-to-calculate notion of liveness and explain how it relates to the semantic notion. Formulate dataflow equations whose solution(s) give the liveness at each program point. You need only consider liveness of simple non-address-taken variables. [4 marks] (b) Suppose we have a basic block of p simple statements. Give a formula relating the liveness on entry to the block to those of its q neighbouring blocks in the control flow graph. This formula naturally uses O(p) +O(q) operations – justify this statement. It is claimed that this formula can be re-arranged to require only O(q) time to calculate by only using one ‘?’ and one ” operator. Determine whether this is true. [Hint: you may wish to consider examples, and to start by solving the case p = 2. Partial credit will be given for a good set of concrete examples arguing for or against.] [5 marks] (c) To solve the dataflow equations, an initial approximation to liveness at the start of each basic block is required. What is it, and indicate why this leads to a preferable solution. [2 marks] (d) Solving dataflow equations is usually expressed iteratively, where each iteration is of the form “for every basic block re-calculate the set of live variables from the current sets of live variables of its neighbours”. We want to determine whether some basic-block orderings in “for every basic block” result in fewer overall iterations than others. Suppose the program has k basic blocks, but no cycle in the control flow graph; give an optimal ordering which only requires one dataflow iteration to calculate liveness (a second would only calculate the same value of the first). Also give such a program and an ordering which maximises the number of iterations required, giving the number of iterations in terms of k. [5 marks] (e) Consider the program with four labelled blocks (with B1 as entry node): B1: x = read(); y = read(); z = read(); goto B2; B2: z = z+1; x = x-1; if (x>0) goto B3; else goto B4; B3: z = z+1; y = y-1; if (y>0) goto B2; else goto B4; B4: print(z); Show (i) there is no basic block ordering for which a single iteration gives the correct liveness at each label, but (ii) there is an ordering for which two iterations suffice (in the sense that a third would agree with the second). Give your ordering both explicitly as a permutation of {B1, B2, B3, B4} and also as a general principle along the lines of your answer to part (d). [4 marks] 12 CST.2013.7.13 12 Principles of Communications Suppose that you read about the design of an end-to-end transport protocol for an early version of the Internet, which uses window-based flow control with a fixed size window, with Go-Back-N retransmission of all un-acknowledged packets when there is a time-out awaiting an acknowledgement for any given data packet. How would you convince the designer that they are going to have real problems with such a simplistic scheme? [20 marks] 13 (TURN OVER) CST.2013.7.14 13 Security II (a) Formally state the two rules of the Bell-LaPadula (BLP) security policy model and then re-state them informally in terms of a single rule about the direction of information flow. [2 marks] (b) Consider a distributed system in which A is a TOP SECRET process running on machine Alice and B is a CONFIDENTIAL object residing on machine Bob. (i) Explain and justify whether A is allowed to read and/or write from B according to the BLP policy. [2 marks] (ii) Discuss the claim made by some researchers that this scenario highlights a fundamental problem with the BLP policy. [4 marks] (c) Consider the following description of Brewer and Nash’s Chinese Wall security policy model. • Simple rule: Read or write access to object o2 by subject s is granted if and only if, for all objects o1 to which s has had access, we have: (class(company(o1)) 6= class(company(o2)) or (company(o1) = company(o2)). • *-rule: Write access to object o2 by subject s is granted if and only if access is granted by the simple rule and there does not exist any unsanitized object o1, readable by s, for which company(o1) 6= company(o2). (i) Explain the context and goal of the Chinese Wall security policy model. Then explain what each of the two rules is intended to enforce or prevent. [4 marks] (ii) Some researchers have claimed that the formal rules of Chinese Wall do not match the policy that Brewer and Nash intended to enforce, to the extent that the resulting policy is unusable in practice. Explain precisely why the policy would be unusable and give a clear proof of this claim. [8 marks] 14 CST.2013.7.15 14 Topical Issues Consider an inertial measurement unit that reports its change in distance and heading each second, but is subject to typical sensor errors such as bias and noise. A particle filter is to be used to fuse its output with a building map to estimate the current location of a user within that building.The top and bottom of the S perfectly touch the top and bottom of the hemisphere. The dimensions of the sculpture are as follows: • Sphere radius: 100cm • Line width: 20cm • Radius of the ends of the S: 10cm Describe how you would build this sculpture using the technique of Constructive Solid Geometry. Assume that you have only three primitives, each centred on the origin: • A cube, where each edge is 10cm long. • A sphere, of radius 100cm. • A torus, where the radius of a cross-section of the tube is 2cm and the ring of the tube is a circle of radius 9cm. The torus lies in the xy plane. For full marks, specify every transformation, in order, for every primitive (e.g., “Translate the cube by 1m up x” or “Rotate this object by 45 degrees around the z-axis”) and every binary operation between primitives. [8 marks] (b) (i) Given two disks of radius 1, one centered at (1, 1, 1) with normal vector (0, 0, ?1) and the other centered at (1, 1, ?1) with normal vector (0, ? 2, ? 2), compute the exact radiosity view factor between them. Clearly state the equation you use. Assume there is no occlusion between the two disks. [4 marks] (ii) Briefly describe an efficient mechanism for using modern hardware to compute (approximate) view factors between patches in a radiosity system, including occlusion. [4 marks] (iii) Describe a hybrid method which could produce images which both solve the global illumination problem with a radiosity solution and also correctly portray lighting phenomena such as caustics. [4 marks] 2 CST.2013.8.3 2 Artificial Intelligence II (a) Denoting the utility of a state s of the world by U(s), and given that we have evidence E regarding the world and probability distribution Pr(s|A = a, E) modelling the effect of taking specific actions, define the expected utility associated with taking an action. [2 marks] (b) Evil Robot is, despite his undoubted evilness, very shy where romance is concerned. He has fallen for a beautiful vacuum cleaner, called SN05718, and is wondering whether to ask her to accompany him for a change of oil. He rates the utility of going alone as ?10 and the utility of being accompanied as +100. Being shy, he feels that if he asks her then she will accept with probability 0.1, but if he does not then there is a small chance of 0.01 that she will in fact ask him. What is the expected utility of this situation? [3 marks] (c) If in the scenario described in part (b) we discover that it is possible to obtain further evidence E 0 in addition to E regarding the world, derive an expression for the value of perfect information associated with finding the value of E 0 . [5 marks] (d) Evil Robot has a plan to acquire SN05718’s diary to find out whether or not she likes him. He believes that the likelihood of her liking him is 0.3. Also, if she likes him and he asks her to accompany him he thinks she will accept with probability 0.7, whereas if he does not ask she will in any case accompany him with probability 0.4. On the other hand, if she does not like him then the corresponding probabilities are 0.05 and 0.01. It will cost Evil Robot 15 to get someone to steal the diary. Compute whether or not he should. [10 marks] 3 (TURN OVER) CST.2013.8.4 3 Comparative Architectures (a) How do superblock and trace scheduling differ? [4 marks] (b) How might a programmer improve the performance of a program given detailed knowledge of a processor’s memory hierarchy? [6 marks] (c) Larger scale networks, i.e. those involving chip-to-chip or longer distance communications, have been designed for many years. What new challenges and constraints are introduced when designing on-chip networks? [6 marks] (d) As fabrication technologies scale the performance of wires improves slowly relative to that of transistors. Why is this particularly problematic when attempting to increase the performance of superscalar processors? [4 marks] 4 CST.2013.8.5 4 Computer Systems Modelling Consider a single server queue with customer arrivals occuring at times of a Poisson process of rate ?. Customers are served with independent exponential service times which have mean 1/µˆ if there are less than k customers present and mean 1/µ if there are k or more customers present and where k is fixed. The number present, n, can be modeled as a birth-death process with the birth rates ?n = ? for each n = 0, 1, 2, . . . and state-dependent death rates µn = ( µˆ 1 ? n < k µ n ? k . Write ˆ? = ?/µˆ and ? = ?/µ and assume that ? < 1. (a) Find an expression for ?n the probability of being in state n under the equilibrium distribution which you may assume to exist. [4 marks] (b) Show that if ˆµ = µ then your result for ?n in part (a) coincides with the case of a M/M/1 queue, namely ? n (1 ? ?). [1 mark] (c) Find an expression for L the expected number of customers in the system. [6 marks] (d) Show that Lq = L ? (1 ? ?0) where Lq is the expected number of customers in the queue waiting for service. [2 marks] (e) Find expressions for the expected time, W, that a customer spends in the system and the expected time, Wq, that a customer spends waiting for service. [2 marks] (f ) Consider an example where customers arrive according to a Poisson process with a mean inter-arrival time of 30 minutes. Suppose that the service times are exponential with mean 40 minutes if there are no customers waiting but have mean 20 minutes if there are any customers waiting. Compute ?0, L, Lq, W and Wq. [5 marks] 5 (TURN OVER) CST.2013.8.6 5 Computer Vision (a) Consider the following 2D filter function f(x, y) incorporating the Laplacian operator that is often used in computer vision: f(x, y) = ? 2 ?x2 + ? 2 ?y2 e ?(x 2+y 2 )/?2 (i) In 2D Fourier terms, what type of filter is this? Is it a lowpass, a highpass, or a bandpass filter? Justify your answer. [2 marks] (ii) Are different orientations of image structure treated differently by this filter, and if so, how? Is it isotropic, or anisotropic? [2 marks] (iii) Approximately what is the spatial frequency bandwidth of this filter, in octaves? [Hint: the answer is independent of ?.] [2 marks] (iv) What is meant by image operations "at a certain scale of analysis?" Explain the scale parameter ?, and define a scale-space fingerprint. [2 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) 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] (d) 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] 6 CST.2013.8.7 6 Digital Signal Processing Consider the discrete system yn = X? i=0 xn?2i · ? 1 2 i (a) Write down the first 8 samples of the impulse response of this filter. [2 marks] (b) Provide the finite-difference equation of an equivalent recursive filter that can be implemented with not more than two delay elements. [4 marks] (c) What is the z-transform H(z) of the impulse response of this filter? [4 marks] (d) Where are the zeros and poles of H(z)? [6 marks] (e) We now operate this discrete system at sampling frequency fs = 1 MHz and feed it with input xn = cos(2?fn/fs). For which f (with 0 ? f ? fs/2) will the peak amplitude of the output sequence {yn} be largest, and how large will it be? [4 marks] 7 (TURN OVER) CST.2013.8.8 7 E-Commerce (a) Discuss how you would use social media to attract traffic to your website. [4 marks] (b) Discuss the difficulties in measuring the use of your website and related social media campaign. [5 marks] (c) Discuss whether the use of third party analytics creates opportunities to leak personal information. [5 marks] (d) Discuss why it is sometimes good to give things away. [6 marks] 8 CST.2013.8.9 8 Hoare Logic Use notation from logic (?, ?, etc.) in your answers to the questions below. (a) Define the semantics of the partial correctness Hoare triple, {P} C {Q}. Briefly explain this definition. [3 marks] (b) Define the semantics of the total correctness Hoare triple, [P] C [Q]. Explain what is 'total' about total correctness. [3 marks] (c) State an inference rule for partial correctness Hoare Logic that is not sound in total correctness Hoare Logic. Explain your choice. [3 marks] (d) State and briefly explain the semantics of the separation logic Hoare triple. Point out at least two differences between {P} C {Q} in traditional Hoare logic and separation logic. [5 marks] (e) Carefully state an inference rule that is part of separation logic but not present in traditional Hoare logic. [3 marks] (f ) Point out at least two aspects in which the semantics of Hoare logic or separation logic do not reflect the semantics of real programming languages. [3 marks] 9 (TURN OVER) CST.2013.8.10 9 Information Retrieval Question Answering (QA) is the task of building a system that can select answer strings from a corpus, in response to a natural language question. (a) Mean Reciprocal Rank (MRR) has been used for several years by the TREC QA organisers as the main evaluation metric. Give the formula for MRR, and state two disadvantages of this method. [4 marks] (b) The Microsoft system competing in the TREC-10 conference (QA track) used an unusual approach for Question Answering (QA). Give a brief overview of how the system works. [4 marks] (c) Describe in detail, with an example, how the Microsoft system generates query strings and scores answers. [6 marks] (d) Consider the following question answer pair from the official TREC QA corpus: Question: Who killed Abraham Lincoln? Answer: John Wilkes Booth is perhaps America's most infamous assassin. He is best known for having fired the bullet that ended Abe Lincoln's life. Can the Microsoft system as described in part (b) be awarded a point in the TREC competition for finding this answer? If yes, describe how and under which conditions. If no, describe changes to the system in part (b) that would make it possible to do so. [6 marks] 10 CST.2013.8.11 10 Principles of Communications The Internet makes use of distributed route computation algorithms such as link-state, distance-vector, and path-vector schemes. When these were designed and implemented in the early days, there was little information about the possible future statistical properties of the topology of the Internet. Since then, measurements show that the way the network has evolved has led to highly clustered, and possibly small-world characteristics in the graph representing the topology. In this situation, how might you choose to design your routing system, and furthermore how might the topology impact how you choose to represent the graph for the purposes of a link-state or distance-vector computation, and for forwarding? [20 marks] 11 (TURN OVER) CST.2013.8.12 11 Quantum Computing Let a0a1 be the two-bit representation of a ? {0, 1, 2, 3}. We define the 2-bit Boolean function fa by: fa(x0, x1) = (a0 · x0) ? (a1 · x1). where · denotes Boolean and and ? represents exclusive or. For each such function f, let Uf denote the 3-qubit unitary operator that computes f in the sense that: Uf |x0x1yi = |x0x1i|y ? f(x0, x1)i. In the following, H?n denotes the n-bit Hadamard operator. (a) Show how Uf2 can be implemented with the use of C-NOT gates. [3 marks] (b) Show that: (H ?2C-NOTH ?2 )|xyi = C-NOT|yxi. [3 marks] (c) Using (b) or otherwise, show that for each of the four possible values of a, the operator (H?3UfaH?3 ) can be implemented as a circuit using only C-NOT gates. [6 marks] (d) Given a black box implementing Ufa for an unknown value of a, show that we can construct a quantum circuit that determines the value of a with certainty, using the black box only once. [Hint: Consider the circuit from (c) applied to a suitable computational basis state.] [8 marks] 12 CST.2013.8.13 12 Security II The RSA public-key crypto system performs calculations in the group Zn, with n = pq being the product of two large prime numbers p and q. The public key consists of the tuple (n, e), with gcd(?(n), e) = 1, and the corresponding private key is (n, d). A message m ? Zn is encrypted via c = me mod n and decrypted as m = c d mod n. (a) Given p, q, and e, how can you apply the extended Euclidian algorithm to find a suitable d? [6 marks] (b) If we modified RSA to use as the public modulus a prime number instead of a composite of two large prime numbers, that is n = p instead of n = pq, would this affect its security, and if so how? [4 marks] (c) In the UltraSecure virtual-private network, each router knows of each of its remote communication peers the RSA public key (n, e), which all have e = 3 and 21023 ? n < 2 1024. If router alice needs to establish a shared 256-bit AES secret key k with remote