Provide an appropriate query to show that the above program can give an incorrect result. [4 marks] (b) Explain the cause of the error. [6 marks] (c) Suggest a correction. [5 marks] (d) Write a Prolog program to find the maximum of a list of numbers. [5 marks] 9 Databases (a) Explain how to describe the structure of a collection of data using entities, attributes and relationships. [6 marks] (b) How would you identify particular instances of data in order to record the information in a database? Illustrate your answer by considering both a relational database maintained using SQL-92 and an ODMG database. [6 marks] (c) A high street bank has just announced a merger with a nationwide building society. You are employed as a consultant to advise on the integration of their client databases. Both institutions use relational databases. Write brief notes to alert the database administrators to the difficulties that they may encounter. [8 marks] 6 CST.2001.12.7 10 Numerical Analysis II (a) A cubic spline over knots x1, x2, . . . xn is defined by (x) = (x  xj )yj+1 + (xj+1  x)yj dj  (x  xj )(xj+1  x){(dj + xj+1  x)j + (dj + x  xj )j+1} 6dj for x  [xj , xj+1] where dj = xj+1  xj . The spline is continuous in its first and second derivatives. (i) Find (xj ). [2 marks] (ii) Find formulae for  0 (xj ) and  0 (xj+1) for x  [xj , xj+1]. [4 marks] (iii) What is  00(xj )? [2 marks] (b) Form a set of equations for computing the unknowns {j}, specifying suitable end conditions to simplify these equations. [10 marks] (c) What are the important properties of these equations with respect to their numerical solution?(a) Write a polymorphic curried function prefix which, when applied to x and a list L, gives the list of pairs (x, y) for each y in L. For example, prefix "a" [1,2] = [("a",1), ("a",2)] What is the type of prefix? [5 marks] (b) Using your definition of prefix, write a definition of a function cartesian which, when applied to a pair of lists L1 and L2, produces a list of pairs containing the pair (x, y) for every element x in L1 and y in L2. For example, cartesian (["a","b"], [1,2]) = [("a",1), ("a",2), ("b",1), ("b",2)] What is the type of cartesian? [5 marks] (c) Write definitions in ML for the built-in higher-order functionals foldl and map. [6 marks] (d) Combine your definition of prefix with the functionals map and foldl to give an alternative definition of cartesian, which is not explicitly recursive. [4 marks] 12 Computer Vision 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] 8 CST.2001.12.9 13 Complexity Theory (a) Give a precise definition of the complexity class NP and of NP-completeness. [2 marks each] (b) For any natural number k, the problem k-colourability is defined as the following decision problem. Given a graph G = (V, E), is there a mapping  : V  {c1, . . . , ck} such that if (u, v)  E, then (u) 6= (v)? (i) Explain why, for each k, the problem k-colourability is in the class NP. [2 marks] (ii) For what values of k is the problem k-colourability decidable in polynomial time? Why? [2 marks] (iii) For which values of k is the problem k-colourability NP-complete? Give a brief indication how this might be proved. [2 marks] (c) The company Fon-X runs a mobile 'phone service. It has 2000 'phone masts stationed across the country. The frequency spectrum assigned to the company is split into 20 bands. Each mast is to be assigned a frequency band in such a way that masts within 50 miles of each other do not share the same frequency band. (i) What is the relationship between this problem and k-colourability? [2 marks] (ii) What can you say about the complexity of the problem Fon-X is trying to solve?

 

address all

(b) Let datatype tree = empty | node of * tree list type forest = tree list respectively be the types of finitely-branching trees and forests. As usual, the maximal paths of a tree are given by the lists of consecutive nodes from the root to a leaf (empty tree). The trace of a tree is the list of all its maximal paths, and the trace of a forest that of all its trees. (i) Write SML function trace: forest list list that outputs the trace of a forest according to a depth-first traversal.

Write SML function mkf: list forest that outputs a forest whose trace consists only of the input list. (ii) The paths of a forest are given by lists of consecutive nodes from a root to any other node. A trie (or prefix forest) is a forest without repeated paths. Write SML function add: list forest forest that, given as input a list ` and then a trie t, returns as output the trie resulting from adding ` to t; in the sense that the trace of (add ` t) is the trace of t together with `. [4 marks] Write parametric trie-sorting SML function triesort: ( * bool) forest forest such that trace( triesort c t ) = lexsort c (trace t) for all comparison functions c and tries t.

address all quest

(a) Specify the types of the following SML functions: (i) fn f => map f (ii) fn f => map map f (iii) fn f => (map o map) f [Recall that the composition operator o has type ( ) * ( ) .] (b) Let datatype tree = empty | node of * tree * tree be the data type of binary trees. (i) A bijective correspondence between types and is given by a pair of functions f : and g : such that g o f = fn a : => a and f o g = fn b : => b. Exhibit recursive SML functions f: unit tree (unit tree) list and g: (unit tree) list unit tree that establish a bijective correspondence between the types unit tree and (unit tree) list.

(ii) Give an alternative definition of the function g in terms of either foldl or foldr. (iii) Define a treefold function of type ( * tree * ) ( tree) and give an alternative definition of the function f in terms of it.

(c) Rigorously argue for the correctness of the following identities: g o f = fn=> l

(a) What are the principal characteristics of a linked list? (b) Consider a stack that consists solely of characters. A linked list can be used to model such a stack and a programmer has embarked on a class ChLink which begins thus: class ChLink { private char val; private ChLink next; public ChLink() { this.val = '\\'; this.next = null; } The backstroke character '\' is reserved and marks the bottom of the stack. Why does it have to be keyed in twice? (c) Augment class ChLink with two methods push(char) which pushes a character onto the stack and a method pop() which returns the character at the top of the stack and, unless it is backstroke, removes that character from the stack. It is not possible to pop the bottom marker. (d) Write a test program which uses class ChLink to verify that a sequence of square brackets is properly nested. The test program might begin thus: public class ChLinkEx { public static void main(String[] args) { char[] chseq = {'[','[','[','A',']',']','[','A',']'}; ChLink start = new ChLink(); for (int i=0; i

(a) In image compression we use three different mechanisms to compress pixel data: (i) mapping the pixel values to some other set of values; (ii) quantising those values; (iii) symbol encoding the resulting values. Explain each mechanism, describe the way in which it helps us to compress the image, and describe how the mechanism is implemented in the baseline JPEG compression method (b) Describe the limitations of human vision in terms of: (i) spatial resolution, (ii) luminance, (iii) colour, and explain the implications that each of these has on the design of display devices, including numerical estimates of the limits beyond which a human cannot discriminate.

(b) Simplify the function f = a b cd+ a b c d + a b c + a bd with don't care states a b c d and a b cd to give expressions in the following forms: (i) sum of products; [3 marks] (ii) product of sums. [3 marks] (c) Simplify the function f = (a+ b + c ).(b + d) to give an expression in the sum of products form. [6 marks] (d) Implement with 2-level logic the function in part (c) using only (i) NOR gates; (ii) NAND gates. Assume that complemented input variables are available

(a) A hypothetical (and practically rather useless) floating-point number representation inspired by the IEEE floating-point standards uses 6 bits one bit for sign, three bits for exponent and two (stored) bits for mantissa (significand). Assuming that 1.0 is represented in this format as 0:011:00 give the values, in decimal notation (fractions are acceptable), of all the other nonnegative floating-point values in this representation. You do not need to give details of denormalised numbers or NaNs. (b) Explain the following terms: (i) absolute error; (ii) relative error; (iii) rounding error; (iv) truncation error; (v) ill-conditionedness. [5 marks] (c) Assuming the floating-point representation for type float has b bits in its mantissa (significand), what can be said about the output of the following program? float f = 10.0/3.0; for (i=0; i<100; i++) { int v = (int)f; /* get integer part of f */ printf("%d ", v); /* print it */ f = (f - v) * 10; } Discuss how accurately f represents 10.0/3.0 at the start of each iteration and explain which operation(s) represent the main loss of accuracy in f on each iteration. (You may assume that 10 significant bits of accuracy is approximately 3 decimal digits of accuracy.)

(a) You have received a shipment of hardware random-number generators, each of which can output one 128-bit random number every 10 milliseconds. You suspect that one of these modules has been tampered with and that it actually produces only 30-bit random numbers internally, which are then converted via a pseudo-random function into the 128-bit values that it outputs. (i) How does this form of tampering reduce the security of a system that uses a generated 128-bit random number as the secret key of a block cipher used to generate message authentication codes? (ii) Suggest a test that has a more than 0.5 success probability of identifying within half an hour that a module has been tampered with in this way.

(b) Explain briefly (i) the encryption and decryption steps of Cipher Feedback Mode; [3 marks] (ii) why some operating systems ask the user to press a special key combination (e.g., Alt-Ctrl-Del) before each password login; [3 marks] (iii) how a secure hash function can be used to implement a one-time signature scheme;

(a) (i) Define the notion of a register machine and the computations that it carries out. (ii) Explain, in general terms, what is meant by a universal register machine. (You should make clear what scheme for coding programs as numbers you are using, but you are not required to describe a universal register machine program in detail.) [5 marks] (b) (i) Explain what it means for a partial function f from N to N to be computable by a register machine. [2 marks] (ii) Let n > 1 be a fixed natural number. Show that the partial function from N to N fn(x) = n nx if x > 0 undefined if x = 0 is computable. (iii) Explain why there are only countably many computable functions from N to N. Deduce that there exists a partial function from N to N that is not computable. (Any standard results you use about countable and uncountable sets should be clearly stated, but need not be proved.)

(iv) If a partial function f from N to N is computable, how many different register machine programs are there that compute f?

Operating systems are integrated closely with the hardware on which they run. (a) Distinguish the hardware and software involved in interrupt-driven I/O.

(b) Describe three uses of the interrupt mechanism in addition to device I/O.

(c) Give examples of how the privilege state bit in a CPU's status register is used.

(d) (i) What could go wrong in a system that does not make use of a timing device in process scheduling? (ii) What class of scheduling algorithms would be impossible to implement without a timing device? (e) What is the main advantage of using half the virtual address space of a process for the operating system and half for applications? [1 mark] (f ) Explain memory-mapped I/O.

We have a basic search problem, consisting of a set S of states, a start state s0, a goal test G(s) that returns True if s S is a goal and False otherwise, and a function exp(s) that returns the set of states obtained by expanding state s. (a) Describe in detail the Graph Search algorithm for solving a problem of this type. How does it differ from the related Tree Search algorithm? [8 marks] (b) Give detailed description of the Recursive Best First search algorithm, and explain why it might be used in preference to the A? algorithm.

(b) Explain why the code shown below, when executed, will print the value 420. #include #define init_employee(X,Y) {(X),(Y),wage_emp} typedef struct Employee Em; struct Employee {int hours,salary;int (*wage)(Em*);}; int wage_emp(Em *ths) {return ths->hours*ths->salary;} #define init_manager(X,Y,Z) {(X),(Y),wage_man,(Z)} typedef struct Manager Mn; struct Manager {int hours,salary;int (*wage)(Mn*);int bonus;}; int wage_man(Mn *ths) {return ths->hours*ths->salary+ths->bonus;} int main(void) { Mn m = init_manager(40,10,20); Em *e= (Em *) &m; printf("%d ",e->wage(e)); return 0; }

(c) the C code shown in part (b) using C++ primitives and give four reasons why your C++ solution is better than the C one.

program in C to display the Minimum number among three Integers by using Compound statement. 2. Write program in to display a Triangle with Integer numbers in Write program to concatenate one list at the end of the other.

b) Write program of copying one list into another.

State the requirements for (S, 6) to be: (a) a partially ordered set; (b) a totally ordered set; (c) a well ordered set. Let N be the natural numbers. Give, without proof, three examples of relations 6i , where i = 1, 2, 3, such that (N, 6i) satisfies exactly i of the conditions (a), (b), (c). [3 marks] Let S = {a, b} be an alphabet, with total order a < b. Let = S

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?