Represent multisets using binary trees. Compare the representations (a), (b) and (c), stating the advantages and drawbacks of each. [Answers need not contain ML code. You may refer to algorithms and data structures from the notes Problem Solving in ML.] SECTION D 10 What is an operating system kernel, and what runtime services does an executable binary program expect from a typical time-sharing kernel? How may transfer of control (program flow) between the loaded application and the resident kernel be achieved? 5 [TURN OVER CST.93.2.6 11 Describe and compare the following two programming approaches: (a) execution of a compiled and linked set of modules; (b) using an interpreter. Include examples of each, showing when one method is preferable to the other. Is there an absolute distinction between the two methods or is there a spectrum of approaches? 12 Outline the data protection principles set down in the Data Protection Act, and discuss the possible justifications for them.

. Px returns the result (abort or commit) to the client; other processes discard the transaction result. (i) This model works well if queries do not contain the SQL time keyword, which is substituted with the current is evaluated. Explain why using time might synchronously, one at a time, to the local database. In a later version, to improve performance, processes are allowed to submit multiple transactions at a time asynchronously to the local database. Why does this fail to provide strong consistency for distributed transactions? Describe a solution that might allow limited (but useful) local concurrency to be supported. [3 marks] (iii) Describe changes to the design to support weak consistency, and describe two reasons why this might improve performance.

answer all

Some banks issue their Automatic Teller Machine (ATM) card customers with a randomly selected personal identification number (PIN). Others issue their customers with an initial PIN only, and let the customers choose their own PIN the first time they use the card in an ATM. Describe the advantages and disadvantages of these approaches. [5 marks] Again, some banks compute the customer PIN by encrypting the account number using DES and a key known only to their central systems and ATMs, taking the first four hex digits of the result, replacing the digits A, . . . , F with 0, . . . , 5 respectively, and finally, if the first digit of the result is 0, replacing it with a 1. What is the probability that a criminal can get the PIN right given three guesses? [5 marks] Yet other banks have used DES, and a key known only to their central systems and ATMs, to encrypt the PIN (whether randomly generated or customer selected); they then write the result on the magnetic strip on the customer's card, so that the ATM can verify it without reference to the central system. Describe the disadvantages of this arrangement. [5 marks] In order to prevent attacks based on manipulating magnetic strips, banks in some countries have moved to using smart cards. What effect would you expect such a move to have on the incidence of card-based fraud? [5 marks] 5 [TURN OVER CST.98.12.6 7 Compiler Construction Explain how a parse-tree representation of a program may be converted into a stack-based intermediate language giving sketches of code to translate expressions, assignments and the if-then-else command; you should also explain how occurrences of a variable in an expression or assignment are translated. The program may be assumed to conform to the following syntax: E -> n | x | E + E | f(E,E) D -> let f(x,x) = {Dseq; Cseq; E} | let x = E C -> x := E; | if E then C else C Cseq -> C | C Cseq Dseq -> D | D Dseq with start symbol Dseq. Here n corresponds to integer constants, x corresponds to identifiers used as variable names and f corresponds to identifiers used as function names (you may assume these are disjoint). The function declaration construct has the effect of defining a function which, when called, makes declarations, performs commands and then returns the result of its expression; note that therefore functions may be defined within functions, but the above restriction on identifiers means that they cannot be returned as results. [20 marks] 8 Prolog for Artificial Intelligence Write Prolog programs that define the following predicates. Your programs should ensure that backtracking does not produce spurious alternative solutions. (a) The nth element of a list: nth(X,N,L) instantiates X to the Nth element of list L. Assume that list elements are numbered increasing from 1. [4 marks] (b) The last element of a list: last(X,L) instantiates X to the last element of list L. [4 marks] (c) Remove an element from a list: remove(X,L,M) instantiates M to a list containing all the elements of list L except for every occurrence of term X. [6 marks] (d) Substitute one element for another: subst(L,X,Y,M) instantiates M to a list containing all the elements of list L except that every occurrence of term X in L is replaced by term Y in M.

Consider a program in a simple language L which manipulates only two forms of values: 64-bit two's-complement integers and 64-bit IEEE floating-point values. L includes variables, integer and floating-point operators and constants, and conditional expressions, but no functions. It is considered a (hard) error if a bit-pattern representing a floating-point value is operated on as if it were an integer and vice versa. There are no implicit coercions, so 1 + 2.3 would be an error. The job of both static and dynamic type checkers is to stop such errors from happening. (i) Explain the difference between static type checking and dynamic type checking, pointing out any compile-time or run-time costs and any differences in how variables are declared. [3 marks] (ii) We can say that a static type system is sound if whenever we have two programs S and D, differing only in whether they use static or dynamic type checking, then S passing type checking implies D executes successfully. In a sound type system, does D executing successfully imply that S passes type checking? Justify your answer for L. [2 marks] (b) Give three programs exemplifying failure of type soundness in existing languages. Two should involve distinct past-or-current programming languages and one should reflect the absence of checks performed by most linkers. [4 marks] (c) To what extent does Java use static and/or dynamic typing? [2 marks] (d) (i) A monad M can be seen as a type constructor for an abstract data type. Give the two operations which every monad must possess, along with their types. [3 marks] (ii) Now consider the monad E and the functions f and safediv, given in SML syntax by: datatype a E = return a | fail fun (fail >>= f) = fail | ((return v) >> f) = f v fun f(w,x,y,z) = (w div x) div (y div z) fun safediv(x,y) = if y<>0 then return(x div y) else fail Re-code f as a function g which uses operations from monad E along with function safediv so that the only non-zero tests around division are within safediv. Remark on any difference between the types of f and g. [6 marks] 2 CST1+CST2.2020.7.3 2 Economics, Law and Ethics You have an idea for an innovative new type of application for self-directed teaching and learning. The eTeacher uses state-of-the-art natural language processing approaches to allow for text and speech interaction. Over time, it builds a profile of the user's most effective means of learning, and tailors the teaching style accordingly. The intended users are secondary school students and adults who wish to refresh their understanding of Mathematics, English, Geography, or History. You plan to monetise the application by way of advertisements and in-app purchases. (a) You are seeking investors. Discuss the economic and legal considerations that might inform your business plan and persuade investors to fund your startup. For a convincing pitch, you should define the necessary terms and explain your reasoning. [7 marks] (b) Explain how things might change if the economy goes into recession. [3 marks] (c) Outline the principles of the General Data Protection Regulation (GDPR). How might you comply with the GDPR and allow individuals to exercise their rights? [10 marks] 3 Economics, Law and Ethics (a) Define the following terms, providing examples to illustrate their meaning. (i) Pareto improvement [2 marks] (ii) Pareto efficient allocation [2 marks] (iii) Utility [2 marks] (b) Explain the theorems of welfare economics, comparing and contrasting classical utilitarian welfare and Rawlsian welfare. [8 marks] (c) Do you expect the free market will solve the privacy problem? [6 marks] 3 (TURN OVER) CST1+CST2.2020.7.4 4 Formal Models of Language The string 'a b c d e' has the following dependency parse: a b c d e root The table shows the first two actions when deriving this parse using a modified shift-reduce parser which uses the actions: shift, right-arc and left-arc. stack buffer action abcde shift a bcde shift ab cde (a) Describe the actions shift, right-arc and left-arc in terms of their effect on the stack and buffer. Also describe any arcs that are recorded when the actions are used. [5 marks] (b) The parser also uses the action terminate which links a lone item on the stack to root. Complete the parse action table such that the actions derive the parse shown at the top of the page. [6 marks] (c) In Part (b) you have selected the parse actions by hand; explain how the sequence of parse actions is obtained from data in an automatic parser. [4 marks] (d) The dependency parse for the string 'a b c d e' is homomorphic with the English language string 'Alice shook up the potion'. An alternative word order for this string is 'Alice shook the potion up'. (i) Draw the dependency parse for the alternative string. [1 mark] (ii) Compare capturing natural language alternations using a context-free grammar as opposed to a dependency grammar.

c, d, e are melodic elements. A birdsong is composed of a sequence of these elements as follows: c c d c c e c c d c c d c c e (a) (i) Using byte pair encoding induce a context-free grammar for this sequence of birdsong. Show your workings and state what you have decided to do in the case of a tie. [6 marks] (ii) Draw the derivation tree that parses the birdsong using your induced grammar. [1 mark] (iii) What are the shortcomings of this method of grammar induction for natural languages? [3 marks] (b) Assuming that c, d and e are the only melodic elements available in the birdsong, and that the excerpt we are given is probabilistically representative of the birdsong in the wild, what is the average information produced per element? Provide relevant equations. [3 marks] (c) In Part (b) we assumed a 1st-order model of the birdsong. What assumption does this make about the sequence of elements? [1 mark] (d) Consider a 2nd-order model of the birdsong and calculate the conditional entropy. Provide relevant equations. [4 marks] (e) How can we calculate the entropy rate of birdsong? Provide relevant equations. [2 marks] 5 (TURN OVER) CST1+CST2.2020.7.6 6 Further Graphics (a) Consider the b-spline curve P(t) with knot vector [ 0, 1, 2, 3, 3, 3 ] and k = 3. (i) In a single sentence, explain the effect on P(t) of repeating a knot value k times. [1 mark] (ii) State the equations that define P(t). [3 marks] (iii) State the equation and sketch the graph for each of the three quadratic basis functions Ni,3(t) of P(t). [8 marks] (iv) Plot the path of P(t) for control points P0 = (0, 0), P1 = (4, 0), P2 = (4, 4).

The relational model of data was introduced in the early 1970s in a sequence of papers by E.F. Codd. This model proposes a tabular view of data, with a simple Data Manipulation Language (DML) based on relational algebra or relational calculus. Briefly explain the essential features of the model and its DML. [6 marks] Later work by Codd and others addressed weaknesses in the expressive power of the relational model. For each of the following give an example to show how the weakness arises, and explain an approach proposed to resolve the difficulty: (a) computing the transitive closure [4 marks] (b) manipulating collections of records [4 marks] (c) handling entity specialisation [6 marks] In case (c) you should outline the proposals of either the Object-Oriented Database System Manifesto or the Third Generation Database System Manifesto. 10 Introduction to Functional Programming Write an ML function upto of type int -> int list such that upto n generates the list [1,2,3,...,n]. [7 marks] What is wrong with the following function to take the head of a list? fun wrong_headed [h,t] = h; What is the type of wrong_headed? [5 marks] Why is the following function to evaluate Fibonacci numbers inefficient? fun fib 0 = 1 | fib 1 = 1 | fib n = fib(n-1) + fib(n-2); Write a similar but more efficient version. [8 marks] 7 [TURN OVER CST.98.12.8 11 Computer Vision Give three examples of problems in computer vision which are formally ill-posed. In each case explain how one or more of Hadamard's criteria for well-posed problems has failed to be satisfied. Illustrate how the addition of ancillary constraints or assumptions, even metaphysical assumptions about how the world behaves, enables one to convert the ill-posed problem into a well-posed problem. Finally, discuss how the use of Bayesian priors can perform this function. [20 marks] 12 Complexity Theory (a) Describe the problem 3-SAT. [2 marks] (b) Show how any instance of the seemingly more general problem n-SAT can be reduced to an equivalent one where each term has exactly three literals in it. Estimate how much larger the reduced problem would be than the original one. [4 marks] (c) A certain computation using a non-deterministic Turing machine completes in T time-steps. The Turing machine has k states and uses an alphabet of N symbols. A major theorem underpinning the concept of NP-completeness is based on a conversion of a description of such computations to boolean formulae which characterise them. Explain how, in such a reduction, boolean variables may be used to describe states that the Turing machine might be in. Show how to derive those components of the boolean formula that relate just to the way in which the Turing machine moves its read-write head. Your explanation should be sufficiently complete and carefully explained that it could be used as a specification of a program that would perform that part of the translation from Turing machine descriptions to boolean formulae. You should not attempt to explain the rest of the boolean formula or how it fits into a complete proof or program. [11 marks] (d) In terms of T, k and N, about how many symbols does it take to write the boolean expression you generate?

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?