GATE CSE
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.
Recent activity by KISHALAY DAS
User KISHALAY DAS
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User KISHALAY DAS
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
1
answer
1
TIFR2013B5
Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time $O (n)$ $O(n . \log(n))$ but not $O (n)$ $O(n^{1.5})$ but not $O (n \log n)$ $O(n^{3})$ but not $O(n^{1.5})$ $O(2^{n})$ but not $O(n^{3})$
commented
6 hours
ago
in
Algorithms

137
views
tifr2013
algorithms
0
answers
2
SIMPLIFICATION OF CFG
commented
5 days
ago
in
Theory of Computation

39
views
contextfree
simplification
0
answers
3
STATIC SCOPING RULE CONFUSION!!
asked
5 days
ago
in
Programming

18
views
programming
scopingrule
1
answer
4
Compilers_BottomUpParsing
Consider the grammar: S → aSa  bSb  aa  bb A shiftreduce parser works by identifying the handle of each rightsentential form and replacing it by the head of the corresponding production. In this question, we indicate the handle ... grammar with the handle properly marked? a) abab[aababa] b) ababaS[ababa] c) ababbS[bbaba] d) abab[bSb]baba
answered
Jan 8
in
Compiler Design

56
views
1
answer
5
GATE20141_34
A canonical set of items is given below $S \to L .> R $ $Q \to R.$ On input symbol $<$ the set has (A) a shiftreduce conflict and a reducereduce conflict. (B) a shiftreduce conflict but not a reducereduce conflict. (C) a reducereduce conflict but not a shiftreduce conflict. (D) neither a shiftreduce nor a reducereduce conflict.
commented
Jan 7
in
Compiler Design

776
views
gate20141
compilerdesign
parsing
normal
5
answers
6
GATE20152_23
A system has 6 identical resources and $N$ processes competing for them. Each process can request atmost 2 requests. Which one of the following values of $N$ could lead to a deadlock? 1 2 3 4
commented
Jan 5
in
Operating System

1.6k
views
gate20152
operatingsystem
resourceallocation
easy
6
answers
7
GATE20151_46
Consider a uniprocessor system executing three tasks $T_{1}, T_{2}$ and $T_{3}$ each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 ... millisecond and task preemptions are allowed, the first instance of $T_{3}$ completes its execution at the end of_____________________milliseconds.
commented
Jan 5
in
Operating System

1.7k
views
gate20151
operatingsystem
processschedule
normal
numericalanswers
8
answers
8
GATE2005IT41
Given below is a program which when executed spawns two concurrent processes : semaphore X : = 0 ; /* Process now forks into concurrent processes P1 & P2 */ P1 P2 repeat forever V (X) ; Compute ; P(X) ; repeat forever P(X) ; Compute ; V(X) ; ... holds? Both I and II are true. I is true but II is false. II is true but I is false Both I and II are false
commented
Jan 5
in
Operating System

1.2k
views
gate2005it
operatingsystem
processsynchronization
normal
3
answers
9
GATE 2016136
What will be the output of the following pseudocode when parameters are passed by reference and dynamic scoping is assumed? a = 3; void n(x) { x = x * a; print (x); } void m(y) { a = 1 ; a = y  a; n(a); print (a); } void main () { m(a); } $6,2$ $6,6$ $4,2$ $4,4$
commented
Jan 4
in
Compiler Design

1.7k
views
gate20161
parameterpassing
normal
1
answer
10
GATE2005IT6
The language {0n 1n 2n  1 ≤ n ≤ 106} is regular contextfree but not regular. contextfree but its complement is not contextfree. not contextfree
commented
Jan 3
in
Theory of Computation

221
views
gate2005it
theoryofcomputation
easy
1
answer
11
GATE2008IT36
Consider the following two finite automata. M1 accepts L1 and M2 accepts L2. Which one of the following is TRUE? L1 = L2 L1 ⊂ L2 L1 ∩ L2' = ∅ L1 ∪ L2 ≠ L1
commented
Jan 3
in
Theory of Computation

457
views
gate2008it
theoryofcomputation
finiteautomata
normal
4
answers
12
GATE200447
Consider a system with a twolevel paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, ... 000 instructions. What is the effective average instruction execution time? 645 nanoseconds 1050 nanoseconds 1215 nanoseconds 1230 nanoseconds
commented
Jan 3
in
CO & Architecture

4.2k
views
gate2004
co&architecture
virtualmemory
normal
6
answers
13
GATE200482
Let A[1, n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i] = ... complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$
commented
Jan 2
in
Algorithms

920
views
gate2004
algorithms
timecomplexity
normal
3
answers
14
GATE200440
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among $\text{union, intersection, membership, cardinality}$ will be the slowest? $\text{union}$ only $\text{intersection, membership}$ $\text{membership, cardinality}$ $\text{union, intersection}$
commented
Jan 2
in
DS

532
views
gate2004
datastructure
linkedlists
normal
4
answers
15
GATE200613
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be $\log_2 n$ $n$ $2n+1$ $2^n1$
commented
Jan 2
in
DS

686
views
gate2006
datastructure
binarytree
normal
2
answers
16
GATE200611
Consider a weighted complete graph G on the vertex set {v1,v2,.....vn} such that the weight of the edge (vi, vj) is . The weight of a minimum spanning tree of G is: n1 2n3 $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$
commented
Jan 2
in
Algorithms

341
views
gate2006
algorithms
spanningtree
normal
2
answers
17
TIFR2015B10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which ... regular. $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.
comment edited
Dec 31, 2016
in
Theory of Computation

229
views
tifr2015
regularset
identifyclasslanguage
4
answers
18
TIFR2015B8
Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ ... . $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable.
commented
Dec 31, 2016
in
Theory of Computation

351
views
tifr2015
identifyclasslanguage
1
answer
19
Candidate key
A candidate key should have unique values and a chosen CK is called primary key. Null is also unique. Why (C) is not answer?
commented
Dec 31, 2016
in
Databases

29
views
3
answers
20
GATE2008IT18
How many bytes of data can be sent in 15 seconds over a serial link with baud rate of 9600 in asynchronous mode with odd parity and two stop bits in the frame? 10,000 bytes 12,000 bytes 15,000 bytes 27,000 bytes
commented
Dec 30, 2016
in
Computer Networks

1.2k
views
gate2008it
computernetworks
communication
serialcommunication
normal
3
answers
21
GATE2005IT85b
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that ... to node A at time (t + 100) is : $>100$ but finite $\infty$ $3$ $>3$ and $\leq 100$
commented
Dec 30, 2016
in
Computer Networks

978
views
gate2005it
computernetworks
routing
normal
2
answers
22
GATE200646
Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and gobackn error control strategy. All packets are ready and immediately available for transmission. If every 5th packet that A transmits ... lost), then what is the number of packets that A will transmit for sending the message to B? 12 14 16 18
commented
Dec 30, 2016
in
Computer Networks

1.7k
views
gate2006
computernetworks
slidingwindow
normal
1
answer
23
TIFR2016B14
Consider a family $\mathcal{F}$ of subsets of $\{1, 2, \dots , n\}$ such that for any two distinct sets $A$ and $B$ in $\mathcal{F}$ we have: $A \subset B$ or $ B \subset A$ or $A \cap B = \emptyset$. Which of the following statements is TRUE? ... 2^{n1}$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n1}$ None of the above
commented
Dec 29, 2016
in
Others

55
views
tifr2016
1
answer
24
TIFR2016B13
An undorected graph $G = (V, E)$ is said to be $k$colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the ... is the maximum degree in $G$ There is a polynomial time algorithm to check if $G$ is 2colourable If $G$ has no triangle then it is 3colourable
answered
Dec 29, 2016
in
Others

15
views
tifr2016
2
answers
25
GATE200469
A 4stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be 120.4 microseconds 160.5 microseconds 165.5 microseconds 590.0 microseconds
commented
Dec 29, 2016
in
CO & Architecture

528
views
gate2004
co&architecture
pipeline
normal
4
answers
26
GATE2008IT39
Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal ... the minimum size of the control word and control address register? 125, 7 125, 10 135, 9 135, 10
commented
Dec 28, 2016
in
CO & Architecture

913
views
gate2008it
co&architecture
microprogramming
normal
1
answer
27
TIFR2017B7
An array of $n$ distinct elements is said to be unsorted if for every index $i$ such that $ 2 \leq i \leq n1$, either $A[i] > max \{A [i1], A[i+1]\}$, or $A[i] < min \{A[i1], A[i+1]\}$. What is the timecomplexity of the fastest algorithm that ... n)$ $O(n)$ but not $O(\sqrt{n})$ $O(\sqrt{n})$ but not $O(\log n)$ $O(\log n)$ but not $O(1)$ $O(1)$
commented
Dec 27, 2016
in
Algorithms

99
views
tifr2017
algorithms
sorting
1
answer
28
TIFR2017B13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are incident on the ... vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two
commented
Dec 27, 2016
in
Graph Theory

95
views
tifr2017
graphtheory
linegraph
2
answers
29
TIFR2017B9
Which of the following regular expressions correctly accepts the set of all 0/1strings with an even (poossibly zero) numbe of 1s? $(10^*10^*)^*$ $(0^*10^*1)^*$ $0^*1(10^*1)^*10^*$ $0^*1(0^*10^*10^*)^*10^*$ $(0^*10^*1)^*0^*$
commented
Dec 27, 2016
in
Theory of Computation

79
views
tifr2017
theoryofcomputation
regularexpressions
2
answers
30
ACE TEST SERIES:Transaction 2pl and Time stamp based protocol
answer selected
Dec 27, 2016
in
Databases

71
views
databases
transactions
conflict_serializable
testseries
1
answer
31
ACETestSeries:TOCwhich type of language
commented
Dec 26, 2016
in
Theory of Computation

111
views
theoryofcomputation
1
answer
32
ACETestSeries:Algorithm Time Complexity
commented
Dec 25, 2016
in
Algorithms

144
views
algorithms
timecomplexity
1
answer
33
ACEMockTest:Matrix algebraRank
answer selected
Dec 25, 2016
in
Linear Algebra

96
views
matrix
rankofmatrix
1
answer
34
ACEMockTestCProgramming
commented
Dec 25, 2016
in
Programming

68
views
cprogramming
1
answer
35
ACEMockTest:Countable Set
commented
Dec 24, 2016
in
Set Theory & Algebra

49
views
settheory&algebra
1
answer
36
DBMSNormalisationLossless Join Decomposition
commented
Dec 22, 2016
in
Databases

60
views
databases
decomposition
functionaldependencies
losslessjoin
1
answer
37
MEFST6:Recursive Function call and Callstack
commented
Dec 22, 2016
in
Algorithms

66
views
algorithms
1
answer
38
ACEMockTEST:Recurrence Relation Solution
asked
Dec 22, 2016
in
Algorithms

44
views
algorithms
#recurrencerelation
1
answer
39
ACEMockTestSerializability Problem
asked
Dec 21, 2016
in
Databases

38
views
view_serializable
databases
conflict_serializable
1
answer
40
MEFST6:Transaction,Recoverability and 2PL
commented
Dec 21, 2016
in
Databases

64
views
transactions
databases
concurrency
conflict_serializable
18,813
questions
23,785
answers
51,449
comments
20,130
users