State carefully, with proof, the compositionality, soundness, and adequacy results for PCF. [6 marks] (ii) Define the notion of contextual equivalence in PCF. [2 marks] (You need not describe the syntax and the operational and denotational semantics of PCF.) (b) Show that for all types and closed terms M and M0 of type , if [[M]] and [[M0 ]] are equal elements of the domain [[ ]] then M and M0 are contextually equivalent. [4 marks] (c) Consider the following closed PCF terms of type nat bool nat: F0 = fn x : nat. fn y : bool. x F1 = fix fn f : nat bool nat. fn x : nat. fn y : bool. if zero(x) then 0 F2 = fn x : nat. fn y : bool. if y then x else x State whether or not F1 and F2 are contextually equivalent to F0. Justify your answers. [4 marks each]

Do any special issues arise if an exception is to be used as a way of exiting through multiple layers of procedures, for instance if the exception will be activated from deep within a nest of calls of a pair of mutually recursive methods? [10 marks] There are Java classes (each with a constructor) called File, FileInputStream, InputStreamReader. In the last of these there is a method read() which returns the integer code of the next Unicode character from the stream it represents. All the IO functions can raise Write code that counts the number of characters and lines in a file and displays those to System.out. [10 marks] 5 [TURN OVER CST.99.1.6 10 Programming in Java In the Discrete Mathematics course you learned that RSA encryption involved having a public key (N, e) where N is the product of two secret primes P and Q and e is an exponent. To encrypt a message that is represented by a number m you just compute me mod N. The Java BigInteger class contains (among others) methods called add, subtract, multiply, divide and remainder. The class String has a method charAt that allows you to extract a character at a given position, and length to tell you how long the string is. Casting a character to an integer yields its character code. Supposing you are given a BigInteger that represents N and an integer for e, and not using any built-in Java methods for raising numbers to powers, write code that (a) takes a string and encodes it as an integer; if the string contains characters c0, c1 . . . the integer required will be c0 + Kc1 + K2 c2 + with the constant K set to 216 so that the full Unicode character set can be accommodated; [7 marks] (b) encodes this number (assuming it is less than N) using the RSA method; [7 marks] (c) creates an encoded string by viewing the integer as if it was written d0 +Ld1 + L 2 d2 + with L = 26 and then representing each d1 as a lower-case letter so that the 26 possible values are all accounted for. [6 marks] 6 CST.99.1.7 SECTION E 11 Operating Systems Most operating systems provide each process with its own address space by providing a level of indirection between virtual and physical addresses. Give three benefits of this approach. [6 marks] Are there any drawbacks? Justify your answer. [2 marks] A processor may support a paged or a segmented virtual address space. (a) Sketch the format of a virtual address in each of these cases, and explain using a diagram how this address is translated to a physical one. [8 marks] (b) In which case is physical memory allocation easier? Justify your answer. [2fits of the segmented approach. [2 marks] 12 Operating Systems File systems comprise a directory service and a storage service. What are the two main functions of the directory service? [2 marks] What is a directory hierarchy? Explain your answer with the aid of a diagram. [2 marks] What information is held in file meta-data? [4 marks] What is a hard link? Does file system support for hard links place any restrictions on the location of file meta-data? [2 marks] What is a soft (or symbolic) link? Does file system support for soft links place any restrictions on the location of file meta-data? [2 marks] Describe with the aid of a diagram a Unix inode. You should explain the motivation behind indirect blocks, and how they are used when accessing a file.

How might you investigate this, and how could you communicate your findings to the development team? [2 marks] (b) A study of the system data logs shows two surprising patterns of behaviour. Some users repeatedly enter different values and then change them, apparently trying out the results. The other pattern includes long pauses between entering each piece of data, with the same users accessing help and documentation pages in alternation with data entry pages. (i) How might you account for these two patterns? [4 marks] (ii) What usability analysis procedures might you carry out to improve usability of the system for these two classes of user? [4 marks] (iii) What improvements might be experienced by each class as a result? [4 marks] (c) After the project has begun, it is decided that the new design should also support two further classes of user: those who do not want to make a tax return online, but simply need to find out what paper documents to request, and staff within the tax office who need to use the system to review people's tax returns when the taxpayer rings up with a telephone enquiry. What usability analysis procedures might you use when customising the user interface for these classes of user, and what improvements might they experience as a result? [6 marks] 10 CST.2009.7.11 11 Information Theory and Coding (a) Let X and Y be discrete random variables over state ensembles {x} and {y} having probability distributions p(x) and p(y), conditional probability distributions p(x|y) and p(y|x), and joint probability distribution p(x, y). Using only these quantities, provide expressions for each of the following: (i) The joint uncertainty H(X, Y ) about both random variables. [2 marks] (ii) The uncertainty H(X|y = bj ) about random variable X once it is known that variable Y has taken on a particular value y = bj . [2 marks] (iii) The average uncertainty H(X|Y ) remaining about random variable X when Y is known. [2 marks] (iv) The mutual information I(X; Y ) between random variables X and Y . (Your answer can use expressions you have defined above.) [2 marks] (v) The union of H(X|Y ), I(X; Y ), and H(Y |X). [2 marks] (b) A noisy binary communication channel randomly corrupts bits with probability p, so its channel matrix is: 1 p p p 1 p (i) If the input bit values {0, 1} are equiprobable, what is the mutual information between the input and output for this noisy channel? [2 marks] (ii) What is the channel capacity of this noisy channel? [1 mark] (iii) If an error-correcting code were designed for this noisy channel, what would be the maximum possible entropy of an input source for which reliable transmission could still be achieved? Express your answer in terms of p. [1 mark] (iv) Name the theorem by Shannon that is the basis for the result in (iii). [1 mark] (c) Explain why the encoding of continuous signals into sequences of coefficients on Gabor wavelets encompasses, as special cases, both the delta function sampling basis and the Fourier Transform basis. Show how one particular parameter determines where a signal representation lies along this continuum that bridges from delta function sampling to the complex exponential. [5 marks] 11 (TURN OVER) CST.2009.7.12 12 Optimising Compilers (a) Explain two concepts of a variable being live - one related to execution behaviour and one related to the structure of a program. Relate them by implication, and explain their relative ease of computation in a compiler. [4 marks] (b) Explain how live variable analysis can be used to allocate variables to registers by colouring. Give and justify an algorithm that performs this colouring, particularly noting how it avoids early decisions causing inconvenient early choices of colour. [5 marks] Let Kn be the graph of n nodes, each having an edge to each other; let Cn have n nodes, but with n edges arranged to give a cycle; and let S be C4 with an additional edge forming a diagonal of C4 seen as a square. (c) What is the minimum number of colours necessary to colour Kn, Cn and S? [3 marks] (d) How many colours does your algorithm require for Cn (if it makes arbitrary choices give both best-case and worse-case)?

(a) Briefly describe what is meant by active and passive RFID tags. [2 marks] (b) Some RFID manufacturers now produce semi-active RFID tags, where a battery is used to power the microelectronics but backscattering is used for all radio communications. Give two advantages and two disadvantages of such tags. [4 marks] (c) Consider a typical binary tree search applied to identify all RFID tags within range of a transmitter. Each request takes the form [ REQ | F | X ], where REQ is a c-bit command ID, F is the f < K filter bits and X is a (K f) bit sequence of 1s. Any response then has the form [ RESP | F | I ], where RESP is a c-bit command ID, F is the first f bits of the replying tag's ID and I represents the remaining (K f) bits of that ID. In an attempt to increase efficiency, a manufacturer proposes that the reader just send [ REQ | F ] and the tags immediately respond with [ I ]. (i) What addition would you have to make to the communications protocol for this to work? What would its overhead be in bits? [3 marks] (ii) Derive an expression for the proportional reduction in search time that this new scheme would provide. Estimate the value of the ratio for a typical tag on the market today. [5 marks] (d) In a probabilistic RFID scheme, the reader transmits the number of slots in a round, N. RFID tags choose a slot uniformly at random and transmit their ID in it. Suggest how to estimate the number of tags in range based only on one round at the reader. [Hint: Consider the expected number of slots with a given property such as being empty or containing a collision.] [6 marks] 2 CST.2009.7.3 2 Advanced Graphics (a) State the Jordan curve theorem. [1 mark] (b) Given point V and simple convex planar polygon P={v0, v1, . . . , vn1} in R 3 , express: (i) A test for whether V is coplanar with P. [1 mark] (ii) A test for whether V lies strictly inside P. [2 marks] (iii) A test for whether V lies on the border of P. [1 mark] (c) (i) Describe an algorithm for ray-tracing a complex CSG (Constructive Solid Geometry) shape. How could your algorithm be represented by a state machine? [4 marks] (ii) Identify three Boolean operations that your algorithm would support between primitives. [1 mark] (iii) Would your algorithm perform ray-primitive intersections in local, eye, screen, or world co-ordinates? Why? [2 marks] (d) (i) Show that the closed uniform B-Spline of degree 2 and with knot vector {0, 0, 0, 1, 1, 1} is a quadratic Bezier curve. [6 marks] (ii) Sketch the basis functions of the curve's coefficient polynomials. Accuracy is not critical. [2 marks] 3 (TURN OVER) CST.2009.7.4 3 Advanced Systems Topics (a) The size and rate of growth of routing tables is an issue of considerable concern for inter-domain routing in the Internet. (i) Describe at least three factors that contribute to this problem. [3 marks] (ii) How might a distinction between Locators and Identifiers help address this problem? [4 marks] (iii) What are the costs and risks of implementing a Loc/ID split? [4 marks] (b) BGP employs a mechanism called Route Flap Damping (RFD) to reduce route instabilities. (i) Describe how RFD works. [4 marks] (ii) Describe some problems with RFD. [2 marks] (iii) Describe another approach to reducing the number of BGP updates. [3 marks] 4 CST.2009.7.5 4 Artificial Intelligence II Evil Robot has almost completed his Evil Plan for the total destruction of the human race. He has two nasty chemicals, which he has imaginatively called A and B and which are currently stored in containers 1 and 2 respectively. All he has to do now is mix them together in container 3. His designeran equally evil computer scientisthas equipped Evil Robot with a propositional planning system that allows him to reason about the locations of particular things and about moving a thing from one place to another. (a) Explain how this problem might be represented within a propositional planning system. Give specific examples of the way in which the start state and goal can be represented. [5 marks] (b) Describe in detail an algorithm that can be used to find a plan using this form of representation. [5 marks] (c) Give a specific example of a successor-state axiom using the representation you suggested in part (a). [2 marks] (d) Explain why in this particular planning problem it might be necessary to include one or more precondition axioms and give an example of such an axiom using your representation. [2 marks] (e) Explain why in this particular planning problem it might be necessary to include one or more action exclusion axioms and give an example of such an axiom using your representation. Suggest why it might be unwise to include too many axioms of this type, and explain how a reasonable collection of such axioms might be chosen in a systematic way. [4 marks] (f ) Explain how in this problem it might be possible to include state constraints as an alternative to action exclusion axioms, and give a specific example of such a constraint using your representation. [2 marks] 5 (TURN OVER) CST.2009.7.6 5 Bioinformatics (a) Discuss, with one example, the complexity of the Nussinov algorithm for RNA folding. [5 marks] (b) In the context of algorithms on strings, what is the advantage of using spaced seeds in database search? [3 marks] (c) Hidden Markov models (HMM) are used to identify genes in genome sequencing projects. (i) Describe how you would build a hidden Markov model to identify genes in a genome sequence. [7 marks] (ii) How would you assess the sensitivity and specificity performance of the HMM? [5 marks] 6 Business Studies (a) Distinguish between debt and equity financing for a young company. [5 marks] (b) You have won a contract to write and supply some software and set up a company to do so. The contract is worth 100,000, with 30% payable at start, 20% at a milestone expected to be completed in month 3 after starting, 40% on delivery expected in month 6 and 10% 1 month after delivery. You will need to employ two contract programmers at a rate of 2,500 each per month (plus overheads) for the duration of the contract. (i) Draw up an outline cash flow budget. What is the working capital requirement? [5 marks] (ii) You raise investment of 15,000 in the company and arrange a bank loan facility up to another 15,000 (ignore bank charges and loan interest for this question). You purchase 10,000 of capital equipment initially (computers etc). Draw up the balance sheet at the end of month 6. [5 marks] (iii) The project unfortunately takes an additional two months before passing the milestone. Draw up a revised cash-flow budget including the funds raised and purchases made as specified in part (b)(ii). What effect does this have on the working capital requirement? What options do the Directors have if the bank refuses to extend the loan? [5 marks] 6 CST.2009.7.7 7 Comparative Architectures (a) What dependencies exist between the instructions in the code fragment below? Identify both true data dependencies and name dependencies, and for each name dependence indicate whether it is an antidependence or an output dependence. [4 marks] LI R1, 25 /* R1=25 */ LI R2, 8 /* R2=8 */ ADD R1, R1, R2 /* R1=R1+R2 */ LD R2, 0(R1) /* R2=mem[R1] */ (b) How would a hardware register renaming mechanism remove the name dependencies? Illustrate your answer by providing a version of the code showing the destination and source registers for each instruction after renaming has taken place. Clearly state what free physical registers you assume are available prior to renaming. [4 marks] (c) Why is the removal of name dependencies beneficial within a superscalar processor? [4 marks] (d) In addition to removing name dependencies, for what other purposes may register renaming hardware be used in a superscalar processor? [4 marks] (e) The out-of-order execution of ALU instructions in a superscalar processor is only constrained by the availability of functional units and true data dependencies. Why must the out-of-order execution of memory instructions (e.g. load and store instructions) be constrained further?

kindly answer all the questions