rr1

all questions should be answered correctly

SECTION C 9 Foundations of Functional Programming Consider binary trees that are either empty (written Lf) or have the form Br x t1 t2 where t1 and t2 are themselves binary trees. Give an encoding of binary trees in the -calculus, including functions isLeaf, label , left and right satisfying isLeaf Lf true isLeaf(Br x t1 t2) false label(Br x t1 t2) x left (Br x t1 t2) t1 right (Br x t1 t2) t2 If you use encodings of other data structures, state the properties assumed. [6 marks] Consider the ML functions f and g defined to satisfy f([], ys) = ys f(x :: xs, ys) = f(xs, x :: ys) g([], ys) = ys g(x :: xs, ys) = x :: g(xs, ys) Using list induction, prove f(f(xs, []), []) = xs. [14 marks] [Hint: generalize this formula, making use of g. You may assume the equation g(xs, []) = xs.] 10 Logic and Proof For each of the following formul, construct a proof in the tableau calculus or show that no proof exists. ((A B) A) A [4 marks] z x y ((P(y) Q(z)) (P(x) Q(x))) [12 marks] tu(A B) tu(B A) [4 marks] Assume S4 modal logic for the last one. 6 CST.96.5.7 11 Complexity Theory (a) Show that the problem 3-SAT is at least as hard to solve as n-SAT. [5 marks] (b) Show that the task of finding a minimum cost closed circuit in a weighted directed graph (a Travelling Salesman Problem of the minimization variety) is at least as hard as the Hamiltonian Circuit Problem. [5 marks] (c) Show that the class NP-complete is contained in the class P-space. [5 marks] (d) Show that the class P-space is contained in the class EXP-time. [5 marks] In each case ensure that your answer makes it clear what the problems and classes involved are. Standard results do not need to be proved provided they are clearly stated. 7 CST.96.5.8 12 Semantics The abstract syntax of commands in a simple parallel programming language P is given by C ::= skip X := ie C1 ; C2 if be then C1 else C2 while be do C C1 k C2 where ie, be and X range over the syntactic categories of integer expressions, boolean expressions and program variables, respectively. The intended behaviour of C1 k C2 is that C1 and C2 are executed in parallel until they have both terminated. Hence atomic execution steps from C1 and C2 may be arbitrarily interleaved. The other command forms behave as usual. (a) Give a small-step transition semantics for P which derives statements of the form hC, Si hC 0 , S0 i, where S and S 0 are states. You may assume that rules for the evaluation of expressions have already been given. Comment briefly on your choice of what constitutes an atomic execution step. [9 marks] (b) The binary relation on commands is defined by C1 C2 S, S0 . hC1, Si hskip, S0 i hC2, Si hskip, S0 i. Show that is not a congruence. [5 marks] (c) Assuming that S(X) = S(Y ) = 0, describe the set of possible execution traces which are derivable in your semantics starting from the configuration hC, Si, where C is (X := 1) k (while X = 0 do Y := Y + 1). Why might one argue that this does not accurately reflect the behaviour of a reasonable implementation of the language? [6 marks]

This question offers with stochastic approaches N(t), t zero where N(t) represents the number of activities within the time c programming language [0, t]. (a) (i) Define a Poisson technique N(t), t 0 of price > zero. [2 marks] (ii) Show that N(t) Pois(t) for every constant t > 0. You may additionally use the end result that limn(1 x/n) n = e x with out evidence. [4 marks] (iii) Let X1 be the time of the first occasion of the Poisson procedure N(t). Show that X1 Exp(). (iv) Now given that N(t) = 1 derive the distribution of the time of the single occasion in [0, t]. [4 marks] (b) Suppose that events of a Poisson method of rate are independently selected at random with chance p > 0. Show that the method of selected occasions is likewise a Poisson manner and establish its price. [2 marks] (c) Describe how your result from component (b) can be used to simulate a nonhomogeneous Poisson method whose rate characteristic (t) is such that (t) for all t 0. [6 marks] 4 CST2.2018.8.5 4 Computer Vision (a) Explain how every of the subsequent equations or expressions can be used for detecting and estimating visible motion in a spatio-temporal photograph series I(x, y, t). Include on your solution the call used to explain every of those preferred classes of motion extraction models: (i) I(x, y, t) t = v I(x, y, t)

(a) A processor's most important memory is usually carried out the usage of DRAM. (i) Describe a regular DRAM cellular. [2 marks] (ii) Show, with the useful resource of a diagram, how DRAM is organised, making reference to devices, ranks, banks and arrays. [4 marks] (iii) Describe the difference between an open-web page and closed-page row-buffer coverage and the types of get entry to styles they advantage. [2 marks] (b) The MOSI cache coherence protocol provides a new owned (O) nation to the fundamental MSI protocol.When a cache protecting a line in M nation snoops a read request from every other cache, it transitions to O nation and forwards the facts to the requestor. Subsequent snoops for read requests also are fulfilled by this owner cache. An owned line is dirty and simplest one cache can maintain a line in O kingdom at any time. (i) Describe the difference between cache coherence and reminiscence consistency. [2 marks] (ii) Draw a country transition diagram for the MOSI protocol, the use of a new motion Forward to suggest facts being forwarded from one cache to some other. [6 marks] (iii) Draw a table showing how the country of a line in one cache limits the states the same line will have in a one of a kind cache. [2 marks] (iv) Give two benefits of adding this greater owned country to the simple MSI protocol.

(a) At the bottom degree, what is the number one purchaser of electrical energy in digital logic today? Give a components for the predicted electricity or energy use for a CMOS gate. [2 marks] (b) A matrix (a 2-dimensional array) is saved on-chip in static RAM. What primary factors make a contribution to the time and energy had to transpose it? [4 marks] (ii) When might or not it's beneficial to keep a couple of-copies of the matrix (or every other example records structure) in one DRAM bank? [2 marks] (iii) One manner to avoid transposing a matrix is truly to keep an annotation that it's been transposed and to then switch over the row and column arguments for every operation. Why would possibly bodily performing the transpose in the end advantage performance? Where would the annotation be held? [2 marks] (d) A computation operates on rectangular matrices of length one zero five one zero five . The internal loop, to be elevated in hardware, has the su...

What is a branch delay slot and why does it arise? [7 marks] How can branch delays be avoided? [7 marks] If a processor exhibited one branch delay slot how would you reorder (and possibly modify) the instructions in the following loop to gain a performance advantage? loop ldr r2,r3,#4 % r2=load(r3), r3=r3+4 add r4,r4,r2 % r4=r4+r2 add r1,r1,#1 % r1=r1+1 cmp r1,#10 % compare r1 with constant 10 bne loop % branch if not equal to loop [6 marks] 1 [TURN OVER CST.96.5.2 2 Computer Architecture Write short notes on each of the following parameters of cache design: (a) size [4 marks] (b) mapping function [4 marks] (c) replacement algorithm [4 marks] (d) write policy [4 marks] (e) block size [4 marks] 3 Digital Communication I X A B C D Y Hosts X and Y are communicating through the data network provided by the switches A, B, C and D and the links interconnecting them as shown above. Initially all packets are travelling through switches A, C and D. (a) A packet is corrupted on the link between C and D. Describe the events that take place to recover from the error when (i) an end to end flow and error control protocol is in operation [5 marks] (ii) flow and error control are performed on a hop by hop basis [5 marks] (b) Switch C fails. Describe the events that follow to recover when (i) the network is a datagram network [5 marks] (ii) the network is connection oriented [5 marks] 2 CST.96.5.3 4 Graphics Consider the control of detail in a curve represented as a sequence of straight line segments. Describe Douglas and Peucker's algorithm for removing superfluous points. [10 marks] Describe how Overhauser interpolation can be used to introduce additional points. [10 marks] SECTION B 5 Programming in C and C++ For five of the following C or C++ features write a very short fragment of code (perhaps 2 or 3 lines will suffice in most cases) that illustrates the syntax involved. In each case explain very briefly what your example achieves. (a) preprocessor macros and conditional compilation (b) casts that convert from one pointer type to another (c) C and C++ style comments (d) the declaration of a simple C++ class (e) overloading the operator '+' (f ) the C setjmp function (g) the switch statement, including a default label [4 marks each] 3 [TURN OVER CST.96.5.4 6 Compiler Construction Outline the key features of the design of the part of a compiler that will translate the abstract syntax tree representation of a program into a stack-based intermediate code. Concentrate on those features used in the translation of the following fragment: ... LET i = k LET j = k WHILE (i>0) AND (j<100) DO { i := i-1; j := j+2 } ... In particular, concentrate on the mechanism you would choose to deal with (a) the scopes of identifiers [6 marks] (b) the compilation of boolean expressions involving the operators NOT, AND and OR [6 marks] (c) the translation of the WHILE command [4 marks] (d) the translation of the two assignments [4 marks] 7 Prolog for Artificial Intelligence An ordered integer binary search tree (or OIBS tree) is either empty or a tuple (T, N, U), where T and U are also OIBS trees and N is an integer. Every node in T has a value less than N, which in turn is less than the value of every node in U. (a) Give two Prolog terms which are suitable for representing an empty OIBS tree and a node in the OIBS tree respectively. [2 marks] (b) Define a Prolog procedure insert(Item, T, NT), where Item is an integer being inserted into OIBS tree T, producing an OIBS tree NT. If Item is already present in T, then NT equals T. [9 marks] (c) Define a Prolog procedure lookup(Item, T), where Item is to be looked for in OIBS tree T. A lookup goal will succeed if Item is found, or fail otherwise. [9 marks