correct answer please.

1 Processor Architecture What is a branch delay slot and why does it arise? [7 marks If a processor exhibited one branch delay slot how would you reorder (and possibly modify) the instructions in the following loop to gain a performance advantage? loop ldr r2,r3,#4 % r2=load(r3), r3=r3+4 add r4,r4,r2 % r4=r4+r2 add r1,r1,#1 % r1=r1+1 cmp r1,#10 % compare r1 2 Computer Architecture Write short notes on each of the following parameters of cache design: (a) size [4 marks] (b) mapping function [4 marks] (c) replacement algorithm [4 marks] (d) write policy [4 marks] (e) block size [4 marks] CST.96.12.2 3 Digital Communication I Hosts X and Y are communicating through the data network provided by the switches A, B, C and D and the links interconnecting them as shown above. Initially all packets are travelling through switches A, C and D. (a) A packet is corrupted on the link between C and D. Describe the events that take place to recover from the error when (i) an end to end flow and error control protocol is in operation [5 marks] (ii) flow and error control are performed on a hop by hop basis (b) Switch C fails. Describe the events that follow to recover when [5 marks] (i) the network is a datagram network [5 marks] (ii) the network is connection oriented [5 marks] 4 Graphics Consider the control of detail in a curve represented as a sequence of straight line segments. Describe Douglas and Peucker's algorithm for removing superfluous points. [10 marks] Describe how Overhauser interpolation can be used to introduce additional points. [10 marks] CST.96.12.3 5 Business Studies In a project plan what is meant by a critical path, and why is the concept useful? [5 marks] A certain software project has two phases. Each phase has three tasks (analysis, coding and testing) which must be performed sequentially. Analysis for phase 2 cannot be started until analysis for phase 1 is complete. The effort in person-weeks, as estimated by the programmers, in each task is given in the table below. Task Phase 1 Phase 2 Analysis 4 8 Coding 4 4 Testing 4 8 Two staff are assigned to the project. Tasks may be performed by either member of staff. Analysis and coding tasks can have only one person usefully working at a time whereas, for testing, the time to completion is inversely proportional to the effort expended. Draw PERT and GANTT charts for the project, and indicate the critical path. [5 marks] Staff are each paid 24,000 per annum. The company allows for overheads of 100% of salary. Equipment worth 50,000 will be needed, depreciated over 5 years. Payment is proposed as 25% on start, 25% on delivery of the first phase, and 50% on completion. Draw up a rough budget and cash flow for the project. How much working capital (excluding equipment purchase, but including depreciation) is required? [5 marks] What price and delivery would you quote for this project? Explain the additional factors you have considered in formulating your quotation. [5 marks] CST.96.12.4 6 Programming in C and C++ For five of the following C or C++ features write a very short fragment of code (perhaps 2 or 3 lines will suffice in most cases) that illustrates the syntax involved. In each case explain very briefly what your example achieves. (a) preprocessor macros and conditional compilation (b) casts that convert from one pointer type to another (c) C and C++ style comments (d) the declaration of a simple C++ class (e) overloading the operator '+' (f ) the C setjmp function (g) the switch statement, including a default label [4 marks each] 7 Compiler Construction Outline the key features of the design of the part of a compiler that will translate the abstract syntax tree representation of a program into a stack-based intermediate code. Concentrate on those features used in the translation of the following fragment: ... LET i = k LET j = k WHILE (i>0) AND (j<100) DO { i := i-1; j := j+2 } ... In particular, concentrate on the mechanism you would choose to deal with (a) the scopes of identifiers [6 marks] (b) the compilation of boolean expressions involving the operators NOT, AND and OR [6 marks] (c) the translation of the WHILE command [4 marks] (d) the translation of the two assignments [4 marks] CST.96.12.5 8 Prolog for Artificial Intelligence An ordered integer binary search tree (or OIBS tree) is either empty or a tuple (T, N, U), where T and U are also OIBS trees and N is an integer. Every node in T has a value less than N, which in turn is less than the value of every node in U. (a) Give two Prolog terms which are suitable for representing an empty OIBS tree and a node in the OIBS tree respectively. [2 marks] (b) Define a Prolog procedure insert(Item, T, NT), where Item is an integer being inserted into OIBS tree T, producing an OIBS tree NT. If Item is already present in T, then NT equals T. [9 marks] (c) Define a Prolog procedure lookup(Item, T), where Item is to be looked for in OIBS tree T. A lookup goal will succeed if Item is found, or fail otherwise. [9 marks] 9 Databases Describe the essentials of the ODMG-93 standard for Object Database Management. [7 marks] To what extent do these proposals conform to the ANSI/SPARC architecture for database management? [3 marks] Describe how binary relationships can be modelled directly within the ODMG-93 standard. [4 marks] In what way is it possible to create a representation for n-ary relationships that is similar to that of the relational model? [2 marks] Explain how these alternative approaches allow a navigational style of data manipulation as well as supporting an extension of SQL. [4 marks] CST.96.12.6 10 Designing Interactive Applications Some of today's photocopiers are connected by networks to repair centres so that technicians can monitor their performance and detect problems without visiting customer premises. Although this offers cost savings, it can have a negative impact on customer relations. Suggest an explanation for this, drawing on your knowledge of the service technician's job. [5 marks] You have been asked to design a modification to a networked photocopier, to enable users to send messages to the repair centre when they encounter problems. Again drawing on your understanding of the nature of photocopier repair work, produce a rough design for the message-system user interface. Include a one-sentence problem statement, a mental-model description and an outline of the design of the user interface itself. [15 marks] 11 Introduction to Functional Programming Describe how recursive definitions are modelled in the -calculus using Y. [6 marks] Consider the following attempt to define Y in ML: val Y = fn f => (fn x => f (x x)) (fn x => f (x x)) Explain why this doesn't work. [6 marks] Give a satisfactory definition of Y in ML and illustrate its use by defining the factorial function. [4 + 4 marks] 12 Computer Vision Discuss the problem of face recognition and face detection based on wavelet encodings of facial structure and facial features. How can one distinguish between those facial undulations that are generic (universal, or normally present in all faces), and those which are particular to a given face and which therefore distinguish it from others? How can statistical decision theory formalize these two pattern recognition problems - face detection and face recognition? What are the main advantages and disadvantages of using wavelets for the encoding of faces? [20 marks] CST.96.12.7 13 Complexity Theory (a) Show that the problem 3-SAT is at least as hard to solve as n-SAT. [5 marks] (b) Show that the task of finding a minimum cost closed circuit in a weighted directed graph (a Travelling Salesman Problem of the minimization variety) is at least as hard as the Hamiltonian Circuit Problem. [5 marks] (c) Show that the class NP-complete is contained in the class P-space. [5 marks] (d) Show that the class P-space is contained in the class EXP-time. [5 marks] In each case ensure that your answer makes it clear what the problems and classes involved are. Standard results do not need to be proved provided they are clearly stated. 14 Numerical Analysis II In Peano's theorem, if a quadrature rule integrates polynomials of degree N exactly over an interval [a,b], then the error in integrating f CN+1[a,b] is conventionally expressed as where Explain the notation ( and Ex. [3 marks] It follows directly from Taylor's theorem that . Explain clearly, in simple stages, how to complete the proof of Peano's theorem. [8 marks] For the mid-point rule, what is N? If K(t) does not change sign in [a,b] then [1 mark] for some (a,b). Use this result to simplify (0) Write Java program to remove the third element from a array list. Write Java program to search an element in a array list. Write Java program to sort a given array list. Write Java program to copy one array list into another. Write Java program to shuffle elements in a array list.

(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 le service, operating behind a rewall. 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 le service. Policy: The owner may authorise other principals to download the le. (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 qualied 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 (a) Explain why display devices appear to be able to reproduce (almost) all the colours of the spectrum using only red, green and blue light. [4 marks] (b) Describe an algorithm (other than thresholding) which will convert a greyscale image (8 bits per pixel) to a bi-level black and white image (1 bit per pixel), with the same number of pixels, while retaining as much detail as possible. [8 marks] (c) Explain what specular and diuse reection are in the real world. State and explain equations for calculating approximations to both in a computer. [8 marks] (a) Explain the dierences (illustrating each with a small program) between (i) static and dynamic binding (scoping); [4 marks] (ii) static and dynamic typing. [2 marks] (b) Java is sometimes said to be "dynamically typed" in that a variable whose type is (class) C can be assigned a value of (class) D provided that D extends C; conversely a variable of type D can be assigned a value of type C using a cast. By considering storage layouts, explain why the former assignment is always valid and the latter sometimes invalid. [4 marks] (c) A new programming language has the notion of "statically scoped exceptions" in which the program exception foo; void f() { try { void g() { raise foo; } try { g(); } except (foo) { C2 } } except (foo) { C1 } } would execute C1 rather than C2 as the former was in scope at the raise point. By analogy with statically scoped variables, or otherwise, explain how such exceptions might be implemented on a stack. [10 marks]

In the following, N is a feedforward neural network architecture taking a vector xT = ( 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 + k X 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]

30940919 (a) Dene the operators of the core relational algebra. [5 marks] (b) Let R be a relation with schema (A1,...,An,B1,...,Bm) and S be a relation with schema (B1,...,Bm). The quotient of R and S, written RS, is the set of tuples t over attributes (A1,...,An) such that for every tuple s in S, the tuple ts (i.e. the concatenation of tuples t and s) is a member of R. Dene the quotient operator using the operators of the core relational algebra. [8 marks] (c) The core relational algebra can be extended with a duplicate elimination operator, and a grouping operator. (i) Dene carefully these two operators. [3 marks] (ii) Assuming the grouping operator, show how the duplicate elimination operator is, in fact, unnecessary. [2 marks] (iii) Can the grouping operator be used to dene the projection operator? Justify your answer. [2 marks]

Answer the above questions