Which solution is adopted by Ethernet and what measures are taken to ensure stability in circumstances of high load? [4 marks] 1 [TURN OVER CST.93.5.2 4 Graphics I A certain image contains a number Q of differently coloured pixels. There are not enough different pixel values available to represent these and so a method of approximation is needed. Describe an approach and comment on its performance. [15+5 marks] SECTION B 5 Programming in C You have a C compiler which is ANSI conforming in all respects except that it has no facility for the definition, declaration or use of standard C structures. Outline a set of routines written in this language to provide a mechanism for handling structures. Your solution should contain the following: (a) function prototypes for each of the routines [10 marks] (b) a few sentences describing the behaviour of each function [10 marks] Note: no code other than the prototypes is required. 6 Programming Language Compilation Discuss the issues that must be considered when designing the calling sequence to be used for recursive procedures on a machine with several general-purpose central registers. Assume that the language allows procedures to be declared within other procedures and that procedures may be passed as arguments in calls. Pay particular attention to how arguments, local variables and free variables are accessed. [20 marks] 2 CST.93.5.3 7 Concurrent Systems Main Memory Persistent Memory type operations data object data object operation 1 operation 2 operation n The figure illustrates an object model which is used in a concurrent software system. We are concerned with how to implement atomic operations in the presence of concurrency and crashes. In thchine multiprocessor implementation should be assumed. (a) A data object exists in main memory only. Invocations of its type operations involve no writes to persistent memory and no output to clients. Concurrent processes may invoke the object. How can the operations be made atomic? [8 marks] (b) A data object exists in persistent memory. (i) A single operation is invoked on it in response to a request from a client. The result of the invocation is output to the client. How can the operation be made atomic? [4 marks] (ii) A client requests a high-level operation which comprises more than one of the type operations on the data object. How can the high-level operation be made atomic? [8 marks] 3 [TURN OVER CST.93.5.4 8 Databases Describe the relational model of data. [4 marks] What is meant by a candidate key? [2 marks] Explain what it means for a relational data model to be presented in (a) Third Normal Form (3NF) [5 marks] (b) Fourth Normal Form (4NF) [5 marks] in each case illustrating your answer with a suitable example data model. In what circumstances might it not be sensible to hold relational data according to these normal forms? [4 marks] SECTION C 9 Foundations of Functional Programming Describe how the -calculus models the operations of addition, test for zero and successor, representing the natural numbers by Church numerals. [4 marks] The Fibonacci sequence is defined by F0 = 0, F1 = 1 and Fk = Fk1 + Fk2 for k > 2. Present a -term fib that computes the Church numeral for Fk given the Church numeral for k, for all k > 0. Do not use Y or any other fixed point combinator. You may take as primitive the -calculus encodings of standard data structures. [6 marks] Describe how to assign Godel numbers to -terms and explain the notation pMq. Describe an application of these techniques. [3 marks] Present a -term iszero, such that iszeropMq = true if M = 0 false if M 6= 0 or prove that no such term exists. [7 marks] 4 CST.93.5.5 10 Computation Theory Show that there is no way of deciding by algorithms whether a general register machine program with code p will terminate when started with initial data of 0 in every register. [10 marks] Show that there is no way of deciding by algorithm whether the blank character will be printed during the course of a general Turing machine computation. [10 marks] Note: any standard form of the undecidability result for the general halting problem may be assumed, but should be stated clearly. 11 Complexity Theory Explain how to measure the size of a problem in complexity theory. [3 marks] What is meant by reducing one problem to another? [4 marks] Given that the Boolean Satisfiability Problem is NP-complete, show th

 

a) Describe four of the problems from which classical multilevel-secure systems suffer. [12 marks] (b) Your client is proposing to implement an e-mail system with the property that every e-mail sent internally within the company - that is, with no outside recipients - should be deleted after 180 days unless a manager authorises its retention. Which of the problems in part (a) would you have to consider, and why? [8 marks] 3 [TURN OVER CST.2004.7.4 4 Advanced Graphics (a) Specify an appropriate knot vector for each of the following NURBS curves. (i) A uniform cubic NURBS curve defined by six control points. (ii) Similar to (i) but passing through both endpoints. (iii) Similar to (i) but passing through the third control point, possibly with lower continuity at that point. (iv) The cubic Bezier curve defined by four control points. [8 marks] (b) Give the continuity class for each of: (i) curve (a)(i) between the knots; (ii) curve (a)(ii) at the knots; (iii) curve (a)(iii) at the third control point. [The continuity class is the highest derivative which is guaranteed to be continuous at the point(s) in question.] [3 marks] (c) The Loop and Butterfly subdivision schemes can both operate on triangular meshes, in which all of the polygons have three sides. Both schemes subdivide the mesh by introducing new vertices at the midpoints of edges, splitting every original triangle into four smaller triangles, as shown below. Each scheme has rules for calculating the locations of the new "edge" and "vertex" vertices based on the locations of the old vertices. These rules are shown below. All weights should be multiplied by 1 16 . (i) Which of the two schemes produces a limit surface which interpolates the original data points? (ii) Which of the four rules must be modified when there is an extraordinary vertex? For each of the four rules either explain why it must be modified or explain why it does not need to be modified. (iii) Suggest appropriate modifications where necessary to accommodate extraordinary vertices. [9 marks] 4 CST.2004.7.5 5 Computer Systems Modelling (a) Consider an interactive system with average system response time R and system throughput X. Derive the interactive response time law when there are M users present, each with an average think time Z. [6 marks] (b) Consider an interactive timesharing system with M users, one CPU and two disks labelled A and B respectively. Suppose that measurements of the system have determined that: the average user think time Z is 5 seconds; the average time spent by a job in the CPU is 40 ms per request; the average time spent by a job at the individual disks per request is 30 ms for disk A and 25 ms for disk B; the visit counts per job are 25 requests for the CPU, 20 requests for disk A and 4 requests for disk B. (i) For each of the devices: CPU, disk A and disk B, determine the service demands. [4 marks] (ii) If disk A has a utilisation of 60%, what is the utilisation of the CPU and of disk B? [5 marks] (iii) If the utilisation of disk B is 10%, what is the average response time when there are 20 users present? [5 marks] 6 Specification and Verification I Write short notes (approximately one paragraph) explaining the similarities and differences between each of the following: (a) Annotations and verification conditions. [5 marks] (b) Partial and total correctness. [5 marks] (c) Deep and shallow embedding. [5 marks] (d) First order and higher order logic. [5 marks] 5 [TURN OVER CST.2004.7.6 7 Specification and Verification II (a) Explain how combinational and sequential devices can be modelled in higher order logic in a uniform way (i.e. so that combinational and sequential devices can be connected). [3 marks] (b) Illustrate your explanation by showing how to define combinational devices NOT and AND that perform negation and conjunction, respectively, and a sequential unit-delay device DEL such that the output of DEL at time t+1 is the value input at t. [3 marks] (c) Define in higher order logic a predicate Rose such that if t > 0 then Rose f t is true if and only if f has a rising edge at time t (i.e. f is true at t but false at t1). [2 marks] (d) Draw a diagram showing how to connect instances of NOT, AND and DEL to implement a device RoseImp, with one input and one output, such that the output is true at time t, where t > 0, if and only if there is a rising edge on the input at time t. [6 marks] (e) Represent your diagram in higher order logic by defining a predicate RoseImp, and then outline how to show that: in out. RoseImp(in, out) t. out(t+1) = Rose in (t+1) You need not give a detailed proof, just an overview of how such a proof could be performed (i) If someone has selected one of these symbols and you need to discover which symbol it is by asking "yes/no" questions that will be truthfully answered, 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 is maximally informative? [2 marks] (iii) On average, how many such questions will need to be asked before the selected symbol is discovered? [2 marks] (iv) What is the entropy of the above symbol set? [2 marks] (v) Construct a uniquely decodable prefix code for the symbol set, and explain why it is uniquely decodable and why it has the prefix property. [2 marks] (vi) Relate the bits in your prefix code to the "yes/no" questions that you proposed in (i). [2 marks] (b) Explain the meaning of "self-Fourier", and cite at least two examples of mathematical objects having this property. [3 marks] (c) Explain briefly: (i) sensation limit;

(a) When defining and selecting which features to extract in a pattern classification problem, what is the goal for the statistical clustering behaviour of (ii) What is the "DC" response of each of the kernels, and what is the significance of this? [1 mark] (iii) To which orientations and to what kinds of image structure are these filters most sensitive? [1 mark] (iv) Mechanically how would these kernels be applied directly to an image for filtering or feature extraction? [1 mark] (v) How could their respective Fourier Transforms alternatively be applied to an image, to achieve the same effect as in (iv)? [1 mark] (vi) How could these kernels be combined to locate facial features? [2 marks] (c) Explain why inferring object surface properties from image properties is, in general, an ill-posed problem. In the case of inferring the colours of objects from images of the objects, how does knowledge of the properties of the illuminant affect the status of the problem and its solubility? [5 marks] (d) Explain and illustrate the "Paradox of Cognitive Penetrance" as it relates to computer vision algorithms that we know how to construct, compared with the algorithms underlying human visual competence. Discuss how human visual illusions may relate to this paradox. Comment on the significance of this paradox for computer vision research. [5 marks] 9 [TURN OVER CST.2004.8.10 12 Numerical Analysis II (a) State a recurrence formula for the sequence of Chebyshev polynomials, {Tk(x)}, and list these as far as T5(x). [4 marks] (b) What is the best L polynomial approximation over [1, 1] to x k

A company proposes to introduce a new e-mail service, one with a small postage charge for each message. It is believed that by charging for each message sent the amount of spam will be reduced. The response rate for spam is about 0.005%, that is about five in a hundred thousand messages elicit a positive response. (a) Estimate a price that might economically discourage spam. [5 marks] (b) Describe approaches to handling the micro-payments involved. [5 marks] (c) What is meant by a network externality, and how might it be overcome in this case? [5 marks] (d) The postage charges might be credited to the recipient, less a handling fee. Describe a mechanism for this. [5 marks] 15 Additional Topics VNC is an ultra-thin client system based on a simple display protocol that is platform-independent. (a) Describe the advantages of a stateless architecture as used in VNC. [2 marks] (b) List the basic protocol interactions. [6 marks] (c) Give four pixel data encodings. [6 marks] (d) Comment on the tradeoff between compression factor and complexity. [6 marks] 13 [TURN OVER CST.2004.7.14 16 Additional Topics Guy Fawkes and TESLA are streaming authentication protocols based on hash chains. (a) Describe the problem that Guy Fawkes was designed to solve. [2 marks] (b) Briefly describe how Guy Fawkes works. Draw a diagram of a Guy Fawkes packet (or several) and explain the function and purpose of all the parts. [8 marks] (c) List and explain the practical shortcomings of Guy Fawkes. [4 marks] (d) Draw a diagram of a chain of TESLA packets. For each of the Guy Fawkes shortcomings you found in part (c), explain how TESLA fixes it, if it does.

at x = 1. Use the method of economisation to find a polynomial approximation of the required accuracy. [9 marks] 13 Specification and Verification I (a) Describe how to use Floyd-Hoare logic to specify that a program sorts an array A so that A(0), A(1), . . . , A(N) are in ascending order. [8 marks] (b) What is VDM notation? Use the sorting example to show how it can shorten specifications. Does the VDM specification of sorting have the same meaning as the Floyd-Hoare specification you gave in answer to part (a)? [6 marks] (c) Describe the concept of weakest preconditions and weakest liberal preconditions. How do they relate to Floyd-Hoare specifications? [6 marks] 10 CST.2004.8.11 14 Natural Language Processing 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.