answer well.

The core relational algebra can be extended with a duplicate elimination operator, and a grouping operator. (i) Define carefully these two operators. [3 marks] (ii) Assuming the grouping operator, show how the duplicate elimination operator is, in fact, unnecessary. [2 marks] (iii) Can the grouping operator be used to define the projection operator? Justify your answer. [2 marks] 8 CST.2004.13.9 9 Numerical Analysis II (a) A Riemann integral over [a, b] is defined by Z b a f(x) dx = limn?? ???0 Xn i=1 (?i ? ?i?1)f(xi) . Explain the terms Riemann sum and mesh norm. [4 marks] (b) Consider the quadrature rule Qf = 3h 8 [f(a) + 3f(a + h) + 3f(a + 2h) + f(a + 3h)] ? 3f (4)(?)h 5 80 . If [a, b] = [?1, 1] find ?0, ?1, . . . , ?4 and hence show that this is a Riemann sum. [3 marks] (c) Suppose R is a rule that integrates constants exactly over [?1, 1], and that f(x) is bounded and Riemann-integrable over [a, b]. Write down a formula for the composite rule (n R)f and prove that limn?? (n R)f = Z b a f(x) dx [6 marks] (d) What is the formula for (n Q)f over [a, b]? [4 marks] (e) Which polynomials are integrated exactly by Qf? Which monomials are integrated exactly by the product rule (Q Q)F when applied to a function of x and y? [3 marks] 9 [TURN OVER CST.2004.13.10 10 Introduction to Functional Programming (a) Define a polymorphic datatype 'a tree to represent binary trees. [1 mark] (b) A breadth-first traversal of a tree walks over all the nodes at each level before proceeding to the next level. For example the breadth-first traversal of the tree: 1 2 3 4 5 6 7 visits the nodes in the order 1, 2, 3, 4, 5, 6, 7. Define a function breadth: 'a tree -> 'a list such that breadth(t) returns the nodes of tree t in breadth-first order. [10 marks] (c) Define a polymorphic datatype 'a seq to represent lazy lists. [1 mark] (d) Define a polymorphic datatype 'a ltree to represent lazy binary trees. [3 marks] (e) Define a function inorder of type 'a ltree -> 'a seq that traverses a lazy tree in-order, returning the nodes in a lazy list. (You should define any auxiliary functions you may use.) [5 marks] 10 CST.2004.13.11 11 Natural Language Processing (a) Give brief definitions of the following terms: (i) referring expression; (ii) cataphora; (iii) pleonastic pronoun. [6 marks] (b) Describe the Lappin and Leass algorithm for pronoun resolution, illustrating its operation on the text below. Exact weights for salience factors are not required. Owners love the new hybrid cars. They all say that they have much better fuel economy than conventional vehicles. And it seems that the performance of hybrid cars matches all expectations. [14 marks] 11 CST.2004.13.12 12 Complexity Theory (a) Define a one-way function. [4 marks] (b) Explain why the existence of one-way functions would imply that P6=NP. [7 marks] (c) Recall that Reach is the problem of deciding, given a graph G a source vertex s and a target vertex t, whether G contains a path from s to t; and Sat is the problem of deciding whether a given Boolean formula is satisfiable. For each of the following statements, state whether it is true or false and justify your answer. (i) If Reach is NP-complete then P=NP. [3 marks] (ii) If Reach is NP-complete then NP6=PSPACE. [3 marks] (iii) If Sat is PSPACE-complete then NP=PSPACE.1 Data Structures and Algorithms (a) Describe an efficient algorithm to determine whether two finite line segments in a plane intersect. You may assume that the end points of each line are given as x-y coordinates. [8 marks] (b) Describe in detail an efficient algorithm to find the convex hull of a set of points lying on a plane. Show that the complexity of the Graham scan used in the algorithm is O(n) and that the algorithm as a whole has complexity O(n log n). [8 marks] (c) Discuss how it is possible to eliminate many of the points before the convex hull algorithm is entered. [4 marks] 2 Computer Design The ARM processor allows the second operand to be shifted by an arbitrary amount. In order to improve the performance, a six-stage pipeline is proposed with the following stages: instruction decode and shift execute memory register fetch register fetch operand 2 access write back (a) What are control hazards and how could they be resolved in the above pipeline? [4 marks] (b) What are data hazards and how could they be resolved in the above pipeline? [4 marks] (c) What are feed-forward paths and where could they be added to the above pipeline to improve performance? [6 marks] (d) Why might a branch instruction result in pipeline bubbles and how many bubbles will appear in the above pipeline as a result of taking a branch instruction? [6 marks] 2 CST.2004.13.3 3 Digital Communication I (a) Define the terms latency and capacity as applied to communication channels. [2 marks] (b) Is there a strict relation between the two? [1 mark] (c) Show how the latency of a channel can have a direct effect on the capacity of a higher-layer channel which uses it. [10 marks] (d) How can the capacity of the higher-layer channel be improved (keeping the characteristics of the underlying channel unchanged)? [4 marks] (e) In what circumstances might these improvements have only limited benefit? [3 marks] 3 [TURN OVER CST.2004.13.4 4 Distributed Systems A network-based service manages persistent objects. The service must enforce an access control policy to protect the objects. (a) Discuss how this access control might best be implemented for the following example of objects and policy components: Objects: Files in a University Department's file service, operating behind a firewall. Policy: The owner may specify read, write and execute rights in terms of principals and groups. [4 marks] (b) Discuss how this access control might best be implemented for two of the following examples: (i) Objects: Files in a commercial, distributed, Internet-based file service. Policy: The owner may authorise other principals to download the file. (ii) Objects: Sales data relating to a company. Policy: Those employed in the Sales Departments of all branches of the company worldwide may read the data. (iii) Objects: Electronic health records (EHRs) in a nationwide service. Policy: The owner (patient) may read from its own EHR. A qualified and employed doctor may read and write the EHR of a patient registered with him/her. (iv) Object: The solution to online coursework. Policy: The coursework setter has read and write access. A candidate has no access until after the marks have been published. [8 marks each] 4 CST.2004.13.5 5 Computer Graphics and Image Processing (a) Explain why display devices appear to be able to reproduce (almost) all the colours of the spectrum using only red, green and blue light.

l. Compute /(0). b. Compute f(2). c. Compute P(x = 2). d. Compute P(x 2 1). e. Compute E(x). f. Compute Var(x) and o. 33. Consider a binomial experiment with n = 20 and p = .70. a. Compute f( 12). b. Compute f(16). c. Compute P(x 2 16). d. Compute P(x = 15). e. Compute E(x). f. Compute Var(x) and o. Applications 34. For its Music 360 survey, Nielsen Co. asked teenagers how they list 12 months. Nearly two-thirds of U.S. teenagers under the age of Inc's video-sharing site to listen to music and 35% of the teenageRegression HW Problem Regression HW Problem 310 2 2 20 6 18 g 9 13 26 20 75 20 23 5 10 15 1. Compute X 2. Compute y 3. Compute SSxy 4. Compute SS, 5. Compute By