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. For hardcopy of previous year questions please see
here
Recent activity 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
1
answer
1
Which are the exams apart from gate for mtech admission?
answered
8 hours
ago
in
GATE

24
views
0
answers
2
Gate Over Book
Gateoverflow book is showing unavailable status on amazon.When it will be available next?
commented
1 day
ago
in
Study Resources

14
views
1
answer
3
Hash Function
Which of the following is the least suitable hash function H(x) where X is some non negative integer ? 1. h(k) =k%n 2.h(k) =k*k %n 3.h(k)=(gcd(k+1,2k+2) +k ) %n Linear probing is used for collision resolution .
commented
3 days
ago
in
DS

83
views
hashing
datastructure
2
answers
4
GATE201034
The weight of a sequence $a_0,a_1, \dots, a_{n1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n1}/2^{n1}$. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the maximum ... dots, a_{n1}$. Then $X$ is equal to $max(Y, a_0+Y)$ $max(Y, a_0+Y/2)$ $max(Y, a_0 +2Y)$ $a_0+Y/2$
commented
4 days
ago
in
Algorithms

4.1k
views
gate2010
algorithms
dynamicprogramming
normal
4
answers
5
How many solutions are there to the equation x+y+z=17 ?They are nonnegative integers
answered
6 days
ago
in
Combinatory

956
views
permutationsandcombinations
1
answer
6
Wooe Test Series
Is wooe online test series good for Gate ?
commented
6 days
ago
in
Others

22
views
testseries
0
answers
7
Reduction
A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true? A) B is Recursive B) B is Recursive Enumerable C) B is Not RE D) B is CFL
commented
6 days
ago
in
Theory of Computation

26
views
theoryofcomputation
reduction
2
answers
8
Decidability
Let M1 be a Turing machine and M2 be a finite automaton. Is the problem, whether M1 and M2 accept the same language decidable? An elaborative answer with proof is most welcome.
commented
Sep 17
in
Theory of Computation

43
views
decidability
theoryofcomputation
0
answers
9
SELD DOUBT WHAT IS DIFFERENCE BETWEEN THESE QUESTIONS
commented
Sep 16
in
DS

40
views
2
answers
10
Choose the correct statement about HEAP
I. A heap is always nearly complete tree. II. Worst case complexity of heapify operation is O( log n) III. Worst case complexity of build heap operation is O( n log n) a. I only b. I and II only c. II and III only d. I, II and III
answered
Sep 16
in
Algorithms

157
views
datastructure
0
answers
11
TM that rejects input string x
$D = \left \{ <M> \mid \ M \text{ is a TM that rejects the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
commented
Sep 16
in
Theory of Computation

44
views
decidability
3
answers
12
GATE2006IT50
Which one of the choices given below would be printed when the following program is executed? #include <stdio.h> void swap (int *x, int *y) { static int *temp; temp = x; x = y; y = temp; } void printab () { static int i, a = 3, b = 6; i = 0; while (i <= 4) { if ((i++)%2 == 1 ... 3$ $a = 3, b = 0$ $a = 12, b = 9$ $a = 3, b = 6$ $a = 3, b = 6$ $a = 6, b = 3$ $a = 15, b = 12$
commented
Sep 16
in
Programming

3.1k
views
gate2006it
programming
programminginc
normal
1
answer
13
TM that accepts input string x
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
answer selected
Sep 16
in
Theory of Computation

88
views
theoryofcomputation
decidability
turingmachine
3
answers
14
L(M) is infinite
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
commented
Sep 16
in
Theory of Computation

982
views
theoryofcomputation
turingmachine
decidability
difficult
3
answers
15
GATE2014235
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$. Let $$L=\left\{\langle M \rangle \mid M \text{ is a Turing machine}\\\text{ that accepts a ... right\}.$$ Then $L$ is: decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable
commented
Sep 16
in
Theory of Computation

6.1k
views
gate20142
theoryofcomputation
turingmachine
normal
2
answers
16
GATE199292,xv
Which of the following predicate calculus statements is/are valid? $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$ $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$ $(\forall (x)) (P(x) \vee Q(x ... \vee (\forall (x)) Q(x)$ $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$
commented
Sep 14
in
Mathematical Logic

3.4k
views
gate1992
mathematicallogic
normal
firstorderlogic
0
answers
17
Closure Property
If L1 is CSL and L2 is CFL, then which of the following is correct ? A.L1'  L2 is CSL always B. L1  L2' is CSL always C. L1 intersection Regular is Regular always D. L1.L2 is CSL but not CFL
commented
Sep 10
in
Theory of Computation

64
views
theoryofcomputation
contextfreelanguage
closureproperty
0
answers
18
NPTEL
/* sizeof(int)=4; sizeof(float)=8; sizeof(unsigned char)=1 ; */ What is the output of the following program ? #include<iostream> #include<stdio.h> using namespace std; int main(){ union Data{ int i; float f; unsigned char str[20]; }data; printf("size =%d\n",sizeof(data)); data.i=10; data.f=220.5; printf("data.i: %d\n",data.i); return 0; }
commented
Sep 10
in
Programming

50
views
nptelquiz
0
answers
19
Turing machine
Consider <M> be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M>  M is a TM that halts on all the input and L(M) = L' for some Undecidable language L' } then L is ? A. Decidable and Recursive B. Decidable and Non recursive C. Undecidable and RE D. Undecidable and Non RE
closed
Sep 9
in
Theory of Computation

19
views
turingmachine
recursiveandrecursivelyenumerablelanguages
decidability
1
answer
20
Test Series
commented
Sep 9
in
Algorithms

26
views
0
answers
21
self doubt
Consider the Context free language which has equal no of as and bs. eg abab Since a proper prefix ab also belongs to this language, this language does not satisfy prefix property as far as i understand. But we can clearly draw a deterministic PDA ... with empty stack for CFL without prefix property. But above example forms a contradiction. Please resolve my doubt. I am getting confused.
commented
Sep 8
in
Theory of Computation

50
views
theoryofcomputation
contextfreelanguage
pushdownautomata
1
answer
22
GATE200749
Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE? There is a minimum spanning tree containing $e$ If $e$ is not in a minimum spanning tree ... all edges have the same weight. Every minimum spanning tree has an edge of weight $w$ $e$ is present in every minimum spanning tree
commented
Sep 7
in
Algorithms

1.6k
views
gate2007
algorithms
spanningtree
normal
3
answers
23
Sipser: Prove that given language is undecidable?
commented
Sep 3
in
Theory of Computation

615
views
theoryofcomputation
identifyclasslanguage
decidability
turingmachine
1
answer
24
Doubt
Ques: Which is not possible in L and L'(complement of L) theorem? 1. Both are REC. 2. Both are RE. 3. One is REC & other is RE. 4. Both are RE BUT NOT REC. 5. One is REC & other is NOT RE. 6. One is RE & other is RE BUT NOT REC. 7. One is NOT RE & other is RE.
commented
Sep 2
in
Theory of Computation

36
views
3
answers
25
Masters theorem
Solve using Master's Theorem $T(n)=T(n/2)+$ 2n
commented
Sep 2
in
Algorithms

72
views
mastertheorem
algorithms
timecomplexity
3
answers
26
GATE2017139
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$ ... $f$ is computable then $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
commented
Sep 1
in
Theory of Computation

3.8k
views
gate20171
theoryofcomputation
decidability
difficult
0
answers
27
Normal
Can anyone provide link for NPTEL vedios??
commented
Sep 1
in
GATE

27
views
3
answers
28
GATE20153GA2
The Tamil version of __________ John Abrahamstarrer Madras Cafe __________ cleared by the Censor Board with no cuts last week, but the film's distributor _______ no takers among the exhibitors for a release in Tamilnadu _______ this Friday. Mr., was, found, on a, was, found, at the, was, found, on a, being, find at
answer selected
Sep 1
in
Verbal Ability

722
views
gate20153
verbalability
normal
englishgrammar
6
answers
29
TIFR2010A19, TIFR2014A6
Karan tells truth with probability $\dfrac{1}{3}$ and lies with probability $\dfrac{2}{3}.$ Independently, Arjun tells truth with probability $\dfrac{3}{4}$ and lies with probability $\dfrac{1}{4}.$ Both watch a cricket match. Arjun tells you that India won, Karan tells you ... 3}\right)$ $\left(\dfrac{3}{4}\right)$ $\left(\dfrac{5}{6}\right)$ $\left(\dfrac{6}{7}\right)$
answer edited
Sep 1
in
Probability

1.3k
views
tifr2010
probability
conditionalprobability
tifr2014
0
answers
30
GO pdf vol 2
commented
Sep 1
in
Programming

77
views
0
answers
31
GO pdf
commented
Sep 1
in
Programming

190
views
2
answers
32
Gate CS
#include<stdio.h> int main() { int x, y = 7; x = ++y + ++y + y; printf("%d\n", x); return 0; } What is the output of this code snippet ? A. 27 B. 26 C. 25 D. Compilation error
commented
Sep 1
in
Programming

57
views
gate2019
programminginc
0
answers
33
Made easy test serirs
Why q5 is included in partisions ??
commented
Sep 1
in
Theory of Computation

48
views
1
answer
34
Regular Expression
Check the Language is Regular or Not? WXWR (W,X ∈ (0,1)+) Please Explain.
commented
Aug 31
in
Theory of Computation

34
views
regularlanguages
0
answers
35
ACE test series
how to solve this question as I am able to think of statement 1 but unable to visualise 2 clearly ,please tell me any fast way to do such question. can you please tell me relation between det and det of adjoint and how to derive them please .
closed
Aug 31
in
Mathematical Logic

11
views
2
answers
36
Linked list
What are sequential access structures? Are arrays or linked list the sequential access structures?
reopened
Aug 31
in
Programming

42
views
datastructure
1
answer
37
Correct the sentence
The professor ordered to the student to go out of the class
answer selected
Aug 29
in
Verbal Ability

45
views
verbalability
englishgrammar
1
answer
38
recursive and recursively enumerable
What will the intersection of a recursive and recursive enumerable language. Will it be recursive???
answered
Aug 28
in
Theory of Computation

140
views
3
answers
39
GATE2014320
A system uses $3$ page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? $\text{4, 7, 6, 1, 7, 6, 1, 2, 7, 2}$
answer edited
Aug 28
in
Operating System

844
views
gate20143
operatingsystem
pagereplacement
numericalanswers
normal
0
answers
40
Relational algebra
closed
Aug 26
in
Databases

13
views
39,814
questions
46,793
answers
140,922
comments
58,853
users