The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Questions by Arjun
User Arjun
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Arjun
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
+2
votes
1
answer
1
TIFR2018B15
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $SCYCLE=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ and $LCYCLE=\{(G,k) ... NPcomplete. $SCYCLE \leq_{p} LCYCLE$ (i.e, there is a polynomial time manytoone reduction from $SCYCLE$ to $LCYCLE$).
asked
Dec 10, 2017
in
Others

143
views
tifr2018
+3
votes
1
answer
2
TIFR2018B14
Define the language $INFINITE_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\},$ where $(A)$ denotes the description of the deterministic finite automata (DFA).Then which of ... is Turing decidable (recursive). It is Turing recognizable but not decidable. Its complement is Turing recognizable but it is not decidable.
asked
Dec 10, 2017
in
Theory of Computation

185
views
tifr2018
identifyclasslanguage
+3
votes
2
answers
3
TIFR2018B13
Let $n\geq 3,$ and let $G$ be a simple , connected, undirected graph with the same number $n$ of vertices and edges. Each edge of $G$ has a distinct real weight associated with it. Let $T$ be the minimum weight spanning tree of $G.$ Which of ... edge of $C$ is not in $T.$ $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$
asked
Dec 10, 2017
in
Others

200
views
tifr2018
+3
votes
1
answer
4
TIFR2018B12
Consider the following statements: For every positive integer $n,$ let $\#{n}$ be the product of all primes less than or equal to $n.$ Then, $\# {p}+1$ is a prime, for every prime $p.$ $\large\pi$ is a universal constant ... Only statement (ii) is correct. Only statement (iii) is correct. Only statement (iv) is correct. None of the statements are correct.
asked
Dec 10, 2017
in
Others

209
views
tifr2018
+3
votes
2
answers
5
TIFR2018B11
Consider the language L$\subseteq \left \{ a,b,c \right \}^{*}$ definded as L = $\left \{ a^{p}b^{q}c^{r} : p=q\quad or\quad q=r \quad or\quad r=p \right \}.$ Which of the following answer is TRUE about complexity of this language? (a) ... , defined as $\overline{L} = \left \{ a,b,c \right \}^{*}$\L, is regular. (e) L is regular, contextfree and decidable
asked
Dec 10, 2017
in
Theory of Computation

160
views
tifr2018
+6
votes
0
answers
6
TIFR2018B10
For two $n$ bit strings $x,y \in\{0,1\}^{n},$ define $z=x\oplus y$ to be the bitwise XOR of the two strings (that is, if $x_{i},y_{i},z_{i}$ denote the $i^{th}$ bits of $x,y,z$ respectively, then $z_{i}=x_{i}+y_{i} \bmod 2$). A function $h:\{0,1\ ... such linear functions for $n \geq 2$ is: $2^{n}$ $2^{n^{2}}$ $\large2^{\frac{n}{2}}$ $2^{4n}$ $2^{n^{2}+n}$
asked
Dec 10, 2017
in
Others

122
views
tifr2018
+3
votes
1
answer
7
TIFR2018B9
Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each vertex $\large v,$ let $\large \phi(v)$ be the length of the ... is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.
asked
Dec 10, 2017
in
Others

148
views
tifr2018
+3
votes
1
answer
8
TIFR2018B8
In an undirected graph G with n vertices, vertex 1 has degree 1, while each vertex 2,...,n1 has degree 10 and the degree of vertex n is unknown, Which of the following statement must be TRUE on the graph G? (a) There is a path from vertex 1 to ... degree 1. (d) The diameter of the graph is at most $\frac{n}{10}$ (e) All of the above choices must be TRUE
asked
Dec 10, 2017
in
Graph Theory

126
views
tifr2018
graphtheory
+5
votes
1
answer
9
TIFR2018B7
Consider the recursive quicksort algorithm with "random pivoting". That is, in each recursive call, a pivot is chosen uniformly at random from the subarray being sorted.When this randomized algorithm is applied to an array of size $n$ all whose elements are distinct, ... \left(\dfrac{1}{n^{2}}\right)$ $\Theta\left(\dfrac{1}{n \log^{2} n}\right)$
asked
Dec 10, 2017
in
Others

169
views
tifr2018
+1
vote
2
answers
10
TIFR2018B6
Consider the following implementation of a binary tree data strucrure.The operator $+$ denotes listconcatenation. That is, $[a,b,c]+[d,e]=[a,b,c,d,e].$ struct TreeNode: int value TreeNode leftChild TreeNode rightChild function preOrder(T): if T == null: ... 12,6,7,9,10,15,2,1,4,8,11,14,3,13,5]$ $\text{Cannot be uniquely determined from given information.}$
asked
Dec 10, 2017
in
Others

93
views
tifr2018
+2
votes
1
answer
11
TIFR2018B5
Which of the following functions, given by there recurrence, grows the fastest asymptotically ? (a) T(n) = 4T$\left ( \frac{n}{2} \right )$ + 10n (b) T(n) = 8T$\left ( \frac{n}{3} \right )$ + 24n$^{2}$ (c) T(n) = 16T$\left ( \frac{n}{4} ... n) = 25T$\left ( \frac{n}{5} \right )$ + 20$\left ( n log n \right )^{1.99}$ (e) They all are asymptotically the same
asked
Dec 10, 2017
in
Algorithms

146
views
tifr2018
asymptoticnotations
recurrencerelation
+1
vote
3
answers
12
TIFR2018B4
The notation "$\Rightarrow$" denotes "implies" and "$\wedge$" denotes "and" in the following formulae. Let X denote the formula: (b $\Rightarrow$ a ) $\Rightarrow$ ( a $\Rightarrow$ b) Let Y denote the formula: ... satisfiable. (d) X is not tautology and Y is satisfiable. (e) X is a tautology and Y is satisfiable,
asked
Dec 10, 2017
in
Mathematical Logic

130
views
tifr2018
mathematicallogic
+1
vote
1
answer
13
TIFR2018B3
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? 1 2 4 6 8
asked
Dec 10, 2017
in
Others

148
views
tifr2018
+1
vote
1
answer
14
TIFR2018B2
Consider the following nondeterministic automation, where $\large s_{1}$ is the start state and $\large s_{4}$ is the final (accepting) state.The alphabet is $\{a,b\}.$ A transition with label $\large\epsilon$ can be taken without consuming any symbol from the input. Which of ... ^{*}aba$ $aba(a+b)^{*}aba$ $(a+b)aba(b+a)^{*}$ $aba(a+b)^{*}$ $(ab)^{*}aba$
asked
Dec 10, 2017
in
Others

81
views
tifr2018
+2
votes
4
answers
15
TIFR2018B1
What is the remainder when $4444^{4444}$ is divided by 9 ? (a) 1 (b) 2 (c) 5 (d) 7 (e) 8
asked
Dec 10, 2017
in
Others

188
views
tifr2018
+1
vote
1
answer
16
TIFR2018A12
An $n \times n$ matrix $M$ with real entries is said to be positive definite if for every nonzero $n$dimensional vector $x$ with real entries, we have $x^{T}Mx>0.$Let $A$ and $B$ be symmetric,positive definite matrices of size $n\ ... Only $(1)$ and $(3)$ None of the above matrices are positive definite All of the above matrices are positive definite
asked
Dec 10, 2017
in
Others

78
views
tifr2018
+1
vote
1
answer
17
TIFR2018A11
We are given a (possibly empty) set of objects.Each object in the set is colored either black or white, is shaped either circular or rectangular, and has a profile that is either fat or thin, Those properties obey the following principles: Each white ... $(i) \text{ and } (iii)$ only None of the statements must be TRUE All of the statements must be TRUE
asked
Dec 10, 2017
in
Others

149
views
tifr2018
+2
votes
1
answer
18
TIFR2018A10
Let $C$ be a biased coin such that the probability of a head turning up is $p.$ Let $p_n$ denote the probability that an odd number of heads occurs after $n$ tosses for $n \in \{0,1,2,\ldots \},$ Then which of the following is TRUE ? $p_n=\dfrac{1}{2}\text{ for ... }n \in \{0,1,2,\ldots\}$. $p_{n}=1 \text{ if } n \text{ is odd and } 0 \text{ otherwise}.$
asked
Dec 10, 2017
in
Others

89
views
tifr2018
+4
votes
2
answers
19
TIFR2018A8
A crime has been committed with four people at the scene of the crime.You are responsible for finding out who did it.You have recorded the following statements from the four witnesses, and you know one of them has committed the crime. ... \text{Chacko}$ $\text{Desmond}$ $\text{Either Anuj or Binky;the information is insufficient to pinpoint the criminal}$
asked
Dec 10, 2017
in
Others

128
views
tifr2018
+2
votes
3
answers
20
TIFR2018A7
Consider the following function definition. void greet(int n) { if(n>0) { printf("hello"); greet(n1); } printf("world"); } If you run greet(n) for some nonnegative integer n, what would it print ... n times "helloworld" (d) n+1 times "helloworld" (e) n times "helloworld", followed by "world"
asked
Dec 10, 2017
in
Programming

129
views
tifr2018
programminginc
+5
votes
3
answers
21
TIFR2018A6
What is the minimum number of student needed in a class to guarantee that there are at least 6 student whose birthday fall in same month ? (a) 6 (b) 23 (c) 61 (d) 72 (e) 91
asked
Dec 10, 2017
in
Combinatory

164
views
tifr2018
pigeonhole
0
votes
1
answer
22
TIFR2018A5
Which of the following id the derivative of $f(x)=x^{x}$ when $x>0$ ? $x^{x}$ $x^{x} \;ln \;x$ $x^{x}+x^{x}\;ln\;x$ $(x^{x}) (x^{x}\;ln\;x)$ $\text{None of the above;function is not differentiable for }x>0$
asked
Dec 10, 2017
in
Others

96
views
tifr2018
0
votes
2
answers
23
TIFR2018A4
The distance from your home to your office is 4 kilometers and your normal walking speed is 4 Km/hr. On the first day, you walk at your normal walking speed and take time T1 to reach office. On the second day, you walk at a speed of 3 Km/hr from 2 Kilometers, and at a ... (d) T$_{1}$=T$_{2}$ and T$_{1}$<T$_{3}$ (e) T$_{1}$<T$_{2}$ and T$_{1}$=T$_{3}$
asked
Dec 10, 2017
in
Others

95
views
tifr2018
0
votes
1
answer
24
TIFR2018A3
Which of the following statements is TRUE for all sufficiently large integers n ? (a) $2^{2^{\sqrt{log log n}}} <2^{\sqrt{log n}} < n$ (b) $2^{\sqrt{log n}}<n<2^{2^{\sqrt{log log n}}}$ (c) $n<2^{\sqrt{log n}}<2^{2^{\sqrt{log log n}}} ... ^{2^{\sqrt{log log n}}} <2^{\sqrt{log n}}$ (e) $2^{\sqrt{log n}}<2^{2^{\sqrt{log log n}}} < n$
asked
Dec 10, 2017
in
Algorithms

133
views
tifr2018
asymptoticnotations
0
votes
1
answer
25
TIFR2018A2
Consider the following subset of $\mathbb{R} ^{3}$ (the first two are cylinder, the third is a plane): $C_{1}=\left \{ \left ( x,y,z \right ): y^{2}+z^{2}\leq 1 \right \};$ $C_{2}=\left \{ \left ( x,y,z \right ... the following best describe the shape of set A? (a) Circle (b) Ellipse (c) Triangle (d) Square (e) An octagonal convex figure with curved sides
asked
Dec 10, 2017
in
Others

80
views
tifr2018
0
votes
1
answer
26
TIFR2018A1
Consider a point A inside a circle C that is at distance 9 from the centre of a circle. Suppose you told that there is a chord of length 24 passing through A with A as its midpoint. How many distinct chords of C have integer length and pass through A ? (a) 2 (b) 6 (c) 7 (d) 12 (e) 14
asked
Dec 10, 2017
in
Others

107
views
tifr2018
+1
vote
0
answers
27
UGCNETNov2017iii75
asked
Nov 5, 2017
in
Others

62
views
ugcnetnov2017iii
+1
vote
0
answers
28
UGCNETNov2017iii74
asked
Nov 5, 2017
in
Others

45
views
ugcnetnov2017iii
+1
vote
0
answers
29
UGCNETNov2017iii73
asked
Nov 5, 2017
in
Others

35
views
ugcnetnov2017iii
+1
vote
0
answers
30
UGCNETNov2017iii72
asked
Nov 5, 2017
in
Others

30
views
ugcnetnov2017iii
Page:
1
2
3
4
5
6
...
17
next »
33,687
questions
40,230
answers
114,266
comments
38,783
users