A simple game works as follows. We have a board divided into n by m square...

   

Transcribed Image Text:

A simple game works as follows. We have a board divided into n by m square cells. We also have an unlimited number of L-shaped tiles, each made to cover exactly three squares. The tiles can appear in any of the four possible orientations. Our aim is to cover the board completely with non-overlapping tiles. (a) A single tile on the board can be described using a list such as [[1,1],[1,2],[2,1]] containing three tuples, specifying the position of each part of the tile on the board. Consider the following Prolog predicate, which is true if the six variables describe a correct, L-shaped tile. tile ([[A,B],[CD],[E,F]]):- C is A+1, D is B, E is A, F is B-1; C is A+1, D is B, E is A, F is B+1; C is A-1, D is B, E is A, F is B+1; C is A-1, D is B, E is A, F is B-1. Explain what happens in response to a query of the form tile([[4,5],[B,C].[D,E]]). Keep in mind the effects of backtracking. [2 marks] (b) Write a Prolog predicate goodplace([[A,B],[CD],[E,F]],[N,M]) that is true if [[A,B],[C,D],[E,F]] is a validly shaped tile and all of its parts lie within an N by M board. Your predicate should behave under backtracking in such a way that the response to a query of the form goodplace([[10,4],[B.C].[D,E]],[10,10]). is to find the unspecified values for all tiles which have a valid shape and fall within the board. In this example there would be two such tiles. [6 marks] (c) Write a Prolog predicate tiling (Available,Solution,Size). Here, Size is the size of the board represented as above, Solution is a list of tiles that solves the problem, and Available is a list of available positions on a board of the given size. For example, if Size is [2,2] then Available is [[1,1],[1,2],[2,1],[2,2]] Your predicate should be true if the Solution given is a valid one, and should be capable of finding a valid Solution in response to a query such as tiling ([[1,1],[1,2], [10,10]],X,[10,10]). Full marks will only be given for predicates that can exploit backtracking to find all possible solutions. [12 marks] 7 [TURN OVER CST.2003.6.8 8 Databases (a) Define the ACID properties of a transaction. [6 marks] (b) Define what is meant by strict two-phase locking (strict 2PL). [4 marks] (c) Assume that in addition to traditional Read and Write actions a DBMS supports increment and decrement actions: Inc and Dec (both are assumed to perform blind writes). Consider the following two transactions. T1: [Inc(A), Dec(B), Read(C)] T2: [Inc(B), Dec(A), Read(C)] (i) By considering some possible schedules of the above transactions, describe carefully the concurrency permitted by strict 2PL using just shared/read and exclusive/write locks. [3 marks] (ii) Detail a way to gain more interleaving whilst still maintaining strict 2PL. [7 marks] SECTION C 9 Logic and Proof (a) Define the concepts of a true sequent, a valid sequent and a basic sequent. You may take the concepts of true and valid formul as primitive. [3 marks] (b) Gentzen claimed that his proof systems performed natural logical reasoning. Consider the following sequent calculus rules: A, T = AB, T=A Av B, r = A A, A 3x A, A State the second rule's proviso and explain the intuitions behind each rule. (c) Choose one of these rules and give a rigorous argument for its soundness, using the concept of a valid sequent. [6 marks] (d) Precisely define the concept of the Most General Unifier (MGU) of two terms, giving examples. : Write program that takes n number of elements from user (where, n is specified by user), stores data in an array and calculates the average of those numbers. A simple game works as follows. We have a board divided into n by m square cells. We also have an unlimited number of L-shaped tiles, each made to cover exactly three squares. The tiles can appear in any of the four possible orientations. Our aim is to cover the board completely with non-overlapping tiles. (a) A single tile on the board can be described using a list such as [[1,1],[1,2],[2,1]] containing three tuples, specifying the position of each part of the tile on the board. Consider the following Prolog predicate, which is true if the six variables describe a correct, L-shaped tile. tile ([[A,B],[CD],[E,F]]):- C is A+1, D is B, E is A, F is B-1; C is A+1, D is B, E is A, F is B+1; C is A-1, D is B, E is A, F is B+1; C is A-1, D is B, E is A, F is B-1. Explain what happens in response to a query of the form tile([[4,5],[B,C].[D,E]]). Keep in mind the effects of backtracking. [2 marks] (b) Write a Prolog predicate goodplace([[A,B],[CD],[E,F]],[N,M]) that is true if [[A,B],[C,D],[E,F]] is a validly shaped tile and all of its parts lie within an N by M board. Your predicate should behave under backtracking in such a way that the response to a query of the form goodplace([[10,4],[B.C].[D,E]],[10,10]). is to find the unspecified values for all tiles which have a valid shape and fall within the board. In this example there would be two such tiles. [6 marks] (c) Write a Prolog predicate tiling (Available,Solution,Size). Here, Size is the size of the board represented as above, Solution is a list of tiles that solves the problem, and Available is a list of available positions on a board of the given size. For example, if Size is [2,2] then Available is [[1,1],[1,2],[2,1],[2,2]] Your predicate should be true if the Solution given is a valid one, and should be capable of finding a valid Solution in response to a query such as tiling ([[1,1],[1,2], [10,10]],X,[10,10]). Full marks will only be given for predicates that can exploit backtracking to find all possible solutions. [12 marks] 7 [TURN OVER CST.2003.6.8 8 Databases (a) Define the ACID properties of a transaction. [6 marks] (b) Define what is meant by strict two-phase locking (strict 2PL). [4 marks] (c) Assume that in addition to traditional Read and Write actions a DBMS supports increment and decrement actions: Inc and Dec (both are assumed to perform blind writes). Consider the following two transactions. T1: [Inc(A), Dec(B), Read(C)] T2: [Inc(B), Dec(A), Read(C)] (i) By considering some possible schedules of the above transactions, describe carefully the concurrency permitted by strict 2PL using just shared/read and exclusive/write locks. [3 marks] (ii) Detail a way to gain more interleaving whilst still maintaining strict 2PL. [7 marks] SECTION C 9 Logic and Proof (a) Define the concepts of a true sequent, a valid sequent and a basic sequent. You may take the concepts of true and valid formul as primitive. [3 marks] (b) Gentzen claimed that his proof systems performed natural logical reasoning. Consider the following sequent calculus rules: A, T = AB, T=A Av B, r = A A, A 3x A, A State the second rule's proviso and explain the intuitions behind each rule. (c) Choose one of these rules and give a rigorous argument for its soundness, using the concept of a valid sequent. [6 marks] (d) Precisely define the concept of the Most General Unifier (MGU) of two terms, giving examples. : Write program that takes n number of elements from user (where, n is specified by user), stores data in an array and calculates the average of those numbers.