QUIZ...

Let D be a poset and let f : D D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that whenever D is a domain and f is a continuous function, fix (f) exists. [5 marks] (b) A poset (P, v) has binary meets if for every pair of elements x, y P there is a necessarily unique element (x u y) P such that (x u y) v x and (x u y) v y, and for all z P, z v x and z v y imply z v (x u y). (i) Let (P, v) be a poset with binary meets. Show that the function meet : P P P given by meet(x, y) = x u y is monotone. [5 marks] (ii) Exhibit a domain with binary meets for which the function meet is not continuous. Justify your answer.

All the IO functions can raise some sub-class of IOException. Write code that counts the number of characters and lines in a file and displays those to System.out. [10 marks] Programming in Java In the Discrete Mathematics course you learned that RSA encryption involved having a public key (N, e) where N is the product of two secret primes P and Q and e is an exponent. BigInteger class contains (among others) methods called add, subtract, multiply, divide and remainder. The class String has a method charAt that allows you to extract a character at a given position, and length to tell you how long the string is. Casting a character to an integer yields its character code. Supposing you are given a BigInteger that represents N and an integer for e, and not using any built-in Java methods for raising numbers to powers, write code that (a) takes a string and encodes it as an integer; if the string contains characters c0, c1 . . . the integer required will be c0 + Kc1 + K2 c2 + with the constant K set to 216 so that the full Unicode character set can be accommodated; [7 marks] (b) encodes this number (assuming it is less than N) using the RSA method; [7 marks] (c) creates an encoded string by viewing the integer as if it was written d0 +Ld1 + L 2 d2 + with L = 26 and then representing each d1 as a lower-case letter so that the 26 possible values are all accounted for. [6 marks] 6 CST.99.1.7 SECTION E 11 Operating Systems Most operating systems provide each process with its own address space by providing a level of indirection between virtual and physical addresses. Give three benefits of this approach. [6 marks] Are there any drawbacks? Justify your answer. [2 marks] A processor may support a paged or a segmented virtual address space. (a) Sketch the format of a virtual address in each of these cases, and explain using a diagram how this address is translated to a physical one. [8 marks] (b) In which case is physical memory allocation easier? Justify your answer. [2fits of the segmented approach. [2 marks] 12 Operating Systems File systems comprise a directory service and a storage service. What are the two main functions of the directory service? [2 marks] What is a directory hierarchy? Explain your answer with the aid of a diagram. [2 marks] What information is held in file meta-data? [4 marks] What is a hard link? Does file system support for hard links place any restrictions on the location of file meta-data? [2 marks] What is a soft (or symbolic) link? Does file system support for soft links place any restrictions on the location of file meta-data? [2 marks] Describe with the aid of a diagram a Unix inode. You should explain the motivation behind indirect blocks, and how they are used when accessing a file.

How might you investigate this, and how could you communicate your findings to the development team? [2 marks] (b) A study of the system data logs shows two surprising patterns of behaviour. Some users repeatedly enter different values and then change them, apparently trying out the results. The other pattern includes long pauses between entering each piece of data, with the same users accessing help and documentation pages in alternation with data entry pages. (i) How might you account for these two patterns? [4 marks] (ii) What usability analysis procedures might you carry out to improve usability of the system for these two classes of user? [4 marks] (iii) What improvements might be experienced by each class as a result? [4 marks] (c) After the project has begun, it is decided that the new design should also support two further classes of user: those who do not want to make a tax return online, but simply need to find out what paper documents to request, and staff within the tax office who need to use the system to review people's tax returns when the taxpayer rings up with a telephone enquiry. What usability analysis procedures might you use when customising the user interface for these classes of user, and what improvements might they experience as a result? [6 marks] 10 CST.2009.7.11 11 Information Theory and Coding (a) Let X and Y be discrete random variables over state ensembles {x} and {y} having probability distributions p(x) and p(y), conditional probability distributions p(x|y) and p(y|x), and joint probability distribution p(x, y). Using only these quantities, provide expressions for each of the following: (i) The joint uncertainty H(X, Y ) about both random variables. [2 marks] (ii) The uncertainty H(X|y = bj ) about random variable X once it is known that variable Y has taken on a particular value y = bj . [2 marks] (iii) The average uncertainty H(X|Y ) remaining about random variable X when Y is known. [2 marks] (iv) The mutual information I(X; Y ) between random variables X and Y . (Your answer can use expressions you have defined above.) [2 marks] (v) The union of H(X|Y ), I(X; Y ), and H(Y |X). [2 marks] (b) A noisy binary communication channel randomly corrupts bits with probability p, so its channel matrix is: 1 p p p 1 p (i) If the input bit values {0, 1} are equiprobable, what is the mutual information between the input and output for this noisy channel? [2 marks] (ii) What is the channel capacity of this noisy channel? [1 mark] (iii) If an error-correcting code were designed for this noisy channel, what would be the maximum possible entropy of an input source for which reliable transmission could still be achieved? Express your answer in terms of p. [1 mark] (iv) Name the theorem by Shannon that is the basis for the result in (iii). [1 mark] (c) Explain why the encoding of continuous signals into sequences of coefficients on Gabor wavelets encompasses, as special cases, both the delta function sampling basis and the Fourier Transform basis. Show how one particular parameter determines where a signal representation lies along this continuum that bridges from delta function sampling to the complex exponential. [5 marks] 11 (TURN OVER) CST.2009.7.12 12 Optimising Compilers (a) Explain two concepts of a variable being live - one related to execution behaviour and one related to the structure of a program. Relate them by implication, and explain their relative ease of computation in a compiler. [4 marks] (b) Explain how live variable analysis can be used to allocate variables to registers by colouring. Give and justify an algorithm that performs this colouring, particularly noting how it avoids early decisions causing inconvenient early choices of colour. [5 marks] Let Kn be the graph of n nodes, each having an edge to each other; let Cn have n nodes, but with n edges arranged to give a cycle; and let S be C4 with an additional edge forming a diagonal of C4 seen as a square. (c) What is the minimum number of colours necessary to colour Kn, Cn and S? [3 marks] (d) How many colours does your algorithm require for Cn (if it makes arbitrary choices give both best-case and worse-case)?

(a) Briefly describe what is meant by active and passive RFID tags. [2 marks] (b) Some RFID manufacturers now produce semi-active RFID tags, where a battery is used to power the microelectronics but backscattering is used for all radio communications. Give two advantages and two disadvantages of such tags. [4 marks] (c) Consider a typical binary tree search applied to identify all RFID tags within range of a transmitter. Each request takes the form [ REQ | F | X ], where REQ is a c-bit command ID, F is the f < K filter bits and X is a (K f) bit sequence of 1s. Any response then has the form [ RESP | F | I ], where RESP is a c-bit command ID, F is the first f bits of the replying tag's ID and I represents the remaining (K f) bits of that ID. In an attempt to increase efficiency, a manufacturer proposes that the reader just send [ REQ | F ] and the tags immediately respond with [ I ]. (i) What addition would you have to make to the communications protocol for this to work? What would its overhead be in bits? [3 marks] (ii) Derive an expression for the proportional reduction in search time that this new scheme would provide. Estimate the value of the ratio for a typical tag on the market today. [5 marks] (d) In a probabilistic RFID scheme, the reader transmits the number of slots in a round, N. RFID tags choose a slot uniformly at random and transmit their ID in it. Suggest how to estimate the number of tags in range based only on one round at the reader. [Hint: Consider the expected number of slots with a given property such as being empty or containing a collision.] [6 marks] 2 2 Advanced Graphics (a) State the Jordan curve theorem. [1 mark] (b) Given point V and simple convex planar polygon P={v0, v1, . . . , vn1} in R 3 , express: (i) A test for whether V is coplanar with P. [1 mark] (ii) A test for whether V lies strictly inside P. [2 marks] (iii) A test for whether V lies on the border of P. [1 mark] (c) (i) Describe an algorithm for ray-tracing a complex CSG (Constructive Solid Geometry) shape. How could your algorithm be represented by a state machine? [4 marks] (ii) Identify three Boolean operations that your algorithm would support between primitives. [1 mark] (iii) Would your algorithm perform ray-primitive intersections in local, eye, screen, or world co-ordinates? Why? [2 marks] (d) (i) Show that the closed uniform B-Spline of degree 2 and with knot vector {0, 0, 0, 1, 1, 1} is a quadratic Bezier curve. [6 marks] (ii) Sketch the basis functions of the curve's coefficient polynomials. Accuracy is not critical. [2 marks] 3 Advanced Systems Topics (a) The size and rate of growth of routing tables is an issue of considerable concern for inter-domain routing in the Internet. (i) Describe at least three factors that contribute to this problem. [3 marks] (ii) How might a distinction between Locators and Identifiers help address this problem? [4 marks] (iii) What are the costs and risks of implementing a Loc/ID split? [4 marks] (b) BGP employs a mechanism called Route Flap Damping (RFD) to reduce route instabilities. (i) Describe how RFD works. [4 marks] (ii) Describe some problems with RFD. [2 marks] (iii) Describe another approach to reducing the number of BGP updates. [3 marks] 4 4 Artificial Intelligence II Evil Robot has almost completed his Evil Plan for the total destruction of the human race. He has two nasty chemicals, which he has imaginatively called A and B and which are currently stored in containers 1 and 2 respectively. All he has to do now is mix them together in container 3. His designeran equally evil computer scientisthas equipped Evil Robot with a propositional planning system that allows him to reason about the locations of particular things and about moving a thing from one place to another. (a) Explain how this problem might be represented within a propositional planning system. Give specific examples of the way in which the start state and goal can be represented. [5 marks] (b) Describe in detail an algorithm that can be used to find a plan using this form of representation. [5 marks] (c) Give a specific example of a successor-state axiom using the representation you suggested in part (a). [2 marks] (d) Explain why in this particular planning problem it might be necessary to include one or more precondition axioms and give an example of such an axiom using your representation. [2 marks] (e) Explain why in this particular planning problem it might be necessary to include one or more action exclusion axioms and give an example of such an axiom using your representation. Suggest why it might be unwise to include too many axioms of this type, and explain how a reasonable collection of such axioms might be chosen in a systematic way. [4 marks] (f ) Explain how in this problem it might be possible to include state constraints as an alternative to action exclusion axioms, and give a specific example of such a constraint using your representation. [2 marks] 5 Bioinformatics (a) Discuss, with one example, the complexity of the Nussinov algorithm for RNA folding. [5 marks] (b) In the context of algorithms on strings, what is the advantage of using spaced seeds in database search? [3 marks] (c) Hidden Markov models (HMM) are used to identify genes in genome sequencing projects. (i) Describe how you would build a hidden Markov model to identify genes in a genome sequence. [7 marks] (ii) How would you assess the sensitivity and specificity performance of the HMM? [5 marks] 6 Business Studies (a) Distinguish between debt and equity financing for a young company. [5 marks] (b) You have won a contract to w rite and supply some software and set up a company to do so. The contract is worth 100,000, with 30% payable at start, 20% at a milestone expected to be completed in month 3 after starting, 40% on delivery expected in month 6 and 10% 1 month after delivery. You will need to employ two contract programmers at a rate of 2,500 each per month (plus overheads) for the duration of the contract. (i) Draw up an outline cash flow budget. What is the working capital requirement? [5 marks] (ii) You raise investment of 15,000 in the company and arrange a bank loan facility up to another 15,000 (ignore bank charges and loan interest for this question). You purchase 10,000 of capital equipment initially (computers etc). Draw up the balance sheet at the end of month 6. [5 marks] (iii) The project unfortunately takes an additional two months before passing the milestone. Draw up a revised cash-flow budget including the funds raised and purchases made as specified in part (b)(ii). What effect does this have on the working capital requirement? What options do the Directors have if the bank refuses to extend the loan? [5 marks] 6 7 Comparative Architectures (a) What dependencies exist between the instructions in the code fragment below? Identify both true data dependencies and name dependencies, and for each name dependence indicate whether it is an antidependence or an output dependence. [4 marks] (b) How would a hardware register renaming mechanism remove the name dependencies? Illustrate your answer by providing a version of the code showing the destination and source registers for each instruction after renaming has taken place. Clearly state what free physical registers you assume are available prior to renaming. [4 marks] (c) Why is the removal of name dependencies beneficial within a superscalar processor? [4 marks] (d) In addition to removing name dependencies, for what other purposes may register renaming hardware be used in a superscalar processor? [4 marks] (e) The out-of-order execution of ALU instructions in a superscalar processor is only constrained by the availability of functional units and true data dependencies. Why must the out-of-order execution of memory instructions (e.g. load and store instructions) be constrained further?

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 wr ite 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.