# gate cs computer science 2014 set 3 solved explanation with answers

 Question 1
While trying to collect(I) an envelope from under the table (II), Mr. X fell down (III) and was losing consciousness (IV) Which one of the above underlined parts of the sentence is NOT appropriate?
 A I B II C III D IV
Explanation:

Here, part IV is incorrect. “was losing consciousness” shows continuous process of losing consciousness, but he was not in the process, rather he just lost consciousness. So, the correction is ” was losing consciousness ”  → ” lost consciousness “.

Thus, IV is the correct choice.

 Question 2
If she _______________ how to calibrate the instrument, she _______________ done the experiment.
 A knows, will have B knew, had C had known, could have D should have known, would have

Explanation:  A)knows, will have //Present ,future B)knew, had //past past c)had known, could have//past perfect,perfect conditional D)should have known, would have //present,future     In a Type 3 conditional sentence, the tense in the ‘if’ clause is the past perfect, and the tense in the main clause is the perfect conditional or the perfect continuous conditional.

IF CLAUSE (CONDITION) MAIN CLAUSE (RESULT)
If + past perfect perfect conditional or perfect continuous conditional
If this thing had happened that thing would have happened.

 Question 3
Choose the word that is opposite in meaning to the word “coherent”.
 A sticky B well-connected C rambling D friendly
Explanation:

Coherent – Adj. Meaning – (of an argument, theory, or policy) logical and consistent. Rambling – Adj. Meaning – (of writing or speech) lengthy and confused or inconsequential. Hence both are opposite to each other.

 Question 4
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
 A 17 B 37 C 64 D 26

Explanation:

```Given series is 2,5,10,17,26,37,50,64.

Here total number of terms are 8..i.e. A(1) to A(8).

For the 1st 7 terms, you can observe the relationship
between the terms which is
A(n) = [ A(n-1) - {A(n-1) + A(n-2)} + 2 ] where n >= 3

Now for the 8th term i.e. A(8), this relationship violates.
According to the relationship,
A(8) = [A(7) + {A(7) - A(6)} + 2 ]
= [50 + {50 - 37} + 2 ]
= 50 + 13 + 2
= 65.
But in the series it is 64. Hence 64 doesn't belong to
the series.```

 Question 5
The table below has question-wise data on the performance of students in an examination. The marks for each question are also listed. There is no negative or partial marking in the examination. What is the average of the marks obtained by the class in the examination
 A 1.34 B 1.74 C 3.02 D 3.91
Explanation:
```As you can see from each row that the total number of
students in the class are 44.

Now we have to find the total number of marks obtained
by the class.

Marks are given for correct answers only.
No negative or partial marking.

For 1st question total marks obtained are : 2*21 = 42
For 2nd question total marks obtained are : 3*15 = 45
For 3rd question total marks obtained are : 2*23 = 46

hence total marks obtained by the class are = 42+45+46 = 133

Now, Average marks obtained = Total Marks/Total no of students
= 133/44
= 3.02

 Question 6 A dance programme is scheduled for 10.00 a.m. Some students are participating in the programme and they need to come an hour earlier than the start of the event. These students should be accompanied by a parent. Other students and parents should come in time for the programme. The instruction you think that is appropriate for this is
 A Students should come at 9.00 a.m. and parents should come at 10.00 a.m. B Participating students should come at 9.00 a.m. accompanied by a parent, and other parents and students should come by 10.00 a.m. C Students who are not participating should come by 10.00 a.m. and they should not bring their parents. Participating students should come at 9.00 a.m. D Participating students should come before 9.00 a.m. Parents who accompany them should come at 9.00 a.m. All others should come at 10.00 a.m.
EXPLanation:
• A is not the appropriate instruction as only the participating students and their parents have to come at 9.00 a.m. and other students along with their parents have to come at 10.00 a.m., while the statement in A says that all students should come at 9.00 a.m. and all the parents should come at 10.00 a.m.
• B is the appropriate instruction and covers all the aspects of the information to be conveyed.
• C is not the appropriate instruction as the non participating students have to come at 10.00 a.m. with their parents, while the statement in B says that these students have to come without their parents.
• D is not the appropriate instruction as it states that the participating students have to come before 9.00 a.m. whereas they have to come at 9.00 a.m.

So B is Correct option.

 Question 7

By the beginning of the 20th century, several hypotheses were being proposed, suggesting a paradigm shift in our understanding of the universe. However, the clinching evidence was provided by experimental measurements of the position of a star which was directly behind our sun. Which of the following inference(s) may be drawn from the above passage?

```(i) Our understanding of the universe changes
based on the positions of stars
(ii) Paradigm shifts usually occur at the
beginning of centuries
(iii) Stars are important objects in the
universe
(iv) Experimental evidence was important in
```
 A (i), (ii) and (iv) B (iii) only C (i) and (iv) D (iv) only

Explanation:

Paradigm shift means a fundamental change in approach to something or change in the underlying assumptions in relation to something. This change, as per the question, was verified with the experimental measurements of the position of a star that was behind the sun. (i) is incorrect as it generalizes the experimental evidence of the star and assumes it to be always true, which may not be the case every time. (ii) is also incorrect. If there was a paradigm shift at the beginning of the 20th century, it does not necessarily means that all paradigm shifts usually occur at the beginning of centuries. (iii) is incorrect as it again generalizes an experimental statement. Stars proved to be important in the given case does not necessarily imply that they would be important every time. (iv) is correct as it is clearly understood from the given case conditions that this experimental measurements provided a clinching (solid/concrete) evidence to our understanding of the universe.

So, D is the correct choice as only (iv) is the correct statement.   Please comment below if you find anything wrong in the above post.

 Question 8
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%
Explanation:
```Suppose original GDP was x then its international
value is x/50.

Now GDP becomes 107*x/100 and its international
value becomes (107x/100)/60= 107x/6000.

The value has decreased by (x/50)-(107x/6000).
Percentage approx 10.8% = 11%```

 Question 9
The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students in 2011 and 2012 is equal, what is the ratio of male students in 2012 to male students in 2011?
 A 1:1 B 2:1 C 1.5:1 D 2.5:1

Explanation:

```Number of female students in 2011 and 2012 are equal.
Suppose they are x.

Now,
Males students in 2011 = Female students in 2011
= x (as the ratio is 1)

And in 2012, Male students / Female students =
1.5(Given)

Hence Male students in 2012 = 1.5 * Female students
= 1.5 * x

Now ratio of Male students in 2012 to Male students
in 2011 = ( 1.5 * x ) / x
= 1.5 / 1
i.e. 1.5 : 1

 Question 10
Consider the equation: (7526)8 − (Y)8 = (4364)8 , where (X)N stands for X to the base N. Find Y.
 A 1634 B 1737 C 3142 D 3162

Explanation:

(X)N stands for X to the base N. 7526(8) – Y(8) = 4364(Y) Base 8(Octal) uses digits 0 to 7. Now Y(8) = 7526(8) – 4364(8) The subtraction of octal numbers follows the same rules as the subtraction of numbers in any other number system. The only variation is in borrowed number. In the decimal system, you borrow a group of 10(10). In the binary system, you borrow a group of 2(10). In the octal system you borrow a group of 8(10).

 Question 11

Consider the following statements:

```  P: Good mobile phones are not cheap
Q: Cheap mobile phones are not good

L: P implies Q
M: Q implies P
N: P is equivalent to Q```

Which one of the following about L, M, and N is CORRECT?

 A Only L is TRUE. B Only M is TRUE. C Only N is TRUE. D L, M and N are TRUE

Explanation:

```Let a and b be two proposition
a: Good Mobile phones.
b: Cheap Mobile Phones.

P and Q can be written in logic as
P: a-->~b
Q: b-->~a.

Truth Table
a   b   ~a  ~b   P   Q
T   T   F    F   F   F
T   F   F    T   T   T
F   T   T    F   T   T
F   F   T    T   T   T

it clearly shows P and Q are equivalent.
so option D is Correct```

 Question 12
Let X and Y be finite sets and f: X -> Y be a function. Which one of the following statements is TRUE?
 A A B B C C D D

Explanation:

```Let x = {a, b, c} and y = {1, 2}
A Function f maps each element of x to 1 in y.
f(a)=1 , f(b)=1 , f(c) =1
A = {a, b} B = {b, c}
----------------------------------------------
A ]
| f(A u B) | = |f({a, b, c})| = 3
| f(A)|+|f(B)| = 2 + 2 = 4 , LHS != RHS.
----------------------------------------------
B ]
f(A ∩ B) = f({b}) = { 1 }
f(A) ∩ f(B) = {1, 1} ∩ {1, 1} = {1, 1}
LHS != RHS
-----------------------------------------------
C ]
|f(A ∩ B)| = |f({b})| = |{ 1 }| = 1
min{|f(A)|,|f(B)|} = min(2,2) = 2
LHS != RHS
-----------------------------------------------
D ] In a function a value can be mapped only to one value.```

 Question 13
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L != G and that the size of L is at least 4. The size of L is __________.
 A 3 B 5 C 7 D 9

Explanation:

This is according to Lagrange’s theorem that states that the order of subgroup should divide the order of group. Subgroups of G can be of order 1,3,5 or 15 and according to the conditions and choices, B is the right answer.

 Question 14
Which one of the following statements is TRUE about every
 A If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative. B If the trace of the matrix is positive, all its eigenvalues are positive. C If the determinant of the matrix is positive, all its eigenvalues are positive. D If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive.

 Question 15
If V1 and V2 are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of V1 ∩ V2 is ______.
 A 1 B 2 C 3 D 4

Explanation:

First, note that V1+V2 is still in V, so dim(V1+V2)≤ 6. We know that dim(V1+V2)=dimV1+dimV2−dim(V1∩V2). So 6≥dim(V1+V2)=dimV1+dimV2−dim(V1∩V2) dim(V1∩V2)≥4+4−6=2. The answer is B.

 Question 16
 A 2 B 3 C 4 D 5

 Question 17
 A A B B C C D D

 Question 18

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.

 `f (x, y, a, b)` `{` `   ``if` `(x is 1) y = a;` `   ``else` `y = b;` `}`

Which one of the following digital logic blocks is the most suitable for implementing this function?

 A Full adder B Priority encoder C Multiplexer D Flip-flop

Explanation:

This function can be interpreted as having two inputs a, b and select signal x. Output y will depend on the select signal x. Function will be like (ax+bx’) Its implementation will be like So ans is ( C) .

 Question 19

Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency.

```P1: Four-stage pipeline with stage
latencies 1 ns, 2 ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage
latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with stage
latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns.
P4: Five-stage pipeline with stage
latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns.```

Which processor has the highest peak clock frequency?

 A P1 B P2 C P3 D P4

Explanation:

```Peak clock frequency = 1 / Maximum latency

Maximum of latencies is minimum in P3```

 Question 20

Let A be a square matrix of size n x n. Consider the following program. What is the expected output?

 `C = 100` `for` `i = 1 to n ``do` `    ``for` `j = 1 to n ``do` `    ``{` `        ``Temp = A[i][j] + C` `        ``A[i][j] = A[j][i]` `        ``A[j][i] = Temp - C` `    ``} ` `for` `i = 1 to n ``do` `    ``for` `j = 1 to n ``do` `        ``Output(A[i][j]);`
 A The matrix A itself B Transpose of matrix A C Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A D None of the above

Explanation:

If we take look at the inner statements of first loops, we can notice that the statements swap A[i][j] and A[j][i] for all i and j. Since the loop runs for all elements, every element A[l][m] would be swapped twice, once for i = l and j = m and then for i = m and j = l. Swapping twice means the matrix doesn’t change.

 Question 21
The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4X3 + 6X + 5 for a given value of X using only one temporary variable.
 A 6 B 7 C 8 D 9

Explanation:

```P(X) = x5 + 4x3 + 6x + 5

=x ( x4 + 4x2 + 6 ) +5

=x ( x ( x3 + 4x ) + 6 ) + 5

=x ( x ( x ( x2 + 4 ) ) + 6 ) + 5

=x ( x ( x (x (x) + 4 ) ) + 6 ) + 5

Let T be a temporary variable to store intermediate results.

1. T = (x) * (x)
2. T = T + 4
3. T = (x) * (T)
4. T = (x) * (T)
5. T = T + 6
6. T = (x) * T
7. T = T + 5

Thus, we need 7 operations if we are to use only one temporary variable.```

 Question 22
Consider the following rooted tree with the vertex P labeled as root

The order in which the nodes are visited during in-order traversal is
 A SQPTRWUV B SQPTURWV C SQPTWUVR D SQPTRUWV

Explanation:

```Algorithm Inorder(tree) - Use of Recursion
Steps:
1. Traverse the left subtree,
i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree,
i.e., call Inorder(right-subtree)

Understanding this algorithm requires the basic
understanding of Recursion

Therefore, We begin in the above tree with root as
the starting point, which is P.

# Step 1( for node P) :
Traverse the left subtree of node or root P.
So we have node Q on left of P.

-> Step 1( for node Q)
Traverse the left subtree of node Q.
So we have node S on left of Q.

* Step 1 (for node S)
Now again traverse the left subtree of node S which is
NULL here.

* Step 2(for node S)
Visit the node S, i.e print node S as the 1st element of
inorder traversal.

* Step 3(for node S)
Traverse the right subtree of node S.
Which is NULL here.

Now move up in the tree to Q which is parent
of S.( Recursion, function of Q called for function of S).
Hence we go back to Q.

-> Step 2( for node Q):
Visit the node Q, i.e print node Q as the 2nd
element of inorder traversal.

-> Step 3 (for node Q)
Traverse the right subtree of node Q.
Which is NULL here.

Now move up in the tree to P which is parent
of Q.( Recursion, function of P called for function of Q).
Hence we go back to P.

# Step 2(for node P)
Visit the node P, i.e print node S as the 3rd
element of inorder traversal.

# Step 3 (for node P)
Traverse the right subtree of node P.
Node R is at the right of P.

Till now we have printed SQP as the inorder of the tree.
Similarly other elements can be obtained by traversing
the right subtree of P.

The final correct order of Inorder traversal would
be SQPTRWUV.```

 Question 23
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

 A 17 B 18 C 19 D 20

Explanation:

The following diagram shows the worst case situation where the recursion tree has maximum depth.

So the recursion depth is 19 (including the first node).

 Question 24
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
 A O(n2) B O(nLogn) C Theta(nLogn) D O(n3)

 Question 25

The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.

`a*b*(ba)*a*`
 A 2 B 3 C 4 D 5

Explanation:

The string “bab” is the shortest string not acceptable by regular expression.

 Question 26
 A A B B C C D D

 Question 27
One of the purposes of using intermediate code in compilers is to
 A make parsing and semantic analysis simpler. B improve error recovery and error reporting. C increase the chances of reusing the machine-independent code optimizer in other compilers. D improve the register allocation.

Explanation:

After semantic Analysis, the code is converted into intermediate code which is language independent, the advantage of converting into intermediate code is to improve the performance of code generation and to increase the chances of reusing the machine-independent code optimizer in other compilers.

 Question 28

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

Explanation:

1) Static allocation of all data areas by a compiler makes it impossible to implement recursion. True, dynamic allocate of memory is required for function call stack as number of calls is not known advance for recursive functions. 2) Automatic garbage collection is essential to implement recursion. False, Automatic garbage collection is not essential. 3) Dynamic allocation of activation records is essential to implement recursion. True, as number of calls or number of activation records is not known advance for recursive functions. 4) Both heap and stack are essential to implement recursion. Heap is not needed for function calls. It is generally used for dynamic memory allocation by user (or programmer). See Memory Layout of C Programs for details.

 Question 29
In the context of modular software design, which one of the following combinations is desirable?
 A High cohesion and high coupling B High cohesion and low coupling C Low cohesion and high coupling D Low cohesion and low coupling

Explanation:

Coupling is the manner and degree of interdependence between software modules.Cohesion refers to the degree to which the elements of a module belong together. In a good software design, it is always desirable to have less interaction among modules (Low coupling). Advantages of high cohesion (or “strong cohesion”) are: 1) Reduced module complexity (they are simpler, having fewer operations). 2) Increased system maintainability, because logical changes in the domain affect fewer modules, and because changes in one module require fewer changes in other modules. 3) Increased module reusability,because application developers will find the component they need more easily among the cohesive set of operations provided by the module.

 Question 30
A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? 4, 7, 6, 1, 7, 6, 1, 2, 7, 2
 A 4 B 5 c 6 d 7

Explanation:

What is a Page fault ? An interrupt that occurs when a program requests data that is not currently in real memory. The interrupt triggers the operating system to fetch the data from a virtual memory and load it into RAM. Now, 4, 7, 6, 1, 7, 6, 1, 2, 7, 2 is the reference string, you can think of it as data requests made by a program. Now the system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy.

```[ ] - Initially page frames are empty.i.e. no
process pages in main memory.

[ 4 ] - Now 4 is brought into 1st frame (1st
page fault)```

Explanation: Process page 4 was requested by the program, but it was not in the main memory(in form of page frames),which resulted in a page fault, after that process page 4 was brought in the main memory by the operating system.

```[ 4 7 ] - Now 7 is brought into 2nd frame
(2nd page fault) - Same explanation.

[ 4 7 6 ] - Now 6 is brought into 3rd frame
(3rd page fault)

[ 1 7 6 ] - Now 1 is brought into 1st frame, as 1st
frame was least recently used(4th page fault).```

After this 7, 6 and 1 are were already present in the frames hence no replacements in pages.

```[ 1 2 6 ] - Now 2 is brought into 2nd frame, as 2nd
frame was least recently used(5th page fault).

[ 1 2 7 ] -Now 7 is brought into 3rd frame, as 3rd frame
was least recently used(6th page fault).```

Hence, total number of page faults(also called pf) are 6. Therefore, C is the answer.

 Question 31
 A A B B C C D D

Explanation:

The Relational Algebra expression in the question above, does 4 operations, step by step ( innermost braces first ) .

```1. Select those tuples from relation r which satisfies
expression/condition F1, say the result of this
operation is set A.

2. Select those tuples from set A which satisfies
expression/condition F2, say the result of this
operation is set B.

3. Select attrributes set A2 from set B, say the
result of this operation is set C.

4. Select attrributes set A1 from set C, say the
result is set D which is the final result.```

Now to optimize this expression, we can combine operations/steps 1 and 2 by AND operator between F1 and F2 condition, like F1 ^ F2, and instead of selecting first attribute set A2, we can directly select attribute set A1 from the result of the combined operation, which is represented by expression in Option A .

 Question 32
A prime attribute of a relation scheme R is an attribute that appears
 A in all candidate keys of R. in some candidate key of R. C in a foreign key of R. only in the primary key of R.

Explanation:

The constituent attributes of a Candidate key or simply the attributes of a candidate key are called the prime attributes. Suppose ABC is one candidate key of a Relation R(ABCDEFGH). Then the attributes A, B and C all are prime attributes. Similarly if ABD is also another candidate key in the same relation R, then D is also the prime attribute. And conversely, an attribute that does not occur in ANY candidate key is called a non-prime attribute.

 Question 33
In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is
 A Network layer and Routing B Data Link Layer and Bit synchronization C Transport layer and End-to-end process communication D Medium Access Control sub-layer and Channel sharing

Explanation:

```1) Yes, Network layer does Rotuing
2) No, Bit synchronization is provided by Physical Layer
3) Yes, Transport layer provides End-to-end process
communication
4) Yes, Medium Access Control sub-layer of Data Link Layer provides
Channel sharing.```

 Question 34
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

Explanation:

Bit Stuffing is used to create framing.

```8-bit delimiter pattern is 01111110.

The output bit-string after stuffing is 01111100101.

The above highlighted bit is stuffed bit.
So input bit-string must be 0111110101.```

 Question 35

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)

Explanation:

All (i), (ii) and (iii) are changed: (i) TTL is decremented at every hop. So TTL is different from orginal value (ii) Since TTL changes, the Checksum of the packet also changes. (iii) A packet is fragmented if it has a size greater than the Maximum Transmission Unit (MTU) of the network. There may be intermediate networks that may change fragment offset by fragmenting the packet.

 Question 36

Classless Inter-domain Routing (CIDR) receives a packet with address 131.23.151.76. The router’s routing table has the following entries:

```Prefix           Output Interface Identifier
131.16.0.0/12              3
131.28.0.0/14              5
131.19.0.0/16              2
131.22.0.0/15              1```

The identifier of the output interface on which this packet will be forwarded is ______.

 A 1 B 2 C 3 D 5

Explanation:

In this question, we need to find out Netmask for each entry and BITWISE AND with given packet address, whichever equals the Netid, is the ans. Ex. 1st entry in table: 131.16.0.0/12. its MASK is first 12 bits of network(they are all 1) and remaining 20 bits of host(they are all 0). so MASK is 255.240.0.0 AND 131.23.151.76 = 131.16.0.0. Last entry is 131.22.0.0/15 MASK—>255.254.0.0 AND 131.23.151.76 = 131.22.0.0. Two ans coming interfaces 1,3. Longest Prefix Matching is used to decide among two. When one destination address matches more than one forwarding table entry. The most specific of the matching table entries is used as the interface. The interface 1 has the longest matching prefix with the input IP address. Therefore 1 is chosen.

 Question 37
Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a 50-bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?
 A 128 B 64 C 256 D 512

Explanation:

Wrap-around time is nothing but in how many seconds will all the hosts generate all IDs possible. (i.e. TOTAL_IDS / NO. OF IDS PER SEC). Total IDs possible with 50-bit is 2^50. One host generating 1000 identifiers per sec. So all hosts will generate 2^32 * 1000 —-> 2^32 * 2^10—–> 2^42 unique IDs. If we Divide them, we get answer (i.e. 2^50/2^42=2^8)

 Question 38
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
 MF bit: 0, Datagram Length: 1444; Offset: 370 B MF bit: 1, Datagram Length: 1424; Offset: 185 MF bit: 1, Datagram Length: 1500; Offset: 37 D MF bit: 0, Datagram Length: 1424; Offset: 2960

Explanation:

```Number of packet fragments = ⌈ (total size of packet)/(MTU) ⌉
= ⌈ 4404/1500 ⌉
= ⌈ 2.936 ⌉
= 3

So Datagram with data 4404 byte fragmented into 3 fragments.```

The first frame carries bytes 0 to 1479 (because MTU is 1500 bytes and HLEN is 20 byte so the total bytes in fragments is maximum 1500-20=1478). the offset for this datagram is 0/8 = 0. The second fragment carries byte 1480 to 2959. The offset for this datagram is 1480/8 = 185.finally the third fragment carries byte 2960 to 4404.the offset is 370.and for all fragments except last one the M bit is 1.so in the third bit M is 0..

 Question 39

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(Y); r2(Z); w2(Z)
T3: r3(Y); 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.

Explanation:

For conflict serializability of a schedule( which gives same effect as a serial schedule ) we should check for conflict operations, which are Read-Write, Write-Read and Write-Write between each pair of transactions, and based on those conflicts we make a precedence graph, if the graph contains a cycle, it’s not a conflict serializable schedule. To make a precedence graph: if Read(X) in Ti followed by Write(X) in Tj ( hence a conflict ), then we draw an edge from Ti to Tj ( Ti -> Tj) If we make a precedence graph for S1 and S2 , we would get directed edges for S1 as T2->T1, T2->T3, T3->T1, and for S2 as T2->T1, T2->T3, T3->T1, T1->T2. In S1 there is no cycle, but S2 has a cycle. Hence only S1 is conflict serializable. Note : The serial order for S1 is T2 -> T3 -> T1.

 Question 40

Consider the relational schema given below, where eId of the relation dependent is 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.

Explanation:

The below subquery after the subtraction sign produces id’s of those employees who have at least one dependent with age greater than or equal the employee’s age.

When the result of above subquery is subtracted from all employees, we get the employees whose age is greater than all dependents.

 Question 41
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
 A 6 B 7 C 8 D 9

Explanation:

If 6 resources are there then it may be possible that all three process have 2 resources and waiting for 1 more resource. Therefore, all of them will have to wait indefinitely. If 7 resources are there, then atleast one must have 3 resources so deadlock can never occur.

 Question 42

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):

```Process      Arrival Time    Burst Time
P1           0               12
P2           2               4
P3           3               6
P4           8               5```

The average waiting time (in milliseconds) of the processes is _________.

 A 4.5 B 5 C 5.5 D 6.5

Explanation:

```Process   Arrival Time   Burst Time
P1           0           12
P2           2           4
P3           3           6
P4           8           5```

Burst Time – The total time needed by a process from the CPU for its complete execution. Waiting Time – How much time processes spend in the ready queue waiting their turn to get on the CPU Now, The Gantt chart for the above processes is :

```P1 - 0 to 2 milliseconds

P2 - 2 to 6 milliseconds

P3 - 6 to 12 milliseconds

P4 - 12 to 17 milliseconds

P1 - 17 to 27 milliseconds```

Process p1 arrived at time 0, hence cpu started executing it. After 2 units of time P2 arrives and burst time of P2 was 4 units, and the remaining time of the process p1 was 10 units,hence cpu started executing P2, putting P1 in waiting state(Pre-emptive and Shortest remaining time first scheduling). Due to P1’s highest remaining time it was executed by the cpu in the end.

```Now calculating the waiting time of each process:
P1 -> 17 -2 = 15
P2 -> 0
P3 -> 6 - 3 = 3
P4 -> 12 - 8 = 4

Hence total waiting time of all the processes is
= 15+0+3+4=22
Total no of processes = 4
Average waiting time = 22 / 4 = 5.5

 Question 43
Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.
 A 120 B 122 C 124 D 118

Explanation:

As both page table and page are in physical memory T(eff) = hit ratio * (TLB access time + Main memory access time) + (1 – hit ratio) * (TLB access time + 2 * main memory time) = 0.6*(10+80) + (1-0.6)*(10+2*80) = 0.6 * (90) + 0.4 * (170) = 122

 Question 44

Consider the basic block given below.

```  a = b + c
c = a + d
d = b + c
e = d - b
a = e + b```

The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

 A 6 and 6 B 8 and 10 C 9 and 12 D 4 and 4

Explanation:

Simplifying the given equations :

d = b + c (given) e = d – b (given) => d = b + c and e = c

e = d – b (given) a = e + b (given) => a = d

Thus, the given DAG has 6 nodes and 6 edges.

 Question 45
Which of the following problems is undecidable?
 A Deciding if a given context-free grammar is ambiguous. B Deciding if a given string is generated by a given context-free grammar. C Deciding if the language generated by a given context-free grammar is empty. D Deciding if the language generated by a given context-free grammar is finite.

Explanation:

Context free grammar is not closed under ambiguity.A set is closed under an operation means when we operate an element of that set with that operator we get an element from that set. Here, context free grammar generates a context free language and set of all context free languages is also a set. But, ambiguity is not an operation and hence we can never say that CFG is closed under ambiguity. Thus, problem mentioned in option (A) is undecidable.

 Question 46
Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?
 A None of the languages B Only L1 C Only L1 and L2 D All the three languages

 Question 47
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is _____.
 A 50 B 100 C 150 D 200

Explanation:

T(k) is the smallest number of steps needed to move from k to 100. Now, it is given that ‘y’ and ‘z’ are two numbers such that T(9) = 1 + min (T(y), T(z)), i.e., T(9) = 1 + min (Steps from y to 100, Steps from z to 100), where ‘y’ and ‘z’ are two possible values that can be reached from 9. One number that can be reached from 9 is 10, which is the number obtained if we simply move one position right on the number line. Another number is 15, the shortcut path from 9, as given in the question. So, we have two paths from 9, one is 10 and the other is 15. Therefore, the value of y and z is 10 and 15 (either variable may take either of the values). Thus, yz = 150.

 Question 48
Consider the decision problem 2CNFSAT defined as follows:
 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.

Explanation:

2CNF-SAT can be reduced to strongly connected components problem. And strongly connected component has a polynomial time solution. Therefore 2CNF-SAT is polynomial time solvable.

 Question 49
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nalogb n + mc logd n), the value of a + 10b + 100c + 1000d is ____.
 A 60 B 110 C 210 D 50

Explanation:

```int getSum(node *root, int L, int H)
{
// Base Case
if (root == NULL)
return 0;

if (root->key < L)
return getSum(root->right, L, H);

if (root->key > H)
return getSum(root->left, L, H)

if (root->key >= L && root->key <=H)
return getSum(root->left, L, H) + root->key +
getSum(root->right, L, H);
}```

The above always takes O(m + Logn) time. Note that the code first traverses across height to find the node which lies in range.  Once such a node is found, it recurs for left and right children. Two recursive calls are made only if the node is in range. So for every node that is in range, we make at most one extra call (here extra call means calling for a node that is not in range).

 Question 50
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
 A (97 × 97 × 97)/1003 B (99 × 98 × 97)/1003 C (97 × 96 × 95)/1003 D (97 × 96 × 95)/(3! × 1003)

Explanation:

Simple Uniform hashing function is a hypothetical hashing function that evenly distributes items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. (Source: https://en.wikipedia.org/wiki/SUHA_%28computer_science%29).

```Probability that the first 3 slots are unfilled after the first 3 insertions =
(probability that first item doesn't go in any of the first 3 slots)*
(probability that second item doesn't go in any of the first 3 slots)*
(probability that third item doesn't go in any of the first 3 slots)

= (97/100) * (97/100) * (97/100)```

 Question 51

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

 `typedef` `struct` `treeNode* treeptr;` `struct` `treeNode` `{` `    ``treeptr leftMostChild, rightSibling;` `};` `int` `DoSomething (treeptr tree)` `{` `    ``int` `value=0;` `    ``if` `(tree != NULL)` `    ``{` `        ``if` `(tree->leftMostChild == NULL)` `            ``value = 1;` `        ``else` `            ``value = DoSomething(tree->leftMostChild);` `        ``value = value + DoSomething(tree->rightSibling);` `    ``}` `    ``return``(value);` `}`

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

 A number of internal nodes in the tree. B height of the tree. C number of nodes without a right sibling in the tree. D number of leaf nodes in the tree.

Explanation:

The function counts leaf nodes for a tree represented using leftMostChild-rightSibling representation. Below is function with comments added to demonstrate how function works. 1

 Question 52

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

 `int` `ProcessArray(``int` `*listA, ``int` `x, ``int` `n)` `{` `    ``int` `i, j, k;` `    ``i = 0;` `    ``j = n-1;` `    ``do` `    ``{` `        ``k = (i+j)/2;` `        ``if` `(x <= listA[k])` `            ``j = k-1;` `        ``if` `(listA[k] <= x)` `            ``i = k+1;` `    ``}` `    ``while` `(i <= j);` `    ``if` `(listA[k] == x)` `        ``return``(k);` `    ``else` `        ``return` `-1;` `}`

Which one of the following statements about the function ProcessArray is CORRECT?

 A It will run into an infinite loop when x is not in listA. B It is an implementation of binary search. C It will always find the maximum element in listA. D It will return −1 even when x is present in listA.

Explanation:

```The function is iterative implementation of Binary Search.

k keeps track of current middle element.

i and j keep track of left and right corners
of current subarray```

 Question 53
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.
 A 1.5 B 1.4 C 1.8 D 2.5

Explanation:

```Each one takes average 1CPI.

In 1st case 80% take 1 clock and 20% take 3 clocks so total time:

p = (.8*1 + .2*3)*2.2=3.08.
q = (.8*1 + 6*.2)*1=2
p/q = 1.54```

 Question 54
The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10 nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. The cache hit-ratio is 0.9. The average memory access time (in nanoseconds) in executing the sequence of instructions is __________.
 A 1.26 B 1.68 C 2.46 D 4.52

Explanation:

```The question is to find the time taken for,
"100 fetch operation and 60 operand red operations and 40 memory
operand write operations"/"total number of instructions".

Total number of instructions= 100+60+40 =200

Time taken for 100 fetch operations(fetch =read)
= 100*((0.9*1)+(0.1*5)) // 1 corresponds to time taken for read
// when there is cache hit

= 140 ns //0.9 is cache hit rate

Time taken for 60 read operations = 60*((0.9*1)+(0.1*5))
= 84ns

Time taken for 40 write operations = 40*((0.9*2)+(0.1*10))
= 112 ns

// Here 2 and 10 the time taken for write when there is cache
// hit and no cahce hit respectively

So,the total time taken for 200 operations is = 140+84+112
= 336ns

Average time taken = time taken per operation = 336/200
= 1.68 ns```

 Question 55
The above sequential circuit is built using JK flip-flops is initialized with Q2Q1Q0 = 000. The state sequence for this circuit for the next 3 clock cycle is
 A 001, 010, 011 B 111, 110, 101 C 100, 110, 111 D 100, 011, 001

Explanation:

JK ff truth table—

 j k Q 0 0 Q0 1 0 1 0 1 0 1 1 Q0’

Initially Q2Q1Q0=000 Present state FF input                   Next state

 Q2 Q1 Q0 J2 K2 J1 K1 J0 K0 Q2 Q1 Q0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1

So ans is ( C) .

 Question 56
 A I Only B II Only C Both I and II D Neither I or II

 Question 57
 A A B B C C D D

 Question 58
Let S be the sample space and two mutually exclusive events A and B be such that A U B = S. If P(.) denotes the probability of the event. The maximum value of P(A)P(B) is ______
 A 0.5 B 0.25 C 0.225 D 0.125

Explanation:

Sample Space(S) – A set of all possible outcomes/events of a random experiment. Mutually Exclusive Events – Those events which can’t occur simultaneously.   P(A)+P(B)+P(A∩B)=1   Since the events are mutually exclusive, P(A∩B)=0. Therefore, P(A)+P(B)=1   Now, we now that AM >= GM So, (P(A)+P(B))/2 >= sqrt(P(A)*P(B))   P(A)*P(B) <= 1/4
Hence max(P(A)*P(B)) = 1/4.
We can think of this problem as flipping a coin, it has two mutually exclusive events ( head and tail , as both can’t occur simultaneously). And sample space S = { head, tail }   Now, lets say event A and B are getting a “head” and “tail” respectively. Hence, S = A U B.   Therefore, P(A) = 1/2 and P(B) = 1/2.   And, P(A).P(B) = 1 /4 = 0.25.   Hence option B is the correct choice.

 Question 59

There are two elements x, y in a group (G,∗) such that every element in the group can be written as a product of some number of x’s and y’s in some order. It is known that

`  x ∗ x = y ∗ y = x ∗ y ∗ x ∗ y = y ∗ x ∗ y ∗ x = e`

where e is the identity element. The maximum number of elements in such a group is __________.

 A 2 B 3 C 4 D 5

Explanation:

```x * x = e, x is its own inverse
y * y = e, y is its own inverse

(x*y) * (x* y) = e, x*y is its own inverse

(y*x) * (y*x) = e, y*x is its own inverse
also x*x*e = e*e can be rewritten as follows

x*y*y*x = e*y*y*e = e, (Since y *y = e)

(x*y) * (y*x) = e shows that (x *y) and (y *x)
are each other’s inverse and we already know that
(x*y) and (y*x) are inverse of its own.

As per (G,*) to be group any element should have
only one inverse element (unique)

This implies x*y = y*x (is one element)

So the elements of such group are 4 which are
{x, y, e, x*y}.```

See following definition of group from wikipedia. A group is a set, G, together with an operation • (called the group law of G) that combines any two elements a and b to form another element, denoted a • b or ab. To qualify as a group, the set and operation, (G, •), must satisfy four requirements known as the group axioms:[5] Closure For all a, b in G, the result of the operation, a • b, is also in G.b[›] Associativity For all a, b and c in G, (a • b) • c = a • (b • c). Identity element There exists an element e in G, such that for every element a in G, the equation e • a = a • e = a holds. Such an element is unique (see below), and thus one speaks of the identity element. Inverse element For each a in G, there exists an element b in G such that a • b = b • a = e, where e is the identity element. Source:

 Question 60
If G is a forest with n vertices and k connected components, how many edges does G have?
 A floor(n/k) B ceil(n/k) C n-k D n-k+1

Explanation:

Each component will have n/k vertices (pigeonhole principle). Hence, for each component there will be (n/k)-1 edges. Since there are k components, total number of edges= k*((n/k)-1) = n-k.

 Question 61 Let d denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with d ≥ 3, which one of the following is TRUE?
 A In any planar embedding, the number of faces is at least n/2 + 2 B In any planar embedding, the number of faces is less than n/2 + 2 C There is a planar embedding in which the number of faces is less than n/2 + 2 D There is a planar embedding in which the number of faces is at most n/(d+1)

Explanation:

```Euler's formula for planar graphs:

v − e + f = 2.

v => Number of vertices
e => Number of edges
f => Number of faces

Since degree of every vertex is at least 3,
below is true from handshaking lemma (Sum of
degrees is twice the number of edges)

3v >= 2e
3v/2 >= e

Putting these values in Euler's formula.
v - 3v/2 + f >= 2

f >= v/2 + 2```

 Question 62

Consider the set of all functions f: {0,1, … ,2014} → {0,1, … ,2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements:

```P. For each such function it must be the case that
for every i, f(i) = i.
Q. For each such function it must be the case that
for some i, f(i) = i.
R. Each such function must be onto.```

Which one of the following is CORRECT?

 A P, Q and R are true B Only Q and R are true C Only P and Q are true D Only R is true

Explanation:

This kind of functions are called identity functions. We assume f(i) = k. So, f(k) = i. Now, since the values of ‘ i ‘ and ‘ j ‘ would be same for atleast some values if the domain and co – domain intersect, which is true for the given question, Q is definitely true. But this might not happen for all the values of ‘ i ‘, hence, P is not always true. Now, ‘ i ‘ ranges from 0 to 2014, so, it takes 2015 possible values. From the definition of a function, we know that for each input to the function, we have a unique output. Also, in the given question, domain and co – domain are exactly same. Therefore, the function is onto and hence, R is definitely true.   Thus, the correct option is B.

 Question 63
The CORRECT formula for the sentence, “not all rainy days are cold” is
 A A B B C C D D

Explanation:

(A) Note that (p ∧ ~q) ≡ ~(p -> q). So it means rainy day to cold implication is false for all days. Which means non-rainy days are cold. (B) For all days, if day is not rainy, then it is cold [Non-Rainy days are cold] (C) There exist some days for which not rainy implies cold. [Some non-rainy days are cold] (D) Note that (p ∧ ~q) ≡ ~(p -> q). So it means rainy day to cold implication is false for some days. Which means not all rainy days are cold.

 Question 64

Consider the following relational schema:

```  employee(empId, empName, empDept)
customer(custId, custName, salesRepId, rating)```

salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?

```SELECT empName
FROM employee E
WHERE NOT EXISTS (SELECT custId
FROM customer C
WHERE C.salesRepId = E.empId
AND C.rating <> ’GOOD’);```
 A Names of all the employees with at least one of their customers having a ‘GOOD’ rating. B Names of all the employees with at most one of their customers having a ‘GOOD’ rating. C Names of all the employees with none of their customers having a ‘GOOD’ rating. D Names of all the employees with all their customers having a ‘GOOD’ rating.

Explanation:

```If any employee has received rating other than 'good' from some customer,
then there will be some rows returned by the inner query.

And not exists will return false so that employee won't be printed
only those employees which have got rating good from all their
customers will be printed.```

 Question 65

Let X denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q:

`F(P, Q) = ( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )`

The equivalent expression for F is

 A P + Q B (P + Q)’ C P X Q D (P X Q)’

Explanation:

We need to simplify the above expression. As the given operation is XOR, we shall see property of XOR. Let A and B be boolean variable. In A XOR B, the result is 1 if both the bits/inputs are different, else 0. Now,

```( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )

( P' X P X Q ) X ( P X Q X Q ) ( as 1 X P = P' and Q X 0 = Q )

(1 X Q) X ( P X 0) ( as P' X P = 1 , and Q X Q = 0 )

Q' X P ( as 1 X Q = Q' and P X 0 = P )

PQ + P'Q' ( XOR Expansion, A X B = AB' + A'B )

This is the final simplified expression.

Now we need to check for the options.

If we simplify option D expression.

( P X Q )' = ( PQ' + P'Q )' ( XOR Expansion, A X B = AB' + A'B )

((PQ')'.(P'Q)') ( De Morgan's law )

( P'+ Q).(P + Q') ( De Morgan's law )

P'P + PQ + P'Q' + QQ'

PQ + P'Q' ( as PP' = 0 and QQ' = 0 )

Hence both the equations are same. Therefore Option D.

source: geeksforgeeks```