GATE Practice Question

In a GATE test series on theoretical computer science, the following logical statements are presented to evaluate students’ understanding of predicate logic and integer arithmetic. Assume the domain is the set of all integers.

• Q₁: ∀a ∀b ((a < 0) ∧ (b < 0) ⇒ (a * b > 0))
• Q₂: ∀a ∃b (a + b = 0)
• Q₃: ∀a ∀b ((a < 0) ∧ (b ≥ 0) ⇒ (a * b < 0))

Question:

Which of the following statements is/are correct?

Options:

1. Q₁ and Q₂ only
2. Q₂ and Q₃ only
3. Q₁ and Q₃ only
4. Q₁, Q₂, and Q₃

Solution:

Correct Option: A (Q₁ and Q₂ only)

Explanation:

• Q₁: True. If both a and b are negative integers, their product is positive. This satisfies the given implication.
• Q₂: True. For every integer a, there exists an integer b such that their sum is zero. For example, b = -a satisfies the equation a + b = 0.
• Q₃: False. If b = 0, the product a * b is zero, which violates the condition that the product must always be negative as stated in the implication.

Final Answer: Q₁ and Q₂ only

GATE Practice Question

Scenario: In a computer network, a spanning tree is used to ensure that no cycles exist in the network graph. To analyze the network’s stability, a new edge is temporarily added between two existing vertices in the spanning tree, creating a cycle. The cyclic cardinality of a spanning tree is defined as the number of unique cycles formed when any two vertices of the tree are directly connected by an additional edge.

Consider a spanning tree T with v vertices and (v − 1) edges. Given a spanning tree with 10 vertices, what is the cyclic cardinality of this tree?

Options:

1. 10
2. 100
3. 45
4. 90

Solution:

Correct Option: C (45)

Explanation:

For a tree with v vertices, the cyclic cardinality is determined by the number of ways to select two vertices from the v vertices, as connecting any two vertices creates exactly one unique cycle. This is computed using the combination formula:

^vC₂ = (v × (v − 1)) / 2

Here, v = 10. Substituting the values:

¹⁰C₂ = (10 × (10 − 1)) / 2 = (10 × 9) / 2 = 45

Thus, the cyclic cardinality of the tree is 45.

GATE Practice Question

Scenario: A computer scientist is designing undirected graphs to represent different network topologies. The degree sequence of a graph is defined as a list of the vertex degrees arranged in non-increasing order (d₁ ≥ d₂ ≥ … ≥ d_n). A degree sequence is said to be graphical if there exists a simple undirected graph with n vertices that satisfies the sequence.

Consider the following degree sequences:

• S₁: (2^8, 2^7, 2^6, 2^5, 2^4, 2^3, 2^2, 2^1)
• S₂: (8^0, 7^0, 6^0, 5^0, 4^0, 3^0, 2^0, 1^0)

Question:

Which of the sequences given above is graphical?

Options:

1. S₁ and S₂
2. Only S₁
3. Only S₂
4. None of these

Solution:

Correct Option: C (Only S₂)

Explanation:

• S₁: This sequence is not graphical.Thus, S₁ is not graphical.
• S₂: This sequence satisfies the graphical conditions: Thus, S₂ is graphical.

Graph Validation for S₂:

An example graph that satisfies the sequence S₂:

• Vertices: A, B, C, D, E, F, G, H
• Edges:
  • A – B
  • C – D
  • E – F
  • G – H

This graph satisfies the degree sequence S₂ because each vertex has degree 1, and all conditions for a simple undirected graph are met.

GATE Practice Question

Scenario: A network administrator is analyzing a binary communication protocol where binary strings are used for encoding data. However, to prevent errors caused by consecutive high signals, no two consecutive bits in the binary strings can be 1. The administrator needs to find the recurrence relation that determines the number of valid n-bit binary strings in which no two consecutive bits are 1.

Let N(n) represent the number of valid n-bit binary strings. Which of the following correctly represents the recurrence relation for N(n)?

Options:

1. N(n) = 2N(n − 1) + N(n − 2); N(1) = 2, N(2) = 3
2. N(n) = N(n − 1) + N(n − 2); N(1) = 2, N(2) = 3
3. N(n) = (N(n − 1) + N(n − 2)) / 2; N(1) = 2, N(2) = 3
4. N(n) = N(n − 1) − N(n − 2); N(1) = 2, N(2) = 3

Solution:

Correct Option: B (N(n) = N(n − 1) + N(n − 2); N(1) = 2, N(2) = 3)

Explanation:

To determine the recurrence relation, we compute the number of valid n-bit binary strings without consecutive 1s:

• For n = 2, the possible strings are: 00, 01, and 10. Thus, N(2) = 3.
• For n = 3, the possible strings are: 000, 001, 010, 100, and 101. Thus, N(3) = 5.
• For n = 4, the possible strings are: 0000, 0001, 0010, 0100, 0101, 1000, 1001, and 1010. Thus, N(4) = 8.

From this pattern, it is clear that:

N(n) = N(n − 1) + N(n − 2)

This recurrence relation matches the Fibonacci sequence, where each term is the sum of the two preceding terms.

Final Recurrence Relation:

• N(1) = 2
• N(2) = 3
• N(n) = N(n − 1) + N(n − 2)

GATE Practice Question

Scenario: A database administrator is analyzing three datasets: A, B, and C. They need to verify the correctness of logical statements involving unions and intersections of these datasets to ensure consistency during data operations. The administrator considers the following statements:

• P₁: If A ∪ C = B ∪ C, then A = B.
• P₂: If A ∩ C = B ∩ C, then A = B.

Question:

Which of the above statements is/are true?

Options:

1. P₁ and P₂ only
2. Only P₁
3. Only P₂
4. None of these

Solution:

Correct Option: D (None of these)

Explanation:

• P₁ is false:
  • Consider a counterexample:
    • A = {1}, B = {1, 2}, C = {2, 3}
    • A ∪ C = {1, 2, 3}
    • B ∪ C = {1, 2, 3}
  • Here, A ≠ B, so P₁ is false.
• P₂ is false:
  • Consider another counterexample:
    • Let C = ∅ (empty set), A = {1}, and B = {2}.
    • A ∩ C = ∅
    • B ∩ C = ∅
  • Here, A ≠ B, so P₂ is false.

Hence, both statements are false, and the correct answer is None of these.

 

GATE Practice Question

Scenario: A project manager is analyzing the dependencies between three tasks in a software development project. The following conditions govern the tasks:

• P₁: Task A will be completed before the deadline only if Task B is started.
• P₂: Task B will not start if Task C is not assigned to a team.
• P₃: Task A was completed before the deadline.

Which of the following does not follow from P₁, P₂, and P₃?

Options:

1. Task C is assigned to a team.
2. Task B is started.
3. Task A is completed after the deadline.
4. None of these

Solution:

Correct Option: C (Task A is completed after the deadline)

Explanation:

• P₁: Task A being completed before the deadline implies Task B must have started. This is consistent with the given conditions.
• P₂: If Task C is not assigned to a team, then Task B will not start. However, since Task A is already completed before the deadline (from P₃), Task B must have started. This implies Task C was assigned to a team (to satisfy P₂).
• P₃: It is explicitly stated that Task A was completed before the deadline. Therefore, the statement “Task A is completed after the deadline” directly contradicts P₃.

Since option C contradicts the given information, it does not follow from P₁, P₂, and P₃. Hence, the correct answer is C.

GATE Practice Question

Question: Let f(x, y) = (x + y, x − y). What is f⁻¹(x, y)?

Options:

1. (x − y, x + y)
2. (x − 2y, x + 2y)
3. ((x − y)/2, (x + y)/2)
4. ((x + y)/2, (x − y)/2)

Solution:

Correct Option: D ((x + y)/2, (x − y)/2)

Explanation:

To find f⁻¹(x, y), we need to express x and y in terms of u and v, where f(x, y) = (u, v).

• From the definition of f(x, y), we have:
  • u = x + y
  • v = x − y
• We solve these equations to find x and y:
  • Add the two equations: u + v = (x + y) + (x − y) = 2x ⇒ x = (u + v)/2.
  • Subtract the two equations: u − v = (x + y) − (x − y) = 2y ⇒ y = (u − v)/2.

Thus, the inverse function is:

f⁻¹(u, v) = ((u + v)/2, (u − v)/2).

Verification:

Let’s verify this with an example:

• Let x = 1 and y = 2. Then f(1, 2) = (1 + 2, 1 − 2) = (3, −1).
• Now, applying f⁻¹(3, −1):
  • x = (3 + (−1))/2 = 2/2 = 1
  • y = (3 − (−1))/2 = 4/2 = 2
• This matches the original values of x and y.

Options A, B, and C fail to satisfy this condition. Hence, the correct answer is D ((x + y)/2, (x − y)/2).

GATE Practice Question

Question: Given below is the matrix representation (M_R) of a relation R with 4 elements: {1, 2, 3, 4} respectively.

    1 2 3 4
1 | 1 1 0 1
2 | 0 1 0 0
3 | 0 1 1 0
4 | 0 0 0 0

Which of the following correctly represents R³ in set-builder notation?

Options:

1. {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 1), (3, 3), (3, 3)}
2. {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)}
3. {(1, 1), (1, 2), (1, 4), (2, 2), (2, 4), (3, 3), (3, 3)}
4. {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 1), (3, 3), (3, 4)}

Solution:

Correct Option: B

Explanation:

The matrix M_R represents the adjacency matrix of a directed graph for relation R. Each entry M_R[i][j] is 1 if there is an edge from node i to node j, and 0 otherwise.

Step 1: Convert the matrix to a directed graph.

From the matrix, we derive the edges of the graph:

• (1, 1), (1, 2), (1, 4)
• (2, 2)
• (3, 2), (3, 3)

Step 2: Find R³.

R³ represents all pairs (a, b) such that there exists a path of length 3 from node a to node b. To compute this, we chain paths of length 3 using the adjacency matrix or by manual path construction:

• For example, (1 → 2 → 3 → 4) is part of R³.
• Similarly, paths like (1 → 1 → 1 → 1) and (1 → 2 → 2 → 4) are included.

After computation, the set representing R³ is:

{(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)}

Hence, the correct option is B.