CS GATE 2016 PAPER 01 - Online Test

Q1. Consider the following two phase locking protocol. Suppose a transaction T accesses (for read or write operations), a certain set of objects {O1, . . . , OK}. This is done in the following manner:
Step 1. T acquires exclusive locks to O1, . . . , Ok in increasing order of their addresses. 
Step 2. The required operations are performed. 
Step 3. All locks are released. 
This protocol will
Answer : Option A
Explaination / Solution:

2PL ensures serializability and here as we are following linear order in acquiring the locks there will not be any deadlock.

Q2. Consider a carry look ahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is
Answer : Option B
Explaination / Solution:
No Explaination.


Q3. Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by  for x = A, B, respectively. Let Kx(m) represent the operation of encrypting m with a key Kx and H (m) represent the message digest. Which one of the following indicates the CORRECT way of sending the message m along with the digital signature to A?
Answer : Option B
Explaination / Solution:



Q4. Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?
Answer : Option A
Explaination / Solution:

SRTF is pre emptive SJF which produces less average waiting time.

Q5. Which of the following is NOT a super key in a relational schema with attributes V , W , X , Y , Z and primary key V Y ?
Answer : Option B
Explaination / Solution:

Any superset of VY is a super key.

Q6. Which one of the following is NOT a part of the ACID properties of database transactions?
Answer : Option D
Explaination / Solution:

‘D’ means durability not deadlock freedom.

Q7.  A database of research articles in a journal uses the following schema. (VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, YEAR, PRICE) 
The primary key is (VOLUME, NUMBER, STARTPAGE, ENDPAGE) and the following functional dependencies exist in the schema.
(VOLUME, NUMBER, STARTPAGE, ENDPAGE)  → TITLE 
(VOLUME, NUMBER                                              → YEAR 
(VOLUME, NUMBER, STARTPAGE, ENDPAGE)  → PRICE
The database is redesigned to use the following schemas. 
(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, PRICE) (VOLUME, NUMBER, YEAR) 
Which is the weakest normal form that the new database satisfies, but the old one does not?
Answer : Option A
Explaination / Solution:

candidate key is (volume, number, start page, end page) (Volume number) → year is a partial dependency. So original table is in 1NF but not in 2NF

Q8. Which of the following languages is generated by the given grammar? S → aS|bS|ε
Answer : Option D
Explaination / Solution:

Given grammar generates all strings of a’s and b’s including null string ∴ L = (a + b) *

Q9.  Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ?
II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ∗, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?
Answer : Option C
Explaination / Solution:

There is no known algorithm to check whether the language accepted by TM is empty. Similarly there is no algorithm to check whether language CFG’s are equivalent.

Q10. A rewording of something written or spoken is a ___________.
Answer : Option A
Explaination / Solution:
No Explaination.