# GATE Computer Science Solved Session I 2016 - Part 1

Q.1 - Q.25 carry one mark each.

1.       Let p, q, r, s represent the following propositions.
p: x ϵ {8, 9, 10, 11, 12}
q: x is a composite number
r: x is a perfect square
s: x is a prime number
The integer x≥2 which satisfies ¬((p q)(¬r¬s)) is ..............
Explanation:
pq = {8,9,10,12}
¬r = {8,10,11,12}
¬s = {8,9,10,12}
¬r¬s = {8,9,10,11,12}
(pq)(¬r¬s) = {8,9,10,12}
¬((pq)(¬r¬s)) = 11
2.       Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for an ?
(A) an = an-1 + 2an-2                   (B) an = an-1 + an-2
(C) an = 2an-1 + an-2                   (D) an = 2an-1 + 2an-2
Explanation:
For n = 1, number of strings = 2 (0, 1)
For n = 2, number of strings = 3 (00, 01, 10)
For n = 3, number of strings = 5 (000, 001, 010, 100, 101)
For n = 4, number of strings = 8 (0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001) ...   This series follows Fibonacci series and the recurrence relation for it is an=an−1+an−2.
3.

Explanation:
Put x = y + 4. So, the equation becomes
It is equal to 1. (By Property of Limits on sine)
4.       A probability density function on the interval [a, 1] is given by 1/x2 and outside this interval the value of the function is zero. The value of a is .................
Explanation:
a1(1/x2) = [-1/x]a1 = -1+1/a
This is equal to 1.
So, -1+1/a = 1 => a=0.5
5.       Two eigen values of a 3 x 3 real matrix P are (2 + √-1) and 3. The determinant of P is ...............
Explanation:
For a 3×3 matrix, characteristic equation will be cubic, so we will have 3 roots.
If one eigen value is complex, the other eigen value has to be its conjugate.
So, the eigen values of the matrix will be (2 + √-1), (2 - √-1) and 3.
Determinant is the product of all eigen values.
So, (2 + √-1)* (2 - √-1)*(3) = (4-(-1))*(3) = (5)*(3) = 15.

6.       Consider the Boolean operator # with the following properties:
x#0 = x, x#1 = x’, x#x = 0 and x#x’ = 1. Then x#y is equivalent to
(A) xy’ + x’y       (B) xy’ + x’y’
(C) x’y + xy        (D) xy + x’y’
Explanation:
Here, the operator # represents XOR. So answer is A.
7.       The 16-bit 2’s complement representation of an integer is 1111 1111 1111 0101; its decimal representation is .................
Explanation:
1] 111 1111 1111 0101, first bit is sign bit.
Its 2’s complement is 1] 000 0000 0000 1011 = -11
8.       We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is ...............
9.       A processor can support a maximum memory of 4 GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of the processor is at least ............. bits.
Explanation:
Maximum memory = 4 GB = 232 Bytes.
Since 1 word = 2 bytes; total number of words=232/2=231
So to address these words we need minimum 31 bits.
10.    A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
(A) Both operations can be performed in O(1) time
(B) At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
(C) The worst case time complexity for both operations will be Ω(n)
(D) Worst case time complexity for both operations will be Ω(log n)