For monotone functions f, f0: P Q between posets (P, vP ) and (Q, vQ), let f v f(i) Prove that the binary relation v is a partial order. [3 marks] (ii) For monotone functions between posets p : P 0 def x P. f(x) vQ f 0 (x).0 P, f, f0 : P Q, and q : Q Q0 , prove that f v f 0 = q f p v q f 0 p. [1 mark] (b) An adjoint pair f : P Q, g : Q P is a pair of monotone functions between posets such that idP v g f and f g v idQ. (i) Let f1, f2 : P Q and g1, g2 : Q P be monotone functions between posets such that (f1, g1) and (f2, g2) are adjoint pairs. Prove that: (A) f1 v f2 g2 v g1 [4 marks] (B) f1 = f2 g1 = g2 [2 marks] (ii) Let f : P Q, g : Q P be an adjoint pair where the posets P and Q have least elements. Prove that the monotone function f is strict. [2 marks] (i) Prove that the binary relation v is a partial order. [3 marks] (ii) For monotone functions between posets p : P 0 P, f, f0 : P Q, and q : Q Q0 , prove that f v f 0 = q f p v q f 0 p. [1 mark] (b) An adjoint pair f : P Q, g : Q P is a pair of monotone functions between posets such that idP v g f and f g v idQ. (i) Let f1, f2 : P Q and g1, g2 : Q P be monotone functions between posets such that (f1, g1) and (f2, g2) are adjoint pairs. Prove that: (A) f1 v f2 g2 v g1 [4 marks] be an adjoint pair where the posets P and Q have least elements. Prove that the monotone function f is strict. [2 marks] (c) (i) Define the notion of lub (least upper bound) of a countable increasing chain in a poset. [2 marks] (ii) Let f : D E, g : E D be an adjoint pair where each of the posets D and E is a cpo (chain complete poset). Prove that the monotone function f is continu

Write LISP program for detecting whether a LISP interpreter treats the language as being dynamically scoped (as was the case in historical LISP) or as being statically scoped (as is the case in modern LISP). You may use pseudo-code and should explain your answer in detail. [4 marks] (b) You manage two junior programmers and overhear the following conversation: A: "I don't know why anyone needs a language other than Java, it provides clean thread-based parallel programming." B: "Maybe, but I write my parallel programs in a functional programming language because they are then embarrassingly parallel." Discuss the correctness of these statements and the extent to which they cover the range of languages for parallel programming. [6 marks] (c) Explain why the SML interpreter accepts the declarations datatype 'a FBtree = node of 'a * 'a FBtree list; fun dfs P (t: 'a FBtree) = let exception Ok of 'a; fun auxdfs( node(n,F) ) = if P n then raise Ok n else foldl (fn(t,_) => auxdfs t) NONE F; in auxdfs t handle Ok n => SOME n end; while it does not accept the declaration exception Ok of 'a; [4 marks] (d) Consider the declarations structure Z = struct type t = int; val z = 0 end; structure A = Z : sig type t ; val z: t end; structure B = Z :> sig type t = int ; val z: t end; structure C = Z :> sig type t ; val z: t end; in the SML Modules language. Explain the behaviour of the SML interpreter on inputting each of the expressions Z.z = A.z; Z.z = B.z; Z.z = C.z; [6 marks]

Selectional restrictions can be used to block parses of semantically anomalous sentences such as: The pebble snores. The pebble wrote a book. The dog wrote a book. Describe how selectional restrictions might be encoded in a feature structure grammar. (a) Describe how to construct the function cpo ((D E), v) of two cpos (D, vD) and (E, vE). Prove that ((D E), v) is a cpo. (You may use general facts about least upper bounds provided you state them clearly.) [7 marks] (b) The function uncurry is inverse to the function curry; it takes a continuous function in (D1 (D2 E)) as argument and yields a continuous function in ((D1 D2) E) as result. Give a definition of uncurry and show it is a continuous function. (You may use general facts about continuous functions provided you state them clearly.) [6 marks] (c) Exhibit two terms of PCF which are contextually equivalent and yet have distinct denotations in the domain (B (B B)) B where B = {true, false} is the set of truth values. Explain why their denotations differ. The syntax of parallel commands is given by: c ::= X := a | c0; c1 | c0 || c1 | if b then c | while b do c where X ranges over locations, a over arithmetic expressions, and b over boolean expressions. (a) Give an operational semantics to parallel commands, assuming an operational semantics for arithmetic and boolean expressions. [5 marks] (b) This part is concerned with a Petri net semantics for parallel commands. There are to be two kinds of conditions: data conditions, pairs of locations and integers, which specify the contents of locations, and control conditions, which specify the local control points in parallel components of commands. A parallel command is to be represented by a basic net (where every condition has capacity one) in which a subset of control conditions I is to be distinguished as its initial conditions and another subset T is to be distinguished as its terminal conditions; the initial conditions are precisely those control conditions which hold at the start of execution of the command; the terminal conditions are precisely those control conditions which hold if and when the command terminates. A diagrammatic account suffices for answers to the questions below. (i) Describe an (infinite) net for X := X + 1. [2 marks] (ii) Describe a construction on nets for c0; c1. [Hint: Replace the terminal conditions T0 of c0 and the initial conditions I1 of c1 with their product T0 I1.] [4 marks] (iii) Describe a construction on nets for c0 || c1. [2 marks] (iv) Describe a construction on nets for if X > 0 then c. [2 marks] (v) Describe a construction on nets for while X > 0 do c.

(a) In the context of networking, what is congestion? [2 marks] (b) Discuss the evolution of congestion control in TCP. You may like to consider some or all of the following in your answer: congestion window, slow start, fast retransmit, fast recovery, TCP Vegas, RED, ECN, and congestion pricing. [12 marks] (c) Compare and contrast congestion control in TCP with the ways in which congestion is managed in ATM networks.

(a) For a given order, k, there is only one basis function for uniform B-splines. Every control point uses a shifted version of that one basis function. How many different basis functions are there for open-uniform B-splines of order k with n + 1 control points, where n > 2k 3? [6 marks] (b) Explain what is different in the cases where n < 2k 3 compared with the cases where n > 2k 3. [3 marks] (c) Sketch the different basis functions for k = 2 and k = 3 (when n > 2k 3). [4 marks] (d) Show that the open-uniform B-spline with k = 3 and knot vector [000111] is equivalent to the quadratic Bezier curve. [7 marks] 5 Business Studies You are inspired to make your fortune by starting a distance learning enterprise to teach the world Computer Science, using multimedia lessons distributed over the Web. Write notes for a business plan for the potential investors, under the following headings: (a) The market. [5 marks] (b) The team required. [5 marks] (c) Outline overall project plan. [5 marks] (d) Business model, with a rough estimation of capital expenditure and profitability. [5 marks] 4 CST.2001.8.5 6 Security In the Wired Equivalent Privacy protocol used in IEEE 802.11 networks, data are protected at the link level during transmission on a wireless LAN. Each frame has a 32-bit CRC appended to it; it is then encrypted using the RC4 stream cipher, initialised with a shared key and a 24-bit initial value; and finally, the initial value is sent with the encrypted frame. (a) Why is the initial value used? [4 marks] (b) Is the CRC an appropriate mechanism, and, if not, what should be used instead? [4 marks] (c) Describe one passive attack on this system. [4 marks] (d) Describe one active attack on this system. [4 marks] (e) What would be the effect of upgrading from RC4 to a stronger cipher, such as AES used in output feedback mode?

A company that sells both spreadsheets and word processors has received complaints from users in the banking industry. The users often copy data from spreadsheets into letters offering special finance terms to individual customers. The default behaviour of the word processor "paste" command is simply to insert the numeric value, whereas a special option (in the "paste special . . ." dialog) inserts a recalculating formula. The special option is used so regularly that users have requested an extra item on the pop-up (right click) menu. (a) How would you estimate the increase in operation speed that might result from this change? [6 marks] (b) How would you confirm the actual speed increase after constructing a prototype? [4 marks] (c) The design team suggest an alternative - that the word processor should be enhanced with sufficient calculation functions that a spreadsheet is not needed at all. What factors should be taken into account in order to assess the effect this would have on user tasks? [10 marks] 2 VLSI Design (a) Sketch stick diagrams of memory cells for: (i) read-only memory; [3 marks] (ii) static memory; [3 marks] (iii) dynamic memory using standard CMOS; [3 marks] (iv) dynamic memory for dense layout. [3 marks] (b) Extend your design for parts (ii) and (iii) to accommodate four read ports. What would inhibit such an extension for design (iv)? [6 marks] (c) State two considerations that are becoming increasingly important in memory design as feature sizes decrease. [2 marks] 2 (a) Compare and contrast the request routing mechanisms of Gnutella and Pastry. [10 marks] (b) It has been said: "Unstructured peer-to-peer systems are better than structured peer-to-peer systems because they implement searching and complex queries." Describe how a structured system might be able to implement search. [10 marks] 6 Advanced Graphics (a) Compare and contrast B-spline and subdivision representations of curves. [4 marks] (b) Explain how B-spline basis functions are derived from the knot vector. [4 marks] (c) Derive the quadratic uniform B-spline basis function (use the knot vector [0, 1, 2, 3]). [4 marks] (d) Describe an algorithm to give the first intersection point of a ray with a closed cylinder of finite length aligned along the z-axis. [8 marks] 4 CST.2005.9.5 7 Optimising Compilers (a) Summarise the basic principles behind strictness analysis including: what language paradigm it can be applied to, the representation of compile-time values expressing strictness, how these may be calculated and how the results of such calculations can be used to optimise programs. [8 marks] (b) A program contains the following user function definitions. Give corresponding strictness functions assuming that if-then-else takes an integer as its first argument. (i) fun f(x) = 42 [1 mark] (ii) fun g(x) = g(x+1) [1 mark] (iii) fun h(y,z) = if f(7) then y else z [2 marks] (iv) fun k(x,y,z) = pif(x,y,z) where pif(e, e0 , e00) is a primitive which evaluates its three arguments in parallel, returning e 0 if e evaluates to a non-zero integer, returning e 00 if e evaluates to zero and also returning e 0 if e 0 and e 00 evaluate to the same integer even if e is still being evaluated. [4 marks] (c) "Any Boolean expression be containing variables {x1, . . . , xk} but not containing negation can be expressed as the strictness function for a userdefined function fun u(x1, . . . , xk) = e." Argue that this statement is true, showing how to construct some such e from a given be. [4 marks] [Hint: you may assume be has been written in DNF form (v11 v1m1 ) (vn1 vnmn ) where vij are members of {x1, . . . , xk}.] 5 [TURN OVER CST.2005.9.6 8 Artificial Intelligence II We wish to model the unobservable state of an environment using a sequence S0 S1 S2 of sets of random variables (RVs) where at time i we are in state Si and observe a set of RVs Ei . The distributions of the RVs do not change over time, and observations depend only on the current state. (a) Define a Markov process, the transition model and the sensor model within this context. [3 marks] (b) Assuming that evidence E1:t = e1:t = (e1, e2, . . . , et) has been observed define the tasks of filtering, prediction and smoothing. [3 marks] (c) Derive a recursive estimation algorithm for performing filtering by combining the evidence et obtained at time t with the result of filtering at time t 1. [8 marks] (d) How does a hidden Markov model differ from the setup described? [1 mark] (e) Show how for the case of a hidden Markov model your filtering algorithm can be expressed in terms only of matrix operations. [5 marks] 9 Bioinformatics (a) Present the aim of phylogeny algorithms: (i) Describe the main differences between Parsimony, Distance and Likelihood-based algorithms. [5 marks] (ii) Describe the input and the output of a distance-based algorithm. [5 marks] (iii) Discuss the complexity of the Neighbour-Joining algorithm. [5 marks] (b) Describe with one example the Needleman-Wunsch algorithm. [5 marks] 6 CST.2005.9.7 10 Types Give a polymorphic lambda calculus (PLC) type list that contains a single free type variable and which corresponds to the ML datatype of polymorphic lists: datatype 'a list = Nil | Cons of 'a * ('a list) [2 marks] Give PLC expressions Nil, Cons and iter of appropriate types that encode the ML constructors Nil and Cons and the ML function iter given by fun iter x f Nil = x | iter x f (Cons(h, t)) = f h (iter x f t) You should prove the PLC typings you claim for these expressions. [13 marks] Show that iter has -conversion properties corresponding to the above declaration of the ML function iter. [5 marks] (iii) Approximately what is the spatial frequency bandwidth of this filter, in octaves? [Hint: the answer is independent of .] [1 mark] (iv) What is meant by image operations "at a certain scale of analysis"? In this context, define a scale-space fingerprint, and explain the role of the scale parameter. [3 marks] (b) What surface properties can cause a human face to form either a Lambertian image or a specular image, or an image lying anywhere on a continuum between those two extremes? In terms of geometry and angles, what defines these two extremes of image formation? What difficulties do these factors create for efforts to extract facial structure from facial images using "shape-fromshading" inference techniques? [3 marks] (c) Why can't any computer vision operations be performed directly on .jpeg image formats? [1 mark] (d) Discuss the significance of the fact that mammalian visual systems send perhaps ten times as many corticofugal neural fibres back down from the visual cortex to the thalamus, as there are ascending neural fibres bringing visual data from the retina up to the thalamus. Does this massive neural feedback projection support the thesis of "vision as graphics", and if so how? [4 marks] (e) 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? [4 marks] 8 CST.2005.9.9 12 Numerical Analysis II (a) Explain the term positive semi-definite. If A is a real square matrix show that AT A is symmetric and positive semi-definite. [3 marks] (b) How is the l2 norm of A defined? State Schwarz's inequality for the product Ax. [2 marks] (c) Describe briefly the properties of the matrices U, W, V in the singular value decomposition A = UWVT . [3 marks] (d) Let x be an approximate solution of Ax = b, and write r = bAx, e = xx. Derive a computable estimate of the relative error kek/kxk in the approximate solution, and show how this may be used with the l2 norm. [8 marks] (e) Suppose A is a 7 7 matrix whose singular values are 102 , 104 , 1010 , 1016, 1022, 1029, 1056. Construct the matrix W+ that you would use (i) if machine epsilon ' 1015, and (ii) if machine epsilon ' 1030 . [4 marks] 13 Specification and Verification II (a) Discuss the challenge of modelling transistors in a way that is both tractable for formal verification and accurate enough to be useful. [5 marks] (b) Discuss the accuracy of the simple switch model of transistors and discuss how the model can be improved. [5 marks] (c) Outline how transistor circuits that use precharging can be formally modelled in higher order logic. Briefly discuss potential inaccuracies of such models. [5 marks] (d) Describe how to specify that a bit-level circuit with 4-bit inputs a and b and an 8-bit output prod performs multiplication.

(a) Explain the ideas of strictness analysis, including over what languages the ideas are applicable and what transformations are enabled by it. Describe how strictness functions for (i) built-in and (ii) user-defined functions are defined, clarifying the similarities and differences. [10 marks] (b) A language has a user-defined function f which is defined in terms of builtin functions a1, , at and possibly recursion. Later, to aid efficiency, an additional function at+1 is added to the set of system functions, but its effect (semantics) is the same as that of f. By considering examples similar to those used to show analyses are safe but imprecise, or otherwise, determine a relationship between the strictness functions f ] and a ] t+1. [5 marks] (c) It is noted that strictness functions, e.g. cond] (x, y, z) = x (y z) do not generally use negation in their defining boolean expressions. Show that all strictness functions can be written without negation or find a counterexample. Hint: No computable function f can have semantics such that there are x and y which satisfy f(x, y) = and f(x, ) 6= . [5 marks] 8 Artificial Intelligence Can a computer think? [20 marks] 6 CST.2001.8.7 9 Neural Computing (a) (i) A competitive Kohonen neural network forms feature maps which can be regarded as performing dimensionality reduction. Explain this. [4 marks] (ii) Is training time normally faster, or slower, in a supervised neural network compared with an unsupervised one? What is the major disadvantage inherent in the use of supervised neural networks? [2 marks] (iii) What class of neural network can be used to overcome the mathematical difficulties caused by the use of non-orthogonal sensory and motor representations? [2 marks] (b) (i) Give three examples of biological sensory or motor control systems that seem to rely on the use of non-orthogonal coordinates. [3 marks] (ii) Explain why this creates a problem in the computational evaluation and simulation of such systems, and discuss whether or not you think this issue matters in the function of the actual neurobiological systems. [2 marks] (c) (i) Give four examples of neural activity having a fundamentally quantal structure, in the sense that signals or events are quantised into discrete packages rather than being continuous. [4 marks] (ii) For purposes of understanding neurobiological computation, what can be learned from studying the brain's failures, either as the consequences of specific forms of trauma or in normal function as revealed in the systematic visual illusions? [3 marks] 7 [TURN OVER CST.2001.8.8 10 Comparative Architectures An important application spends a large proportion of its running time executing a particular loop. The loop is responsible for summing two arrays containing unsigned eight-bit values packed in memory into a similar third array. Saturating arithmetic is used, whereby results that overflow are "clipped" to the maximum representable value. For example, for the unsigned eight-bit case, 250 plus 20 would result in 255. In this particular application, such overflows are rare in practice, and this fact may be exploited to optimise the implementation. (a) Write pseudo code for a simple implementation of the inner loop for a 32- bit processor with a RISC-like instruction set. [Hint: It is possible to use the CPU's 32-bit ALU to perform four eight-bit additions with a single add instruction, and then use further code to detect if overflow occurred and correct it. You may assume the arrays start on word-aligned boundaries.] [10 marks] (b) Assuming the arrays are present in the CPU's L1 data cache, estimate the number of cycles required to sum arrays of length N on a statically-scheduled two-way super-scalar processor. State any assumptions you make. [5 marks] (c) Many instruction set architectures have been augmented with SIMD (Single Instruction Multiple Data) instructions to enhance processors' performance when dealing with packed arrays such as those used by this application. Demonstrate how SIMD instructions could be used to optimise the loop. Assuming that 50% of the running time of the application was spent executing your previous loop implementation, estimate the program's speedup when using the SIMD optimised loop. [5 marks] 8 CST.2001.8.9 11 Numerical Analysis II (a) A cubic spline over knots x1, x2, . . . xn is defined by (x) = (x xj )yj+1 + (xj+1 x)yj dj (x xj )(xj+1 x){(dj + xj+1 x)j + (dj + x xj )j+1} 6dj for x [xj , xj+1] where dj = xj+1 xj . The spline is continuous in its first and second derivatives. (i) Find (xj ). [2 marks] (ii) Find formulae for 0 (xj ) and 0 (xj+1) for x [xj , xj+1]. [4 marks] (iii) What is 00(xj )? [2 marks] (b) Form a set of equations for computing the unknowns {j}, specifying suitable end conditions to simplify these equations. [10 marks] (c) What are the important properties of these equations with respect to their numerical solution? [2 marks] 12 Specification and Verification I (a) Describe the axioms and rules of Floyd-Hoare logic for reasoning about FOR-commands. Carefully explain any side conditions. [8 marks] (b) Let n! be the factorial of n (0! = 1 and (n + 1)! = (n + 1) n!). Give a proof of {N > 0} X := 1; FOR Y := 2 UNTIL N DO X := X Y {X = N!}

Write java program to find if a particular element is present in a multi-dimensional array. a Java program to find the shortest distance using Travelling Salesman Problem

Understanding, classifying, and identifying human faces has been a longstanding goal in computer vision. Yet because the face is an expressive social organ, as well as an object whose image depends on identity, age, pose and viewing angle, and illumination geometry, many forms of variability are all confounded together, and the performance of algorithms on these problems remains very poor. Discuss how the different kinds and states of variability (e.g. same face, different expressions; or same identity and expression but different lighting geometry) might best be handled in a statistical framework for generating categories, making classification decisions, and recognising identity. In such a framework, what are some of the advantages and disadvantages of wavelet codes for facial structure and its variability? [20 marks] 14 Computer Systems Modelling Two servers operate with different performance characteristics at mean rates 1 and 2. You wish to combine them into a single system by associating each server with a separate FIFO queue and dispatching incoming work items to the first queue with probability p1 and to the other queue with probability p2. Incoming items arrive at a rate and none are discarded from the system. You may assume that the inter-arrival-time distribution and both service-time distributions are exponential, that there is no limit on the queue lengths and that the population size is infinite. (a) Using Kendall notation, describe the first server and its queue. Construct a Markov-chain model for this part of the system. [2 marks] (b) Let qk,i denote the probability that there are exactly i items of work in server k and its queue. By using detailed flow balance equations or otherwise express qk,i in terms of , pk and k. [6 marks] (c) Hence derive Tk, the mean response time of work items served at k. [6 marks] (d) Suppose that the system administrator wishes to ensure that work items receive the same mean response time irrespective of which server they visit. Express p1 in terms of , 1 and 2. Qualitatively, when is it reasonable to consider dispatching work to both servers to maintain an equal mean response time? How will the system behave at other times? [6 marks] 10 CST.2001.8.11 15 Topics in Concurrency (a) Describe an algorithm for deciding whether or not a finite-state CCS process satisfies an assertion in the modal -calculus. [6 marks] (b) Draw the reachable transition system of the CCS process P, where P def = a.P + b.(b.nil + a.nil). [2 marks] (c) Illustrate the use of the algorithm of part (a) by giving a derivation which decides whether or not the CCS process P above satisfies the modal -calculus assertion A, where A X.([b]F (haiT []X)). (You should assume the usual properties of boolean operations.) [8 marks] (d) Give, without proof, a short description of those finite-state processes which satisfy the assertion A.

kindly answer all the questions