A network based service manages persistent objects. The service must enforce an access control policy to protect the objects. (a) Discuss how this access control might best be implemented for the following example of objects and policy components: Objects: Files in a University Department's file service, operating behind a firewall. Policy: The owner may specify read, write and execute rights in terms of principals and groups. [4 marks] (b) Discuss how this access control might best be implemented for two of the following examples: (i) Objects: Files in a commercial, distributed, Internet-based file service. Policy: The owner may authorise other principals to download the file. (ii) Objects: Sales data relating to a company. Policy: Those employed in the Sales Departments of all branches of the company worldwide may read the data. (iii) Objects: Electronic health records (EHRs) in a nationwide service. Policy: The owner (patient) may read from its own EHR. A qualified and employed doctor may read and write the EHR of a patient registered with him/her. (iv) Object: The solution to online coursework. Policy: The coursework setter has read and write access. A candidate has no access until after the marks have been published.

(a) Describe the way in which a problem should be represented in order to allow its solution using a heuristic search technique. [5 marks] (b) Define what it means for a search algorithm to be complete, and to be optimal. [2 marks] (c) Define what it means for a heuristic function to be admissible, and to be monotonic. [2 marks] (d) Describe the operation of the A? heuristic search algorithm. [5 marks] (e) Prove that the A? heuristic search algorithm is optimal when applied in conjunction with a monotonic heuristic. State the conditions under which the algorithm is also complete, and explain why this is the case. [6 marks] 9 Database Theory (a) Define formally the semi-structured data (SSD) model. [5 marks] (b) Show how SSD expressions can be expressed in XML. [2 marks] (c) What are the main differences between the SSD and XML models? [2 marks] When viewed graphically, simple SSD expressions denote trees. Consider a variant, d-SSD, where the edges emanating from any node in the tree must have a unique label, but where the labels may themselves be d-SSD expressions. (You may disregard object identities (oids); hence d-SSD expressions always denote trees.) (d) Define the syntax of d-SSD expressions. [3 marks] (e) Give a d-SSD expression to represent the following: (i) the array ["Do","Re","Mi"]; (ii) the set {11, 52, 44}; (iii) the bag {{10, 10, 13, 42, 13, 10}}. [1 mark each] (f ) Define the syntax for path expressions in the d-SSD model.

(a) Consider a binary symmetric communication channel, whose input source is the alphabet X = {0, 1} with probabilities {0.5, 0.5}; whose output alphabet is Y = {0, 1}; and whose channel matrix is 1 1 where is the probability of transmission error. (i) What is the entropy of the source, H(X)? [2 marks] (ii) What is the probability distribution of the outputs, p(Y ), and the entropy of this output distribution, H(Y )? [2 marks] (iii) What is the joint probability distribution for the source and the output, p(X, Y ), and what is the joint entropy, H(X, Y )? [2 marks] (iv) What is the mutual information of this channel, I(X; Y )? [2 marks] (v) How many values are there for for which the mutual information of this channel is maximal? What are those values, and what then is the capacity of such a channel in bits? [2 marks] (vi) For what value of is the capacity of this channel minimal? What is the channel capacity in that case? [2 marks] (b) A variable length, uniquely decodable code which has the prefix property, and whose N binary code word lengths are n1 n2 n3 nN must satisfy what condition on code word lengths? (State the condition, and name it.) [3 marks] (c) You are asked to compress a collection of files, each of which contains several thousand photographic images. All images in a single file show the same scene. Everything in this scene is static (no motion, same camera position, etc.) except for the intensity of the five light sources that illuminate everything. The intensity of each of the five light sources changes in completely unpredictable and uncorrelated ways from image to image. The intensity of each pixel across all photos in a file can be described as a linear combination of the intensity of these five light sources. (i) Which one of the five techniques discrete cosine transform, -law coding, 2-D Gabor transform, Karhunen-Lo`eve transform and Golomb coding would be best suited to remove redundancy from these files, assuming your computer is powerful enough for each?

Assume that a program consists of a sequence of declarations Object o; where o is an object name, followed by a sequence of function definitions f(x1, . . . , xk) = e where expressions, e, have syntax e ::= n | o | x | f(e1, . . . , ek) | let x = e1 in e2 | if e1 then e2 else e3. where n ranges over integer constants and x over variables (which may contain integers or object references). Variables may not contain function values. Alias Analysis is a technique which will determine that, during evaluation of e within let x = o in let y = o in e x and y alias because they are both references to the same object o. (a) Show how to associate a flow variable with each variable and (sub-)expression of the program. State the values which flow variables might reasonably take in such an analysis. [4 marks] (b) Show how, given a program, we can generate a set of constraint-style equations (analogously to control-flow analysis for -expressions) whose solution gives a superset of the values which might be returned from each (sub-)expression of the program. [Hint: suppose that each function definition has flow variables representing the value ranges of each of its arguments and of its result.] [8 marks] (c) Explain what happens in, and give modifications to part (b) for, the generalisation whereby variables can also reference functions and be called by the syntax e ::= e0(e1, . . . , ek) [4 marks] (d) Explain how you would respond to the criticism that your analysis may fail to terminate if your language is extended with arithmetic expressions because a single expression may give rise to an infinite set of values. [2 marks] (e) Briefly describe any optimisation whereby knowing that x and y cannot alias is necessary for the optimisation to be safe.

(a) Why is the performance of current face recognition algorithms so poor? Address both what makes the problem domain intrinsically so challenging, and the shortcomings of the strategies adopted in the design of current algorithms. Comment on possible directions for improving performance. [8 marks] (b) For what size of filter kernel does it become more efficient to perform convolutions by instead computing Fourier Transforms, and why? [2 marks] (c) For an aligned stereo pair of cameras separated by base distance b, each with focal length f, when a target point projects outside the central axis of the two cameras by amounts and : (i) What is the computed target depth d? [2 marks] (ii) Why is camera calibration so important for stereo vision computations? [1 mark] (iii) Identify four relevant camera degrees-of-freedom and briefly explain their importance for stereo vision algorithms. [2 marks] (d) What does the Spectral Co-Planarity Theorem assert about translational visual motion, and how the parameters of such motion can be extracted? [2 marks] (e) What information about the shape and orientation of an object can be inferred, and how, from the extraction of texture descriptors; and what is the role of prior assumptions in making such inferences?

A context free grammar for a fragment of English is shown below: S -> NP VP NP -> Det N N -> N N VP -> rumbles, rusts Det -> the, a, every N -> bus, car, train, park, airport, station (a) Show the parse trees for the two parses that the grammar assigns for sentence S1. S1: the train station bus rumbles [3 marks] (b) Give an algorithm for a bottom-up passive chart parser without packing. Illustrate your answer by showing the edges constructed when parsing sentence S1. [11 marks] (c) Describe how this algorithm could be modified so that edges may be packed, illustrating your answer by considering sentences S1 and S2. What effect does packing have on parsing efficiency? S2: the airport car park bus rumbles

(a) Describe an algorithm to find the intersection point between an arbitrary ray and an arbitrary plane. [5 marks] (b) Explain how a plane can be used as a Computational Solid Geometry (CSG) primitive. [2 marks] (c) List the three binary operations used in CSG. Explain how a CSG object can be represented as a binary tree. Describe an algorithm to find the first intersection point between a ray and an arbitrary CSG object. Assume that there are already algorithms which you can use to find the intersection points between the ray and each type of CSG primitive. Ensure that you state any assumptions you make about the information provided to you by these rayprimitive intersection algorithms. [8 marks] (d) Derive the NURBS basis function N4,4 for the knot vector [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 10]. [5 marks] 7 Digital Communication II (a) Multicast Addressing and Routing provides a set of mechanisms for senders to transmit packets that are replicated by the routers so that they can be received by multiple systems. Explain how the basic mechanisms of IGMP, reverse path forwarding based on the underlying unicast routes, pruning and grafting, fit together to create this network service. [8 marks] (b) How might IP multicast be a risk for a network provider? [2 marks] (c) The Resource Reservation Protocol, RSVP, is a receiver oriented signalling protocol to establish state in routers for the purposes of classifying packets into flows and scheduling those flows onto routers. Explain what is meant by "receiver oriented", and how this enables RSVP to be used by a multicast (many-to-many) application. [5 marks] (d) Why is TCP not going to work well with multicast?

(a) Give brief definitions of the following terms: (i) referring expression; (ii) cataphora; (iii) pleonastic pronoun. [6 marks] (b) Describe the Lappin and Leass algorithm for pronoun resolution, illustrating its operation on the text below. Exact weights for salience factors are not required. Owners love the new hybrid cars. They all say that they have much better fuel economy than conventional vehicles. And it seems that the performance of hybrid cars matches all expectations. [14 marks] 15 Denotational Semantics (a) Show that any continuous function h : D D on a domain D has a least prefixed point fix(h). [5 marks] (b) Let f : D E D and g : D E E be continuous functions where D and E are domains. The continuous function hf, gi : D E D E, acts so that (d, e) 7 (f(d, e), g(d, e)). Bekic's theorem states that the least fixed point of hf, gi is the pair ( d, e) where d = fix(d. f(d, e)) where e = fix(e. g(fix(d. f(d, e)), e)) . You are asked to show Bekic's theorem in the following stages. Write (d0, e0) for the least fixed point of hf, gi. (i) Show that ( d, e) is a fixed point of hf, gi. Deduce that (d0, e0) v ( d, e). [5 marks] (ii) Show the converse, that ( d, e) v (d0, e0).

Write program that reads a sequence of integers into an array and that computes the alternating sum of all elements in the array. Write Java program that reads a 1D array of integers from standard input and returns it. Write program that prompts the user to read two integers and displays their sum. Your program should prompt the user to read the number again if the input is incorrect.

: Write program that first gets a list of six integers from input. The first five values are the integer list. The last value is the upper threshold. Then output all integers less than or equal to the threshold value

(a) If you had been one of the original inventors of the WIMP interface, and engineers on the technical team had been sceptical about the advantages that it would bring, then: (i) What two pieces of empirical evidence could you have presented to sceptics to help convince them? [2 marks] (ii) Describe the technique that you would use to collect data for each of these. [4 marks] (iii) Describe the technique that you would use to analyse each of those data sets. [4 marks] (b) If you were the HCI researcher on a speech interaction project intended to replace the WIMP interface, then (i) Which of the techniques described above would be most relevant to your work? Why? [3 marks] (ii) Explain how a modern analytic evaluation method could give design guidance to the team, including a description of how the analysis would be conducted, and two design improvements that might result from that analysis.

(a) Sketch designs for an n-input NAND gate in CMOS using (i) static CMOS; (ii) dynamic CMOS; (iii) pseudo-nMOS. [2 marks each] (b) Assuming that a conducting p-channel has a resistance times that of a similarly sized n-channel, annotate each of your circuit diagrams with suitable widths for the transistors, and explain the reasons for their values. [2 marks each] (c) For each design, calculate the logical effort and the parasitic delay. [2 marks each] (d) Which is likely to be fastest for the case when n = 4 and = 3? What difference would it make if the circuit were driving a large capacitative load?

Consider a database with one binary relation B. (a) Write programs in stratified Datalog for the following queries: (i) Give the set of elements x for which there are fewer than three elements y such that B(x, y). [3 marks] (ii) Give the set of elements x such that there is no path (in the graph formed by B) from x back to itself. [3 marks] (iii) Give the set of elements x such that B(x, y) for every y. [3 marks] (b) Which of the queries defined in part (a) is: (i) safe? [3 marks] (ii) domain independent? [4 marks] (iii) monotone? [4 marks] In each case, justify your answer fully. 10 Types Let be a type variable and let range over type variables distinct from . The subsets of polymorphic lambda calculus (PLC) types that are positive (ranged over by ) and negative (ranged over by ) in are defined by the following grammar: ::= ( ) | | | ::= () | | (a) Give inductive definitions, following the structure of the grammar above, of closed PLC terms P for each positive type , and N for each negative type , such that ` P : 1, 2((1 2) ( [1/] [2/])) ` N : 1, 2((1 2) ([2/] [1/])) [12 marks] (b) Now let be the type (( ) ), which is positive in . Calculate the beta-normal form of P .

Suppose that bus inter-arrival times, X, at a given bus stop have a probability density function fX(x) with mean = E(X) and variance 2 = Var(X) = E(X2 ) 2 . Suppose that a randomly arriving customer arrives during a bus inter-arrival interval of length Y and suppose that the probability density of Y is fY (y). It may be assumed that fY (y) = CyfX(y) for some constant C. (a) Derive an expression for the constant C in terms of and 2 . [7 marks] (b) Derive an expression for the average waiting time as seen by a randomly arriving customer. [7 marks] (c) For each of the following cases, calculate the average waiting time as seen by a randomly arriving customer. (i) X is deterministic taking a value of 10. [2 marks] (ii) X is exponentially distributed with mean = 10. [2 marks] (iii) X has a general distribution with mean = 10 and variance 2 = 500.