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.