Describe how to construct the function cpo ((D E), v) of two cpos (D, vD) and
Question:
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 facts about least upper bounds provided you state them clearly.) [7 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. Exhibit the domain element on which the two denotations differ. [7 marks] 2 VLSI Design Write brief notes (including circuit diagrams if appropriate) on the following schemes for carry propagation in binary addition: (a) ripple carry; (b) Manchester carry; (c) carry look-ahead tree; (d) carry skip; (e) carry select. [4 marks each] 2 CST.2002.9.3 3 Digital Communication II (a) Current TCP incurs loss to discover the available capacity. Describe the AIMD (Additive Increase, Multiplicative Decrease) mechanism, and fast recovery, and show how this leads to the characteristic "saw tooth" throughput behaviour of TCP over time. [5 marks] (b) Consider a TCP connection operating in steady-state whereby each time the congestion window increases to W segments a single packet loss occurs. In terms of W and the round trip time (R), derive a simple formula for the time between the minimum and maximum data rates achieved. In this optimal scenario, how many packets are sent between each loss event? [4 marks] (c) Derive the connection's average throughput in terms of the fraction of packets lost (p), the connection's round trip time (R), and the segment size (B). [4 marks] (d) Under what conditions is this very simplistic model likely to be accurate? [3 marks] (e) How can router support for Explicit Congestion Notification (ECN) be used to smooth the TCP throughput? [4 marks] 3 [TURN OVER CST.2002.9.4 4 HCI (a) Identify three notations that might be found in the user interface of a generic word processor. For each of these, identify an important attribute relevant to the design of a new word processor, explaining how each would affect users' experience of the product. [10 marks] (b) The following screen shot is taken from a product designed by a local company. Describe two techniques for examining usability of this product, suggesting for each of them four ways in which they might influence the design. [10 marks] 4 CST.2002.9.5 5 Business Studies (a) Explain the differences between (i) credit and debit; (ii) cash-flow and profit & loss statements; (iii) equity and debt finance; (iv) NPV and IRR; (v) asset and DCF based valuation. [2 marks each] (b) A certain small software company has assets of about £100K (not including development work-in-progress), and an average cash-flow of about £15,000 per month, with a net profit of around £2000 per month. They are developing, but have not yet completed, a new graphical search engine into which they have invested about £100K of design and programmer time. The founders have invested about £150K, mostly in equity, and there is a long term debenture of £100K. Provide a range of valuations for the company. Include notes explaining your assumptions and the basis for each valuation. [10 marks] 5 [TURN OVER CST.2002.9.6 6 Types (a) Give the typing rules for the polymorphic lambda calculus (PLC). [5 marks] (b) Let prod(α1, α2) denote the PLC type ∀α((α1 → (α2 → α)) → α). Explain how it behaves like the ML product type α1 * α2. To do so, you should give PLC expressions pair , fst and snd of types ∀α1(∀α2(α1 → (α2 → prod(α1, α2)))), ∀α1(∀α2(prod(α1, α2) → α1)), and ∀α1(∀α2(prod(α1, α2) → α2)) respectively, corresponding to the ML polymorphic pairing and projection functions fn x1 => fn x2 => (x1, x2) , fn (x1, x2) => x1 , and fn (x1, x2) => x2 . Give proofs for the typing of pair and fst, and explain the beta-conversion properties of fst τ1 τ2(pair τ1 τ2 M1 M2), for any PLC types τ1, τ2 and terms M1, M2. [10 marks] (c) Is it always the case that a PLC term M of type prod(τ1, τ2) is beta-convertible to pair τ1 τ2(fst τ1 τ2 M)(snd τ1 τ2 M)? Justify your answer. [Hint: consider terms with free variables.] [5 marks] 6 CST.2002.9.7 7 Optimising Compilers (a) Explain clearly an algorithm to schedule assembler code for a given architecture to increase its efficiency; the algorithm must give exactly the same instructions as in the original code, possibly in a different order. You may assume the hardware is interlocked so that NOPs are not required. Your answer should state the range over which scheduling takes place and, if this is smaller than a procedure, what actions can sensibly be taken at the boundary between separately scheduled sections of code. [10 marks] (b) Consider an architecture which is ARM-like—the first operand is the destination register except in the case of stores. All operations take one cycle, with the exceptions that (i) using the value resulting from an immediately previous load will cause a single-cycle stall, as does (ii) the second of two successive store instructions. Use your algorithm to schedule the following code, noting briefly, for each instruction emitted, why your algorithm has chosen this instruction over other candidates. ldr r3,[r1,#0] str r3,[r2,#0] ldr r4,[r1,#4] str r4,[r2,#4] add r5,r4,#4 [6 marks] (c) Give with brief explanation the number of possible valid schedulings of the following code (not just the one produced by your algorithm): add r3,r1,r2 or r4,r1,r2 sub r5,r3,r4 xor r4,r1,r3 [4 marks] 7 [TURN OVER CST.2002.9.8 8 Advanced Algorithms (a) Explain how to check a large number for primality using a probabilistic method that gives you a bound of the probability of getting an incorrect judgment. [7 marks] (b) Give an asymptotic formula predicting the number of computer operations needed to verify that a number with n bits is prime, supposing that multiplication, division and remaindering are done using O(n 2 ) methods and that you want to achieve a probability of error bounded by 1 in 260. You do not need to prove that the algorithm you describe works, but you should nevertheless explain it carefully and completely. [7 marks] (c) The gap between adjacent primes near the integer N is roughly log(N). Estimate roughly the number of computer operations you would expect to be needed to find a 2000-bit prime that is just slightly larger than some given 2000-bit random number. [6 marks] 8 CST.2002.9.9 9 Neural Computing Explain the mechanisms and computational significance of nerve impulse generation and transmission. Include the following aspects: (a) Equivalent electrical circuit for an excitable nerve cell membrane. (b) How different ion species flow across the membrane, in terms of currents, capacitance, conductances, and voltage-dependence. (Your answer can be qualitative.) (c) Role of positive feedback and voltage-dependent conductances. (d) The respect in which a nerve impulse is a mathematical catastrophe. (e) Approximate time-scale of events, and the speed of nerve impulse propagation. (f ) What happens when a propagating nerve impulse reaches an axonal branch. (g) What would happen if two impulses approached each other from opposite directions along a single nerve fibre and collided. (h) How linear operations like integration in space and time can be combined in dendritic trees with logical or Boolean operations such as AND, OR, NOT, and veto. (i) Whether "processing" can be distinguished from "communications" as it is for artificial computing devices. (j) Respects in which stochasticity in nerve impulse time-series may offer computational opportunities that are absent in synchronous deterministic logic. [2 marks each] 9 [TURN OVER CST.2002.9.10 10 Information Theory and Coding (a) (i) A Hamming Code allows reliable transmission of data over a noisy channel with guaranteed error correction as long as no more than one bit in any block of 7 is corrupted. What is the maximum possible rate of information transmission, in units of (data bits reliably received) per (number of bits transmitted), when using such an error correcting code? [2 marks] (ii) In such a code, what type of Boolean operator on the data bits is used to build the syndromes? Is this operator applied before transmission, or upon reception? [2 marks] (b) (i) For each of the four classes of signals in the following table, Class Signal Type 1. continuous, aperiodic 2. continuous, periodic 3. discrete, aperiodic 4. discrete, periodic identify its characteristic spectrum from the following table: Class Spectral Characteristic A. continuous, aperiodic B. continuous, periodic C. discrete, aperiodic D. discrete, periodic (Give your answer just in the form 1-A, 2-B, etc. Note that you have 24 different possibilities.) [8 marks] (ii) For each case, name one example of such a function and its Fourier transform. [4 marks] (c) Give two reasons why Logan's Theorem about the richness of zero-crossings for encoding and recovering all the information in a one-octave signal may not be applicable to images as it is for one-dimensional signals. [4 marks] 10 CST.2002.9.11 11 Numerical Analysis II Consider the alternative formulae yn+1 = yn + hf(xn, yn) + O(h 2 ) (1) yn+1 = yn−1 + 2hf(xn, yn) + O(h 3 ) (2) applied to the ODE y 0 = −5y, y(0) = 1 using h = 0.1 in each case. (a) Define the terms local error and order for an ODE formula. What is the order of each of the methods (1) and (2)? [2 marks] (b) Giving answers to 2 significant decimal digits of accuracy, compute the solution of the ODE for xn = 0, 0.1, 0.2, . . . 1.0 for each method. Tabulate your answers. The exact solutions to 2 significant digits are: 1.0, 0.61, 0.37, 0.22, 0.14, 0.082, 0.050, 0.030, 0.018, 0.011, 0.0067 Assume the exact value of y(0.1) for method (2). [7 marks] (c) Which method is more accurate initially and why?You have available a 20 Gbyte disc on which you need to hold an indexed sequential file consisting of variable length records each having a 20 byte key. Records, including the key, are typically 500 bytes long but never exceed 1000 bytes. The total size of all the records is never more than 10 Gbytes. (a) Suggest, in detail, how you would represent this file on the disc. You should choose an organisation that allows (i) efficient insertion of new records, (ii) efficient updating of existing records identified by key, and (iii) efficient inspection of all records in key order. [14 marks] (b) If the total size of the database is 10 Gbytes, estimate, for your organisation of the file, how many disc transfers would be needed to access a record with a given key, and estimate how many transfers would be required to read the entire database in sequential order. [6 marks] 2 Computer Design Modern dynamic random access memories (e.g. DRAM, SDRAM and RAMBUS) all support burst mode read and write access. (a) Give an outline of the bus activity for a burst mode read access. [4 marks] (b) Explain the difference between a direct mapped cache and an associative cache. [4 marks] (c) What cache line replacement policies are typically used for a direct mapped cache and a set associative cache? [4 marks] (d) Why are caches able to exploit burst mode accesses, and why is a write buffer often used? [4 marks] (e) What is bus snooping and what does it achieve? [4 marks] 2 CST.2002.12.3 3 Digital Communication I Consider the real-time transport of audio across a network. (a) What are the advantages of digitising the audio? [5 marks] (b) What are the disadvantages and how can they be mitigated? [5 marks] (c) What characteristics of the end-to-end channel across the network would be desirable, and how are these different from those which would be desirable for time-insensitive data? [5 marks] (d) Discuss the applicability of asynchronous and synchronous multiplexing in carrying real-time audio traffic. [5 marks] 4 Business Studies (a) Distinguish between top-down, bottom-up and spiral (rapid prototype) development methodologies. Illustrate your answer with reference to an example of designing a building. [5 marks] (b) You are in charge of commissioning the design of a new building, such as the new Computer Laboratory building. Draw up a high-level GANTT chart for this task up to the letting of the building contract. [10 marks] (c) Discuss what monitoring and quality control procedures might apply to the design process. How will you get the agreement of the various stakeholders? [5 marks] 3 [TURN OVER CST.2002.12.4 5 Comparative Programming Languages This question concerns the representation of parse tree nodes for expressions composed of integer constants, identifiers, and integer operators for addition, subtraction, multiplication and division. In a typeless language, such as BCPL, each node can be implemented as a vector whose first element holds an integer identifying the node operator. The size of the vector and the kinds of value held in the other elements then depends on this node operator. (a) Complete the description of how you would represent such integer expressions in a typeless language. [5 marks] (b) Suggest how you would represent such integer expressions in C and either ML or Java. [10 marks] (c) Briefly discuss the relative merits of your C data structure compared with that used in the typeless approach. [5 marks] 6 Compiler Construction (a) Assuming a Java type is given to each variable, state a method by which an overloaded operator (such as +,- etc.) in a Java program can be determined to be an int, real or other operator. [3 marks] (b) Explain, using pseudo-code as appropriate, how to convert a syntax-tree into stack code such as that used in the JVM. For the purposes of this question, you only need consider trees representing bodies of void-returning functions, and these bodies only as consisting of a list of statements of the form int x = e; or x = e; where x ranges over variables and e over expressions; expressions contain variables, integer constants, the binary operator + and static method invocations. [10 marks] (c) Show how a sequence of simple stack code instructions, such as those used in your answer to part (b) above, can be translated into a sequence of instructions for a register-oriented architecture of your choice, for example ARM or Pentium. [7 marks] 4 CST.2002.12.5 7 Prolog for Artificial Intelligence (a) Give a simple definition of the Prolog predicate dfx that can perform symbolic differentiation with respect to the variable x of expressions composed of integers (e.g. 0, 1, . . .), symbolic constants (e.g. a, b, . . .), symbolic variables (e.g. x, y, . . .) and the operators +, - and *, for addition, subtraction and multiplication. The first argument of dfx is the expression to differentiate and the second argument is the result. Your definition need not perform any simplification of the result. [6 marks] (b) Trace the execution of the call: dfx(x*x-2, R). [2 marks] (c) Now modify your definition so that it simplifies the result by the applications of rewriting rules such as: 1*x⇒x and x-0⇒x. [8 marks] (d) Discuss to what extent, if any, either of your predicates could be used to integrate an expression. [4 marks] 8 Databases (a) Describe the relational model of data. [6 marks] (b) Explain the following concepts in relational databases: (i) entity integrity constraint; [1 mark] (ii) foreign key and how it can specify a referential integrity constraint between two relations; [4 marks] (iii) semantic integrity constraint. [1 mark] (c) (i) What is a functional dependency? [1 mark] (ii) Define Boyce-Codd Normal Form (BCNF). [3 marks] (iii) Define Third Normal Form (3NF). [3 marks] (iv) What is the relationship between BCNF and 3NF? [1 mark] 5 [TURN OVER CST.2002.12.6 9 Numerical Analysis II (a) In the Chebyshev characterisation theorem, the best L∞ approximation to f(x) over a closed finite interval by a polynomial pn−1(x) of degree n − 1 has the property that the maximum error |e(x)| is attained at M distinct points ξj such that e(ξj ) = −e(ξj−1). What is M? [2 marks] (b) Let x = m × 2 k represent a normalised number in a floating-point implementation. When computing √ x show how the domain of the problem can be reduced to x ∈ [1, 4). Find the coefficients a, b which minimise ||e(x)||∞ over [1, 4] where e(x) = ax + b − √ x. [8 marks] (c) Taking full account of symmetry, describe the form of the best polynomial approximation p(x) to x 4 over [−1, 1] by a polynomial of lower degree. Sketch x 4 and p(x), showing the extreme values of |e(x)| where e(x) = x 4 − p(x).Outline how partial and total correctness specifications can be translated into higher order logic. [4 marks] (d) Give one advantage and one disadvantage of regarding Hoare Logic as a theory in higher order logic. [2 + 2 marks] 2 CST.2002.7.3 2 Specification and Verification II Consider a 3 × 3 array of 9 switches 1 2 3 4 5 6 7 8 9 Suppose each switch 1, 2, . . . , 9 can be either on or off, and that toggling any switch will automatically toggle all its immediate neighbours. For example, toggling switch 5 will also toggle switches 2, 4, 6 and 8, and toggling switch 6 will also toggle switches 3, 5 and 9. (a) Devise (i) a state space and (ii) transition relation to represent the behaviour of the array of switches. [4 + 6 marks] (b) You are given the problem of getting from an initial state in which even numbered switches are on and odd numbered switches are off, to a final state in which all the switches are off. Write down predicates on your state space that characterise the (i) initial and (ii) final states. [2 + 2 marks] (c) Explain how you might use a model checker to find a sequence of switches to toggle to get from the initial to final state. [6 marks] You are not expected actually to solve the problem, but only to explain how to represent it in terms of model checking. 3 [TURN OVER CST.2002.7.4 3 Comparative Architectures A na¨ıve programmer writes the following code for performing the matrix multiplyadd function C = AB + C on square matrices: for (i=0;i Hence compute the coefficients of p(x). [10 marks] 10 Introduction to Functional Programming (a) Give a recursive definition of an ML datatype 'a tree of binary trees consisting of nodes where data items are stored. Each such node is either a leaf or a branch node with left and right trees as branches. [3 marks] (b) Write a recursive function size of type 'a tree -> int that returns the number of nodes of a given tree. [4 marks] (c) Write an iterative function isize of type int * 'a tree -> int which satisfies the following identity for all integers n and all trees t isize(n, t) = size(t) + n (1) [6 marks] (d) Prove, by structural induction, that the identity (1) holds for the two functions you defined. [7 marks] 6 CST.2002.12.7 11 Computer Vision The following very useful operator is often applied to an image I(x, y) in computer vision algorithms, to generate a related "image" g(x, y): g(x, y) = Z α Z β ∇2 e −((x−α) 2+(y−β) 2 )/σ2 I(α, β) dα dβ where ∇2 = ∂ 2 ∂x2 + ∂ 2 ∂y2 (a) Give the general name for this type of mathematical operator, and the chief purpose that it serves in computer vision. [2 marks] (b) What image properties should correspond to the zeroes of the equation, i.e. those points (x, y) in the image I(x, y) where the above result g(x, y) = 0? [3 marks] (c) What is the significance of the parameter σ? If you increased its value, would there be more or fewer points (x, y) at which g(x, y) = 0? [3 marks] (d) Describe the effect of the above operator in terms of the two-dimensional Fourier domain. What is the Fourier terminology for this image-domain operator? What are its general effects as a function of frequency, and as a function of orientation? [4 marks] (e) If the computation of g(x, y) above were to be implemented entirely by Fourier methods, would the complexity of this computation be greater or less than the image-domain operation expressed above, and why? What would be the tradeoffs involved? [4 marks] (f ) If the image I(x, y) has 2D Fourier Transform F(u, v), provide an expression for G(u, v), the 2D Fourier Transform of the desired result g(x, y) in terms of only the Fourier plane variables u, v, F(u, v), and the above parameter σ. [4 marks] 7 [TURN OVER CST.2002.12.8 12 Complexity Theory (a) Give a precise definition of what is meant by the statement that a decision problem A is polynomial-time reducible to a decision problem B. [2 marks] (b) Consider the following three decision problems on graphs. Connect—the collection of graphs G such that there is a path between any two vertices of G. Hamilton—the collection of graphs that contain a Hamiltonian cycle. non-3-colour—the collection of graphs that are not 3-colourable. For each of the following statements, state whether it is true, false or an unresolved open question. Give a brief justification for your answer. (i) Connect is decidable by a polynomial time algorithm. (ii) Hamilton is decidable by a polynomial time algorithm. (iii) non-3-colour is decidable by a polynomial time algorithm. (iv) Connect is polynomial-time reducible to Hamilton. (v) Hamilton is polynomial-time reducible to non-3-colour. (vi) non-3-colour is polynomial-time reducible to Connect. [3 marks each] Explain the behaviour of each method as x increases. [3 marks] (d) Solve the ODE. Find a general term for yn in method (1) and show that the absolute error in (1) will be small when n is large. Without performing any further calculations, how do you expect the absolute error in method (2) to behave when n is large? [5 marks] (e) Discuss briefly the suitability of formulae (1) and (2) as predictors for predictor-corrector methods in respect of order and stability. [3 marks] 11 [TURN OVER CST.2002.9.12 12 Specification and Verification II The multiplexer MUX, register REG c (where c is the initial value) and combinational unit COM f (where f is the function computed) are defined to have the behaviour given below. MUX(sw,i1,i2,o) = ∀t. o t = if sw t then i1 t else i2 t REG c (i,o) = (o 0 = c) ∧ ∀t. o(t+1) = i t COM f (i,o) = ∀t. o t = f(i t) Using only instances of MUX, REG c and COM f design a device DEV(c,f) that satisfies DEV(c,f)(reset,i,o) = (o 0 = c) ∧ ∀t. o(t+1) = if reset(t+1) then c else f(o t) [8 marks] Prove that your design meets this specification. [12 marks] 12 CST.2002.9.13 13 Computer Vision (a) Consider the "eigenfaces" approach to face recognition in computer vision. (i) What is the rˆole of the database population of example faces upon which this algorithm depends? [4 marks] (ii) What are the features that the algorithm extracts, and how does it compute them? How is any given face represented in terms of the existing population of faces? [4 marks] (iii) What are the strengths and the weaknesses of this type of representation for human faces? What invariances, if any, does this algorithm capture over the factors of perspective angle (or pose), illumination geometry, and facial expression? [4 marks] (iv) Describe the relative computational complexity of this algorithm, its ability to learn over time, and its typical performance in face recognition trials. [4 marks] (b) What is the following block of code doing over the image array image[i][j] as it computes the resulting new image array result[i][j] ? Give the appropriate mathematical name for this operation, and describe what it accomplishes. What are some computer vision tasks that might use this block of four nested for loops? for (i = 0; i < iend; i++) { for (j = 0; j < jend; j++) { sum = 0; for (m = 0; m < mend; m++) { for (n = 0; n < nend; n++ ) { sum += kernel[m][n] * image[i-m][j-n]; } } result[i][j] = sum/(mend*nend); } } [4 marks] 13 [TURN OVER CST.2002.9.14 14 Natural Language Processing The Ultimate Dating Agency has a database which contains enough information to respond to requests like: List every computer scientist with any friends who obsess(es) about some reprogrammable device(s). (a) Describe the different queries that result from adding each morphological suffix in brackets. [2 marks] (b) Give formulae of first-order logic which represent these different queries. [6 marks] (c) Describe techniques for morphological analysis, syntactic parsing and compositional semantic interpretation that would output such representations. [9 marks] (d) How might the database information be represented and queried?