How many bracketings of length 2n will there now be? 1 [TURN OVER CST.93.2.2 2 Two teams A and B play a match in which the winner is the first team to win n games. If A needs i games to win and B needs j games to win, denote by P(i, j) the probability that A will win. B is the better team, and in any particular game A's probability of winning is only 2/5. Write down a relation between P(i, j), P(i1, j) and P(i, j 1). Of what order is the computation of P(k, k) for given k? Show how to lay out the results for maximum re-use of computed values, and work out P(2, 2). 3 In a meteorological experiment the annual rainfall in millimetres is recorded for Aberdeen, Bangor, Canterbury and Dublin: readings are taken in each of the years 1981-83. The data are represented as a set of triples (r, t, y), where rainfall r N is a natural number of millimetres, the town t T is identified by a letter A-D, and the year y Y by a digit 1-3. Show how to identify the data with subsets of each of (N T) Y , (T Y ) N and (Y N) T. Which of these relations either must or may define a (partial) function from (N T) Y , (T Y ) N, (Y N) T respectively? (a) Taking one which must be a function (P Q) R say, show how to convert it to a function whose domain is P and whose range is the set of functions Q R. (b) Assume that one of the other relations, which may define a partial function, does so. Show how to convert it to a partial function whose range is a set of partial functions. Illustrate your answer with suitably chosen example data. SECTION B 4 X and Y are independent random variables having Poisson distributions with parameters and respectively. By using probability generating functions, or otherwise, prove that X + Y has a Poisson distribution and give its parameter. Find the conditional distribution for X given that X + Y = n, and give its mean and variance. Explain your result in words. 5 A single die is repeatedly thrown, and accumulating cou. ., 6s are equal' will ever occur. [Hint: you will need Stirling's approximation n! (2) 1 2 n n+ 1 2 e ction. Of their output, 5%, 4%, and 2% respectively are rejected as faulty. What is the probability that from a collection of chips drawn at random from the output two which are faulty were made on the same machine? What is the probability that three faulty chips were all made on different machines? SECTION C 7 Discuss the requirements of an Automatic Teller Machine (ATM) service under the headings: (a) security; (b) availability of service; (c) integrity of stored data; (d) procedure for dispute resolution. 3 [TURN OVER CST.93.2.4 8 Consider these ML functions for performing arithmetic in radix k, where k is an ML variable whose value is a positive integer. fun value [] = 0 | value (x::xs) = x + (k*value xs); fun carry c [] = [c] | carry c (x::xs) = ((c+x) mod k) :: carry ((c+x) div k) xs; fun sum c [] ys = carry c ys | sum c (x::xs) [] = carry c (x::xs) | sum c (x::xs) (y::ys) = ((c+x+y)mod k) :: sum ((c+x+y)div k) xs ys; (a) State and justify the rule of structural induction for lists. (b) Your client would like you to prove the correctness of sum, expressed by the property value(sum 0 xs ys) = value(xs)+value(ys). Generalize this formula so that it permits a useful structural induction proof, explaining your reasons. (c) Prove the base case of the structural induction. (d) Prove the inductive step of the structural induction. (e) What does the correctness proof say about the case where k equals 1? Discuss whether other properties are necessary to ensure correctness. Proofs may assume the analogous correctness property for carry and standard mathematical laws. State these assumptions clearly.

(a) Explain how a Boolean matrix can be used to represent the edges of a finite directed graph whose vertices are numbered 1 to n. (b) Describe Warshall's algorithm to convert the matrix representing a graph to one that represents its transitive closure, and carefully explain why the algorithm works. (c) Outline Floyd's algorithm, without proof of correctness, to find the cost of the cheapest path between any two vertices of a directed graph where the edges carry non-negative atrix R that encodes a path with the minimum number of edges from any vertex i to any other vertex j. Rij will be zero if no path exists from vertex i to vertex j; otherwise, Rij will hold the vertex number of the next vertex of a minimal path from i to j. Suggest an algorithm to compute R from a given Boolean matrix M.

It is proposed to send information across a fixed delay channel using a simple (window of 1) ARQ protocol with a transmitter timeout of T. That is, if the transmitter does not receive an acknowledgement for a packet within time T of sending the packet, it retransmits. The delay of the underlying channel is , the data rate is B and the packet size is p bits. Bit errors in the channel are independent and packets of size p have a packet error rate of e. Errors in the small acknowledgement packets are rare enough to be discounted in this analysis. (a) What is the expected throughput of the ARQ protocol if e is zero? [4 marks] (b) What is the expected throughput if e is non-zero, but small enough that e 2 is negligibly small? (c) How could a forward error code help the throughput of the ARQ scheme? [2 marks] (d) What is meant by the term code rate of a forward error code? [2 marks] (e) What code rate must a code which squared the error rate have in order to improve throughput of the ARQ scheme?

In (1) and (2) below, the words in the sentences have been assigned tags from the CLAWS 5 tagset by a stochastic part-of-speech (POS) tagger: (1) Turkey NP0 will VM0 keep VVI for PRP several DT0 days NN2 in PRP a AT0 fridge NN1 (2) We PNP have VHB hope VVB that CJT the AT0 next ORD year NN1 will VM0 be VBI peaceful AJ0 In sentence (1), Turkey is tagged as a proper noun (NP0), but should have been tagged as a singular noun (NN1). In sentence (2), hope is tagged as the base form of a verb (VVB: i.e., the present tense form other than for third person singular), but should be NN1. All other tags are correct. (a) Describe how the probabilities of the tags are estimated in a basic stochastic POS tagger. [7 marks] (b) Explain how the probability estimates from the training data could have resulted in the tagging errors seen in (1) and (2). [6 marks] (c) In what ways can better probability estimates be obtained to improve the accuracy of the basic POS tagger you described in part (a)? For each improvement you mention, explain whether you might expect it to improve performance on examples (1) and (2).

(a) Explain what it means to say that a problem is (i) NP [2 marks] (ii) NP-Complete [2 marks] (b) Define the standard problem 3-SAT and describe how you would take an instance of it and derive an integer n that you would use in any formulae relating to the cost of solving that instance. [3 marks] (c) What is a non-deterministic Turing Machine? Supposing that some computation of such a machine takes N steps, what information needs to be reported to describe exactly how the computation proceeded? In what way is this relevant to the problem of solving an arbitrary NP problem? [7 marks] (d) Sketch a proof of Cook's result, that the problem 3-SAT is NP complete. Justify that any transformations you introduce are polynomial.

(a) Give a precise definition of each of the complexity classes NP and co-NP. [4 marks] (b) Give an example each of (i) an NP-complete language; and (ii) a co-NP-complete language, in each case giving a precise statement of the decision problem involved. [4 marks] (c) If A and B are the two languages identified in Part (b), give an example of a language that is polynomial-time reducible to both A and B. Justify your answer. [4 marks] (d) Consider the following statement: There is a polynomial p such that every valid Boolean formula of length n has a proof of length at most p(n). Moreover, there is a polynomial-time algorithm that can check the correctness of the proofs. This statement is not known to be true or false. Explain what would be the consequences of this statement being true or false for the relationship between NP and co-NP, giving full justification for your answer.

(a) Describe the characterists of debt and equity financing, highlighting the differences between them. (b) What is the difference between a loan and an overdraft? Your software company is contracted to create a new control system for chocolate bar delivery in Cambridge. The contract is for a 6 month period, with payment of 400k against milestones in months 1, 3 and 6. (c) Create an outline cashflow for the project assuming staff costs of 75k per month and overheads of 60k per month. (d) What is your working capital requirement for the project allowing a contingency of a two month delay to one of either the second or third delivery milestones? [5 marks] (e) How would you suggest to finance this working capital requirement

(a) Describe the DPLL method, explaining briefly each of its four steps. [4 marks] (b) Use the DPLL method to find a model satisfying the following set of clauses, or to prove that no such model exists. {P, Q} {R} {Q, S, Q} {Q, R, S} {P, Q} {P, Q, S} {P, R, S} {P, S} [6 marks] (c) Describe briefly the procedure for constructing a BDD. Illustrate your answer by constructing the BDD (using the variable order P < Q < R < S) for: (P (Q S)) (S (R S))

: Write full C++ program that reads an integer, a list of words, and a character. The integer signifies how many words are in the list. The output of the program is every word in the list that contains the character at least once. Write C++ program which reads three values of types char, int, double and string from the keyboard and primis, appropriately formatted, assigned values and variable types. Write program that reads a string and a character from the keyboard. The program should output how many times the character appears in the string. Write menu based program implementing the following functions:

(a) Given two signed distance field functions f and g, give the formula for their . . . (i) Union (fg) (ii) Intersection (fg) (iii) Difference (fg) [3 marks] (b) Give clear definitions for the Virtual Reality industry's principles of immersion and presence. Compare the two concepts and explain the difference between them with examples demonstrating each. [5 marks] (c) The Doo-Sabin subdivision scheme has kernel (1/4)[. . . , 0, 0, 1, 3, 3, 1, 0, 0, . . .], defining a scheme in which each face is replaced by four new vertices. (i) Give an expression for computing the position of a new vertex given the positions of the four old vertices of a face. [2 marks] (ii) If the face does not have 4 vertices then you must weight each parent vertex differently to find the position of the child. Suggest possible weights for the vertices of faces with 3, 5, and n vertices, and justify your answer. [3 marks] (d) There are several ray-tracing-friendly acceleration structures. (i) Explain the BSP tree data structure. Explain how it is constructed and traversed. [3 marks] (ii) Explain the kd-tree data structure. Explain how it is constructed and traversed. [3 marks] (iii) Which of the two data structures is best-suited to ray-tracing a game of chess in real time?

Most large programs that have been written with considerable care and thoroughly checked still seem to contain bugs at a rate of over one per 3000 lines of source code. Systems involving hundreds of millions of lines of code can thus be expected to contain tens of thousands of potentially catastrophic errors. (a) List several kinds of programming errors that can appear in programs and discuss their relative importance in relation to the long-term reliability of a large application program. [7 marks] (b) Suggest potential ways by which programmers may reduce the number of programming errors they make, paying particular attention to language features that might help, extra features in program development systems and possible changes in overall system architecture. [8 marks] (c) In what ways would you expect languages 25 years from now to differ from those that are currently popular? [5 marks] 8 Databases (a) Define the core operators of the relational algebra. [5 marks] (b) Describe two differences and two similarities between the relational algebra and SQL. [4 marks] (c) Suppose that S(a, b, . . .) and R(a, . . .) are relations (the notation indicates that attribute a is in the schema of both S and R, while attribute b is only in the schema of S). Suppose that v is a value; is the following equation always valid? (a=v or b=v) (R ./ S) = (a=v(R)) ./ (b=v(S)) If yes, provide a short proof. If no, provide a counter-example. [2 marks] (d) Various normal forms are important in relational schema design. (i) Define Third Normal Form (3NF). [3 marks] (ii) Define Boyce-Codd Normal Form (BCNF). [3 marks] (iii) For databases with many concurrent update transactions, explain why schemas in normal form are important for good performance.

An appropriate structure for large-scale distributed systems is as multiple, independently administered, firewall-protected, domains. Examples are a national health service, a national police service and a global company with worldwide branches. Communication must be supported within and between domains and external services may be accessed. For example, health service domains may all access a national Electronic Health Record service; police service domains may all access a national Vehicle Licensing service. (a) (i) Define publish/subscribe communication. [3 marks] (ii) What are the advantages and disadvantages of offering publish/subscribe as the only communication service? [7 marks] (b) (i) Define role-based access control. [3 marks] (ii) What are the advantages and disadvantages of using role names for access control and communication