# CS GATE 2014 PAPER 03 (Test 2)

Tag: cs gate 2014 paper 03
Q.1
A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is
A. 0111110100
B. 0111110101
C. 0111111101
D. 0111111111
Explaination / Solution:

Given 8 – bit delimiter pattern of 01111110.
Output Bit string after stuffing is 01111100101
⇓
StuffedBit
Now, Input String is 0111110101

Workspace
Report
Q.2
Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP V4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D? (i) TTL (ii) Checksum (iii) Fragment Offset
A. (i) only
B. (i) and (ii) only
C. (ii) and (iii) only
D. (i), (ii) and (iii)
Explaination / Solution:

While an IP Datagram is transferring from one host to another host, TTL, Checksum and Fragmentation Offset will be changed.

Workspace
Report
Q.3
An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fields in the header of the third IP fragment generated by the router for this packet are
A. MF bit: 0, Datagram Length: 1444; Offset: 370
B. MF bit: 1, Datagram Length: 1424; Offset: 185
C. MF bit: 1, Datagram Length: 1500; Offset: 370
D. MF bit: 0, Datagram Length: 1424; Offset: 2960
Explaination / Solution:

Workspace
Report
Q.4
The Gross Domestic Product (GDP) in Rupees grew at 7% during 2012-2013. For international comparison, the GDP is compared in US Dollars (USD) after conversion based on the market exchange rate. During the period 2012-2013 the exchange rate for the USD increased from Rs. 50/ USD to Rs. 60/ USD. India’s GDP in USD during the period 2012- 2013
A. increased by 5 %
B. decreased by 13%
C. decreased by 20%
D. decreased by 11%
Explaination / Solution:

Per 100 Rs final value 107 Rs
⇒ Per 100/50 Dollars final value 107/60
for 100 dollars____?
= ((100 × 50)/100) × (107/60) = 89.16
Decreased by 11%.

Workspace
Report
Q.5
What is the optimized version of the relation algebra expression  where A1, A2 are sets of attributes in with A⊂ Aand F1, F2 are Boolean expressions based on
A.
B.
C.
D.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.6
A prime attribute of a relation scheme R is an attribute that appears
A. in all candidate keys of R.
B. in some candidate key of R.
C. in a foreign keys of R.
D. only in the primary key of R.
Explaination / Solution:

A prime attribute or key attribute of a relation scheme R is an attribute that appears in any of the candidate key of R, remaining attributes are known as non-prime or non-key tribute

Workspace
Report
Q.7
Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.
T1 : r1 (X) ; r1 (z) ; w1 (X) ; w1 (z)
T2 : r2 (X) ; r2 (z) ; w2 (z)
T3 : r3 (X) ; r3 (X) ; w3 (Y)
S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?
A. Only S1 is conflict-serializable.
B. Only S2 is conflict-serializable.
C. Both S1 and S2 are conflict-serializable.
D. Neither S1 nor S2 is conflict-serializable.
Explaination / Solution:

Precedence graph for S1 & S2 are as follows

∴Only S1 is conflict serializable.

Workspace
Report
Q.8
Consider the relational schema given below, where eId of the relation dependentis a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation.
employee (empId, empName, empAge)
dependent (depId, eId, depName, depAge)
Consider the following relational algebra query

The above query evaluates to the set of empIds of employees whose age is greater than that of
A. some dependent.
B. all dependents.
C. some of his/her dependents.
D. all of his/her dependents
Explaination / Solution:

Part A of the above given relational algebra query will give the set of empIds of those employees whose age is less than or equal to the age of some of his/her dependents. Now when set of empIds of all employees minus set of empIds obtained from part A is done, then we get the set of empIds of employees whose age is greater than that of all of his/her dependents.

Workspace
Report
Q.9
Consider the decision problem 2CNFSAT defined as follows:
{ φ | φ is a satisfiable propositional formula in CNF with at most two literal per clause}
For example,  is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
A. NP-Complete.
B. solvable in polynomial time by reduction to directed graph reachability.
C. solvable in constant time since any input instance is satisfiable.
D. NP-hard, but not NP-complete.
Explaination / Solution:

2 SAT is in P. This we can prove by reducing 2 SAT to directed graph reachability problem which is known to be in P.
Procedure for reducing 2 SAT to reachability problem:
1. Let ϕ be CNF with clauses of length 2 and let P be the set of propositional variables(literals) in ϕ
2. Build a graph G=(V,E) with V= P { p|p P} ∪ ¬ ∈ and (x, y E )∈ iff there is a clause in ϕ that is equivalent to x y → (all the clauses are converted to equivalent implications and the graph built is called as implication graph)
3. Observe that ϕ is unsatisfiable iff there is a p P ∈ such that there is both a path from p to to ¬p and from ¬p to p in G.
This condition can be tested by running the reachability algorithm several times.

Workspace
Report
Q.10
Which of the following statements are CORRECT?
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
A. 1 and 2 only
B. 2 and 3 only
C. 3 and 4 only
D. 1 and 3 only