Why is there a depletion layer in the immediate vicinity of the junction? 1 [TURN OVER CST.93.1.2 SECTION B 5 Give an ML definition of the function map3 which has the property that map3 f [x1, x2, . . . , xn] = [f 0 x1 x2, f x1 x2 x3, . . . , f xn1 xn 0] and deduce the type of map3. The function map3iter is defined as follows: fun map3iter (0:: ) = 0 | map3iter g x = 1 + map3iter g (map3 g x); Deduce the type of map3iter and explain in words what the function does. Illustrate your answer by considering the call map3iter g [1, 1, 1, 1, 1, 1]; in an environment in which g is defined as follows: fun g 0 1 = 2 | g 1 1 = 1 | g 2 1 = 2 | g 2 0 = 0 | g n = n; 6 The structure of a binary tree containing integers at some of its leaves is given by the ML datatype T defined as follows: datatype T = X | N of int | D of T*T; Define a function filter of type (int -> bool) -> (T -> T) with the property that the call filter p t will yield a simplified copy of t by repeated application of tree rewrite rules: D(X,a) -> a D(a,X) -> a on the tree obtained from t by replacing all leaf nodes of the form N k for which p k yields true by x. Thus, for example: filter (fn n => n=0) should yield a function that converts D(D(N0,N0), D(D(N2,N0), N3)) to D(N2,N3). 2 CST.93.1.3 7 State carefully what it means to say that a function has time complexity O(f(n)), and give ML definitions for some example int ->int functions which have time complexities O(log n), O(n), O(n 2 ), O(n 3 ). In what circumstances can a function have time complexity O(1)? Estimate the time complexities of the functions f1, f2 and f3 defined below: fun f1 0 = 1 | f1 n = 1 + f1(n-1); fun f2 0 = 1 | f2 n = f2(n-1) + f1 n; fun f3 0 = 1 | f3 n = f3(n div 7) + f3(5*n div 7) + f1 n; 8 The structure of a binary tree with integers at the leaves is represented by the following ML datatype: datatype T = n of int | d of T*T; Define a function flatten which when given an argument t of type T will yield the list of integers obtained by a left to right walk over t. For example, flatten (d(d(n1,n2),n3)) = [1,2,3]. Define a function splits which, when given a list of length n > 0, will yield the list of 2-tuples representing t3]), ([1,2], [3]) ]. Hence or otherwise define a function alltrees which, when given a list of length n > 0, will form a list of all the trees of type T that will flatten to the given list. For example, alltrees [1,2,3] = [ d(n1, d(n2, n3)), d(d(n1, n2), n3) ]. 3 [TURN OVER CST.93.1.4 SECTION C 9 A suite of Modula-3 procedures is being developed to handle arbitrarily large nonnegative integers. A test program for handling such numbers includes the following TYPE declaration: TYPE Digit = [0..9]; RefBigNo = REF BigNo; BigNo = RECORD dig:Digit:=0; rest: RefBigNo:= NIL END; A variable of type RefBigNo is a reference to an arbitrarily large number, represented as a sequence of base-10 digits stored in reverse order. The chosen data structure is a record which consists of the last digit of the number and a reference to the remaining digits. Write a procedure Add which will add two of these large numbers and a procedure Print which will convert one such number to type TEXT. The following signatures might be appropriate for the two procedures: PROCEDURE Add(a, b: RefBigNo; carry:=0): RefBigNo = and PROCEDURE Print(N:RefBigNo; first:= TRUE): TEXT =

different basic solutions. (ii) The Simplex Algorithm has a worst-case polynomial runtime. [2 marks] (iii) In each iteration of the Simplex Algorithm, the value of the objective function changes. (iv) The auxiliary linear program in Initialize-Simplex always has a feasible solution. (v) The fundamental theorem of linear programming also holds if linear constraints are allowed to be strict. complete (vi) The set of feasible solutions of any linear program forms a convex set. [2 marks] (b) For the following linear program, write down the auxiliary linear program used by Initialize-Simplex in slack form: [3 marks] minimize 4x1 + x2 subject to 4x1 + 2x2 4 x1 6x2 3 (c) Recall the algorithm for the unweighted vertex cover problem that is based on rounding the solution of a linear program. (i) What is the approximation ratio of this algorithm? [1 mark] (ii) Give an example of a graph and the corresponding linear program for which the gap between the linear program solution and optimal solution is as large as possible. [4 marks] Advanced Algorithms (a) Consider the definition of an approximation algorithm. (i) Explain the meaning of approximation ratio in the case of a maximisation problem. [2 marks] (ii) How is this definition adjusted to the case of a randomised approximation algorithm? [2 marks] (b) State the definition of PTAS and FPTAS. [4 marks] (c) Let G = (V, E) be an undirected graph. For any k 1, define G(k) to be the undirected graph (V (k) , E(k) ), where V (k) is the set of all ordered k-tuples of vertices from V and E (k) is defined so that (v1, v2, . . . , vk) is adjacent to (w1, w2, . . . , wk) if and only if {v1, v2, . . . , vk, w1, w2, . . . , wk} forms a clique. (i) Argue that the graph G(k) can be constructed in time polynomial in n (for any fixed value of k). [3 marks] (ii) Prove that the size of the maximum clique in G(k) is equal to the k-th power of the size of the maximum clique in G. [5 marks] (iii) Argue that if there is a polynomial-time approximation algorithm that has a constant approximation ratio for finding a maximum clique, then there is a polynomial-time approximation scheme (PTAS) for the problem. Hint: Your PTAS should be based on applying the given approximation algorithm with constant approximation ratio to G(k) for a proper choice of k > 0. Then use the equivalence in part (ii) to analyse its approximation ratio. [4 marks] 2 CST2.2019.9.3 2 Bioinformatics (a) Describe, with one example, the complexity of using dynamic programming in multiple alignment. [3 marks] (b) Describe the differences between genome assembly (i.e. using a reference genome) and genome de novo sequencing from a bioinformatics perspective. [5 marks] (c) The de Bruijn Graph is widely used in Bioinformatics. (i) Describe with one example how to construct the paired de Bruijn Graph. [5 marks] (ii) Describe the advantages of the paired de Bruijn Graph versus the non paired version of the de Bruijn Graph. [3 marks] (d) Discuss the advantages of using soft k-means versus hard clustering. [4 marks] 3 (TURN OVER) CST2.2019.9.4 3 Business Studies After graduation you created a venture with 10m in sales with a 20% profit margin. After investing 10 years of your life on this endeavour you have decided that it is time to sell. (a) Describe three exit routes available to you assuming you are not going to liquidate the company. [3 marks] (b) Discuss how you would go about identifying and choosing the exit route to pursue. [6 marks] (c) Identify your preferred exit route and discuss how you would go about managing the process. [11 marks] 4 CST2.2019.9.5 4 Comparative Architectures (a) As modern processors and system-on-chip (SoC) designs become more complex, so does the on-chip interconnect. (i) Why does the design of an on-chip network differ greatly from that of larger scale networks? [3 marks] (ii) Draw a diagram showing the datapath of an on-chip router with virtual channels. [3 marks] (iii) How do virtual channels help to reduce packet latency? [3 marks] (iv) For what reason, other than performance, may virtual-channel flow control be useful? [2 marks] (b) You have been asked to outline the design of a high-performance 16-core processor suitable for use in a server-class machine. Draw a clear block diagram illustrating your architecture. Include all the major building blocks, e.g. processor cores, caches, on-chip interconnects, memory controllers and the main off-chip interfaces. Provide a brief description of how cache coherence is maintained, what type(s) of on-chip interconnect are provided, a brief overview of the features of your individual cores and the characteristics of your caches. For each major component briefly justify your design decisions. [9 marks] 5 (TURN OVER) CST2.2019.9.6 5 Computer Vision (a) In early stages of machine vision systems, the isotropic operator shown on the right is often applied to an image I(x, y) in the following way: [2G(x, y)] I(x, y). What is the purpose of this operation? Which class of neurones in the retina does it mimic? How would the results differ if instead this operation: G(x, y) 2 I(x, y) were performed; or alternatively if this operation: 2 [G(x, y) I(x, y)] were performed? [6 marks] (b) Computer vision colour space is usually three-dimensional, just because human vision is tri-chromatic and therefore cameras are designed with three colour planes. But suppose we added a fourth colour plane, say yellow (Y), to the standard red, green, and blue (RGB) bands. Considering that these are linearly independent but not orthogonal vectors, what would be the added capability of RGBY space? What tests would reveal it? Present a version of the Retinex algorithm for RGBY space, explaining the purpose of each step in the algorithm. [8 marks] (c) Visual inference of surface shape depends on assumptions and prior knowledge, such as "faces are mostly convex". Explain the "rotating hollow mask illusion". Why does a face mask (as pictured below) appear to reverse its direction of rotation, once it is seen from the inside instead of the outside? What is the role of Bayesian inference when interpreting a face-like surface that is actually concave in presentation instead of convex? Should visual illusions like this be considered "features" or "bugs", and should one try to design them in to a computer vision system? [6 marks] 6 CST2.2019.9.7 6 Cryptography (a) (i) Choose and briefly describe one major application of elliptic-curve group operations in cryptography. [4 marks] (ii) What other group operation was previously (and still is) widely used for the same purpose? [2 marks] (iii) What is a major advantage of elliptic curve group operations over the group operation you named in Part (a)(ii)? [4 marks] (b) In the Galois field GF(28 ) modulo x 8 + x 4 + x 3 + x 2 + 1, calculate (i) the sum 0011 1001 plus 0110 1100; [2 marks] (ii) the product 0100 1011 times 0000 1001. [4 marks] (c) In Lamport's one-time password scheme, the user is given a list of passwords Rn, . . . , R0 generated using the following algorithm: R0 random for i := 1 to n Ri := h(Ri1) (i) State two properties required of function h. [2 marks] (ii) Complete the password verification algorithm implemented in the server by filling in the ellipses (...) below: Q := . . . while true P := read password if . . . . . . grant access else deny access [2 marks] 7 (TURN OVER) CST2.2019.9.8 7 Denotational Semantics (a) Suppose that (D, v) is a poset which is chain-complete but does not have a least element, and that f : D D is a continuous function. (i) Give an example of such (D, v) and f for which f has no fixed point. [1 mark] (ii) If d D satisfies d v f(d), prove that there is a least element e D satisfying d v e = f(e). [Hint: consider the method used to prove Tarski's fixed point theorem.] [7 marks] (b) (i) Define the notion of contextual equivalence for the language PCF. (You need not describe the syntax and semantics of PCF.) [2 marks] (ii) State the compositionality, soundness and adequacy properties of the denotational semantics of PCF. Explain why they imply that any two closed PCF terms of the same type with equal denotations are contextually equivalent. [8 marks] (iii) Give, without proof, an example of two contextually equivalent PCF terms that have unequal denotation. [2 marks] 8 CST2.2019.9.9 8 Hoare Logic and Model Checking This question is about modelling a program, defined below, consisting of two threads and a single (mathematical) integer variable X, initially set to 0. Each thread t has its own program counter given by pct , initially set to 0, which describes the current line for that thread. Thread 1 Thread 2 0: X := X+1 0: IF IS ODD(X) THEN STOP ALL 1: GOTO 0 1: GOTO 0 The program is executed by repeatedly carrying out execution steps, where one thread is non-deterministically selected, its entire current line is run, and its program counter is then updated appropriately. This continues until STOP ALL is executed, which immediately terminates the whole program. (a) The program state can be described by (pc1, pc2, X, stopped), where pc1, pc2, and X are mathematical integers, and stopped is a boolean which is true iff STOP ALL has been executed. Let S be the set of all such states. (i) Define S0, the set of initial states of the program, such that S0 S.