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. 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. [4 marks] 7 (TURN OVER) CST.2014.4.8 7 Economics, Law and Ethics (a) Describe the provisions of the Data Protection Act. [8 marks] (b) You are designing and are about to launch a mobile phone app which will seek to understand the emotional condition of the user, using multiple inputs such as motion sensing, facial expression recognition, voice stress measurement and the analysis of entered text. Its declared purpose is to enable services to interact more empathically with users. You propose to monetize it by serving ads at times when the user is more likely to buy. Your "backers" have raised a concern that this app will be able to diagnose depression, and that in consequence you may be storing substantial amounts of sensitive personal information. Discuss this problem from the viewpoints of both data protection law and ethics. [12 marks] 8 CST.2014.4.9 8 Security I (a) Windows implements static inheritance for the access-control lists of NTFS files and folders. (i) What does static inheritance mean here and how does it differ from dynamic inheritance? [4 marks] (ii) Five flag bits (ci,oi,np,io,i) in each NTFS access-control entry (ACE) manage how it is inherited. Briefly describe the purpose of each bit. [5 marks] (iii) User mike gives his folder project the following access-control list: project AllowAccess mike: full-access (oi,ci) AllowAccess alice: read-execute (ci,np) AllowAccess bob: read-only (oi) It contains one folder and two text files, none of which have any noninherited access-control entries: project\doc.txt project\src project\src\main.c For each of these three objects, list all inherited access-control entries, showing in parentheses the inheritance-control flag bits that are set (using the same notation as above). [5 marks] (b) Describe the purpose and four typical functions of a root kit. [6 marks] 9 (TURN OVER) CST.2014.4.10 9 Security I Block ciphers usually process 64 or 128-bit blocks at a time. (iii) output feedback mode (using IV c0 = K). You also pick uniformly at random a private bit b {0, 1} and return a ciphertext C = c0c1 . . . cn, namely the message Mb encrypted with cipher-block chaining using the fresh EK. Finally, your opponent has to guess your bit b. Approximately how large must n be at least for your opponent to have a greater than 75% chance of guessing b correctly? Outline a strategy that your opponent can use to achieve this. Note: [13 marks] (f ) Suggest a way in which the concept of arc consistency, also known as 12-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. [10 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. [4 marks] 3 (TURN OVER) CST.2014.4.4 3 Computer Graphics and Image Processing 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? [12 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. [100 marks] (d) What special provision would have to be made for the segments [V0, V1] and [Vn1, Vn]? [4 marks] 4 CST.2014.4.5 4 Computer Graphics and Image Processing 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. [5 marks] 5 (TURN OVER) CST.2014.4.6 5 Databases 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, c B), T(C, Amount), and R(A,B 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,b, c) into R can be correctly implemented in the {S 0 P P, R, T} database. [14 marks] (d) For an OLTP database, discuss the performance implications of this so-called optimisation.