Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Profile
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Answers by Bhagirathi
–2
votes
81
GATE IT 2008 | Question: 11
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE? If X can be solved in polynomial time, then so can Y X is NP-complete X is NP-hard X is in NP, but not necessarily NP-complete
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?If X can be solved in polynomial time, then so can YX is NP-c...
7.2k
views
answered
Nov 8, 2014
Algorithms
gateit-2008
algorithms
p-np-npc-nph
normal
out-of-syllabus-now
+
–
6
votes
82
GATE IT 2004 | Question: 55
Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that $f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$. Which one of the following statements is FALSE? $f(n) + g(n) = O(h(n) + h(n))$ $f(n) = O(h(n))$ $h(n) \neq O(f(n))$ $f(n)h(n) \neq O(g(n)h(n))$
Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that $f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$.Which one...
13.3k
views
answered
Nov 8, 2014
Algorithms
gateit-2004
algorithms
asymptotic-notation
normal
+
–
4
votes
83
GATE IT 2005 | Question: 15
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity. ... $\text{1→ B, 2 → A, 3 → C, 4 → D}$
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each ...
5.2k
views
answered
Nov 8, 2014
Algorithms
gateit-2005
algorithms
graph-algorithms
match-the-following
easy
+
–
39
votes
84
GATE IT 2005 | Question: 51
Let $T(n)$ be a function defined by the recurrence $T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and $T(1) = 1$ Which of the following statements is TRUE? $T(n) = \Theta(\log n)$ $T(n) = \Theta(\sqrt n)$ $T(n) = \Theta(n)$ $T(n) = \Theta(n \log n)$
Let $T(n)$ be a function defined by the recurrence$T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and$T(1) = 1$Which of the following statements is TRUE?$T(n) = \Theta(\log n)$...
9.5k
views
answered
Nov 8, 2014
Algorithms
gateit-2005
algorithms
recurrence-relation
easy
+
–
14
votes
85
GATE IT 2005 | Question: 52
Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE? There exists a cutset in $G$ having ... $e$ cannot be contained in a cycle. All edges in $G$ have the same weight.
Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which ...
20.9k
views
answered
Nov 8, 2014
Algorithms
gateit-2005
algorithms
minimum-spanning-tree
normal
+
–
6
votes
86
GATE IT 2006 | Question: 72
An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of $O (n)$ $O (\log n)$ $O (n \log n)$ $O (n \log \log n)$
An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy...
7.6k
views
answered
Nov 3, 2014
DS
gateit-2006
data-structures
binary-heap
easy
+
–
23
votes
87
GATE IT 2006 | Question: 73
An array $X$ of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If the root node is at level $0$, the level of element $X[i]$, $i \neq 0$, is $\left \lfloor \log _2 i \right \rfloor$ ... $\left \lfloor \log _2 (i+1) \right \rfloor$ $\left \lceil \log _2 i \right \rceil$
An array $X$ of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If the root node is at level $0$, the le...
9.2k
views
answered
Nov 3, 2014
DS
gateit-2006
data-structures
binary-tree
normal
+
–
–6
votes
88
GATE IT 2005 | Question: 38
Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state of the PDA. The stack is initialized with one $Z$ before the start of ... $L(P)$ and $N(P)$ are necessarily $Σ^*$. Neither $L(P)$ nor $N(P)$ are necessarily $Σ^*$
Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting ...
12.5k
views
answered
Nov 3, 2014
Theory of Computation
gateit-2005
theory-of-computation
pushdown-automata
normal
+
–
33
votes
89
GATE IT 2005 | Question: 40
A language $L$ satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about $L$ is TRUE? $L$ is necessarily a regular language. $L$ is necessarily a context-free language, but not necessarily a regular language. $L$ is necessarily a non-regular language. None of the above
A language $L$ satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about $L$ is TR...
15.7k
views
answered
Nov 3, 2014
Theory of Computation
gateit-2005
theory-of-computation
pumping-lemma
easy
+
–
0
votes
90
GATE CSE 1995 | Question: 2.4
What is the value of $X$ printed by the following program? program COMPUTE (input, output); var X:integer; procedure FIND (X:real); begin X:=sqrt(X); end; begin X:=2 FIND(X); writeln(X); end. $2$ $\sqrt{2}$ Run time error None of the above
What is the value of $X$ printed by the following program?program COMPUTE (input, output); var X:integer; procedure FIND (X:real); begin X:=sqrt(X); end; begin X:=2 FIND(...
7.1k
views
answered
Oct 16, 2014
Compiler Design
gate1995
compiler-design
parameter-passing
runtime-environment
easy
+
–
20
votes
91
GATE CSE 1996 | Question: 2.12
The recurrence relation $T(1) = 2$ $T(n) = 3T (\frac{n}{4}) +n$ has the solution $T(n)$ equal to $O(n)$ $O (\log n)$ $O\left(n^\frac{3}{4}\right)$ None of the above
The recurrence relation$T(1) = 2$$T(n) = 3T (\frac{n}{4}) +n$has the solution $T(n)$ equal to$O(n)$$O (\log n)$$O\left(n^\frac{3}{4}\right)$ None of the above
7.3k
views
answered
Oct 16, 2014
Algorithms
gate1996
algorithms
recurrence-relation
normal
+
–
24
votes
92
GATE CSE 1996 | Question: 1.5
Two dice are thrown simultaneously. The probability that at least one of them will have $6$ facing up is $\frac{1}{36}$ $\frac{1}{3}$ $\frac{25}{36}$ $\frac{11}{36}$
Two dice are thrown simultaneously. The probability that at least one of them will have $6$ facing up is$\frac{1}{36}$$\frac{1}{3}$$\frac{25}{36}$$\frac{11}{36}$
5.0k
views
answered
Oct 16, 2014
Probability
gate1996
probability
easy
+
–
27
votes
93
GATE CSE 1996 | Question: 2.7
The probability that top and bottom cards of a randomly shuffled deck are both aces is $\frac{4}{52} \times \frac{4}{52}$ $\frac{4}{52} \times \frac{3}{52}$ $\frac{4}{52} \times \frac{3}{51}$ $\frac{4}{52} \times \frac{4}{51}$
The probability that top and bottom cards of a randomly shuffled deck are both aces is$\frac{4}{52} \times \frac{4}{52}$$\frac{4}{52} \times \frac{3}{52}$$\frac{4}{52} \t...
5.0k
views
answered
Oct 16, 2014
Probability
gate1996
probability
easy
+
–
5
votes
94
GATE CSE 1996 | Question: 2.24
What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in Fig $B\overline{D} + \overline{B}D$ $(B + \overline{C} +D) (\overline{B} + C + \overline{D})$ $(B + {D})(\overline{B} +\overline{ D})$ $(B + \overline{D})(\overline{B} + {D})$
What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in Fig $B\overline{D} + \overline{B}D$$(B + \overline{C} +D) (\overline{B} + ...
9.2k
views
answered
Oct 16, 2014
Digital Logic
gate1996
digital-logic
k-map
easy
+
–
30
votes
95
GATE CSE 1994 | Question: 1.15
The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is $n$ $n^2$ $\frac{n(n-1)}{2}$ $\frac{n(n+1)}{2}$
The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is$n$$n^2$$\frac{n(n-1)}{2}$$\frac{n(n+1)}{2}$
10.2k
views
answered
Oct 11, 2014
Combinatory
gate1994
combinatory
counting
normal
+
–
3
votes
96
GATE CSE 1994 | Question: 25
An array $A$ contains $n$ integers in non-decreasing order, $A[1] \leq A[2] \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $i, j,$ such that $A[i]+A[j]=a$ given integer $M$, if such $i, j$ exist.
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $...
5.0k
views
answered
Oct 11, 2014
DS
gate1994
data-structures
array
normal
descriptive
+
–
33
votes
97
GATE CSE 1991 | Question: 03,vii
The following sequence of operations is performed on a stack: $PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP$ The sequence of values popped out is $20,10,20,10,20$ $20,20,10,10,20$ $10,20,20,10,20$ $20,20,10,20,10$
The following sequence of operations is performed on a stack:$PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP$The sequence of values poppe...
4.4k
views
answered
Oct 10, 2014
DS
gate1991
data-structures
stack
easy
+
–
5
votes
98
GATE CSE 2011 | Question: 34
A deck of $5$ cards (each carrying a distinct number from $1$ to $5$) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number ... $\left(\dfrac{4}{25}\right)$ $\left(\dfrac{1}{4}\right)$ $\left(\dfrac{2}{5}\right)$
A deck of $5$ cards (each carrying a distinct number from $1$ to $5$) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probabil...
18.3k
views
answered
Oct 10, 2014
Probability
gatecse-2011
probability
normal
+
–
4
votes
99
GATE CSE 1997 | Question: 1.1
The probability that it will rain today is $0.5$. The probability that it will rain tomorrow is $0.6$. The probability that it will rain either today or tomorrow is $0.7$. What is the probability that it will rain today and tomorrow? $0.3$ $0.25$ $0.35$ $0.4$
The probability that it will rain today is $0.5$. The probability that it will rain tomorrow is $0.6$. The probability that it will rain either today or tomorrow is $0.7$...
6.4k
views
answered
Oct 10, 2014
Probability
gate1997
probability
easy
+
–
–4
votes
100
GATE CSE 1994 | Question: 2.6
The probability of an event $B$ is $P_1$. The probability that events $A$ and $B$ occur together is $P_2$ while the probability that $A$ and $\bar{B}$ occur together is $P_3$. The probability of the event $A$ in terms of $P_1, P_2$ and $P_3$ is _____________
The probability of an event $B$ is $P_1$. The probability that events $A$ and $B$ occur together is $P_2$ while the probability that $A$ and $\bar{B}$ occur together is $...
4.7k
views
answered
Oct 10, 2014
Probability
gate1994
probability
normal
conditional-probability
fill-in-the-blanks
+
–
3
votes
101
GATE CSE 1994 | Question: 3.4
Match the following items (i) Newton-Raphson (a) Integration (ii) Runge-Kutta (b) Root finding (iii) Gauss-Seidel (c) Ordinary Differential Equations (iv) Simpson's Rule (d) Solution of Systems of Linear Equations
Match the following items(i) Newton-Raphson(a) Integration(ii) Runge-Kutta(b) Root finding(iii) Gauss-Seidel(c) Ordinary Differential Equations(iv) Simpson's Rule(d) Solu...
12.0k
views
answered
Oct 10, 2014
Numerical Methods
gate1994
numerical-methods
easy
out-of-gate-syllabus
+
–
39
votes
102
GATE CSE 1997 | Question: 6.5
Which one of the following is not decidable? Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps Equivalence of two given Turing machines Language accepted by a given finite state machine is not empty Language generated by a context free grammar is non-empty
Which one of the following is not decidable?Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ stepsEquivalence of two given Turing m...
10.1k
views
answered
Oct 7, 2014
Theory of Computation
gate1997
theory-of-computation
decidability
easy
+
–
89
votes
103
GATE CSE 1994 | Question: 1.11
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$, non-zero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, the index of the ... is: $i+j$ $i+j-1$ $(j-1)+\frac{i(i-1)}{2}$ $i+\frac{j(j-1)}{2}$
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$, non-zero eleme...
28.5k
views
answered
Oct 7, 2014
DS
gate1994
data-structures
array
normal
+
–
0
votes
104
FSM
Suppose we have an encoding of a fsm ... 1.is it regular? 2.does the fsm accepts its own encoding ?
Suppose we have an encoding of a fsm ... 1.is it regular? 2.does the fsm accepts its own encoding ?
671
views
answered
Sep 27, 2014
30
votes
105
GATE CSE 1998 | Question: 1.14
A multiplexer with a $4-bit$ data select input is a $4:1$ multiplexer $2:1$ multiplexer $16:1$ multiplexer $8:1$ multiplexer
A multiplexer with a $4-bit$ data select input is a$4:1$ multiplexer$2:1$ multiplexer$16:1$ multiplexer$8:1$ multiplexer
9.1k
views
answered
Sep 27, 2014
Digital Logic
gate1998
digital-logic
multiplexer
easy
+
–
29
votes
106
GATE CSE 1998 | Question: 1.22
Give the correct matching for the following pairs: ... $\text{A-R B-P C-S D-Q}$ $\text{A-P B-R C-S D-Q}$ $\text{A-P B-S C-R D-Q}$
Give the correct matching for the following pairs: $$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(P)} & \text{Selection} \\\hline \text{(B)} & \t...
7.9k
views
answered
Sep 27, 2014
Algorithms
gate1998
algorithms
sorting
easy
match-the-following
+
–
22
votes
107
GATE CSE 1998 | Question: 2.8
Which of the following operations is commutative but not associative? AND OR NAND EXOR
Which of the following operations is commutative but not associative?ANDORNANDEXOR
9.2k
views
answered
Sep 27, 2014
Digital Logic
gate1998
digital-logic
easy
boolean-algebra
+
–
57
votes
108
GATE CSE 2014 Set 1 | Question: 10
Consider the following program in C language: #include <stdio.h> main() { int i; int*pi = &i; scanf("%d",pi); printf("%d\n", i+5); } Which one of the following statements is TRUE? Compilation fails. Execution ... $5$ more than the address of variable $i$. On execution, the value printed is $5$ more than the integer value entered.
Consider the following program in C language:#include <stdio.h main() { int i; int*pi = &i; scanf("%d",pi); printf("%d\n", i+5); }Which one of the following statements is...
17.6k
views
answered
Sep 27, 2014
Programming in C
gatecse-2014-set1
programming
programming-in-c
easy
pointers
+
–
49
votes
109
GATE CSE 2006 | Question: 52
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?$\T...
53.5k
views
answered
Sep 27, 2014
Algorithms
gatecse-2006
algorithms
sorting
easy
quick-sort
+
–
11
votes
110
GATE CSE 2012 | Question: 35
Suppose a circular queue of capacity $(n −1)$ elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, $REAR = FRONT = 0$. The conditions to detect ... : $(REAR+1) \mod n == FRONT$ full: $(FRONT+1) \mod n == REAR$ empty: $REAR == FRONT$
Suppose a circular queue of capacity $(n −1)$ elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out u...
24.3k
views
answered
Sep 27, 2014
DS
gatecse-2012
data-structures
queue
normal
+
–
Page:
« prev
1
2
3
4
5
6
7
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register