.QUESTION .all the questions to be thoroughly explained

Invocations of its type operations involve no writes to persistent memory and no output to clients. Concurrent processes may invoke the object. How can the operations be made atomic? [8 marks] (b) A data object exists in persistent memory. (i) A single operation is invoked on it in response to a request from a client. The result of the invocation is output to the client. How can the operation be made atomic? [4 marks] (ii) A client requests a high-level operation which comprises more than one of the type operations on the data object. How can the high-level operation be made atomic? [8 marks] 3 [TURN OVER CST.93.5.4 8 Databases Describe the relational model of data. [4 marks] What is meant by a candidate key? [2 marks] Explain what it means for a relational data model to be presented in (a) Third Normal Form (3NF) [5 marks] (b) Fourth Normal Form (4NF) [5 marks] in each case illustrating your answer with a suitable example data model. In what circumstances might it not be sensible to hold relational data according to these normal forms? [4 marks] SECTION C 9 Foundations of Functional Programming Describe how the -calculus models the operations of addition, test for zero and successor, representing the natural numbers by Church numerals. [4 marks] The Fibonacci sequence is defined by F0 = 0, F1 = 1 and Fk = Fk1 + Fk2 for k > 2. Present a -term fib that computes the Church numeral for Fk given the Church numeral for k, for all k > 0. Do not use Y or any other fixed point combinator. You may take as primitive the -calculus encodings of standard data structures. [6 marks] Describe how to assign Godel numbers to -terms and explain the notation pMq. Describe an application of these techniques. [3 marks] Present a -term iszero, such that iszeropMq = true if M = 0 false if M 6= 0 or prove that no such term exists. [7 marks] 4 CST.93.5.5 10 Computation Theory Show that there is no way of deciding by algorithms whether a general register machine program with code p will terminate when started with initial data of 0 in every register. [10 marks] Show that there is no way of deciding by algorithm whether the blank character will be printed during the course of a general Turing machine comutation. [10 marks] Note: any standard form of the undecidability result for the general halting problem may be assumed, but should be stated clearly. 11 Complexity Theory Explain how to measure the size of a problem in complexity theory. [3 marks] What is meant by reducing one problem to another? [4 marks] Given that the Boolean Satisfiability Problem is NP-complete, show that the Hamiltonian Circuit Problem for undirected graphs is also NP-complete. [13 marks] 12 Formal Languages and Automata Explain what is meant by a regular expression over an alphabet , and by the language L(r) denoted by such a regular expression r. [5 marks] For any regular expressions r, s, t, show that if L(r) contains L(t|sr) then it also contains L(s*t). [5 marks] Assuming that the empty string is not in L(s), show that if L(r) = L(t|sr) then L(r) = L(s*t). Hint: argue by induction on the length of strings in L(r). [5 marks] Give an example to show that the above assumption 6 L(s) is necessary.

Give a brief description of the main constructs used in a VDM specification. [7 marks] Discuss to what extent the notation used in VDM is significantly different from that used in a conventional programming language. [6 marks] Use VDM to specify a function that will find the difference between the largest and the smallest values held in an integer array. [7 marks] 2 CST.93.11.3 4 Prolog The following Prolog clauses define the procedure named reverse. The goal reverse(X,Y) succeeds for the list X, instantiating Y to the reverse of the list X. For example, evaluating the goal reverse([a,b,c],Q) instantiates Q to [c,b,a]. reverse(X,Y) :- rev(X,[],Y). rev([],L,L). rev([H|T],R,Y) :- rev(T,[H|R],Y). Explain how this procedure works, using a small example. [10 marks] What is the outcome of the goal reverse(L,[a,b,c])? Explain your answer carefully. [10 marks] 5 Programming Language Compilation Give a brief description of the main features of Lex and Yacc. [5+5 marks] Illustrate their use by outlining how you would construct a parser for expressions composed of identifiers, integers, function calls and the operators *, /, + and -. [10 marks] 6 UNIX Case Study Show how race conditions can arise: (a) among processes over access to shared data [4 marks] (b) between processes and interrupt-driven routines [4 marks] Discuss why the UNIX kernel cannot be run on a shared-memory multiprocessor. [7 marks] Outline how the UNIX kernel could be modified to run on a shared-memory multiprocessor. [3 marks] Describe briefly an alternative approach. [2 marks] 3 [TURN OVER CST.93.11.4 7 Operating System Functions In relation to virtual memory, describe the terms segment, page and translation lookaside buffer (TLB). [6 marks] The operating system for a microprocessor supports a virtual memory model which implements both segmentation and paging. The only hardware assistance for the virtual memory system in the microprocessor is an on-chip TLB. Outline the data structures held by the operating system. [5 marks] Describe the actions of the operating system in response to an address exception due to not matching the address issued by the processor in the TLB. [5 marks] How can the operating system use access permissions to aid its page replacement policy? [4 marks] 8 Data Structures and Algorithms Describe (a) how to determine whether or not a point is inside a simple plane closed polygon, paying proper attention to awkward cases [6 marks] (b) how, with luck, to exclude large numbers of points from the convex hull of a set of points in the plane, with due consideration of what can go wrong [7 marks] (c) how to compute economically the convex hull of the points that are left after the measures you have described in (b) above [7 marks] 9 Graphics II When scan-converting items for display, a Z-buffer is sometimes used to avoid some sorting. Outline its operation and limitations. [12 marks] The use of an A-buffer will improve matters. Explain why. [8 marks] 4 CST.93.11.5 10 Numerical Analysis I What is meant by the term loss of significance? What is the essential difference between the terms condition and stability in numerical analysis? Define the term machine epsilon and explain why it is an important parameter. [6 marks] Use the recurrence formula cos[(k + 1)] = 2 cos cos[k] cos[(k 1)] with starting values cos 0 = 1, cos = 1 2 + to evaluate cos 2 and show that loss of significance occurs. [4 marks] Evaluate cos 3 and cos 4, ignoring terms O( 3 ). On this evidence, comment on the stability of the formula. [8 marks] Is the computed value of cos 2 acceptable? Explain your answer. [2 marks] 11 Discrete Mathematics Let A be a non-empty set, and be a relation on A. What is meant by saying that (A, ) is a partially ordered set? [3 marks] What additional conditions must be satisfied if (A, ) is to form: (a) a totally ordered set [1 mark] (b) a well-ordered set [2 marks] (c) a complete partially ordered set? [3 marks] Suppose now that A is a non-empty set, R a relation on A, and B A a non-empty subset. Write RB = R (B B) for the relation induced on B by R. Show that if (A, ) is a partially ordered set, so also is (B, B). [1 mark] On the set Z = {0, 1, 2, . . .} of integers define the following relations: (i) 6 = S , the reflexive transitive closure of S = {(n, n + 1) : n Z} (ii) d = {(m, n) : q Z such that mq = n}

(a) What is a block chain in the context of electronic money? [4 marks] (b) Explain the use of a block chain in Bitcoin. Why is it required? [4 marks] (c) Discuss whether Bitcoin is anonymous. [6 marks] (d) Discuss whether Bitcoin is a currency. [6 marks] 6 Temporal Logic and Model Checking In this question assume that p and q are atomic formulae. (a) Compare and contrast path formulae and state formulae in temporal logic. [4 marks] (b) Describe and contrast the meanings of F(G p) and AF(AG p). [4 marks] (c) Describe and contrast the meanings of G(F p) and AG(AF p). [4 marks] (d) Write down and justify a temporal logic formula that expresses the property that some state satisfying q is reachable from every state satisfying p. [4 marks] (e) Write down and justify a temporal logic formula that expresses the property that no path contains a consecutive sequence of 256 states satisfying p. [4 marks] 6 CST.2015.8.7 7 Information Retrieval (a) Consider a standard bag-of-words model for the document retrieval problem. (i) Give an expression for the tf-idf weighting scheme which assigns a weight to each term in a document. Motivate each part of your expression, using the notion of Zipf's law when appropriate. [3 marks] (ii) How might you modify your tf-idf scheme for each term in a query? Why might you use different schemes for documents and queries? [3 marks] (b) Edit distance can be used for spelling correction in search queries. (i) Define edit distance. [1 mark] (ii) As an example of how to calculate edit distance efficiently, show how dynamic programming can be used to calculate the edit distance between able and belt. [5 marks] (c) The PageRank algorithm uses a model of a "random surfer" to calculate the importance or validity of a page. Describe how the random surfer can be modelled as an ergodic Markov chain, and how this leads to the PageRank values being calculated as a principal left eigenvector of the transition probability matrix. (You are not required to give a formal definition of an ergodic Markov chain; an informal description will suffice.) [8 marks] 7 (TURN OVER) CST.2015.8.8 8 Quantum Computing (a) Consider the following two-qubit quantum state, |i. 2 3 3 |00i 1 6 |01i + 2i 2 3 3 |10i 5i 3 6 |11i (i) What are the probabilities of outcomes 0 and 1 if the first qubit of |i is measured? (ii) What are the probabilities of outcomes 0 and 1 if the second qubit of |i is measured? (iii) What is the state of the system after the first qubit of |i is measured to be a 0? (iv) What is the state of the system if the second qubit of |i is measured to be a 1? (v) What are the probabilities of outcomes 0 and 1 if the second qubit of the system is measured, after the first qubit of |i has been measured to be 0? (vi) What are the probabilities of outcomes 0 and 1 if the first qubit of the system is measured, after the second qubit of |i has been measured to be 1? [2 marks each] (b) The two qubit quantum Fourier transform is given by the following matrix. F2 = 1 2 1 1 1 1 1 i 1 i 1 1 1 1 1 i 1 i Sketch a circuit for implementing the operator F2 using any combination of 1-qubit Hadamard gates; 1-qubit Pauli gates; 2-qubit C-NOT gates; controlled phase shifts and swap gates (the swap gate S is defined by S|xyi = |yxi). Briefly explain your circuit. [8 marks] 8 CST.2015.8.9 9 Security II You are working on an encryption device with your new colleague, Mallory Baish, who proposes that you use a pseudo-random generator ri = h1(si), si+1 = h2(si) where s0 G is the random initial state and the other si G are subsequent internal states, all invisible to adversaries. The h1, h2 : G G are two secure one-way functions. Adversaries may see any of the past outputs r0, . . . , rn1. If they can predict from those, with non-negligible probability, the next value rn, then the security of your device will be compromised. (a) Give a rough estimate for the probability that an adversary can predict rn, as a function of n and |G|. Explain your answer. [6 marks] (b) Mallory also suggests a specific implementation: h1(x) = f(u x mod p) p = a 2056-bit prime number h2(x) = f(v x mod p) u, v = two numbers from Z p f(x) = x mod 22048 G = Z2 2048 (i) The constants p, u and v will be known to the adversary. What conditions should they fulfill so that h1 and h2 can reasonably be described as one-way functions, and how would you normally generate suitable numbers u and v? [Hint: quadratic residues] [4 marks] (ii) If f were replaced with the identity function, how could an adversary distinguish the ri emerging from this pseudo-random generator from a sequence of elements of Z p picked uniformly at random? [4 marks] (iii) After you choose a value for p, Mallory urges you to use two particular values for u and v generated in your absence. You briefly see "v = u e mod p" scribbled on a whiteboard. You become suspicious that Mallory is trying to plant a secret backdoor into your pseudo-random generator. Explain how Mallory could exploit such a backdoor. [6 marks] 9 (TURN OVER) CST.2015.8.10 10 System-on-Chip Design (a) Explain what factors limit the complexity and performance of an SoC at the heart of a portable electronic device. [4 marks] (b) Compare and contrast the use of hardware and software to implement a compute-intensive algorithm on an SoC, such as data encryption. Include customised processors and co-processors in your analysis. [5 marks] (c) (i) Define the term fully-pipelined with respect to a hardware component. [2 marks] (ii) Describe and compare three designs for a fixed or floating-point multiplier that vary in performance: one at least should be fully pipelined. [6 marks] (iii) Define the term structural hazard and explain why these can affect system performance. Which of your designs from part(c)(ii) might present such a hazard and why