What topics are covered on Page 4 of GATE 2016 CS/IT Set 2?

Page 4 contains Questions 40 to 52. Topics include sorting complexity, set-associative cache addressing, two’s-complement and sign-magnitude representation, ripple-carry addition, XOR identities, planar graph colouring, propositional and predicate logic, graph theory, binary relations, eigenvalues, determinants, probability and polynomial derivatives.

What happens to insertion sort when the input is already sorted?

Insertion sort runs in linear time on an already sorted input because every element is already in its proper position and only constant work is required per element.

What is the difference between the number of 16-bit two’s-complement and sign-magnitude integers?

Two’s complement represents 65536 distinct integer values while sign magnitude represents only 65535 distinct integer values because it has both positive and negative zero. The difference is 1.

How many colours are sufficient to vertex-colour any planar graph?

Four colours are sufficient to vertex-colour any planar graph according to the Four Colour Theorem.

What is the determinant of the transpose of A inverse when the eigenvalues of A are 1, 2 and 4?

The determinant of A is 1 × 2 × 4 = 8. Transposition does not change determinant, while inversion takes the reciprocal, so the determinant is 1/8.

What is the probability that a randomly selected LED bulb lasts more than 100 hours?

Because the two bulb types occur in equal numbers, the required probability is the average of 0.7 and 0.4, which is 0.55.

CS and IT Gate 2016 Set-2 Questions with Answer

1 2 3 4 5

Ques 40 Gate 2016 Set-2

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ?

I. Quicksort runs in Θ(n²) time
II. Bubblesort runs in Θ(n²) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

I and II only

I and III only

II and IV only

I and IV only

Given:
Input sequence is already sorted in ascending order.
Four statements about running times of Quicksort, Bubblesort, Mergesort, and Insertion sort.
To find:
Which of the statements are TRUE.
Solution:
Let me check each statement one by one for an already sorted input.
First, looking at statement I (Quicksort):
In standard Quicksort, the pivot is usually chosen as the first or the last element.
When the array is already sorted, this choice produces the most unbalanced partition possible, of sizes 0 and n - 1.
So the recurrence relation becomes:
T(n) = T(n - 1) + Θ(n)
Solving this recurrence gives:
T(n) = Θ(n²)
So statement I is TRUE.
Now, checking statement II (Bubblesort):
An optimized Bubblesort uses a flag to detect if any swap occurred during a pass.
Since the array is already sorted, no swaps occur in the very first pass of n - 1 comparisons, and the algorithm terminates immediately.
So the running time is Θ(n), not Θ(n²).
Thus, statement II is FALSE.
Next, checking statement III (Mergesort):
Mergesort always divides the list into two equal halves irrespective of the input order.
Its recurrence relation is always:
T(n) = 2T(n/2) + Θ(n)
Solving this always yields Θ(n log n) time in all cases.
So statement III is FALSE.
Finally, checking statement IV (Insertion sort):
For an already sorted array, each element is compared only once with its predecessor and no shifts are needed.
So the inner loop runs in O(1) time for every element.
The total number of comparisons is simply n - 1, which gives a running time of Θ(n).
So statement IV is TRUE.
Therefore, statements I and IV are TRUE.
Answer:
(D) I and IV only

Ques 41 Gate 2016 Set-2

The width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is ____________ bits.

(a) is the correct answer.

Ques 42 Gate 2016 Set-2

Let X be the number of distinct 16-bit integers in 2’s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then X −Y is _________

(a) is the correct answer.

Ques 43 Gate 2016 Set-2

Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2’s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is _____________

(a) is the correct answer.

Ques 44 Gate 2016 Set-2

Let, x₁⊕x₂⊕x₃⊕x₄= 0 where x₁, x₂, x₃, x₄ are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE ?

x₁x₂x₃x₄=0

x₁x₃+x₄=0

x'₁⊕x'₃=x'₂⊕x'₄

x₁+x₂+x₃+x₄=0

(L) is the correct answer.

Given:
x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0
where x₁, x₂, x₃, x₄ are Boolean variables, and ⊕ is the XOR operator.
To find:
Which of the given options must always be TRUE.
Solution:
Let me first test a simple case to eliminate wrong options.
Take x₁ = 1, x₂ = 1, x₃ = 1, and x₄ = 1.
Checking the given condition:
1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 ⊕ 0 = 0, which satisfies the given equation.
Now checking option A with these values:
x₁x₂x₃x₄ = 1 × 1 × 1 × 1 = 1 ≠ 0, so A is false.
Now checking option B:
x₁x₃ + x₄ = (1 × 1) + 1 = 1 ≠ 0, so B is false.
Now checking option D:
x₁ + x₂ + x₃ + x₄ = 1 + 1 + 1 + 1 = 1 ≠ 0, so D is also false.
This leaves option C, let me prove it algebraically.
We are given:
x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0
Since XOR is commutative and associative, I can rearrange terms:
(x₁ ⊕ x₃) ⊕ (x₂ ⊕ x₄) = 0
XORing both sides with (x₂ ⊕ x₄), we get:
x₁ ⊕ x₃ = x₂ ⊕ x₄
Now, I know that the complement of a variable can be written as x' = x ⊕ 1.
Let me substitute this into the left side of option C:
x'₁ ⊕ x'₃ = (x₁ ⊕ 1) ⊕ (x₃ ⊕ 1)
Rearranging the 1s:
x'₁ ⊕ x'₃ = x₁ ⊕ x₃ ⊕ (1 ⊕ 1) = x₁ ⊕ x₃ ⊕ 0 = x₁ ⊕ x₃
Similarly, doing the same for the right side of option C:
x'₂ ⊕ x'₄ = (x₂ ⊕ 1) ⊕ (x₄ ⊕ 1) = x₂ ⊕ x₄ ⊕ 0 = x₂ ⊕ x₄
Since x₁ ⊕ x₃ = x₂ ⊕ x₄, it follows directly that:
x'₁ ⊕ x'₃ = x'₂ ⊕ x'₄
So option C is always true.
Answer:
(C) x'₁⊕x'₃=x'₂⊕x'₄

Ques 45 Gate 2016 Set-2

The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________

(a) is the correct answer.

Ques 46 Gate 2016 Set-2

Consider the following expressions:

(i) false
(ii) Q
(iii) true
(iv) P ∨ Q
(v) ¬Q ∨ P

The number of expressions given above that are logically implied by P ∧ (P ⇒ Q) is ______________

(a) is the correct answer.

Ques 47 Gate 2016 Set-2

Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements:

I. Each compound in U S reacts with an odd number of compounds.
II. At least one compound in U S reacts with an odd number of compounds.
III. Each compound in U S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

Only I

Only II

Only III

None

(Graph Theory) is the correct answer.

PROCESSED

Ques 48 Gate 2016 Set-2

Which one of the following well-formed formulae in predicate calculus is NOT valid?

(∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x¬p(x) ∨ ∀x q(x))

(∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))

∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))

∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))

(Pridicate Calculus) is the correct answer.

PROCESSED

Ques 49 Gate 2016 Set-2

A binary relation R on N x N is defined as follows:

(a, b) R (c, d) if a <= c or b <= d.

Consider the following propositions:

P: R is reflexive
Q: R is transitive

Which one of the following statements is TRUE?

Both P and Q are true.

P is true and Q is false.

P is false and Q is true.

Both P and Q are false.

(Set Theory) is the correct answer.

Reflexivity (Proposition P):
• A relation R on a set A is reflexive if, for every element x ∈ A, x R x holds.
• In this case, the elements are ordered pairs (a, b) from N x N.
• For R to be reflexive, for any (a, b) ∈ N x N, it must be true that (a, b) R (a, b).
• According to the definition of R, (a, b) R (a, b) if a ≤ a or b ≤ b.
• We know that for any natural number 'a', the condition 'a ≤ a' is always true.
• Similarly, for any natural number 'b', the condition 'b ≤ b' is always true.
• Since 'a ≤ a' is true, the compound condition 'a ≤ a or b ≤ b' is true (because an OR statement is true if at least one of its components is true).
• Therefore, for every (a, b) ∈ N x N, (a, b) R (a, b) holds.
• Thus, R is reflexive.
• Proposition P is true.
Transitivity (Proposition Q):
• A relation R on a set A is transitive if, for all x, y, z ∈ A, whenever x R y and y R z, then x R z must also hold.
• Here, x = (a, b), y = (c, d), and z = (e, f).
• We need to check if: [(a, b) R (c, d) AND (c, d) R (e, f)] → (a, b) R (e, f).
• Let's test with a counterexample. We aim to find (a, b), (c, d), and (e, f) such that (a, b) R (c, d) is true, (c, d) R (e, f) is true, but (a, b) R (e, f) is false.
• For (a, b) R (e, f) to be false, by definition, it means NOT (a ≤ e or b ≤ f), which is equivalent to (a > e AND b > f).
• Let's choose the following pairs from N x N (assuming N includes positive integers):
    Let (a, b) = (5, 5)
    Let (c, d) = (1, 10)
    Let (e, f) = (4, 4)
• Check (a, b) R (c, d):
    (5, 5) R (1, 10) means 5 ≤ 1 (False) or 5 ≤ 10 (True).
    Since (False or True) is True, (5, 5) R (1, 10) holds.
• Check (c, d) R (e, f):
    (1, 10) R (4, 4) means 1 ≤ 4 (True) or 10 ≤ 4 (False).
    Since (True or False) is True, (1, 10) R (4, 4) holds.
• Check if (a, b) R (e, f) holds:
    (5, 5) R (4, 4) means 5 ≤ 4 (False) or 5 ≤ 4 (False).
    Since (False or False) is False, (5, 5) R (4, 4) does NOT hold.
• We have found a scenario where (a, b) R (c, d) and (c, d) R (e, f) are both true, but (a, b) R (e, f) is false. This violates the definition of transitivity.
• Therefore, R is not transitive.
• Proposition Q is false.
Conclusion:
• Proposition P (R is reflexive) is true.
• Proposition Q (R is transitive) is false.
This corresponds to option B.

Ques 50 Gate 2016 Set-2

Suppose that the eigenvalues of matrix A are 1, 2, 4. The determinant of (A⁻¹)^T is _________.

(a) is the correct answer.

Ques 51 Gate 2016 Set-2

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type 2 is 0.4. The probability that an LED bulb chosen uniformly at random lasts more than 100 hours is_________.

(a) is the correct answer.

Ques 52 Gate 2016 Set-2

Let f (x) be a polynomial and g(x) = f^^(x) be its derivative. If the degree of (f(x) + f(−x)) is 10, then the degree of (g(x) − g(−x)) is ___________ .

(a) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2016 Set-2 Questions with Answer

Question Options

Sign in to ExamPrev