nnep

This counts as "setting the value", even if the value does not change. If its value was last set to v 6= n less than 30 seconds ago, it leaves its value unchanged and replies false. If a client receives two or more true responses from the servers, it now holds the lease, otherwise it does not hold the lease. Discuss the strengths and weaknesses of this algorithm. What faults does it tolerate? What assumptions does it make for its correctness? How might the algorithm be improved to avoid some assumptions or weaknesses?

EDSAC (1949) was the first practical stored-program computer in operation. Although it had no subroutine jump instruction, a method for using subroutines was devised by Describe the corresponding instruction sequences that you would use in a modern processor. 5 Designing Interactive Applications Distinguish the terms needs analysis and requirements analysis. Provide an example to illustrate the difference. What is a strong requirement? Provide counter-examples and explain why each example is not a strong requirement. What role does a functional specification play in a requirements specification? Give a one-sentence example. The receptionist at a small research laboratory is required to field incoming messages and make sure that they reach the recipient in a timely manner. Some messages arrive by word of mouth, others by phone, courier, e-mail or FAX. There are about 100 recipients, most of whom are researchers. They spend a large proportion of their time in meetings of one sort or another, some of which are held in offices, the remainder in conference rooms. The receptionist endeavours to avoid interrupting important meetings unnecessarily. It is proposed to build a system based upon Active Badge technology to improve message handling activities in the laboratory. Each member of staff wears an active badge. An existing Location Server provides client applications with up-to-date information about the location and movements of each active badge. Sketch out the methods you would employ to establish the users' needs for the proposed system. Describe the categories of information you would pass on to the designer and illustrate each with one or two examples.

Consider the transformations used in the construction and rendering of a threedimensional model on a screen. (a) List the three principal transformations in the processing pipeline and explain their roles. [6 marks] (b) Why is it convenient to represent the transformations as matrices? [2 marks] (c) What are homogeneous coordinates? Explain how they are used in modelling these transformations as matrices. (d) Derive the matrix to represent a perspective transformation for a viewer at the origin of a point in three dimensions to a point on a screen in the plane z = d.

(e) Perspective in classical art has vanishing points towards which parallel lines converge. Explain mathematically why this is the case and show how to calculate the location on the screen of the vanishing point for lines in a particular direction. [5 marks] [Hint: It may be helpful to represent lines parametrically in vector form as P(s) = A + sV where V is a direction and A is any point on the line.] 4 Computer Graphics and Image Processing Consider a curve defined by polynomial parametric segments Pi(s) for i = 1, 2, . . . m that interpolates a set of points {Ai}0im in three dimensions. (a) What is meant by Ck continuity at the junction of two segments? [3 marks] (b) What is the least order of the polynomials that must be used to achieve Ck continuity at the junctions? [2 marks] (c) Derive the Overhauser formulation for a set of weighting functions w2(s), w1(s), w0(s) and w1(s) so that the cubic curve segment joining Ai1 and Ai can be expressed as Pi(s) = w2(s)Ai2 + w1(s)Ai1 + w0(s)Ai + w1(s)Ai+1 for 1 < i < m. [10 marks] (d) Extend this formulation to give a set of parametric patches Pi,j (s, t) for 1 < i < m and 1 < j < n interpolating a surface through an array of points {Ai,j}0im,0jn. [5 marks]

A full adder for a single bit has three inputs, a, b and cin, and two outputs, s and cout for the sum and carry-out. State the formulae for s and cout in disjunctive normal form. [2 marks] (b) Explain the operation of the following three approaches for handling carry in n-bit word adders, deriving formulae for the signals involved and explaining the limiting factors on their speed: (i) ripple carry, [2 marks] (ii) carry-skip with fixed-size blocks, and [6 marks] (iii) carry-skip with variable-size blocks. [4 marks] (c) Assuming a delay of for a round of combinational logic consisting of negation, conjunction and disjunction, estimate the delays for the three designs applied to a 48-bit adder. [3 2 marks] 3 Digital Communication II (a) In the context of Quality of Service (QoS) in networking, what do we mean by elastic and inelastic applications? [2 marks] (b) Give two examples of each type of application and discuss the application attributes and QoS requirements. [8 marks] (c) Discuss the problems faced by traditional Internet routers in dealing with inelastic traffic. [6 marks] (d) How do the IntServ and DiffServ architectures differ in offering QoS, and how might they be employed together to provide an end-to-end QoS? [4 marks] 3 (TURN OVER) CST.2008.9.4 4 Quantum Computing (a) The no-cloning theorem is a statement that is often said to show that a quantum state |i cannot be exactly duplicated. (i) Give a mathematically precise statement of the no-cloning theorem. [2 marks] (ii) Give a proof of the no-cloning theorem. [4 marks] (b) The quantum teleportation protocol is a means by which one party, Alice, can send a quantum state to another party, Bob, by transmitting just two classical bits, provided that the two already share an entangled 2-qubit state. Explain how the quantum teleportation protocol works, sketching any circuit that may be used. [6 marks] (c) The Deutsch-Jozsa problem assumes that we are given a function f : {0, 1} {0, 1} in the form of a quantum black box performing a unitary operation Uf : |abi 7 |a(b f(a))i. Sketch a circuit with only one use of Uf that determines whether f is constant or balanced. Explain carefully what measurement is performed and why it gives the desired result. [8 marks] 4 CST.2008.9.5 5 Artificial Intelligence II A friend of mine likes to climb on the roofs of Cambridge. To make a good start to the coming week, he climbs on a Sunday with probability 0.98. Being concerned for his own safety, he is less likely to climb today if he climbed yesterday, so Pr(climb today|climb yesterday) = 0.4 If he did not climb yesterday then he is very unlikely to climb today, so Pr(climb today|climb yesterday) = 0.1 Unfortunately, he is not a very good climber, and is quite likely to injure himself if he goes climbing, so Pr(injury|climb today) = 0.8 whereas Pr(injury|climb today) = 0.1 (a) Explain how my friend's behaviour can be formulated as a Hidden Markov Model. What assumptions are required? [4 marks] (b) You learn that on Monday and Tuesday evening he obtains an injury, but on Wednesday evening he does not. Use the filtering algorithm to compute the probability that he climbed on Wednesday. [8 marks] (c) Over the course of the week, you also learn that he does not obtain an injury on Thursday or Friday. Use the smoothing algorithm to compute the probability that he climbed on Thursday. (a) Explain how to simulate a physical system consisting of point masses and springs using the Euler method. [5 marks] (b) Explain the problems exhibited by the Euler method and describe an alternative that gives a better solution. [5 marks] (c) State and explain the radiosity equation. [4 marks] (d) Compare and contrast the following ways of solving the radiosity equation: matrix inversion, gathering, shooting. [6 marks] 8 Specification and Verification II (a) Explain how the structure of circuits can be represented in logic. Discuss the role of quantifiers and of higher-order functions and relations. [8 marks] (b) Show how a predicate characterising the set of reachable states of a transition relation can be defined in higher-order logic. [4 marks] (c) Write down formulae in both Computation Tree Logic (CTL) and Linear Temporal Logic (LTL) that are true whenever a property P holds of all reachable states. Define the semantics of any temporal operators that you use. [8 marks] 7 (TURN OVER) CST.2008.9.8 9 Natural Language Processing The following shows a simple context-free grammar (CFG): S -> NP VP NP -> Kim NP -> Sandy NP -> Det N N -> pudding N -> N S Det -> the VP -> V V -> likes V -> stinks V -> believes VP -> V NP VP -> V S (a) Give a parse tree (or trees) to show the analysis this grammar assigns to the following: the pudding Kim believes Sandy likes stinks [3 marks] (b) What is meant by the term overgeneration? Why might overgeneration be a problem when using a grammar for parsing grammatical text? [3 marks] (c) The grammar shown above does not allow for different subcategorization properties of verbs. Assume that the following sentences should all be ungrammatical: Kim likes Kim stinks the pudding the pudding Kim stinks stinks the pudding Kim likes Sandy stinks Assuming the simple CFG formalism, show how the grammar above could be modified to exclude such sentences while still admitting strings such as the one in part (a).

(a) The relational schema R(A, B, C, D, E) has the following functional dependencies. A E B D A, B C Decompose this into a set of relations in BCNF. Show your working. [5 marks] (b) By inspecting your answer to (a), describe a possible interpretation in the language of Entity-Relationship modelling. [5 marks] (c) Heath's Rule tells us that if R(A, B, C) is a relational schema with functional dependency A B, then R = A,B(R) A A,C(R). This rule is often applied in the relational decomposition process that seeks to arrive at relations in a particular normal form. For example, we might decompose R into two implemented relations R1(A, B) and R2(A, C). Some people have been very critical of this approach since it ignores the fact that the implementation of such a decomposition is normally associated with foreign key constraints between tables. What is missing? Can you express, in the relational algebra, what such a missing constraint might look like for the decomposition described above using Heath's rule? Justify your answer. [5 marks] (d) Using your answer to (c), discuss which constraints might be missing from your decomposition in question (a).

Many modern architectures have provision for only 32-bit values in registers. However, ANSI C requires code such as extern void g(int); extern void f(int x) { char c = x; c += 1; g(c); } to have the effect that a call to f() causes g() to receive a parameter value as though c were stored in memory, i.e. in the range CHAR MIN to CHAR MAX. You may assume that char holds 8-bit values and the range is either -128..127 or 0..255. While this example clearly requires range reduction following the incrementation of c, it is claimed that this is not always necessary. One brutal technique to allocate char variables to registers is to treat them as int variables and achieve ANSI C conformance by range reduction just before each reference in the same manner that load-byte hardware might. Develop an optimisation technique which might reduce the amount (static or dynamic) of such range reduction in code like: extern char p(int v[100]) { unsigned char r = 0; int i; for (i=0; i<100; i++) r = (r<<1 ^ r) + v[i]; return (r & 128) != 0; } Little credit will be given for mere hand-compilation. [20 marks] Hints: 1. Consider similarities to live variable analysis. 2. Consider whether register reads or writes occur more often.

1.Write program in C++ to print a welcome text in a separate line.

2. Write program in C++ to print the sum of two numbers

3. Write program in C++ to find Size of fundamental data types.

A sliding-tile puzzle consists of three black tiles, three white tiles and an empty space, thus: B1 B2 B3 W1 W2 W3 There are three legal ways of moving a tile, each with an associated cost: slide into the adjacent empty location cost 1 jump over one tile into the empty location cost 1 jump over two tiles into the empty location cost 2 The goal is to have all the white tiles to the left of all the black tiles and to achieve this at minimum cost. The final position of the empty space is not important. (a) Represent the problem using the following knowledge representation schemes: (i) production system rules [5 marks] (ii) a semantic network [5 marks] In one sentence, describe the different emphases of these two schemes. [1 mark] (b) State two possible heuristics to help solve this problem. [2 marks] (c) For a planner to solve this puzzle, what operators (i.e. planning actions) would be needed? [7 marks] 8 Database Topics Explain the ways in which the data modelling concepts 'IS-A', 'IS-PART-OF' and 'IS-AN-INSTANCE-OF' have been addressed in database design methodology. Your discussion should include the network, relational and functional data models, as well as object-oriented databases.

Describe the main differences between formal languages (such as logics or programming languages) and a natural language (such as English). [8 marks] What different requirements do these differences place on techniques for (a) syntactically parsing (b) semantically interpreting

You are to write a Java program. Its main class should be called Replicate and its behaviour is to be that the following two sequences of Unix commands must result in exactly the same text appearing on your terminal: 1. cat Replicate.java 2. javac Replicate.java java Replicate in other words the output from the program should be identical to its own source. Your code is not permitted to inspect the file system, so items along the lines of ... new InputStream(new File("Replicate.java")) ... are prohibited. Your code is expected to be reasonably neatly laid out and must contain at least one comment! Credit will be given for code brevity and for inclusion of a clear explanation of how your code works. [20 marks] [Hint: it is very probable that your code will consist of two rather similar sections. One will be data and the other executable code. They will be such that the code can print the data out in two different ways: once to re-create itself and a second time to re-create the code.] 8 CST.2003.1.9 SECTION E 11 Operating Systems (a) Describe, with the aid of diagrams where appropriate, how Unix implements and manages: (i) a hierarchical name space for files; [2 marks] (ii) allocation of storage on disk; [2 marks] (iii) file-system and file meta-data; [8 marks] (iv) pipes. [4 marks] (b) A system administrator decides to make a 'versioned' file-system in which there are a number of directories called /root-dd-mm-yyyy, each of which holds a copy of the file-system on day dd, month mm and year yyyy. The idea is that at any particular time only the most recent snapshot will be used as the 'real' filesystem root, but that all previous snapshots will be available by explicitly accessing the directory in question. In this way the system administrator hopes to allow resilience to mistaken edits or unintentional deletions by users, or to hardware problems such as a disk head crash. To implement this, the system administrator arranges for a program to run every morning at 01:00 which recursively 'copies' the current snapshot to the new one. However to save disk space, hardlinks are used in place of actual copies. Once the 'copy' is complete, the new snapshot is used as the new root. To what extent will this scheme provide the functionality the system administrator hopes for? What advantages and disadvantages does it have?