net,,,,,,

8 Computation Theory (a) Define precisely what is meant by the following: (i) f(x1, x2, . . . xn) is a Primitive Recursive (PR) function of arity n. [5 marks] (ii) f(x1, x2, . . . xn) is a Total Recursive (TR) function of arity n. [3 marks] (b) Ackermann's function is defined by the following recursive scheme: f(0, y) = S(y) = y + 1 f(x + 1, 0) = f(x, 1) f(x + 1, y + 1) = f(x, f(x + 1, y)) For fixed n define gn(y) = f(n, y). Show that for all n, y N, gn+1(y) = gn (y+1)(1), where h (k) (z) is the result of k repeated applications of the function h to initial argument z. [4 marks] (c) Hence or otherwise show that for all n N, gn(y) is a PR function. [4 marks] (d) Deduce that Ackermann's function f(x, y) is a TR function. [3 marks] (e) Is Ackermann's function PR?

9 Numerical Analysis I (a) What is meant by a symmetric positive definite matrix ? [3 marks] (b) Verify that A = 2 1 1 2 is positive definite. [4 marks] (c) The Choleski factorisation A = LDLT is to be applied to the solution of Ax = b, where b = 1 1 . It is found that L = 1 1 2 1 , D = 2 3 2 . The next step in the method is to solve Ly = b to get y = 1 1 2 . Form the upper triangular system of equations needed to complete the solution. [4 marks] (d) Solve these equations. [2 marks] (e) What is meant by the order of convergence of an iterative process? [1 mark] (f ) State the Newton-Raphson formula for solving f(x) = 0 for scalar x. What is the order of convergence of this method? [2 marks] (g) This method is used to solve f(x) = x 2 4 = 0 using IEEE Double Precision with a certain starting value x0. It is found that the third iterate x3 ' 2.0006, and x4 ' 2.00000009. Very roughly, how many significant decimal digits of accuracy would you expect in x5?

Computer Graphics and Image Processing (a) Describe an algorithm to draw a straight line using only integer arithmetic. You may assume that the line is in the first octant, that the line starts and ends at integer co-ordinates, and that the function setpixel(x, y) turns on the pixel at location (x, y). [8 marks] (b) Describe Douglas and Pucker's algorithm for removing superfluous points from a line chain. [10 marks] (c) Under what circumstances would it be sensible to employ Douglas and Pucker's algorithm?

1 Continuous Mathematics The complex form of the Fourier series is: f(x) = X + k= cke i2kx where ck is a complex number and ck = c k . (a) Prove that the complex coefficient, ck, encodes the amplitude and phase coefficients, Ak and k, in the alternative form: f(x) = X + k=0 Ak cos(2kx k) [10 marks] (b) What is special about the case k = 0? [2 marks] (c) Explain how the coefficients, ck, of the Fourier series of the periodic function, f(x): f(x) = f(x + T), x can be obtained from the Fourier transform, FL(), of the related function, fL(x): fL(x) = f(x), T 2 6 x < T 2 0, otherwise An interprocess communication environment is based on synchronous message passing. A server is to be designed to support a moderate number of simultaneous client requests. Clients send a request message to the server, continue in parallel with server operation, then wait for the server's reply message. Discuss the design of the server's interaction with the clients. Include any problems you foresee and discuss alternative solutions to them.

(a) Describe how mutual-exclusion locks provided by the synchronized keyword can be used to control access to shared data structures. In particular you should be clear about the behaviour of concurrent invocations of different synchronized methods on the same object, or of the same synchronized method on different objects. [6 marks] (b) Consider the following class definition: class Example implements Runnable { public static Object o = new Object(); int count = 0; public void run() { while (true) { synchronized (o) { count ++; } } } } Show how to start two threads, each executing this run method. [2 marks] (c) When this program is executed, only one of the count fields is found to increment, even though threads are scheduled preemptively. Why might this be? [2 marks] (d) Define a new class FairLock. Each instance should support two methods, lock and unlock, which acquire and release a mutual exclusion lock such that calls to unlock never block the caller, but will allow the longest-waiting blocked thread to acquire the lock. The lock should be recursive, meaning that the thread holding the lock may make multiple calls to lock without blocking. The lock is released only when a matched number of unlock operations have been made. You may wish to make use of the fact the Thread.currentThread() returns the instance of Thread that is currently executing.

Consider the following grammar giving the concrete syntax of a language: E id C E = E; C {B} C C repeatwhile E C if E then C C if E then C else C B B C B C S C eof where C repeatwhile E has the same meaning as do C while E in C or Java. (a) List the terminals and non-terminals of this grammar and explain the significance of S. [3 marks] (b) Identify any ambiguities in the above grammar and rewrite it to remove them, ensuring that your new grammar generates exactly the same set of strings. [4 marks] (c) Specify a suitable abstract syntax, for example by giving a type declaration in a programming language of your choice, which might be used to hold parse trees for this language. [3 marks] (d) Give either a recursive descent parser or a characteristic finite state machine (e.g. for SLR(1)) with associated parser for your grammar. Your parser need not return a parse treeit suffices for your parser either to accept or to reject the input string.

Data Structures and Algorithms (a) Outline how you would determine whether the next line segment turns left or right during the Graham scan phase of the standard method of computing the convex hull of a set of points in a plane. [5 marks] (b) Describe in detail an efficient algorithm to determine how often the substring ABRACADABRA occurs in a vector of 106 characters. Your algorithm should be as efficient as possible. [10 marks] (c) Roughly estimate how many character comparisons would be made when your algorithm for part (b) is applied to a vector containing 106 characters uniformly distributed from the 26 letters A to Z.