Give Correct ANSWERS

Human-Computer Interaction (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. [7 marks] 2 CST.2004.9.3 2 VLSI Design (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? [2 marks] 3 [TURN OVER CST.2004.9.4 3 Optimising Compilers 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. [2 marks] 4 CST.2004.9.5 4 Distributed Systems 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. [8 marks each] 5 Advanced Systems Topics (a) Describe the DHT algorithms that are used in each of CAN and Pastry to route a request for content to the node that holds that content. [5 marks each] (b) CAN and Pastry include mechanisms to reduce the latency of search. Describe how each of these works, and discuss their relative complexity and performance. [5 marks each] 5 [TURN OVER CST.2004.9.6 6 Advanced Graphics (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? [3 marks] (e) What is philosophically odd about using TCP with RSVP? [2 marks] 6 CST.2004.9.7 8 Artificial Intelligence In the following, N is a feedforward neural network architecture taking a vector x T = ( x1 x2 xn ) of n inputs. The complete collection of weights for the network is denoted w and the output produced by the network when applied to input x using weights w is denoted N(w, x). The number of outputs is arbitrary. We have a sequence s of m labelled training examples s = ((x1, l1),(x2, l2), . . . ,(xm, lm)) where the li denote vectors of desired outputs. Let E(w; (xi , li)) denote some measure of the error that N makes when applied to the ith labelled training example. Assuming that each node in the network computes a weighted summation of its inputs, followed by an activation function, such that the node j in the network computes a function g

w (j) 0 + X k i=1 w (j) i input(i) ! of its k inputs, where g is some activation function, derive in full the backpropagation algorithm for calculating the gradient E w = E w1 E w2 E wW T for the ith labelled example, where w1, . . . , wW denotes the complete collection of W weights in the network. [20 marks] 7 [TURN OVER CST.2004.9.8 9 Database Theory 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 . [8 marks] 8 CST.2004.9.9 11 Computer Vision (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? [3 marks] 9 [TURN OVER CST.2004.9.10 12 Numerical Analysis II (a) A Riemann integral over [a, b] is defined by Z b a f(x) dx = limn 0 Xn i=1 (i i1)f(xi) . Explain the terms Riemann sum and mesh norm. [4 marks] (b) Consider the quadrature rule Qf = 3h 8 [f(a) + 3f(a + h) + 3f(a + 2h) + f(a + 3h)] 3f (4)()h 5 80 . If [a, b] = [1, 1] find 0, 1, . . . , 4 and hence show that this is a Riemann sum. [3 marks] (c) Suppose R is a rule that integrates constants exactly over [1, 1], and that f(x) is bounded and Riemann-integrable over [a, b]. Write down a formula for the composite rule (n R)f and prove that limn (n R)f = Z b a f(x) dx [6 marks] (d) What is the formula for (n Q)f over [a, b]? [4 marks] (e) Which polynomials are integrated exactly by Qf? Which monomials are integrated exactly by the product rule (Q Q)F when applied to a function of x and y? [3 marks] 10 CST.2004.9.11 13 Specification and Verification II (a) Discuss when it is appropriate to use theorem proving and when it is appropriate to use model checking for formal verification. Give an example to illustrate when theorem proving would be used, and also one in which model checking would be best. [8 marks] (b) Consider the device shown below: 1 2 3 4 in out It is assumed that 1, 2, 3, 4 constitute a four-phase clock satisfying (i) and (ii), and that the device has the property (iii), where: (i) At all times exactly one of 1, 2, 3, 4 is true. (ii) If i is true at time t then (if i < 4 then i+1 else 1) will be true at time t+1. (iii) If 1, 2, 3, 4 satisfy (i) and (ii) above, and if 1 is true at time t then the value at out at time t+3 will equal the value input at in at time t+1. Express assumptions (i) and (ii) and property (iii) both in higher order logic and in temporal logic. [4 marks each] 11 [TURN OVER CST.2004.9.12 14 Natural Language Processing (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). [10 marks] 12 CST.2004.9.13TLBs and caches are examples of content-addressable memories (CAMs). (a) What is the principal difference between a CAM and a RAM? [4 marks] (b) What is the difference between fully associative, set associative and direct mapped lookup? [6 marks] (c) Why are TLBs always much smaller than caches? [4 marks] (d) Which of the lookup mechanisms in part (b) is usually used for a TLB and why aren't the other mechanisms usually used? [6 marks] 2 CST.2004.10.3 3 Foundations of Programming A Java program is being developed to assist with the processing of examination marks. A test program begins as follows: public class Exam { private static Mark[] question = {new Mark(8), new Mark(), new Mark(6), ... The program makes use of a class Mark which begins: class Mark { public boolean attempted; public int score; ... The Mark array question has one entry for each candidate so the length of the array indicates the total number of candidates. An entry such as new Mark(8) sets up a Mark object whose data field attempted is set to true and whose data field score is set to 8, indicating that the candidate attempted the question and was awarded 8 marks. It may be assumed that every score is an integer in the range 0 to 10 inclusive. An entry such as new Mark() sets up a Mark object whose data field attempted is set to false (and whose data field score is arbitrary) indicating that the candidate did not attempt the question. (a) Supply suitable constructors for class Mark [4 marks] (b) Write two methods int getCount() and double getMean() which, when handed the actual argument question, return the number of candidates who attempted the question and the mean mark achieved by those candidates respectively. If no candidates attempted the question, getMean() should return -1d. [9 marks] (c) Write a method int[] getRank() which begins: private static int[] getRank(Mark[] q) { int[] rank = {0,0,0,0,0,0,0,0,0,0,0}; This method should return the int array rank with each element rank[i] set to the number of candidates who scored more than i marks. Note that if the maximum score is 9 then both rank[9] and rank[10] will be zero and rank[8] will be the number of candidates who scored 9. [7 marks] 3 [TURN OVER CST.2004.10.4 4 Data Structures and Algorithms (a) Describe how the Lempel Ziv text compression algorithm works, illustrating your answer by deriving the sequence of numbers and corresponding bit patterns it would generate when applied to a string starting with the following 24 characters: ABCDABCDABCDABCDABCDABCD ... You may assume that the initial table is of size 256 (containing bytes 0 to 255) and that the codes for "A", "B", "C" and "D" are 65, 66, 67 and 68, respectively. [12 marks] (b) Estimate how many bits the algorithm would use to encode a string consisting of 1000 repetitions of the character "A". [8 marks] 5 Comparative Programming Languages (a) Discuss to what extent a programmer can expect a program that conforms to a standard to generate identical results when run under different conforming compilers on different machines. [6 marks] (b) ALGOL 60 provided call by value and call by name, Pascal provided call by value and call by reference, and ALGOL-W provided a variety of calling methods including call by result and call by value-result. Briefly describe the calling mechanisms just mentioned and discuss why most modern programming languages provide only call by value. [8 marks] (c) Discuss the reasons why languages such as Fortran, Algol and PL/I designed in 1950s and 1960s are less widely used than languages designed in the last 20 years. [6 marks] 4 CST.2004.10.5 6 Operating System Foundations (a) Describe a scheduling algorithm with the following properties: favours I/O-intensive processes responds dynamically when processes change their behaviour: e.g. enter a compute-bound or I/O-intensive phase has acceptable context switching overhead avoids indefinite overlook (starvation) of a process [7 marks] (b) In order to carry out its functions, a filing system holds metadata on each stored object. (i) What is this metadata likely to comprise? [6 marks] (ii) Describe the directory service functions of a filing system, including how the metadata is used. [7 marks] 7 Numerical Analysis I (a) For Single Precision in the IEEE binary floating-point standard (IEEE 754) the precision is defined as 24, and the exponent requires 8 bits of storage. With reference to IEEE Single Precision, explain the terms exponent, significand, precision, sign bit, normalised number, denormal number. [6 marks] (b) Explain the term hidden bit. What are the values of the hidden bit for normalised and denormal numbers? How is the exponent stored and why? How are the exponent, significand and sign bit arranged in memory? [4 marks] (c) Let x denote the floating-point representation of a number x. Define the terms absolute error (x) and relative error (x) in representing x. How are x and x related? Define machine epsilon (m). [3 marks] (d) Assume x = y = z = m. Using worst-case analysis, estimate xy, xy. Find an expression for w where w = z xy. [4 marks] (e) Working to 4 significant decimal digits only, compute w when x = 2.018, y = 2.008, z = 4.058. Given m ' 0.5 103 , how many significant decimal digits of w can be relied on? [3 marks] 5 [TURN OVER CST.2004.10.6 8 Mathematics for Computation Theory Let A, B, C be sets. Define the Cartesian product (A B) and the disjoint union (A + B). [3 marks] Let f (AB), g (B C) be relations between A and B, B and C respectively. Define the inverse relation f 1 between B and A and the product relation (f g) between A and C. [3 marks] What conditions must be satisfied for the relation f to be a function f : A B? [2 marks] Write (A B) for the set of all functions from A to B. If A, B are both finite, |A| = a, |B| = b, how many elements are there in (A B), (A + B), (A B)? [2 marks] If f and f 1 are both functions, we say that f is a bijection, and we write A = B. If A, B are both finite and f : A B is a bijection, prove that a = b. (?) [2 marks] Establish explicit bijections between the following pairs of sets: (a) A (B C), (A B) (A C); [3 marks] (b) (A + B) C, (A C) (B C). [4 marks] If A, B, C are all finite, verify that the cardinality condition (?) above is satisfied in each case. [1 mark] 9 Computation Theory (a) What is Turing's Thesis? [2 marks] (b) Explain the action of a Turing machine that is specified by a quintuplet description. [4 marks] (c) Define the configuration of a Turing machine at step t, and establish equations that specify the configuration of a k-symbol Turing machine at step (t + 1) in terms of the configuration at the previous step t. [6 marks] (d) Explain how you would use your equations to simulate a specific Turing machine by a register machine whose program encodes the quintuplet description. To what extent does this support Turing's Thesis? [Explicit program for a register machine is not required.] [8 marks] 6 CST.2004.10.7 10 Computer Graphics and Image Processing Describe an algorithm for performing scan conversion of a set of 3D polygons, including details of clipping, projection, and the underlying 2D polygon scan conversion algorithm. You may assume that you are given the colour of each polygon and that no lighting calculations are required. Please state any additional assumptions that you need to make. Ray tracing is not an acceptable answer to this question. [20 marks]It is proposed to store a large number of records on a disk using Larsen's method so that any lookup can be done using only one disk transfer. All the records are of length 200 bytes and each contains a 20 byte key. The data is to be held on a single disk preformatted to contain 100,000,000 sectors each of size 4096 bytes. Reading multiple consecutive sectors is regarded as a single transfer. (a) Describe Larsen's algorithm in detail and, for the records and disk specified above, state the disk block size, the signature size and the amount of main memory that you would choose to use. [10 marks] (b) Carefully estimate the maximum number of records that could reasonably be stored on the disk assuming the sizes you gave in part (a). [6 marks] (c) Discuss the advantages and disadvantages of different signature sizes. [4 marks] 2 CST.2004.12.3 2 Computer Design It is possible to design a single instruction computer (SIC). For example, the instruction Subtract and Branch on Negative is sufficiently powerful. This instruction takes the form "A,B,C,D", meaning "Read A, Subtract B, Store in C, and Branch to D if negative". If a branch is not required, the address D can be set to the next instruction in the sequence so that the next instruction will be executed regardless of whether the branch is taken or not. An assembler short form for this branchless instruction is simply "A,B,C". (a) Write fully commented SIC assembler which implements the following pseudo code: a=1; b=1; for(i=1; i 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 [6 marks] 9 [TURN OVER CST.2004.12.10 12 Complexity Theory Recall that a simple path in a graph is a path with no repeated nodes. Consider the following two decision problems: Given a graph G = (V, E), a positive integer k, source s V and a target t V , is there a simple path from s to t of length at least k? Given a graph G = (V, E), a positive integer k, source s V and a target t V , is there a simple path from s to t of length at most k? One of these problems is known to be in P while the other one is known to be NP-complete. (a) Which of the two problems is in P and which is NP-complete? [2 marks] (b) Describe a polynomial time algorithm for the problem that is in P. [6 marks] (c) Give a proof of NP-completeness for the problem that is NP-complete. You may assume the NP-completeness of any problem, such as Hamiltonian Cycle, 11 Introduction to Security (a) Explain briefly mechanisms that software on a desktop computer can use to securely generate secret keys for use in cryptographic protocols. [5 marks] (b) Give two different ways of implementing residual information protection in an operating system and explain the threat addressed by each. [5 marks] (c) Consider the standard POSIX file-system access control mechanism: (i) Under which conditions can files and subdirectories be removed from a parent directory? [2 marks] (ii) Many Unix variants implement an extension known as the "sticky bit". What is its function? [2 marks] (iii) On a POSIX system that lacks support for the "sticky bit", how could you achieve an equivalent effect? [2 marks] (d) VerySafe Ltd offer two vaults with electronic locks. They open only after the correct decimal code has been entered. The VS100 - a low-cost civilian model - expects a 6-digit code. After all six digits have been entered, it will either open or will signal that the code was wrong and ask for another try. The VS110 - a far more expensive government version - expects a 40-digit code. Users of a beta-test version of the VS110 complained about the difficulty of entering such a long code correctly. The manufacturer therefore made a last-minute modification. After every five digits, the VS110 now either confirms that the code has been entered correctly so far, or it asks for the previous five digits again. Compare the security of the VS100 and VS110. [4 marks] 7 [TURN OVER CST.2004.10.8 12 Software Engineering and Design Consider the following four documents that would have improved projects such as the Cambridge University CAPSA project or the London Ambulance Service system: (a) a plan for managing development risk; (b) a safety and reliability specification; (c) a user requirements document; (d) a test specification. Describe each of these four documents, including how you would gather the data to write the document; the main sections of the document; who must read that document; who should approve the document; and how the CAPSA and London Ambulance Service projects differ in the effect this document would have had. [5 marks each] 16 Topics in Concurrency (a) Describe the semantics of the modal -calculus. [4 marks] (b) Describe without proof the meaning of the following modal -calculus assertions: (i) Z. hciZ ; [1 mark] (ii) Z. hciZ ; [1 mark] (iii) Z. (A ([c]F hciZ)) (here F means false); [2 marks] (iv) Z. (B (A hciZ)) ; [2 marks] (v) Z. (B (A hciZ)) . [2 marks] (c) Consider the transition system consisting of two states p, q and two transitions p c q and q c p. (i) Does p satisfy Z. ([c]F (hciT hciZ)) ? (ii) Does p satisfy Z. ([c]F (hciT hciZ)) ? (Again, here F means false and T means true.) In this part you should justify your answers carefully. [8 marks]