For the network from Exercise 4 calculate the conditional probability P r(p1|p2, p3) again. Apply a sampling approximate method. Discuss pros and cons of rejection sampling, likelihood weighting and Gibbs sampling. The table shown below gives an output of a uniform random number generator on the interval (0,1)

For the same network calculate P r(p3) and P r(p2|p3) again. Apply the method of variable elimination. Variable elimination gradually simplifies the original network by removing hidden variables (those that are not query nor evidence). The hidden variables are summed out. The target network is the only node representing the joint probability P r(Q, e). Eventually, this probability is used to answer the query P r(Q|e) = P P r(Q,e) Q P r(Q,e) . The first two steps are the same for both the probabilities: (i) P4 can simply be removed and (ii) P1 is summed out. Then, (iii) P2 gets summed out to obtain P r(p3) while (iv) the particular value p3 is taken to obtain P r(p2|p3).

(a) What is the difference between routing and forwarding? [2 marks] (b) Routing algorithms can be either link-state or distance-vector. Define these two terms and explain the trade-offs between them. [6 marks] (c) You are required to design a topology discovery protocol for a network of switching nodes interconnected by links. There are n nodes, l links, the maximum degree of any node is k and there is a path between any two nodes of not more than d hops. All links are bi-directional. Each node has a unique identifier of four bytes which it knows. (i) Describe a protocol for a node to learn about its immediate neighbours. You should specify the format of your messages and the size of any message fields. [4 marks] (ii) Using the characteristics of the network described above, design a protocol for distributing this information across the network. You should specify the format of your messages and the size of any message fields

This question relates to binary constraint satisfaction problems (CSPs). A CSP has a set X = {x1, . . . , xn} of variables, each having a domain Di = {v1, . . . , vni } of values. In addition, a CSP has a set C = {C1, . . . , Cm} of constraints, each relating to a subset of X and specifying the allowable combinations of assignments to the variables in that subset. (a) Give a general definition of a solution to a CSP. [1 mark] (b) Given a binary CSP, define what it means for a directed arc xi xj between variables xi and xj to be arc consistent. [2 marks] (c) Give an example of how a directed arc xi xj can fail to be arc consistent. Explain how this can be fixed. [2 marks] (d) Describe the AC-3 algorithm for enforcing arc consistency. [5 marks] (e) Prove that the time complexity of the AC-3 algorithm is O(n 2d 3 ) where d is the size of the largest domain. [3 marks] (f ) Suggest a way in which the concept of arc consistency, also known as 2-consistency can be extended to sets of three, rather than two variables. In the remainder of the question we will refer to this as 3-consistency. [1 mark] (g) Give an example of how a set of three variables might fail to be 3-consistent, and show how 3-consistency might then be imposed. [2 marks] (h) Suggest a modified version of the AC-3 algorithm that can be used to enforce 3-consistency.

Given a sequence of points (Vi) n i=0 on a plane, consider the problem of interpolating a smooth curve through all of the points in order by constructing a sequence of polynomial parametric functions, one for each interval [Vi , Vi+1] n1 i=0 . (a) What is meant by Ck continuity at the junction between two curve segments? [2 marks] (b) Explain how the degree of the polynomial function for a curve segment constrains the continuity at its two ends. What continuity can be achieved at each end of a cubic segment? [4 marks] (c) Derive a cubic parametric function for the interval [Vi , Vi+1] where 0 < i < n1. [10 marks] (d) What special provision would have to be made for the segments [V0, V1] and [Vn1, Vn]?

Given a model of a scene represented as a set of triangles in three-dimensional space defining its surfaces, consider the problem of rendering it on a raster display. Write brief notes on: (a) the data that would be stored for each triangle; [2 marks] (b) perspective projection from an arbitrary viewpoint; [5 marks] (c) clipping the data to a suitable viewing frustrum; [5 marks] (d) identifying pixels on the screen within a triangle; [3 marks] (e) resolving hidden surfaces using a z -buffer

Suppose that an Entity-Relationship model has been constructed that contains two entities S(A, B) and T(C, Amount), where A, B, C and Amount are attributes and the underline indicates a key. Suppose that we also have a many-to-many relationship R between S and T. We might expect that this model would be implemented in a relational schema such as S(A, B), T(C, Amount), and R(A, C). However, the database implementor has noticed that a very common and expensive query is this: given an A-value a, find the sum of all Amount values for records in T related to this a value in S. Therefore, the implementor has decided to "optimise" the database and replace table S with S 0 having schema S 0 (A, B, Sum), where the records in table S 0 will contain the precomputed values for this query. In this way the common and expensive query can be answered by a single key-based read. (Note: Sum should be 0 if no matching records exist.) (a) Explain how the operation insert (a, b) into S can be correctly implemented in the {S 0 , R, T} database. [4 marks] (b) Explain how the operation insert (c, v) into T can be correctly implemented in the {S 0 , R, T} database. [4 marks] (c) Explain how the operation insert (a, c) into R can be correctly implemented in the {S 0 , R, T} database. [4 marks] (d) For an OLTP database, discuss the performance implications of this so-called optimisation. [4 marks] (e) This example illustrates a fundamental trade-off in the design and implementation of database applications. Discuss. [4 marks] 6 CST.2014.4.7 6 Databases (a) We are given a relational schema R(A, B, C, D, E) and told that the following table represents a legal instance of R. A B C D E tuple number 1 2 5 4 3 (#1) 1 4 5 4 4 (#2) 2 4 5 4 5 (#3) 2 5 5 4 3 (#4) Which of the following sets of functional dependencies may hold in R? If a set of dependencies cannot hold, then explain why. You can refer to tuple numbers in your explanation. (i) F1 is the set {A D}. [2 marks] (ii) F2 is the set A, B C E B D, E A [2 marks] (iii) F3 is the set A, B C D, E C A D [4 marks] (b) We are given a relational schema R(Z, W, Y). Suppose that in some (correct) instance of R the query (Z,W(R) Z,Y(R)) R is not empty. What can we conclude about the functional dependency Z W? Explain your answer. [4 marks] (c) In the process of using functional dependencies to normalise a schema, what is meant by a lossless join decomposition and how is such a decomposition guaranteed? [4 marks] (d) In schema normalisation, is Boyce-Codd Normal Form (BCNF) always to be preferred over 3rd Normal Form (3NF)? Explain your answer.