Detailed Solutions of GATE 2019: Computer Science & IT

Let's analyze each statement:

Statement I: "A pointer to the last node of a doubly linked list can be maintained in O(1) time."
This is TRUE. We can maintain a tail pointer that always points to the last node of the list. Inserting or deleting at the end operations can be done in O(1) time with this pointer.

Statement II: "Given a node in a doubly linked list, both its predecessor and successor can be accessed in O(1) time."
This is TRUE. Each node in a doubly linked list contains pointers to both the previous and next nodes. So, if we are given a pointer to a node, we can directly access both its predecessor and successor in constant time.

A Hamiltonian cycle in a graph is a cycle that visits every vertex exactly once (except the starting/ending vertex which is visited twice).

In a complete graph with n vertices, any permutation of the vertices forms a potential Hamiltonian path.

There are n! permutations of n vertices (where n! = n (n-1) (n-2) ... 2 1).

However, for a cycle:
1. Starting point doesn't matter (a cycle is the same no matter where you start). This reduces the count by a factor of n.
2. Direction doesn't matter (clockwise and anti-clockwise represent the same cycle). This further reduces the count by a factor of 2.

Therefore, the number of different Hamiltonian cycles = n!/(2n) = (n-1)!/2.

We have three processes that read, modify, and write the shared variable D:
- P1 adds 20 to D
- P2 subtracts 10 from D
- P3 adds 25 to D

Let's consider different possible execution orders:

Maximum value (Y):
For maximum value, we want as many additions as possible to happen before subtractions.
If processes execute in order P1, P3, P2:
- After P1: D = 100 + 20 = 120
- After P3: D = 120 + 25 = 145
- After P2: D = 145 - 10 = 135
So, the maximum value Y = 135.

Minimum value (X):
For minimum value, we want subtractions to happen before additions.
If processes execute in order P2, P1, P3:
- After P2: D = 100 - 10 = 90
- After P1: D = 90 + 20 = 110
- After P3: D = 110 + 25 = 135
So, the minimum value X = 135.

Y - X = 135 - 135 = 0.

SELECT * FROM students WHERE gpa > (SELECT AVG(gpa) FROM students);

SELECT AVG(gpa) FROM students WHERE gender = 'M';

SELECT COUNT(*) FROM students;

SELECT * FROM students WHERE sname LIKE '%a%';

Let's analyze each query:

Query 1: This is a nested query that selects students whose GPA is greater than the average GPA of all students. The subquery SELECT AVG(gpa) FROM students returns a single value (the average GPA), and the outer query compares each student's GPA with this average. This is a well-defined and safe query.

Query 2: This query calculates the average GPA of male students. If there are no male students, AVG(gpa) will return NULL. This is still a well-defined result, so this query is also safe.

Query 3: This query counts the total number of students in the students table. COUNT(*) always returns a numeric value (possibly 0 if the table is empty). This is a safe query with a well-defined result.

Query 4: This query selects all students whose name contains the letter 'a'. If there are no such students, it will return an empty result set, which is still well-defined. This is also a safe query.

The efficiency of CSMA/CD is given by:

Efficiency = Frame transmission time / (Frame transmission time + Contention period)

Where Contention period = 2 Propagation delay

Given:
- Frame transmission time = 20 microseconds
- Propagation delay = 2 microseconds

Contention period = 2 2 microseconds = 4 microseconds

Efficiency = 20 / (20 + 4) = 20 / 24 = 5/6 0.833 or 83.3%

This means approximately 83.3% of the bandwidth is used for actual data transmission, while the remaining 16.7% is spent on handling collisions and contention.

Let's analyze both languages:

L1 = {$a^n b^n c^m | n,m \geq 0$}

This language consists of strings where the number of a's equals the number of b's (followed by any number of c's).

We can design a pushdown automaton (PDA) for L1 as follows:
1. Read a's and push them onto the stack.
2. For each b, pop an a from the stack.
3. Read all c's (without affecting the stack).

Since we can design a PDA for L1, it is a context-free language (CFL).

L2 = {$a^n b^m c^m | n,m \geq 0$}

This language consists of strings where the number of b's equals the number of c's (with any number of a's before them).

We can design a PDA for L2 as follows:
1. Read all a's without affecting the stack.
2. Read b's and push them onto the stack.
3. For each c, pop a b from the stack.

Since we can design a PDA for L2, it is also a context-free language.

Let's check if L1 L2 is a CFL:

L1 L2 = {$a^n b^n c^n | n \geq 0$}

To accept strings in this intersection, we need to ensure that the number of a's, b's, and c's are all equal. A PDA with a single stack can only track one equality. To track two equalities (a=b and b=c), we would need two stacks, making it a context-sensitive language rather than context-free.

Let's analyze the grammar:

S A B (The start symbol generates a concatenation of A and B)
A a A | (A generates zero or more a's)
B b B | (B generates zero or more b's)

This grammar generates strings with zero or more a's followed by zero or more b's.

In other words, the language generated by this grammar is L = {$a^n b^m | n,m \geq 0$}.

So, strings like "" (empty string), "a", "aa", "b", "bb", "ab", "aab", "abb", "aabb", etc. are all generated by this grammar.

However, any string that has a b before an a would NOT be generated by this grammar. For example, "ba", "bbaa", "aba", etc. are not generated by this grammar.

An XNOR gate has the truth table:
| A | B | Output |
|---|---|--------|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

The Boolean function for XNOR is: A XNOR B = A'B' + AB = (A B)'

Let's implement this using NOR gates:

NOR gate truth table:
| A | B | NOR(A,B) | = (A + B)' |
|---|---|----------|----------|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |

Implementation:

1. Using De Morgan's law, A' = (A)' = NOR(A,A)
So, we need 2 NOR gates to get A' and B'.

2. A XNOR B = A'B' + AB
= (A+B)' + (A'+B')'
= NOR(A,B) + NOR(A',B')

So, we need 1 NOR gate for NOR(A,B) and 1 NOR gate for NOR(A',B').

3. Finally, we need 1 NOR gate to combine these two results:
(A XNOR B) = NOR(NOR(A,B), NOR(A',B'))' = NOR(NOR(NOR(A,B), NOR(A',B')), NOR(NOR(A,B), NOR(A',B')))

Adding up all the NOR gates:
- 2 for A' and B'
- 1 for NOR(A,B)
- 1 for NOR(A',B')
- 1 for the final combination

Total = 2 + 1 + 1 + 1 = 5 NOR gates

However, there's a more efficient implementation:

A XNOR B = (A B)' = (A'B + AB')'
= ((A)NOR(B) NOR NOR(A,NOR(A,B)))NOR(B,NOR(B,NOR(A,B)))

This implementation uses 5 NOR gates as well.

Let me think of another approach:

A XNOR B = ((A+B)(A'+B'))'
= (A+B)' + (A'+B')'
= NOR(A,B) + NOR(A',B')
= NOR(NOR(A,B), NOR(NOR(A,A), NOR(B,B)))

This implementation uses:
- 2 NOR gates for A' and B'
- 1 NOR gate for NOR(A,B)
- 1 NOR gate for NOR(A',B')
- 1 NOR gate for the final combination

Total = 5 NOR gates

There's an even more efficient implementation:

A XNOR B = ((A'B) (AB'))'
= ((A+B')' (A'+B)')'
= NOR(A,B') + NOR(A',B)
= NOR(NOR(A,B'), NOR(A',B))
= NOR(NOR(A,NOR(B,B)), NOR(NOR(A,A),B))

This implementation uses:
- 1 NOR gate for B'
- 1 NOR gate for A'
- 1 NOR gate for NOR(A,B')
- 1 NOR gate for NOR(A',B)
- 1 NOR gate for the final combination

Total = 5 NOR gates