CS and IT Gate 2016 Set-1 Questions with Answer

Given:
A protocol where a transaction acquires exclusive locks on objects in increasing order of their addresses.
All required operations are executed after getting the locks.
All locks are released after the operations are completed.
To find:
Whether this protocol guarantees serializability and/or deadlock-freedom.
Solution:
First, let me check the locking and unlocking phases.
All locks are acquired in Step 1, and no lock is released until Step 3.
Since all lock requests precede all unlock requests, this protocol follows the Two-Phase Locking (2PL) rule.
I know that any 2PL protocol guarantees conflict serializability.
Now let me check the deadlock condition.
Here, transactions acquire locks on items strictly in increasing order of their addresses.
This creates a global total ordering on all resources.
Because every transaction requests objects according to the same global order, circular wait is impossible.
Since circular wait cannot happen, deadlock can never occur.
So this protocol guarantees both serializability and deadlock-freedom.
Answer: (A) guarantee serializability and deadlock-freedom

Given:
Original schema: R(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, YEAR, PRICE)
Primary Key: (VOLUME, NUMBER, STARTPAGE, ENDPAGE)
Functional Dependencies:
FD1: (VOLUME, NUMBER, STARTPAGE, ENDPAGE) → TITLE
FD2: (VOLUME, NUMBER) → YEAR
FD3: (VOLUME, NUMBER, STARTPAGE, ENDPAGE) → PRICE
Redesigned schemas:
R₁(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, PRICE)
R₂(VOLUME, NUMBER, YEAR)
To find:
The weakest normal form that the new database satisfies, but the old one does not.
Solution:
First, let me analyze the normal form of the original schema R.
The candidate key for R is (VOLUME, NUMBER, STARTPAGE, ENDPAGE).
So the prime attributes are: VOLUME, NUMBER, STARTPAGE, ENDPAGE.
The non-prime attributes are: TITLE, YEAR, PRICE.
Looking at FD2: (VOLUME, NUMBER) → YEAR.
Here, (VOLUME, NUMBER) is a proper subset of the candidate key, and YEAR is a non-prime attribute.
This means there is a partial dependency, so R violates 2NF.
Thus, the original schema is only in 1NF.
Now, let me check the redesigned schemas.
For relation R₁:
The candidate key is (VOLUME, NUMBER, STARTPAGE, ENDPAGE).
The functional dependencies are:
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) → TITLE
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) → PRICE
In both FDs, the left-hand side is a superkey. So R₁ is in BCNF.
For relation R₂:
The candidate key is (VOLUME, NUMBER).
The functional dependency is:
(VOLUME, NUMBER) → YEAR
Here too, the left-hand side is a superkey. So R₂ is in BCNF.
Since both R₁ and R₂ are in BCNF, the new database satisfies 2NF, 3NF, and BCNF.
The old database does not satisfy 2NF, 3NF, or BCNF.
Among the normal forms that the new database satisfies but the old one does not (2NF, 3NF, BCNF), the weakest one is 2NF.
Answer:
(B) 2NF

Given:
Four properties related to database transactions: Atomicity, Consistency, Isolation, and Deadlock-freedom.
To find:
The property that is NOT a part of the ACID properties.
Solution:
Let me recall what the acronym ACID stands for in database systems.
A stands for Atomicity, meaning all operations in a transaction succeed, or none do.
C stands for Consistency, ensuring the database moves from one valid state to another.
I stands for Isolation, ensuring concurrent transactions do not interfere with each other.
D stands for Durability, ensuring that committed changes are saved permanently.
Now looking at the options, Deadlock-freedom is given for letter D instead of Durability.
So Deadlock-freedom is definitely not an ACID property.
Answer: (D) Deadlock-freedom

Given:
Relation schema attributes = {V, W, X, Y, Z}
Primary key = V Y
To find:
Which of the given options is NOT a superkey.
Solution:
Okay, let's recall the basic definition of a superkey.
A superkey is simply any set of attributes that contains a candidate key (or primary key) as a subset.
Here, the primary key is given as {V, Y}.
So, any attribute set that contains both V and Y will act as a superkey.
Now let me check each option one by one.
Checking option A: {V, X, Y, Z}.
It contains both V and Y, so this is a superkey.
Checking option B: {V, W, X, Z}.
Wait, Y is missing here! It only has V, not Y.
Since it does not contain the primary key {V, Y}, it cannot be a superkey.
Let me just quickly check the remaining options to be sure.
Checking option C: {V, W, X, Y}.
Contains both V and Y, so it is a superkey.
Checking option D: {V, W, X, Y, Z}.
Contains both V and Y, so it is also a superkey.
Therefore, option B is definitely not a superkey.
Answer: (B)

Given:
Three sorting algorithms: Insertion sort, Merge sort, and Quick sort.
To find:
The worst case running times of Insertion sort, Merge sort, and Quick sort, respectively.
Solution:
Let me analyze the worst case running time for each algorithm one by one.
First, consider Insertion sort.
In the worst case, the input array is reverse sorted.
For each element at index i, we have to make i comparisons and shifts.
Total work done is proportional to 1 + 2 + 3 + ... + (n - 1) = (n(n - 1))/2, which gives Θ(n²).
Next, consider Merge sort.
Merge sort divides the array into two halves, sorts them recursively, and merges them in linear time.
The recurrence relation is T(n) = 2T(n/2) + Θ(n).
Solving this recurrence using Master theorem gives T(n) = Θ(n log n) in all cases, including the worst case.
Now, consider Quick sort.
The worst case occurs when the chosen pivot always partitions the array into two subproblems of sizes 0 and n - 1.
This happens, for instance, when the array is already sorted and we pick the first or last element as the pivot.
The recurrence becomes T(n) = T(n - 1) + Θ(n).
Solving this gives T(n) = Θ(n²).
So, combining all three in order, the worst case times are Θ(n²), Θ(n log n), and Θ(n²).
Checking the options, this matches with option D.
Answer: (D) Θ(n²), Θ(n log n) and Θ(n²)

Given:
Carry lookahead adder for adding two n-bit integers.
Gates have a maximum fan-in of 2.
To find:
The time required to perform the addition.
Solution:
Let me recall how carry lookahead adder works with restricted fan-in.
First, to compute the generate (g_i = a_i b_i) and propagate (p_i = a_i ⊕ b_i) terms for each bit, we only need 2-input gates.
So computing all g_i and p_i takes constant time, which is Θ(1).
Now, to compute the carries, each carry bit c_i depends on up to i variables.
Since the fan-in of each gate is at most 2, an operation combining n inputs requires a binary tree of gates.
The height (or depth) of a balanced binary tree with n inputs is given by log₂(n).
Thus, computing prefix carries using a tree structure takes time proportional to the depth of the tree, which is Θ(log n).
Finally, computing the sum bits s_i = p_i ⊕ c_i takes one more XOR gate delay, which is Θ(1).
Adding all these delays up, the total time required is:
Total time = Θ(1) + Θ(log n) + Θ(1) = Θ(log n).
Answer:
(B) Θ(log (n))

Given:
A Boolean operator # with the following properties:
x # 0 = x
x # 1 = x'
x # x = 0
x # x' = 1
To find:
The equivalent expression for x # y.
Solution:
Let me check the standard Boolean operations that satisfy these conditions.
Looking at the first property, x # 0 = x.
Now looking at the second property, x # 1 = x'.
Next, the third property gives x # x = 0.
And the fourth property gives x # x' = 1.
Wait, this directly matches the standard XOR (Exclusive-OR) logic gate properties.
Let me verify with the XOR truth table and expressions:
x ⊕ 0 = x·0' + x'·0 = x·1 + 0 = x.
x ⊕ 1 = x·1' + x'·1 = x·0 + x' = x'.
x ⊕ x = x·x' + x'·x = 0 + 0 = 0.
x ⊕ x' = x·(x')' + x'·x' = x·x + x' = x + x' = 1.
All four properties are completely satisfied by the XOR operator.
So, x # y is simply x ⊕ y.
Writing the XOR operation in terms of basic Boolean operations, we get:
x ⊕ y = x'y + xy'
Thus, x # y = x'y + xy', which matches Option A.
Answer: (A) x'y + xy'

Given:
a_n = number of n-bit strings that do not contain two consecutive 1s.
To find:
The recurrence relation for a_n.
Solution:
Let me consider a valid n-bit string.
It can either end with a 0 or end with a 1.
Case 1: The string ends with a 0.
If the last bit is 0, the first (n - 1) bits can be any valid string of length (n - 1) with no two consecutive 1s.
So, the number of such strings is a_n-1.
Case 2: The string ends with a 1.
Since consecutive 1s are not allowed, the bit right before the last bit must be 0.
So the string must end with "01".
The remaining first (n - 2) bits can be any valid string of length (n - 2) with no two consecutive 1s.
So, the number of such strings is a_n-2.
Now, combining both mutually exclusive cases, I get:
a_n = a_n-1 + a_n-2.
Let me quickly verify for small values.
For n = 1, valid strings are "0" and "1", so a₁ = 2.
For n = 2, valid strings are "00", "01", "10", so a₂ = 3.
For n = 3, valid strings are "000", "001", "010", "100", "101", so a₃ = 5.
Checking the relation: a₃ = a₂ + a₁ = 3 + 2 = 5, which matches perfectly.
Answer: (B)