Alien head

Computer Science (GATE Exam) 2003 - Previous Question Paper Solution

Description: GATE Exam Previous Year Question Paper Solution Computer Science(CS) - 2003
Number of Questions: 90
Created by:
Tags: Computer Science GATE CS Previous Year Paper
Attempted 0/90 Correct 0 Score 0

Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?

  1. 2

  2. 30

  3. 56

  4. 256


Correct Option: D

n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

  1. $^{2n}\mathrm{C}_n\times 2^n$

  2. $3^n$

  3. $\frac{(2n)!}{2^n}$

  4. $^{2n}\mathrm{C}_n$


Correct Option: A

Let $P(E)$ denote the probability of the event $E$. Given $P(A) = 1$, $P(B) = 1/2$, the values of $P(A\mid B)$ and $P(B\mid A)$ respectively are

  1. 1/4,1/2

  2. 1/2,1/4

  3. 1/2,1

  4. 1,1/2


Correct Option: D
Explanation:

$ P(A/B) = \dfrac{P(A)P(B/A)}{ \sum P(A)P(B/A)} $
So, value of P(A/B) = P(A) = 1
P(B/A) = P(B) = 1/2

Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between

  1. k and n

  2. k - 1 and k + 1

  3. k - 1 and n - 1

  4. k + 1 and n - k


Correct Option: D

Assuming all numbers are in 2's complement representation, which of the following numbers is divisible by 11111011?

  1. 11100111

  2. 11100100

  3. 11010111

  4. 11011011


Correct Option: A
Explanation:

We can't judge the no's in 2's complement first we need to convert them in decimal
Given no. $ 11111011 \rightarrow 00000101 = 5 $

$ 11100111 \rightarrow 00011001 = 25 $
$ 11100100 \rightarrow 00011100 = 28 $

$ 11010111 \rightarrow 00101001 = 41 $
$ 11011011 \rightarrow 00100101 = 37 $

From all only option (1) is divisible by 5.
Shortcut: To convert 2's complement no. directly into original binary,
we should complement all the digits from MSB till the last one (1).
Keep the last 1 from the LSB as it is. Observe the example.

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

  1. Removing left recursion alone

  2. Factoring the grammar alone

  3. Removing left recursion and factoring the grammar

  4. None of the above


Correct Option: C
Explanation:

If a grammar has left recursion & left factoring then it is ambiguous. So to convert a CFG to LL(1) grammar both removal of left recursion & left factoring need to be done.

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

  1. always be evaluated

  2. be evaluated only if the definition is L-attributed

  3. be evaluated only if the definition has synthesized attributes

  4. never be evaluated


Correct Option: C
Explanation:

Every S (synthesized) -attributed definitions is L- attributed. So in a bottom-up evaluation of SDD inherited attributes can be evaluated only if the definition has synthesized attributes.

Consider the set $ \sum^* $ of all strings over the alphabet $ \sum $ = {0, 1}. $ \sum^* $ with the concatenation operator for strings

  1. does not form a group

  2. forms a non-commutative group

  3. does not have a right identity element

  4. forms a group if the empty string is removed from $\sum^*$


Correct Option: D
Explanation:

Let p denote the set of all non -empty strings of letters from M
Where, M = { $\alpha , \beta , \gamma $ }
We have P = { $\alpha , \beta , \gamma ,\alpha ,\alpha ,\alpha ,\pi ,\alpha ,\gamma ,........\alpha ,\alpha ,\alpha ,\alpha ,\alpha ,\beta ....$ }

Assume that the SLR parser for a grammar G has n1 states and the LALR parser for that grammar has n2 states. Which of the following statements about the relationship between n1 and n2 is true?

  1. n1 is necessarily less than n2.

  2. n1 is necessarily equal to n2.

  3. n1 is necessarily greater than n2.

  4. none of these


Correct Option: B
Explanation:

SLR parse has less range of context free languages than LALR, but still both n1 and n2 are the same for SLR and LALR, respectively.

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

  1. O(n log n)

  2. O(n)

  3. O(log n)

  4. O(1)


Correct Option: C
Explanation:

Here we can follow simple procedure, we can rum heap sort for 7 iterations. In each iteration the top most
element is smallest, we note & then replace it with the last element, then we run min heapify algorithm,
which brings next smallest element on top. This procedure
take 0 (log n) time.
We need to run it for 7 times. So tight bound O(7 log n) = O(log n)

Which of the following statements is FALSE?

  1. In statically typed languages, each variable in a program has a fixed type

  2. In un-typed languages, values do not have any types

  3. In dynamically typed languages, variables have no types

  4. In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program


Correct Option: C
Explanation:

(1) True for statically typed languages where each variable has fixed type. Similarly (4) is also correct.
(2) True, in un-typed languages types of values are not defined. But option (3) is false, since in dynamically
typed language variables have dynamically changing types but not that they have no type.

Consider the following three claims
I. (n + k)m = O (nm) where k and m are constants
II. 2n+1 = O(2n)
III. 22n+1 = O(2n)

Which of these claims are correct?

  1. I and II

  2. I and III

  3. II and III

  4. I, II, and III


Correct Option: A
Explanation:

(1) $(n + k)^m$ if we exapnd it.
It is $(n^m + .....)$
During tight bound $\theta (n^m)$ correct
(2) $ 2^{n+1} = 2.2^n \Rightarrow O(2.2^n) \Rightarrow O(2^n) \quad correct $

$ 2^{2n+1} = 2.2^2n \Rightarrow O(2.2^2n) $
$ O(2^{2^n}) \neq O(2^n) \quad incorrect $

In a system with 32 bit virtual addresses and 1KB page size, use of one-level page tables for virtual to physical address translation is not practical because of

  1. the large amount of internal fragmentation

  2. the large amount of external fragmentation

  3. the large memory overhead in maintaining page tables

  4. the large computation overhead in the translation process


Correct Option: C
Explanation:

32 bit virtual address, i.e. $2^{32}$ kB of virtual memory & 1 kB page size.
So total pages = $2^{32}$
So. we need to maintain a page table of $2^{32}$ rows, this require 4 GB main memory which is quite impractical due to large memory overhead

Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?

  1. Recovery from packet losses

  2. Detection of duplicate packets

  3. Packet delivery in the correct order

  4. End to end connectivity


Correct Option: D
Explanation:

Transport protocols are mainly for providing end to end connections by making sockets.
Recovery from packet loss & delivery in correct order, duplication is checked by Data link layer.

How many perfect matching are there in a complete graph of 6 vertices?

  1. 15

  2. 24

  3. 30

  4. 60


Correct Option: A
Explanation:

For complete graph of 6 vertices number of perfect matching
$ = \dfrac{n(n-1)}{2} = \dfrac{6 \times 5}{2} = 15$

Consider the following formula and its two interpretations $I_1$ and $I_2$.

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

$I_1$ : Domain: the set of natural numbers

$P_x$ = 'x is a prime number'
$Q_{xy}$ = 'y divides x'
$I_2$ : same as $I_1$ except that $P_x$ = 'x is a composite number'.

Which of the following statements is true?

  1. I1 satisfies$\alpha$, I2 does not

  2. I2 satisfies $\alpha$, I1 does not

  3. Neither I2 nor I1 satisfies $\alpha$

  4. Both I1 and 12 satisfy $\alpha$


Correct Option: A
Explanation:

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$
I1: domain the set of natural numbers
Px = x is a prime number = 2, 3, 5, 7, 11, 13…
Qxy = y divides x = means y is also prime number = 2,3,5,7,11,13,
I2: px = x is composite number (i.e not prime number)
= 4,6,8,9,10,12,14,…..
Qxy = 2,3,4,5,7,……. = mean all the numbers from expression, we know
I1 satisfies $\alpha$,I2 does not

The usual O(n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

  1. remain O (n2)

  2. become O (n (log n)2)

  3. become O (n log n)

  4. become O (n)


Correct Option: C
Explanation:

Binary search is efficient when the sorted sequence is there, but the worst case scenario for insertion sort would not be sorted sequence so even using binary search instead of linear search the complexity of comparisons will remain O (n2)

Using a larger block size in a fixed block size file system leads to

  1. better disk throughput but poorer disk space utilization

  2. better disk throughput and better disk space utilization

  3. poorer disk throughput but better disk space utilization

  4. poorer disk throughput and poorer disk space utilization


Correct Option: A
Explanation:

Using larger block size in a fixed block size system lead to poor disk space utilization due to data items which are very small comparable to block size cause fragmentation. But it leads to better disk through put since no. of blocks needs to fetch & replace become less.

Which of the following is a valid first order formula? (Here $\alpha$and $\beta$ are first order formulae with x as their only free variable)

  1. ((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]

  2. (∀x)[α] ⇒ (∃x)[α ∧ β]

  3. ((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]

  4. (∀x)[α ⇒ β] ⇒ ((∀x)[α]) ⇒ (∀x)[β])


Correct Option: D
Explanation:

We know that,
If the four tense operators P,F,H and G and following axioms
G (Q $\rightarrow$R) $\rightarrow$(GQ $\rightarrow$GR)
H (Q $\rightarrow$R) $\rightarrow$(HQ $\rightarrow$HR)
G - HQ $\rightarrow$Q

  • H - GQ $\rightarrow$Q

$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ balls?

  1. $ \left( \begin{array}{c} m - k \ n - 1 \end{array} \right)$

  2. $\left( \begin{array}{c} m - kn + n - 1 \ n - 1 \end{array} \right)$

  3. $\left( \begin{array}{c} m - 1 \ n - k \end{array} \right)$

  4. $\left( \begin{array}{c} m - kn + n + k - 2 \ n - k \end{array} \right)$


Correct Option: B
Explanation:

Let n = 3 and k = 1
m = 3
According to question, n is number of distinct bags.
Number of balls = 3
Then number of ways balls be placed in 1 ways then, number of ways = 3 x 2 = 6 = <n ways if k = 2
Number of balls = nk = 6
We have chosen at least k balls
Number of ways = one ways

Consider the following graph


Among the following sequences
I a b e g h f II a b f e h g III a b f h g e IV a f g h b e

Which are depth first traversals of the above graph?

  1. I, II and IV only

  2. I and IV only

  3. II, III and IV only

  4. I, III and IV only


Correct Option: D
Explanation:


Let (S,$\le$) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S
{True, False} be a predicate defined on S. Suppose that
P(a) = True, P(b) = False and P(x)$\Rightarrow$P(y) for all x, y $\epsilon$S satisfying x$\le$y,

Where $\Rightarrow$stands for logical implication. Which of the following statements CANNOT be true?

  1. P(x) = True for all x $\epsilon$S such that x $\ne$b

  2. P(x) = False for all x $\epsilon$S such that x $\ne$a and x $\ne$c

  3. P(x) = False for all x $\epsilon$S such that b $\le$x and x $\ne$c

  4. P(x) = False for all x $\epsilon$S such that a $\le$x and b $\le$x


Correct Option: C
Explanation:

rder=0>P(y)
If P(x) then P(y) and a, y $\epsilon$S, satisfies x $\le$ y
So, -P (a) = True, p(b) = false
$\Rightarrow$False $\cup$False
$\Rightarrow$False
So, P(x) = False for all x $\epsilon$S, such that b $\le$ x and x $\ne$c.

A graph $G=(V,E)$ satisfies $|E| \leq 3 |V| - 6$. The min-degree of $G$ is defined as $ min_{v\in V} \left \{ degree(V) \right \}$. Therefore, min-degree of $G$ cannot be

  1. 3

  2. 4

  3. 5

  4. 6


Correct Option: C
Explanation:

Given |E| $\le$ 3 |V| -6
We know from graph,
Number of edges = $\dfrac{n(n-1)}{2}$
(1) V = 3,                      E = 3
                        |3| $\le$ 9 - 6 $\rightarrow$ True
(2) V = 4,                      E = 6
                        |6| $\le$ 12 - 6 $\rightarrow$ True
(3) V = 5,                      E = 10
                        |10| $\le$ 15 - 6 $\rightarrow$ notTrue
(4) V = 6,                      E = 15
                        |15| < |18| - 6 $\rightarrow$ not True
So, minimum degree of G cannot be 5

A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale).

Diagram 1

If we use the Newton-Raphson method to find the roots of f(x) =0 using x0, x1, and x2 respectively as initial guesses, the roots obtained would be

  1. 1.3, 0.6, and 0.6 respectively

  2. 0.6, 0.6, and 1.3 respectively

  3. 1.3, 1.3, and 0.6 respectively

  4. 1.3, 0.6, and 1.3 respectively


Correct Option: B

Which of the following assertions is FALSE about the Internet Protocol (IP)?

  1. It is possible for a computer to have multiple IP addresses

  2. IP packets from the same source to the same destination can take different routes in the network

  3. IP ensures that a packet is discarded if it is unable to reach its destination within a given number of hops

  4. The packet source cannot set the route of an outgoing packets; the route is determined only by the routing tables in the routers on the way


Correct Option: D
Explanation:

Internet protocol ensures that a packet is forwarded if it is unable to reach its destination within a given no. of hops. One computer can have multiple IP addresses also packets having same source & destination can take different routes. Source doesn't decide where to route the packet, but it is decided by the routing tables at intermediate routers.

Let f : A $\rightarrow$ B be an injective (one-to-one) function. Define g : 2A $\rightarrow$ 2B as:
g(C) = {f(x) | x $\epsilon$ C}, for all subsets C of A.
Define h : 2B$\rightarrow$2A as: h(D) = {x | x $\epsilon$ A, f(x) $\epsilon$ D}, for all subsets D of B.

Which of the following statements is always true?

  1. g(h(D)) $\subseteq $ D

  2. g(h(D)) $\supseteq $ D

  3. g(h(D)) $\cap$ D = $\phi$

  4. g(h(D)) $\cap$ (B—D) $\ne$$\phi$


Correct Option: A
Explanation:

F: A $\rightarrow$B be an injective (one- to - one) function
A $\rightarrow$B means
A $\supseteq $B
Define g: 2A $\rightarrow$2B as: g (C) = {f(x) | x $\epsilon$ C}, for all subset C of A.
g(C) $\subseteq $B
Define : n : 2B $\rightarrow$ 2A as:
h(D) = { x | x $\epsilon$A, f(x) $\epsilon$D}, for all subsets D of B
2B $\subseteq $2A
h(D) $\subseteq $ 2A
2(h(D)) $\subseteq $C

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows:

$g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$.

Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$.

For a non-empty string $s=a_1 \dots a_n$, where each $a_i \in \Sigma$, define $f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$.

For a non-empty sequence$\left \langle s_j, \dots,s_n\right \rangle$ of stings from $\Sigma^+$, define $h\left(\left \langle s_i \dots s_n\right \rangle\right)=\Pi^n_{i=1}P_i^{f\left(s_i\right)}$

Which of the following numbers is the encoding, $h$, of a non-empty sequence of strings?

  1. 273757

  2. 283858

  3. 293959

  4. 210510710


Correct Option: B
Explanation:

Let $\sum$= { a,b,c,d,e }
g(a) = 3, g(b) = 5, g(c) =7, g(d) = 9, g(e) = 11
p1 = 2 (1st prime number
$f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$.
= 23 = 8

he sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz') is 4. What are the minimum possible literal counts of the product-of-sum and sum-of product representations respectively of the function given by the following Karnaugh map? Here, X denotes “don't care”

  1. (11, 9)

  2. (9, 13)

  3. (9, 10)

  4. (11, 11)


Correct Option: A
Explanation:

Consider the following circuit composed of XOR gates and non-inverting buffers

GATE 2003

The non-inverting buffers have delays d1 = 2 ns and d2 = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time

  1. If the following waveform is applied at input A, how many transition(s) (change of logic levels) Occur (s) at B during the interval from 0 to 10 ns?

GATE 2003 Image 2

  1. 1

  2. 2

  3. 3

  4. 4


Correct Option: C
Explanation:

Due to delays s1= 2 & s2=4 the transistions would occur at time1, 2 & 4.

Time Input (A) Output (B)
0 1 0
I 1 1 0 Transition
II 2 1 0 Transition
III 4 0 1 Transition

So total 3 transistions

Consider the grammar shown below.
S $\rightarrow$ C C
C $\rightarrow$ c C | d
This grammar is

  1. LL(1)

  2. SLR(1) but not LL(1)

  3. LALR(1) but not SLR(1)

  4. LR(l) but not LALR(1)


Correct Option: C
Explanation:

Given grammar
$$ S \rightarrow CC $$
$$C \rightarrow cC|d$$
it can't be LL since $C \rightarrow cC$ is recursive. LR(1) also known as CLR parse, and every CF grammar is CLR grammar.
So (A) is false but (C) & (D) can be ccorrect.
This grammar is CLR and also reducible to LALR without any conflicts. So (D) if false.
Only need to check for SLR(1) or LR(0)
This grammar is not SLR

Consider the following system of linear equations $$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \right) \left( \begin{array}{ccc} x \\ y \\ z \end{array} \right) = \left( \begin{array}{ccc} \alpha \\ 5 \\ 7 \end{array} \right)$$ Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of $\alpha$, does this system of equations have infinitely many solutions?

  1. 0

  2. 1

  3. 2

  4. infinitely many


Correct Option: B
Explanation:

$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \right) \left( \begin{array}{ccc} x \\ y \\ z \end{array} \right) = \left( \begin{array}{ccc} \alpha \\ 5 \\ 7 \end{array} \right)$
We can write for this linear equation
2x + y - 4z = a
            4x + 3y - 12z = 5
x + 2y - 8z = 7
For infinitely solutions, D = 0
$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \right) = 0$
Because, 2nd and 3rd columns are linearly dependent
For x
D = $\left( \begin{array}{ccc} \alpha & 1 & -4 \\ 5 & 3 & -12 \\ 7 & 2 & -8 \end{array} \right) = 0$
Because, 2nd and 3rd columns are linearly dependent
For y
$\left( \begin{array}{ccc} 2 & \alpha & -4 \\ 4 & 5 & -12 \\ 1 & 7 & -8 \end{array} \right) = 0$
$\Rightarrow$2(- 40 + 84) -$\alpha$(- 32 + 12) - 4 ( 28 -5) = 0
$\Rightarrow$ 88 + 20$\alpha$-92 = 0
$\Rightarrow$$\alpha = \dfrac{4}{20} = \dfrac{1}{5}$ --- (i)
For z
D = $\left( \begin{array}{ccc} 2 & 1 & \alpha \\ 4 & 3 & 5 \\ 1 & 2 & 7 \end{array} \right) = 0$

$\Rightarrow$2 (21-10) - 1 ( 28 - 5) +$\alpha$ (8 - 3) = 0
$\Rightarrow$ 22 - 23 + 5 $\alpha$ = 0
$\Rightarrow$ $\alpha = \dfrac{1}{5}$--(ii)
Hence from equation, we find that, $\alpha$ have only one value for infinitely solution.

Consider the translation scheme shown below.
S $\rightarrow$T R
R $\rightarrow$ + T {print('+');} R|$\epsilon$
T $\rightarrow$ num {print (num.val);}
Here num is a token that represents an integer and num.val represents the corresponding integer value.
For an input string '9 + 5 + 2', this translation scheme will print

  1. 9 + 5 + 2

  2. 9 5 + 2 +

  3. 9 5 2 + +

    • + 9 5 2

Correct Option: D
Explanation:

$
S \rightarrow TR \\
R \rightarrow +\ T \{ print('+');\}R | \epsilon \\
T \rightarrow num\ \{print(num.val);\}) \\
Given\ string\ 9\ + 5\ + 2 \\
S \rightarrow TR \\
$

T + TR {print(+);}
T + T + T {print(+);}
9 + T + T {print(9);}
9 + 5 + T {print(5);}
9 + 5 + 2 {print(2);}

So ++952 is printed

In a permutation a1 ... an, of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj.

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1. . . n?

  1. $\frac{n(n-1)}{2}$

  2. $\frac{n(n-1)}{4}$

  3. $\frac{n(n+1)}{4}$

  4. $2n[\log_2n]$


Correct Option: B
Explanation:

Let $a_1....a_n$ be 1.....3 here n =3 consider all permutation 123, 132, 231,213, 312, 321.
Let us consider 312 here the inversions are {(3,1), (3,2)}
So in a randomly chosen permutation we need to select two no. following inversion property on an average
$no.\ of\ inverstions\ \dfrac{1}{2}\ nC_2$
$$ = \dfrac{1}{2} \dfrac{n!}{2!(n-2)!} \Rightarrow \dfrac{1}{2}\dfrac{n(n-1)}{2}$$
$$ = \dfrac{n(n-1)}{4}$$

if $n=3 \Rightarrow \dfrac{3(3-1)}{4} = [1.5] \cong 2$

Solving this question taking a random example would be much easier

Consider the syntax directed definition shown below,
S $\rightarrow$ id : = E {gen (id.place = E.place;);}
E $\rightarrow$ E1 + E2 {t = newtemp( );
gen(t = E1.place + E2.place;);
E.place = t;}
E $\rightarrow$ id {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of
a new temporary variable on every call.
Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X : = Y + Z',
the 3-address code sequence generated by this definition is

  1. X = Y + Z

  2. t1 = Y + Z; X = t1

  3. t1 = Y; t2 = t1 + Z; X = t2

  4. t1 = Y; t2 = Z; t3 = t1 + t2; X = t3


Correct Option: D
Explanation:

In 3-address code we use temporary variables to reduce complex instructions so here
$$
t_1 = Y \\
t_2 = Z \\
t_3 = t_1 + t_2 \\
x = t_3 \\
$$

Consider the grammar shown below
S $\rightarrow$i E t S S' | a
S' $\rightarrow$ e S |$\epsilon$
E $\rightarrow$ b
In the predictive parse table, M, of this grammar, the entries M[S' , e] and
M[ S' ,$] respectively area

  1. {S' $\rightarrow$ e S} and{ S'$\rightarrow$$\epsilon$}

  2. { S' $\rightarrow$e S}and { }

  3. {S'$\rightarrow$ $\epsilon$} and { S'$\rightarrow$$\epsilon$}

  4. { S' $\rightarrow$e S, S'$\rightarrow$$\epsilon$} and { S'$\rightarrow$ $\epsilon$}


Correct Option: D
Explanation:

A program consists of two modules executed sequentially. Let $f_1(t)$ and $f_2(t)$ respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by

  1. $f_1(t)+f_2(t)$

  2. $\int_0^t f_1(x)f_2(x)dx$

  3. $\int_0^t f_1(x)f_2(t-x)dx$

  4. $\max{f_1(t),f_2(t)}$


Correct Option: C
Explanation:

Probability density function of f1 (t) and f2 (t) is
= $\int_0^t f_1(x)f_2(t-x)$

Consider the following logic program P

$\begin{align*} A(x) &\gets B(x,y), C(y) \ &\gets B(x,x) \end{align*}$

Which of the following first order sentences is equivalent to P?

  1. $(\forall x) [(\exists y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land \neg (\exists x)[B(x,x)]$

  2. $(\forall x) [(\forall y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land \neg (\exists x)[B(x,x)]$

  3. $(\forall x) [(\exists y) [B(x,y) \land C(y)] \Rightarrow A(x)] \vee \neg (\exists x)[B(x,x)]$

  4. $(\forall x) [(\forall y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land (\exists x)[B(x,x)]$


Correct Option: C

The following program fragment is written in a programming language that allows global
variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

  1. 115, 220

  2. 25, 220

  3. 25, 15

  4. 115, 105


Correct Option: D
Explanation:

In static scoping the variables are initialized at compile time only
So i =100 & j =5
P(i + j) = P(100 + 5) = P(105)

So x =105
x + 10 = 105 + 10 = 115
So 115 and 105 will be printed

In a permutation a1 ... an, of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj.

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1. . . n with at most n inversions?

  1. O(n2)

  2. O (n log n)

  3. O (n1.5)

  4. O (n)


Correct Option: B
Explanation:

The following program fragment is written in a programming language that allows global
variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are

  1. 115, 220

  2. 25, 220

  3. 25, 15

  4. 115, 105


Correct Option: B
Explanation:

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_k+1) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex appears more than once.

Let $A$ be an $n \times n$ array initialized as follows.

$$A[j,k] = \begin{cases} 1 \text { if } (j,k) \in E \\ 0 \text{ otherwise} \end{cases}$$

Consider the following algorithm.

for i=1 to n
    for j=1 to n
        for k=1 to n
            A[j,k] = max(A[j,k], A[j,i] + A[i,k]);  

Which of the following statements is necessarily true for all j and k after termination of the above algorithm?

  1. A[j,k] $\le$ n

  2. If A[j,j] $\ge$ n - 1, then G has a Hamiltonian cycle

  3. If there exists a path from j to k, A[j,k] contains the longest path length from j to k

  4. If there exists a path from j to k, every simple path from j to k contains at most A[j,k} edges


Correct Option: B
Explanation:

What is the weight of a minimum spanning tree of the following graph?

GATE 2003 Paper

  1. 29

  2. 31

  3. 38

  4. 41


Correct Option: B
Explanation:


$\text{Sum}\ 1+2+3+2+8+4+2+4+5=31$

Let G = (V,E) be an undirected graph with a subgraph G1 = (V1, E1). Weights are assigned to edges of G
as follows.

$$G= \begin{cases} 0 \text { if } e \in E_1 \\ 1 \text{ otherwise} \end{cases}$$

A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex
v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?

  1. The number of edges in the shortest paths from v1 to all vertices of G

  2. G1 is connected

  3. V1 forms a clique in G

  4. G1 is a tree


Correct Option: B
Explanation:


Consider the set {a, b, c} with binary operators + and × defined as follows

+ a b c
a b a c
b a b c
c a c b
* a b c
a a b c
b b c a
c c c b

For example, a + c = c, c + a = a, c ×b = c and b × c = a. Given the following set of equations:
(a × x) + (a × y) = c
(b × x) + (c × y) = c

The number of solution(s) (i.e., pair(s) (x, y) that satisfy the equations) is

  1. 0

  2. 1

  3. 2

  4. 3


Correct Option: D
Explanation:
+ a b c
a b a c
b a b c
c a c b
* a b c
a a b c
b b c a
c c c b

We can write from given expression
a + a = b,         a + b = a,         a + c = c
b + a = a,         b + b = b,         b + c = c
c + a = a           c + b = c           c + c = b

a x a = a,          a x b = b,          a x c = c
b x a = b,          b x b = c,          b x c = a
c x a = c,          c x b = c,          c x c = b
a x x + a x y = c                        --- (1)
b x x + c x y = c             --- (2)
First we see, these are the equation which give result c.
a + c = c
b + c = c
c + b = c
For equation (A), we find a x x = b  x = b
We find
a x x = a then x = a, a x y = c, y = c, x = a,b,c 
a x y = c then y = c, a x x = c, x = c, x = c, y = a,b
a x y = b, y = b
for equation (B), we find
b x x = b, c x y = c, b x x = a then x = c
x = a, y = a, b    c x y = c then y = a, b
b x x = c then    x = b    we find
c x y = b then    y = c    x = a,b,c
y = a,b,c
so, total number of solution pairs (x,y) is 3.

A uni-processor computer system only has two processes, both of which alternate 10 ms CPU bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?

  1. First come first served scheduling

  2. Shortest remaining time first scheduling

  3. Static priority scheduling with different priorities for the two processes

  4. Round robin scheduling with a time quantum of 5 ms


Correct Option: A
Explanation:

There should be no doubt that round robin scheduling would lead to maximum CPU utilization, but since in FCFS one task would starve for a long time so min CPU utilization would be in this case.

The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in
chronological order: “as bs cs ae ds ce es fs be de gs ee fe hs ge he”. Here, xs denotes the starting time and xe
denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us.
An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration.
What is the minimum number of rooms required?

  1. 3

  2. 4

  3. 5

  4. 6


Correct Option: B
Explanation:

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

  1. Smaller sizes of executable files

  2. Lesser overall page fault rate in the system

  3. Faster program startup

  4. Existing programs need not be re-linked to take advantage of newer versions of libraries


Correct Option: C
Explanation:

The advantages of shared dynamically linked libraries include.
(1) smaller size of executable since less data
(2) lesser overall page fault rate.
(3) No need for re-linking if newer versions of libraries are there. But since compilation time doesn't include
linking so a long linking time required during runtime in DLL' s so slow startup.

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page.Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.

Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)

  1. 1.5 ns

  2. 2 ns

  3. 3 ns

  4. 4 ns


Correct Option: D
Explanation:

A 2 km long broadcast LAN has 107 bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2 x 108 m/s. What is the minimum packet size that can be used on this network?

  1. 50 bytes

  2. 100 bytes

  3. 200 bytes

  4. None of the above


Correct Option: C
Explanation:

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page.Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.

Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address 0×00400000, and a stack page starting at virtual address 0×FFFFF000. The amount of memory required for storing the page tables of this process is

  1. 8 KB

  2. 12 KB

  3. 16 KB

  4. 20 KB


Correct Option: C
Explanation:

Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 micro second. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 micro second. What is the maximum achievable throughput in this communication?

  1. 7.69 × 106 bps

  2. 11.11 × 106 bps

  3. 12.33 × 106 bps

  4. 15.00 x 106 bps


Correct Option: B
Explanation:

Data packet size = 1000 byte       
Number of packets = 5       
Total data = 5000       
Transmission time = 50 micro second/packet       
Propagation delay = 200 micro second       
So for 5 packets = 50 * 5 = 250 micro second       
Total time for 5 packets = 250 + 200 = 450 micro second       
Rate = Data/time = 5000*1000000/450 = 11.11*1000000 bps

The following resolution rule is used in logic programming.
Derive clause (P$\lor$Q) from clauses (P $\lor$ R), (Q$\lor$$\neg$R)
Which of the following statements related to this rule is FALSE?

  1. ((P $\lor$ R) $\land$ (Q $\lor$ $\neg$R)) _ (P $\lor$ Q) is logically valid

  2. (P $\lor$ Q) $\Rightarrow$ ((P $\lor$ R) $\land$ (Q $\lor$ $\neg$R)) is logically valid

  3. (P $\lor$ Q) is satisfiable if and only if (P $\lor$ R) Ù (Q $\lor$ $\neg$R) is satisfiable

  4. (P $\lor$ Q) $\Rightarrow$ FALSE if and only if both P and Q are unsatisfiable


Correct Option: B
Explanation:

If P = True, Q = false, R =True
Then we find,
(T$\cup$F) $\Rightarrow$((T$\cup$T)$\lor$ (F$\cup$F)
T $\Rightarrow$((T$\lor$F)
T $\Rightarrow$F
F$\cup$F = False(is not valid)

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The codes for the processes P and Q are shown below.
Process P: Process Q:
while (1) { while (1) {
W: Y:
print '0'; print '1';
print '0'; print '1';
X: Z:
} }
Synchronization statements can be inserted only at points W, X, Y and Z

Which of the following will always lead to an output starting with '001100110011'?

  1. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1

  2. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0

  3. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1

  4. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0


Correct Option: B
Explanation:

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The codes for the processes P and Q are shown below.
Process P: Process Q:
while (1) { while (1) {
W: Y:
print '0'; print '1';
print '0'; print '1';
X: Z:
} }
Synchronization statements can be inserted only at points W, X, Y, and Z

Which of the following will ensure that the output string never contains a substring of the form 01n0 or 10n1 where n is odd?

  1. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1

  2. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1

  3. P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1

  4. V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1


Correct Option: C
Explanation:

The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?

  1. 172.57.88.62 and 172.56.87.233

  2. 10.35.28.2 and 10.35.29.4

  3. 191.203.31.87 and 191.234.31.88

  4. 128.8.129.43 and 128.8.161.55


Correct Option: D
Explanation:


Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P { Class Q subclass of P {
void f(int i) { void f(int i) {
print(i); print(2*i);
} }
} }
Now consider the following program fragment:
Px = new Q()
Qy = new Q();
Pz = new Q();
x.f(1); ((P)y).f(1); z.f(1);
Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment
will be

  1. 1 2 1

  2. 2 1 1

  3. 2 1 2

  4. 2 2 2


Correct Option: D
Explanation:

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

  1. O (1)

  2. O (log n)

  3. O (n)

  4. O (n2)


Correct Option: C
Explanation:

The no. of gates used in n bit array multiplier (n x n) is 2n - 1. So. if every single gate takes unit delay, then total delay 0 (2n -1) = 0 (n) It is of linear order

For a pipelined CPU with a single ALU, consider the following situations
I. The j + 1-st instruction uses the result of the j-th instruction as an operand
II. The execution of a conditional jump instruction
III. The j-th and j + 1-st instructions require the ALU at the same time

Which of the above can cause a hazard?

  1. I and II only

  2. II and III only

  3. III only

  4. All the three


Correct Option: D
Explanation:

Case 1 is here of data dependency, this can't be safe with single ALU so read after write.
Case 2 Conditional jumps are always hazardous they create conditional dependency in pipeline
Case 3 this is write after read problem or concurrency dependency so hazardous
All the three are hazardous.

Consider the ALU shown below

GATE 2003 Paper
If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and - denote addition and subtraction respectively)?

  1. A + B, and A - B, but not A + 1

  2. A + B, and A + 1, but not A - B

  3. A + B, but not A - B or A + 1

  4. A + B, and A - B, and A + 1


Correct Option: D
Explanation:

Consider the following assembly language program for a hypothetical processor
A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.
MOV B, #0 ; B $\leftarrow$ 0
MOV C, #8 ; C $\leftarrow$ 8
Z: CMP C, #0 ; Compare C with 0
JZX ; Jump to X if zero flag is set
SUB C, #1 ; C $\leftarrow$ C - 1
RRC A, #1 ; right rotate A through carry by one bit. Thus:
; if the initial values of A and the carry flag are a7… a0 and
; instruction will be c0a7…a1 and a0 respectively
JCY ; jump to Y if carry flag is set
JMP Z ; jump to Z
Y: ADD B, #1 ; B $\leftarrow$ B + 1
X: If the initial value of register A is A0, the value of register B after the program execution will be

  1. the number of 0 bits in A0

  2. the number of 1 bits in A0

  3. A0

  4. 8


Correct Option: B
Explanation:

Here value of B is incremented by 1 only if carry flag is 1, carry is filled using right rotation, so B will store the no. of 1s in A0.

Consider the following assembly language program for a hypothetical processor
A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.
MOV B, #0 ; B $\leftarrow$0
MOV C, #8 ; C$\leftarrow$8
Z: CMP C, #0 ; Compare C with 0
JZX ; Jump to X if zero flag is set
SUB C, #1 ; C $\leftarrow$ C -1
RRC A, #1 ; right rotate A through carry by one bit. Thus:
; if the initial values of A and the carry flag are a7… a0 and
; instruction will be c0a7…a1 and a0 respectively
JCY ; jump to Y if carry flag is set
JMP Z ; jump to Z
Y: ADD B, #1 ; B $\leftarrow$ B + 1
X:

Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value?

  1. RRC A, #1

  2. NOP ; no operation

  3. LRC A, #1 ; left rotate A through carry flag by one bit

  4. ADD A, #1


Correct Option: A
Explanation:

In the end of program execution to check whether both initial and final value of register A is A0, we need to right rotate register A through carry by one bit.

Consider the following C function.
float f,(float x, int y) {
float p, s; int i;
for (s=1,p=1,i=1; i

  1. Xy

  2. ex

  3. In (1+x)

  4. Xx


Correct Option: B
Explanation:

The function f() is implementation of Taylor’s Series to calculates ex
ex = 1 + x + x2/2! + x3/3! + ---
More is the value of y more precise value of ex will be returned by f()
  

Assume the following C variable declaration

int * A[10], B[10][10]; of the following expressions

I. A[2]

II. A[2][3]

III. B[1] IV. B[2][3]

Which will not give compile-time errors if used as left hand sides of assignment statements in a C program?

  1. I,II, and IV only

  2. II, III, and IV only

  3. II and IV only

  4. IV only


Correct Option: A
Explanation:
int main(){
    int *A[10], B[10][10];
    int c[] = {12, 11, 13, 14};

   A[2] = C;

   A[2][3] = 15;

   B[2][3] = 15;

   printf("%d %d', A[2][0], A[2][3]);
   getchar();
}

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

  1. 7 5 1 0 3 2 4 6 8 9

  2. 0 2 4 3 1 6 5 9 8 7

  3. 0 1 2 3 4 5 6 7 8 9

  4. 9 8 6 4 2 3 0 1 5 7


Correct Option: C
Explanation:


Let T(n) be the number of different binary search trees on n distinct elements.
Then T(n) = $\sum_{k -1}^n T(k -1)(x) $, where x is

  1. n - k + 1

  2. n - k

  3. n - k - 1

  4. n - k - 2


Correct Option: A
Explanation:

Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting G in the above tree?

  1. None of the above


Correct Option: C
Explanation:


A data structure is required for storing a set of integers such that each of the following operations can be done in O (log n) time, where n is the number of elements in the set.
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?

  1. A heap can be used but not a balanced binary search tree

  2. A balanced binary search tree can be used but not a heap

  3. Both balanced binary search tree and heap can be used

  4. Neither balanced binary search tree nor heap can be used


Correct Option: B
Explanation:

Both the tasks can be performed by both the data structures but heap is a data structure where to perform
these function every element has to be checked so  O (n) complexity. But the balance binary search tree is
efficient data structure since at every decision it selects one of its sub tree to no. of elements to be checked
are reduced by a factor of / 1 2 every time.
$\dfrac{n}{2!} = x$
x = log n

Let S be a stack of size n $\ge$1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m $\ge$1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

  1. n(X + Y)

  2. 3Y + 2X

  3. n(X + Y) - X

  4. Y + 2X


Correct Option: D
Explanation:

Consider the C program shown below.
#include <stdio.h>
#define print(x) print f(”%d “, x)
int x;
void Q(int z) {
z + = x; print (z);
}
void P(int *y) {
int x = *y+2;
Q(x); *y = x-1;
Print (x);
}
Main (void) {
x = 5;
P (&x)
Print (x);
}
The output of this program is

  1. 12 7 6

  2. 22 12 11

  3. 14 6 6

  4. 7 6 6


Correct Option: A
Explanation:

Consider the function f defined below.
struct item {
int data;
struct item * next;
};
int f(struct item *p) {
return ((p == NULL) || (p ->next == NULL) ||
((p->data <= p -> next -> data) &&
f(p-> next)));
}
For a given linked list p, the function f returns 1 if and only if

  1. the list is empty or has exactly one element

  2. the elements in the list are sorted in non-decreasing order of data value

  3. the elements in the list are sorted in non-increasing order of data value

  4. not all elements in the list have the same data value


Correct Option: B
Explanation:

In the following C program fragment, j, k, n and TwoLog_n are integer variables, and A is an array of
integers. The variable n is initialized to an integer $\ge$3, and TwoLog_n is initialized to the value of 2
*$\lceil log_2(n) \rceil$

for (k = 3; k < = n; k++)
A [k] = 0;
for (k = 2; k < = TwoLog_n ; k++)
for (j = k+1; j < = n ; j++)
A[j] = A[j] || (j% k);
for (j = 3; j < = n ; j++)
if (!A[j]) print f(”%d ”,j);
The set of numbers printed by this program fragment is

  1. {mm $\ge$ n, ($\ge$i)[m=i!] }

  2. {mm $\ge$ n, ($\exists $i)[m=i2]}

  3. {mm $\le $ n, m is prime}

  4. { }


Correct Option: B
Explanation:

 

Consider three data items D1, D2 and D3, and the following execution schedule of transactions T1, T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing in the data item D respectively.

Which of the following statements is correct?

  1. The schedule is serialisable as T2; T3; T1.

  2. The schedule is serialisable as T2; T1; T3.

  3. The schedule is serialisable as T3; T2; T1.

  4. The schedule is not serialisable.


Correct Option: D
Explanation:

Consider the following SQL query.
select distinct a1, a2, ..., an
from r1, r2, ..., rm
where P

For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?

  1. $\Pi_{a_1, a_2, … a_n} \sigma_p \left(r_1 \times r_2 \times \dots \times r_m\right)$

  2. $\Pi_{a_1, a_2, … a_n} \sigma_p \left(r_1 \bowtie r_2 \bowtie \dots \bowtie r_m \right)$

  3. $\Pi_{a_1, a_2, … a_n} \sigma_p \left(r_1 \cup r_2 \cup \dots \cup r_m \right)$

  4. $\Pi_{a_1, a_2, … a_n} \sigma_p \left(r_1 \cap r_2 \cap \dots \cap r_m \right)$


Correct Option: A
Explanation:

Consider the set of relations shown below and the SQL query that follows.
Students: (Roll_number, Name, Date_of_birth)
Courses: (Course number, Course_name, Instructor)
Grades: (Roll_number, Course_number, Grade)
select distinct Name
from Students, Courses, Grades
where Students. Roll_number = Grades.Roll_number
and Courses.Instructor = Korth
and Courses.Course_number = Grades.Course_number
and Grades.grade = A
Which of the following sets is computed by the above query?

  1. Names of students who have got an A grade in all the courses taught by Korth.

  2. Names of students who have got an A grade in all the courses.

  3. Names of students who have got an A grade in at least one of the courses taught by Korth.

  4. None of the above


Correct Option: C
Explanation:

Names are unique since they are selected distinct, so one person will be selected only once, even when he has got grade A in any number of courses taught by Korth. So, if a name is appearing it is not necessary that he scored grade A in all the courses, but scored grade A in at least one course.

Which of the following scenarios may leave the transaction vulnerable to dirty reads, phantom reads, etc. in a database system?

  1. A transaction writes a data item after it is read by an uncommitted transaction.

  2. A transaction reads a data item after it is read by an uncommitted transaction.

  3. A transaction reads a data item after it is written by a committed transaction.

  4. A transaction reads a data item after it is written by an uncommitted transaction.


Correct Option: D
Explanation:

 This may leave the transactions vulnerable to dirty reads, phantom reads, etc. in the database system.

Consider the following functional dependencies in a database.

Date_of_Birth $\rightarrow$ Age Age $\rightarrow$ Eligibility
Name $\rightarrow$ Roll_number Roll_number $\rightarrow$ Name
Course_number $\rightarrow$ Course_name Course_number $\rightarrow$ Instructor
(Roll_number, Course_number) $\rightarrow$ Grade

The relation (Roll_number, Name, Date_of_Birth, Age) is

  1. in second normal form but not in third normal form

  2. in third normal form but not in BCNF

  3. in BCNF

  4. None of the above


Correct Option: D
Explanation:

The regular expression 0*(10*)* denotes the same set as

  1. (1*0)1

  2. 0+(0+10)*

  3. (0+1)10(0+1)

  4. None of these


Correct Option: D
Explanation:

0* (10*)* = 0* = (1* 0*)
(1) (1* 0)* 1* = (1* 0*) 1*
(2) 0 + (0 +10)* = 0 + (0*1*0*)
(3) (0 + 1)* 10 (0 + 1)* = 0* 1* 10 (0* 1*)

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

  1. L is necessarily finite

  2. L is regular but not necessarily finite

  3. L is context free but not necessarily regular

  4. L is recursive but not necessarily context free


Correct Option: B
Explanation:

Since L can be effectively enumerated so L has to be regular, but is doesn't mean that the decisions are finite.

Nobody knows yet if P = NP. Consider the language L defined as follows.

$$L = \begin{cases} (0 +1)^* \text { if } (P = NP) \in E \\ \phi \text{ otherwise} \end{cases}$$

Which of the following statements is true?

  1. L is recursive

  2. L is recursively enumerable but not recursive

  3. L is not recursively enumerable

  4. Whether L is recursive or not will be known after we find out if P = NP


Correct Option: A
Explanation:

A language L is said to be recursive if there exists any rule to determine whether an element belong to language or not, if language can be accepted by turning machine. So there exist the rules so L is recursive.

Consider the following deterministic finite state automaton M.

GATE 2003
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

  1. 1

  2. 5

  3. 7

  4. 8


Correct Option: C
Explanation:

Ram and Shyam have been asked to show that a certain problem $\prod$is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to$\prod$, and Shyam shows a polynomial time reduction from $\prod$to 3-SAT. Which of the following can be inferred from these reductions?

  1. $\prod$ is NP-hard but not NP-complete

  2. $\prod$ is in NP, but is not NP-complete

  3. $\prod$is NP-complete

  4. $\prod$is neither NP-hard, nor in NP


Correct Option: C
Explanation:

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0,1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

0 1 B
q0 q1, 1, R q1, 1, R Halt
q1 q1, 1, R q0, 1, L q0, B, L

The table is interpreted as illustrated below.
The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape
square, then it writes 1 on the same tape square, moves its tape head one position to the right and
transitions to state q1.

Which of the following statements is true about M?

  1. M does not halt on any string in (0+1)+

  2. M does not halt on any string in (00+1)*

  3. M halts on all strings ending in a 0

  4. M halts on all strings ending in a 1


Correct Option: A
Explanation:

Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S $\rightarrow$ a S b | S S | $\epsilon$
Which of the following statements is true?

  1. G is not ambiguous

  2. There exist x, y $\epsilon$ L(G) such that xy $\require{cancel} \cancel{\epsilon}$ L(G)

  3. There is a deterministic pushdown automaton that accepts L(G)

  4. We can find a deterministic finite state automaton that accepts L(G)


Correct Option: C
Explanation:

(1) Incorrect since the production has same non terminal in both sides, so definitely ambiguous.
(2) Since S $\rightarrow$ SS " this leads to conjunction of every possible string to make a valid string in L(G) .
(3) Context free languages are accepted by push down automata so true.
(4) The language is not regular so DFA is not possible.

Consider the NFA M shown below.

Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1 obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting states of M to accepting states. Which of the following statements is true?

  1. L1 = {0,1}* - L

  2. L1 = {0,1}*

  3. L1$\subseteq $ L

  4. L1 = L


Correct Option: A
Explanation:

Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$.

Let $f: \Sigma \to \Sigma$ be a polynomial time, computable bijection, such that:

$$\forall x: \Bigl(x \in L_1 \iff f(x) \in L_2\Bigr )$$

Further, let $f^{-1}$ also be polynomial time computable.

Which of the following canNOT be true?

  1. L1 $\epsilon$ P and L2 is finite

  2. L1 $\epsilon$ NP and L2 $\epsilon$ P

  3. L1 is un decidable and L2 is decidable

  4. L1 is recursively enumerable and L2 is recursive


Correct Option: C
Explanation:

Define languages L0 and L1 as follows:
L0 = {<M, w, 0> | M halts on w}
L1 = {<M, w, 1> | M does not halt on w}
Here <M, w, i> is a triplet, whose first component, M, is an encoding of a Turing
Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L0$\cup$L1. Which of the following is true?

  1. L is recursively enumerable, but $\bar L$ is not

  2. $\bar L$ is recursively enumerable, but L is not

  3. Both L and $\bar L$ are recursive

  4. Neither L nor $\bar L$ is recursively enumerable


Correct Option: B
Explanation:


The following is a scheme for floating point number representation using 16 bits.

Bit Position 15 14 .... 9 8 ...... 0
s e m
Sign Exponent Mantissa

Let s, e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is:

$$\begin{cases}(-1)^s \left(1+m \times 2^{-9}\right) 2^{e-31}, & \text{ if the exponent } \neq 111111 \\ 0, & \text{ otherwise} \end{cases}$$

What is the maximum difference between two successive real numbers representable in this system?

  1. 2-40

  2. 2-9

  3. 222

  4. 231


Correct Option: C
Explanation:

A 1-input, 2-output synchronous sequential circuit behaves as follows:
Let zk, nk denote the number of 0's and 1's respectively in initial k bits of the input
(zk+nk=k). The circuit outputs 00 until one of the following conditions holds.
zk - nk=2. In this case, the output at the k-th and all subsequent clock ticks is 10.
nk - zk = 2. In this case, the output at the k-th and all subsequent clock ticks is 01.

What is the minimum number of states required in the state transition graph of the above circuit?

  1. 5

  2. 6

  3. 7

  4. 8


Correct Option: C
Explanation:

The sequential circuit has 3 variables to decide the state in which input & 2 inputs are present. Output for particular inputs decide states.

i/p op 1 op 2 State
0 0 0 Initial
0 0 1 $n_k - z_k = 2$
0 1 0 $z_k - n_k = 2$
1 0 0 Not applicable
1 0 0 Initial
1 0 1 $n_k - z_k = 2$
1 1 0 $z_k - n_k = 2$
0 0 1 $n_k - z_k = 2$
1 1 1 is correct

using 3 bits we require
$ 2^3 - 1 = 7 $ states here

The cube root of a natural number n is defined as the largest natural number m such that m3 $\le$n. The complexity of computing the cube root of n (n is represented in binary notation) is

  1. O(n) but not O(n0.5)

  2. O(n0.5) but not O((log n)k) for any constant k > 0

  3. O((log n)k) for some constant k > 0, but not O((log log n)m) for any constant m > 0

  4. O((log log n)k) for some constant k > 0.5, but not O((log log n)0.5)


Correct Option: C
Explanation:


Consider the following recurrence relation

$T(1)=1$

$T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$

The value of $T(m^2)$ for $m \geq 1$ is

  1. $\frac{m}{6}\left(21m-39\right)+4$

  2. $\frac{m}{6}\left(4m^2-3m+5\right)$

  3. $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$

  4. $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$


Correct Option: B
Explanation:

T (1) = 1
T(n+1) = T(n) + $\lfloor \sqrt(n+1) \rfloor $ for all n$\ge$1
If n = m2 - 1
T(m2) = T(m2 - 1) + $\lfloor m \rfloor $
T(2) = T(1) + $\lfloor \sqrt(2) \rfloor $ = 1 + 1= 2
T(3) = T(3) + $\lfloor \sqrt(3) \rfloor $ = 2 + 1= 3
T(4) = T(3) + 2 = 5
T(5) = 5 + 2 = 7
T(6) = 7 + 2 = 9
T(7) = 9 + 2 = 11
T(8) = 11 + 2 = 13
T(9) = 13 + 3 = 16
T(10) = 16 + 3 = 19
T(11) = 19 + 3 = 22
T(12) = 22 + 3 = 25
T(13) = 25 + 3 = 28
T(14) = 28 + 3 = 31
T(15) = 31 + 3 = 34
T(16) = 34 + 4 = 38
T(m2) = T(m2 - 1) + $\lfloor m \rfloor $
Put m = 2
T(4) = T(3) + 1 = 4
Put m = 2
T (9) = T(8) + 1 = 13 + 1 = 14
(a) $\dfrac{m}{6}$(21m - 39) + 4
Put m = 2, $\dfrac{2}{6}$(42 - 39 ) + 4 = 5
Put m = 3, $\dfrac{3}{6}$(63 - 39 ) + 4 = 16
Put m = 4, $\dfrac{4}{6}$(84 - 39) + 4 = $\dfrac{2}{4}$x 45 + 4 = 34
(b) Put m = 2, $\dfrac{m}{6}$(4m2 - 3m + 5 )
= $\dfrac{2}{6}$[ 16 - 6 + 5 = 5
Put m = 3, $\dfrac{3}{6}$[4 x 9 - 3 x 3 + 5 ] = $\dfrac{1}{2}$[32] = 16
Put m = 4, $\dfrac{4}{6}$[64 - 12 + 5] = $\dfrac{2}{3}$[57] = 38
Hence, choice (b) satisfies the solution of T(m2)

+ View questions