CS GATE 2017 PAPER 01 - Online Test
Q1. A computer network uses polynomials over GF(2) for error checking with 8 bits as
information bits and uses x3 + x + 1 as the generator polynomial to generate the check bits. In
this network, the message 01011011 is transmitted as
Answer : Option C
Explaination / Solution:
Q2. 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:
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
Q3. 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
Answer : Option D
Explaination / Solution:
By rule of contrapositive,
Q4. 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 ?
Answer : Option A
Explaination / Solution:
Q5. 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?
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.
Q6. 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
T1 is killed
else T2 waits.
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?
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.
Q7. Research in the workplace reveals that people work for many reason ___________.
Answer : Option D
Explaination / Solution:
No Explaination.
Q8. Consider the following grammar.
What is FOLLOW (Q) ?
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}
Q9. After Rajendra chola returned from his voyage to Indonesia, he _______ to visit the temple in
Thanjavur.
Answer : Option C
Explaination / Solution:
No Explaination.
Q10. 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 ?
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.
