CS GATE 2017 PAPER 01 (Test 2)



Tag: cs gate 2017 paper 01
Q.1
The statement (¬p) ⇒ (¬q) is logically equivalent to which of the statements below?
I. p ⇒ q
II. q ⇒ p 
III. (¬q) ∨ p
IV. (¬p) ∨ q
A. I only
B. I and IV only
C. II only
D. II and III only
Answer : Option D
Explaination / Solution:

By rule of contrapositive, 


Workspace
Report
Q.2
The following functional dependencies hold true for the relational schema R{V,W,X,Y,Z}:
V → W 
VW → X 
Y → VX 
Y → Z
Which of the following is irreducible equivalent for this set of functional dependencies ?
A. V → W V → X Y → V Y → Z
B. V → W W → X Y → V Y → Z
C. V →W V → X Y → V Y → X Y → Z
D. V → W W → X Y → V Y → X Y → Z
Answer : Option A
Explaination / Solution:



Workspace
Report
Q.3
 Consider a database that has the relation schemas EMP(EmpId, EmpName, DepId). And DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

Which of the above queries are safe? 
A. (I) and (II) only
B. (I) and (III) only
C. (II) and (III) only
D. (I), (II) and (III)
Answer : Option D
Explaination / Solution:

Query which generates infinite number of tuples is called unsafe query. In the given question all the given queries generate finite number of tuples.

Workspace
Report
Q.4
In a database system, unique time stamps are assigned to each transaction using Lamport’s logical clock . Let TS(T1) and TS(T2) be the timestamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp.
if TS(T2) < TS(T1) then
Tis killed
else Twaits.
Assume any transactions that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks? 
A. The database system is both deadlock-free and starvation- free.
B. The database system is deadlock- free, but not starvation-free.
C. The database system is starvation-free but not deadlock- free.
D. The database system is neither deadlock- free nor starvation-free.
Answer : Option A
Explaination / Solution:

Elder kills younger and youngers waits on elder. So both are not waiting for each other. Hence no deadlock and there won’t be any starvation as well because the transaction who got killed will be starting with same time stamp. 

Workspace
Report
Q.5
A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:
A. x = 1, y = 2
B. x =2, y=1
C. x = 2,y=2
D. x = 1, y = 1
Answer : Option C
Explaination / Solution:

As per given question, there 'x' number of threads and 'y' number of locks for ensuring mutual exclusion while operating on shared memory locations
Option (A): x=1;y=2
Means that 1 thread and 2 locks clearly showing that no deadlock situation
Option (B): x=2;y=1
Means that 2 threads and 1 lock → No deadlock situation
After usage of lock by 1 thread, it can release that lock and then 2nd thread can be used that lock. So no deadlock
Option(C):x=2;y=2
Means that 2 threads and 2 locks→Deadlock can arise
Both threads can hold 1 lock and can wait for release of another lock
Option(D) x=1; y=1
Means that 1 thread and 1 lock →No deadlock situation 

Workspace
Report
Q.6
 Consider the following intermediate program in three address code
p = a - b
q = p *c 
p = u * v 
q = p + q
Which one of the following corresponds to a static single assignment form of the above code ?
A.
B.
C.
D.
Answer : Option B
Explaination / Solution:
No Explaination.


Workspace
Report
Q.7
Consider the following grammar.

What is FOLLOW (Q) ? 
A. {R}
B. {w}
C. {w, y}
D. {w, $}
Answer : Option C
Explaination / Solution:

FOLLOW(Q) is FIRST(R) hence
FIRST(R) = {w, ϵ} 
We add ‘w’ in FOLLOW(Q) and for ϵ we calculate FIRST(S) 
FIRST(S) ={y} 
FOLLOW(Q) is {w ,y}  

Workspace
Report
Q.8
 Consider the following context-free grammar over the alphabet ∑ = {a,b,c} with S as the start symbol.
S → abScT|abcT
T → bT|b
Which one of the following represents the language generated by the above grammar ? 
A.
B.
C.
D.
Answer : Option B
Explaination / Solution:

The given Grammar over Σ = {a, b, c} with S as the start symbol is 
S → abScT | abcT 
T→ bT | b 
The minimum length string generated by the grammar is 1: 
S→abcT→abcb ; hence all variable greater than 1. 
Other cases
S → abScT→ ab abScT cT → ab ab abScT cT cT →........→ (ab)n (cT)n
Here T can generate any number of b’s starting with single b.  

Workspace
Report
Q.9
If G is grammar with productions S → SaS|aSb|bSa|SS|∈ where S is the start variable, then which one of the following is not generated by G?
A. abab
B. aaab
C. abbaa
D. babba
Answer : Option D
Explaination / Solution:
No Explaination.


Workspace
Report
Q.10
Consider the following languages over the alphabet ∑= {a, b,c}

Which of the following are context-free languages ? 
I. L∪ L2                  II. L1 ∩ L2
A. I only
B. II only
C. I and II
D. Neither I nor II
Answer : Option A
Explaination / Solution:



Workspace
Report