Computer Science (GATE Exam) 2012 - Previous Question Paper Solution

Register renaming is done to eliminate WAR/WAW hazards.

L = {ab, aa, baa}
Let S1 = ab, S2 = aaand S3 = baa
abaabaaabaa can be written as S1S2S3S1S2
aaaabaaaa can be written as S1S1S3S1
baaaaabaa can be written as S3S2S1S2

For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence total number of networks possible is 221.

For a 4 bit multiplier, there are 2⁴ ×2⁴ = 2⁸ = 256 combinations.
Output will contain 8 bits.
So, the amount of ROM needed is 2⁸ × 8 bits = 2 Kbits.

E-mail uses SMTP (an application layer protocol), which in turn uses TCP (a transport layer protocol).

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

If B(n), A(n) and W(n) denote best case, average case and worst case time complexities of an algorithm P respectively then B(n) = O(A(n)) , A(n) = O(W(n))

The cumulative distribution function
F(x) = P(X $\le$  x)
F(-1) = P(X $\le$ -1) = P(X = -1) = 0.5
F(+1) = P(X $\le$ +1) = P(X = -1)+P(x  =  + 1) = 0.5 + 0.5 = 1

We have the relation V – E + F = 2, by this we will get the total number of faces, F = 7. Out of 7 faces one is an unbounded face, so total 6 bounded faces.

Let the three pegs be A, B and C, the goal is to move n pegs from A to C using peg B
The following sequence of steps are executed recursively
1.move n - i discs from A to B. This leaves disc n alone on peg A --- T(n - 1)
2.move disc n from A to C 1
3.move n - i discs from B to C so they sit on disc n T(n - 1)
So, T(n) = 2T(n - 1) + 1

In a row of a relational table, an attribute cannot have more than one value.

We use a HAVING clause without a GROUP BY clause, the HAVING condition applies to all rows that satisfy the search condition. In other words, all rows that satisfy the search condition make up a single group. So, option P is true and Q is false.
Function of GROUP BY clause is to group the result obtained using one or more attributes. If attribute name is not present in SELECT clause then GROUP BY cannot find the attribute name in the result according to which result is supposed to be grouped. So, option R is true and S is false.

Language accepted by NFA is a⁺, so complement of this language is $\{\epsilon\}$

(O.5)₁₀ = (1.O)_{2 ×} 2^-1
So, exponent = -1 and fraction is 000 - - - 000

The PDU for Datalink layer, Network layer, Transport layer and Application layer are frame, datagram, segment and message respectively.

1: There exists x which is either real or rational and can be both.
2: All real numbers are rational
3: There exists a real number which is rational.
4: There exists some number which is not rational or which is real.

1 is false since BCNF is stricter than 3NF.
2 is false since the definition given here is of 2NF.
3 is true, since BCNF is stricter than 3NF, every relation in BCNF satisfies all the properties of 3NF.

If fork is called n times, there will be total 2 running processes including the parent process. So, there will be 2i child processes.

XY’ + XY = X(Y’ + Y) = X . 1 = X

The worst case search time in a balanced BST on 'x' nodes is logx. So, if x = n2ⁿ, then log(n2ⁿ) = logn + log(2ⁿ) = logn + n = $\theta$(n)

Since there is no ‘break’ statement, the program executes all the subsequent case statements after printing “choice A”

Total number of functions is 2ⁿ, out of which there will be exactly two functions where all elements map to exactly one element, so total number of onto functions is 2ⁿ – 2.

Access link is defined as link to activation record of closest lexically enclosing block in program text, so the closest enclosing blocks respectively for Al, A2 and A21 are main, main and A2.

Since B is a foreign key referring C, $ \prod_{B}(r_{1}) \subseteq \prod_{C}(r_{2} \Rightarrow \prod_{B}(r_{1})- \prod_{C}(r_{2})= \varnothing$

Since half of 4096 host addresses must be given to organization A, we can set 12^th bit to 1 and include that bit into network part of organization A, so the valid allocation of addresses to A is 245.248.136.0/21
Now for organization B, 12^th bit is set to '0' but since we need only half of 2048 addresses, 13^th bit can be set to '0' and include that bit into network part of organization B so the valid allocation of addresses to B is 245.248.128.0/22

The height of the recursion tree using merge sort is logn and n² comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n² logn)

If P! = NP, then it implies that no NP-Complete problem can be solved in polynomial time which implies that the set P and the set NPC are disjoint.

Graph G is counter example for options (2) and (3) and Graph G₁ is counter example for option (1)

The graph in option (1) has a 3 length cycle whereas the original graph does not have a 3 length cycle.
The graph in option (3) has a vertex with degree 4 whereas the original graph does not have a vertex with degree 4.
The graph in option (4) has a 4 length cycle whereas the original graph does not have a 4 length cycle.

Let S be a non-serial schedule, without loss of generality assume that T1 has started earlier than T2. The first instruction of T1 is read(P) and the last instruction of T2 is write(P), so the precedence graph for S has an edge from T1 to T2, now since S is a non-serial schedule the first instruction of T2 (read(Q)) should be executed before last instruction of T1 (write(Q)) and since read and write are conflicting operations, the precedence graph for S also contains an edge from T2 to T1, So we will have a cycle in the precedence graph which implies that any non serial schedule with T1 as the earliest transaction will not be conflict serializable.
In a similar way we can show that if T2 is the earliest transaction then also the schedule is not conflict serializable.

The final table is

Static local variables: Scope is limited to function/block but life time is entire program.
Automatic local variables: Storage allocated on function entry and automatically deleted or freed when the function is exited.
Register variables: Same as automatic variables except that the register variables will not have addresses. Hence, may not take the address of a register variable.

TAG controller maintains 16 + 4 = 20 bits for every block
Hence, size of cache tag directory = 20 × 2¹³ bits =160 Kbits

Correct Answer: that
With indefinite pronouns 'that' is used. Here 'one' is the indefinite pronoun. 

Correct Answer: setbacks
'Despite' is the key word as it suggests that in spite of something negative the mission succeeded. Here only 'setbacks' is negative and fits the context. Other options are out of context.

Correct Answer: The committee initially asked for a funding of Fifty Lakh rupees, but later settled for a lesser sum.

The use of the word 'lesser' is incorrect here as lesser means inferior in quality or less in inportance - insignificant. Here we have to use 'less' which means the committee settled for an amount which was less than the one initially asked for.

Correct Answer: DiminishMitigate means to lessen or make less severe. Only diminish has the same meaning and hence, is the synonym.

Gender is not mentioned in the advertisement and (2) clearly eliminated.

As the result of subquery is an empty table, ‘>ALL’ comparison is true. Therefore, all the three row id’s of A will be selected from table A.

P and R always hold true.
Otherwise, consider a sample set {1, 2, 3, 4} and check accordingly.

First(A) = First(S) = First(aAbB) $\cup$First(bAaB) $\cup$First($\in$)
= {a}$\cup${b}$\cup${$\in$} = {$\in$,a, b}
First(B)I = First(S) = {$\in$,a, b}
Follow (A) = First(bB) $\cup$ First(aB) = {a, b}
Follow (B) = Follow(S) = {$} $\cup$ Follow(A) = {$, a, b}