Recent questions tagged gatecse-2003 / GATE Overflow for GATE CSE

89 votes

12 answers

31

GATE CSE 2003 | Question: 64
Let S be a stack of size $n \geq1$. 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 ... S. The average stack-life of an element of this stack is $n(X+Y)$ $3Y+2X$ $n(X+Y)-X$ $Y+2X$

Let S be a stack of size $n \geq1$. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform $n$ pop operations. Assume th...

Kathleen

31.4k views

Kathleen asked Sep 17, 2014

65 votes

4 answers

32

GATE CSE 2003 | Question: 63, ISRO2009-25
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. Deletion of the smallest element Insertion of an ... used but not a heap Both balanced binary search tree and heap can be used Neither balanced search tree nor heap can be used

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...

Kathleen

20.4k views

Kathleen asked Sep 17, 2014

66 votes

12 answers

33

GATE CSE 2003 | Question: 61
In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$? $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{4}$ $\frac{n(n+1)}{4}$ $2n[\log_2n]$

In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i a_j$.If all permutations are equally likel...

Kathleen

22.1k views

Kathleen asked Sep 17, 2014

42 votes

5 answers

34

GATE CSE 2003 | Question: 60, ISRO2007-45
A program consists of two modules executed sequentially. Let $f_1(t)$ and $f_2(t)$ ... $\int_0^t f_1(x)f_2(t-x)dx$ $\max\{f_1(t),f_2(t)\}$

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 ...

Kathleen

9.2k views

Kathleen asked Sep 17, 2014

32 votes

4 answers

35

GATE CSE 2003 | Question: 59
Consider the syntax directed definition shown below. ... $t_1 = Y+Z; X=t_1$ $t_1 =Y; t_2=t_1 +Z; X=t_2$ $t_1 =Y; t_2=Z; t_3=t_1+t_2; X=t_3$

Consider the syntax directed definition shown below.$$\begin{array}{ll}S \rightarrow \mathbf{ id :=} E&\qquad \{gen(\mathbf{ id}.place = E.place;);\}\\E \rightarrow E_1 +...

Kathleen

8.6k views

Kathleen asked Sep 17, 2014

39 votes

4 answers

36

GATE CSE 2003 | Question: 58
Consider the translation scheme shown below. $S \rightarrow T\;R$ $R \rightarrow + T \{\text{print}( +');\} R\mid \varepsilon$ $T \rightarrow$ num $\{\text{print}$(num.val)$;\}$ Here num is a token that represents an integer and num.val represents the corresponding integer value. For an ... scheme will print $9 + 5 + 2$ $9 \ 5 + 2 +$ $9 \ 5 \ 2 + +$ $+ + 9 \ 5 \ 2$

Consider the translation scheme shown below.$S \rightarrow T\;R$$R \rightarrow + T \{\text{print}(‘+’);\} R\mid \varepsilon$$T \rightarrow$ num $\{\text{print}$(num....

Kathleen

12.9k views

Kathleen asked Sep 17, 2014

40 votes

3 answers

37

GATE CSE 2003 | Question: 57
Consider the grammar shown below. $S \rightarrow C \ C$ $C \rightarrow c \ C \mid d$ This grammar is LL(1) SLR(1) but not LL(1) LALR(1) but not SLR(1) LR(I) but not LALR(1)

Consider the grammar shown below. $S \rightarrow C \ C$$C \rightarrow c \ C \mid d$This grammar isLL(1)SLR(1) but not LL(1)LALR(1) but not SLR(1)LR(I) but not LALR(1)

Kathleen

20.3k views

Kathleen asked Sep 17, 2014

34 votes

3 answers

38

GATE CSE 2003 | Question: 56
Consider the grammar shown below $S \rightarrow i E t S S' \mid a$ $S' \rightarrow e S \mid \epsilon$ $E \rightarrow b$ In the predictive parse table, $M,$ of this grammar, the entries $M[S' , e]$ and $M[S' , \$]$ respectively are $\{S' \ ... $\{S' \rightarrow \epsilon\}$ $\{S' \rightarrow e S, S' \rightarrow \varepsilon$} and $\{S' \rightarrow \epsilon\}$

Consider the grammar shown below$S \rightarrow i E t S S’ \mid a$$S’ \rightarrow e S \mid \epsilon$$E \rightarrow b$In the predictive parse table, $M,$ of this gramma...

Kathleen

13.5k views

Kathleen asked Sep 17, 2014

45 votes

5 answers

39

GATE CSE 2003 | Question: 55
Consider the NFA $M$ shown below. Let the language accepted by $M$ be $L$. Let $L_1$ be the language accepted by the NFA $M_1$ 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 ... statements is true? $L_1 = \{0,1\}^*-L$ $L_1 = \{0,1\}^*$ $L_1 \subseteq L$ $L_1 = L$

Consider the NFA $M$ shown below.Let the language accepted by $M$ be $L$. Let $L_1$ be the language accepted by the NFA $M_1$ obtained by changing the accepting state of ...

Kathleen

14.5k views

Kathleen asked Sep 17, 2014

41 votes

5 answers

40

GATE CSE 2003 | Question: 53
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 ... halt on any string in $(00+1)^*$ $M$ halts on all strings ending in a $0$ $M$ halts on all strings ending in a $1$

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 $\...

Kathleen

12.0k views

Kathleen asked Sep 17, 2014

64 votes

4 answers

41

GATE CSE 2003 | Question: 51
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ is not ambiguous There ... $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$

Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$Which of the following...

Kathleen

17.7k views

Kathleen asked Sep 17, 2014

61 votes

7 answers

42

GATE CSE 2003 | Question: 50
Consider the following deterministic finite state automaton $M$. 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$ $5$ $7$ $8$

Consider the following deterministic finite state automaton $M$.Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $...

Kathleen

15.1k views

Kathleen asked Sep 17, 2014

35 votes

3 answers

43

GATE CSE 2003 | Question: 48
Consider the following assembly language program for a hypothetical processor $A, B,$ and $C$ are $8-$ ... the program execution will be the number of $0$ bits in $A_0$ the number of $1$ bits in $A_0$ $A_0$ $8$

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 com...

Kathleen

15.3k views

Kathleen asked Sep 17, 2014

53 votes

5 answers

44

GATE CSE 2003 | Question: 46
Consider the ALU shown below. 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 $C_0$ only (+ and - denote addition and subtraction respectively)? $A + B$, and $A - B$, but not $A + 1$ ... $A + B$, but not $A - B$ or $A + 1$ $A + B$, and $A - B$, and $A + 1$

Consider the ALU shown below. If the operands are in $2’s$ complement representation, which of the following operations can be performed by suitably setting the control...

Kathleen

16.9k views

Kathleen asked Sep 17, 2014

54 votes

6 answers

45

GATE CSE 2003 | Question: 45
The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)$ is $4.$ What are the minimum possible literal counts of the product-of-sum and sum-of-product ... ? Here, $X$ denotes "don't care" $(11, 9)$ $(9, 13)$ $(9, 10)$ $(11,11)$

The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)...

Kathleen

16.1k views

Kathleen asked Sep 17, 2014

54 votes

5 answers

46

GATE CSE 2003 | Question: 44
A $\text{1-input}$, $\text{2-output}$ synchronous sequential circuit behaves as follows: Let $z_k, n_k$ denote the number of $0's$ and $1's$ respectively in initial $k$ bits of the input $(z_k+n_k=k)$. The circuit outputs $00$ until one of the ... is $01$. What is the minimum number of states required in the state transition graph of the above circuit? $5$ $6$ $7$ $8$

A $\text{1-input}$, $\text{2-output}$ synchronous sequential circuit behaves as follows:Let $z_k, n_k$ denote the number of $0’s$ and $1’s$ respectively in initial $k...

Kathleen

12.0k views

Kathleen asked Sep 17, 2014

65 votes

9 answers

47

GATE CSE 2003 | Question: 43
The following is a scheme for floating point number representation using $16$ bits. Let $s, e,$ and $m$ ... between two successive real numbers representable in this system? $2^{-40}$ $2^{-9}$ $2^{22}$ $2^{31}$

The following is a scheme for floating point number representation using $16$ bits.Let $s, e,$ and $m$ be the numbers represented in binary in the sign, exponent, and man...

Kathleen

18.2k views

Kathleen asked Sep 17, 2014

0 votes

0 answers

48

GATE CSE 2003 | Question: 42
A piecewise linear function $f(x)$ is plotted using thick solid lines in the figure below (the plot is drawn to scale). If we use the Newton-Raphson method to find the roots of $f(x)=0$ using $x_0, x_1,$ and $x_2$ respectively as initial guesses, the ... .6 respectively 0.6, 0.6, and 1.3 respectively 1.3, 1.3, and 0.6 respectively 1.3, 0.6, and 1.3 respectively

A piecewise linear function $f(x)$ is plotted using thick solid lines in the figure below (the plot is drawn to scale).If we use the Newton-Raphson method to find the roo...

Kathleen

1.5k views

Kathleen asked Sep 17, 2014

34 votes

4 answers

49

GATE CSE 2003 | Question: 41
Consider the following system of linear equations ... linearly dependent. For how many values of $\alpha$, does this system of equations have infinitely many solutions? $0$ $1$ $2$ $3$

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...

Kathleen

12.3k views

Kathleen asked Sep 17, 2014

65 votes

9 answers

50

GATE CSE 2003 | Question: 40
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be $3$ $4$ $5$ $6$

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

Kathleen

15.8k views

Kathleen asked Sep 17, 2014

47 votes

6 answers

51

GATE CSE 2003 | Question: 39
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)$ ... numbers is the encoding, $h$, of a non-empty sequence of strings? $2^73^75^7$ $2^83^85^8$ $2^93^95^9$ $2^{10}3^{10}5^{10}$

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 t...

Kathleen

7.6k views

Kathleen asked Sep 17, 2014

42 votes

10 answers

52

GATE CSE 2003 | Question: 38
Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows: ... $(x, y)$ that satisfy the equations) is $0$ $1$ $2$ $3$

Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows:$$\begin{array}{|c|c|c|c|} \hline \textbf{+} & \textbf{a}& \textbf{b} &\textbf{c...

Kathleen

7.2k views

Kathleen asked Sep 17, 2014

62 votes

6 answers

53

GATE CSE 2003 | Question: 37
Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as: $g(C) = \left \{f(x) \mid x \in C\right\} $, for all subsets $C$ of $A$. Define $h : 2^B \to 2^A$ as: $h(D) = \{x \mid x \in A, f(x) \in D\}$, for all ... always true? $g(h(D)) \subseteq D$ $g(h(D)) \supseteq D$ $g(h(D)) \cap D = \phi$ $g(h(D)) \cap (B - D) \ne \phi$

Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as:$g(C) = \left \{f(x) \mid x \in C\right\} $, for all subsets $C$ of $A$.Define ...

Kathleen

8.3k views

Kathleen asked Sep 16, 2014

61 votes

10 answers

54

GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$

Kathleen

50.6k views

Kathleen asked Sep 16, 2014

52 votes

7 answers

55

GATE CSE 2003 | Question: 35
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 $\frac{m}{6}\left(21m-39\right)+4$ $\frac{m}{6}\left(4m^2-3m+5\right)$ $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$ $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$

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$\frac{m}{6}\left(21...

Kathleen

13.9k views

Kathleen asked Sep 16, 2014

23 votes

9 answers

56

GATE CSE 2003 | Question: 34
$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$ ... $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$

$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 place...

Kathleen

11.3k views

Kathleen asked Sep 16, 2014

115 votes

6 answers

57

GATE CSE 2003 | Question: 33
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: ... I_1\) does not Neither $I_1$ nor $I_2$ satisfies $\alpha$ Both $I_1$ and $I_2$ satisfies $\alpha$

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...

Kathleen

16.1k views

Kathleen asked Sep 16, 2014

59 votes

7 answers

58

GATE CSE 2003 | Question: 32
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) $((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$ $(∀x)[α] ⇒ (∃x)[α ∧ β]$ $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$ $(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$

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)$((∀x)[α] ⇒ (∀x...

Kathleen

17.0k views

Kathleen asked Sep 16, 2014

58 votes

6 answers

59

GATE CSE 2003 | Question: 31
Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) $\implies$ P(y) for all $x, y \in S$ satisfying $x \leq y$ ... for all x $\in$ S such that b ≤ x and x ≠ c P(x) = False for all x $\in$ S such that a ≤ x and b ≤ x

Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(...

Kathleen

11.9k views

Kathleen asked Sep 16, 2014

42 votes

4 answers

60

GATE CSE 2003 | Question: 30
Consider the following SQL query Select distinct $a_1, a_2, , a_n$ from $r_1, r_2, , r_m$ ... $\Pi_{a_1, a_2, a_n} \sigma_p \left(r_1 \cap r_2 \cap \dots \cap r_m \right)$

Consider the following SQL querySelect distinct $a_1, a_2, …, a_n$from $r_1, r_2, …, r_m$where PFor an arbitrary predicate P, this query is equivalent to which of the...

Kathleen

9.1k views

Kathleen asked Sep 16, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true