GATE Technical: GATE 2014 SET-2 COMPUTER - CS questions with solutions

Q1. The dual of a Boolean function F(x1, x2,..., xn, +, ·, ') written as FD is the same expression as that of F with + and · swapped. F is said to be self-dual if F = FD. The number of self-dual functions with Boolean variables is

1. 2ⁿ
2. 2^(n-1)
3. 2^(2ⁿ)
4. 2^(2^(n-1))

Answer: 2^(2^(n-1))

Self-dual functions are those that remain unchanged when the operations of AND and OR are swapped. For n Boolean variables, there are 2^(n-1) independent pairs of inputs that can determine the function's output, leading to a total of 2^(2^(n-1)) distinct self-dual functions.

Q2. Consider the following function double f(double x) { if( abs(x*x - 3) < 0.01) return x; else return f(x/2 + 1.5/x); } Give a value q (to 2 decimals) such that f(q) will return q.

1. 1.73
2. 1.74
3. 1.75
4. 1.76

Answer: 1.73

The function is designed to find a value of x such that the square of x is approximately equal to 3, which corresponds to the square root of 3. The value 1.73 is the closest approximation to the square root of 3 (approximately 1.732), making it the correct choice.

Q3. Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

1. A queue cannot be implemented using this stack.
2. A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
3. A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
4. A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Answer: A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

With a REVERSE-capable stack you can implement a queue: ENQUEUE = REVERSE, PUSH, REVERSE (three instructions) inserts at the bottom, and DEQUEUE = POP (one instruction) removes the front. Thus option 2 is correct; ENQUEUE and DEQUEUE cannot both be single instructions, so the stored answer (idx 3) is wrong.