CS GATE 2016 PAPER 01 (Test 2)



Tag: cs gate 2016 paper 01
Q.1
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
A. guarantee serializability and deadlock-freedom
B. guarantee neither serializability nor deadlock-freedom
C. guarantee serializability but not deadlock-freedom
D. guarantee deadlock-freedom but not serializability
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.

Workspace
Report
Q.2
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?
A.
B.
C.
D.
Answer : Option B
Explaination / Solution:



Workspace
Report
Q.3
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 ?
A. V XY Z
B. V W X Z
C. V W XY
D. V W XY Z
Answer : Option B
Explaination / Solution:

Any superset of VY is a super key.

Workspace
Report
Q.4
Which one of the following is NOT a part of the ACID properties of database transactions?
A. Atomicity
B. Consistency
C. Isolation
D. Deadlock-freedom
Answer : Option D
Explaination / Solution:

‘D’ means durability not deadlock freedom.

Workspace
Report
Q.5
 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?
A. 1NF
B. 2NF
C. 3NF
D. BCNF
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

Workspace
Report
Q.6
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?
A. Shortest remaining time first
B. Round-robin with time quantum less than the shortest CPU burst
C. Uniform random
D. Highest priority first with priority proportional to CPU burst length
Answer : Option A
Explaination / Solution:

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

Workspace
Report
Q.7
Which of the following languages is generated by the given grammar? S → aS|bS|ε
A. {an bm | n,m ≥ 0}
B. {w ∈ {a,b}* | w has equal number of a 's and b's}
C. {an | n ≥ 0} ∪ {bn | n ≥ 0} ∪ {an bn | n ≥ 0}
D. {a, b}∗
Answer : Option D
Explaination / Solution:

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

Workspace
Report
Q.8
 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) = Φ?
A. I and IV only
B. II and III only
C. III and IV only
D. II and IV only
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.

Workspace
Report
Q.9
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
A. (0 + 1)∗0011(0 + 1)∗ + (0 + 1)∗1100(0 + 1)∗
B. (0 + 1)∗(00(0 + 1)∗11 + 11(0 + 1)∗00)(0 + 1)∗
C. (0 + 1)∗00(0 + 1)∗ + (0 + 1)∗11(0 + 1)∗
D. 00(0 + 1)∗11 + 11(0 + 1)∗00
Answer : Option B
Explaination / Solution:

(a) contains 00 & 11 consecutively which is not the required condition. (c) Doesn’t guaranty that both 00 & 11 will be present in the string. (d) Says string should start with 11 & ends with 00 or vice versa.

Workspace
Report
Q.10
Consider the following context-free grammars:
G1: S → aS|B, B → b|bB 
G2: S → aA|bB, A → aA|B|ε , B → bB|ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
A.  {am bn |m > 0 or n > 0} and {am bn |m > 0 and n > 0}
B. {am bn|m > 0 and n > 0} and {am bn|m > 0 or n ≤ 0}
C. {am bn|m ≥ 0 or n > 0} and {am bn|m > 0 and n > 0}
D.  {am bn|m ≥ 0 or n > 0} and {am bn|m > 0 or n > 0}
Answer : Option D
Explaination / Solution:

Lagrange’s generated by G1 = a*b+
Lagrange’s generated by G2 = a+b*\b+

Workspace
Report