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 Sukanya Das
User Sukanya Das
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Sukanya Das
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
4
answers
1
GATEBOOK2019TOC17
If the language accepted by a DFA contains binary strings divisible by $12$ (in decimal), the minimum number of states in it will be ______
commented
2 days
ago
in
Theory of Computation

181
views
gb2019toc1
numericalanswers
1
answer
2
test series  Testbook
Which of the following functions given by their recurrences grows the fastest asymptotically? $T(n) = 8T(n/4) + 100n^2$ $T(n) = 81T(n/9) + 10n^2$ $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$ $T(n) = 100T(n/100)+ n \log^2 n$
answered
2 days
ago
in
Algorithms

104
views
asymptoticnotations
recurrence
0
answers
3
Combinatorics with restrictions
commented
Oct 27
in
Combinatory

100
views
0
answers
4
Second Normal Form
commented
Oct 21
in
Databases

107
views
databasenormalization
functionaldependencies
databases
1
answer
5
Test Series
From the following statements which of them is/are true about SQL a) All attributes used in the group by clause must appear in the select clause b) An SQL query can contain a having clause only if it has a group by clause c) An SQL query can contain a having ... if it does not have a group by clause d) Not all attributes used in the group by clause need to appear in the select clause
commented
Oct 14
in
Databases

49
views
sql
4
answers
6
TIFR2013A20
Consider a well functioning clock where the hour, minute and the seconds needles are exactly at zero. How much time later will the minutes needle be exactly one minute ahead ($1/60$ th of the circumference) of the hours needle and the seconds needle ... have moved an integer multiple of $1/60$ th of the circumference. $144$ minutes $66$ minutes $96$ minutes $72$ minutes $132$ minutes
answered
Oct 10
in
Numerical Ability

237
views
tifr2013
numericalability
clocktime
1
answer
7
Probability  Gravner3
Toss three fair coins. What is the probability of exactly one Heads$(H)$ ?
answered
Sep 26
in
Probability

20
views
probability
gravner
engineeringmathematics
3
answers
8
GATE20068
You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flipflops) will delay the phase of $f$ by $180°$?
answer edited
Jun 28
in
Digital Logic

4.2k
views
gate2006
digitallogic
normal
digitalcircuits
1
answer
9
GATE19882v
Three switching functions $f_1, \: f_2 \:$ and $f_3$ are expressed below as sum of minterms. $f_1 (w, x, y, z) = \sum \: 0, 1, 2, 3, 5, 12$ $f_2 (w, x, y, z) = \sum \: 0, 1, 2, 10, 13, 14, 15$ $f_3 (w, x, y, z) = \sum \: 2, 4, 5, 8$ Express the function $f$ realised by the circuit shown in the below figure as the sum of minterms (in decimal notation).
edited
Jun 28
in
Digital Logic

561
views
gate1988
descriptive
digitallogic
easy
circuitoutput
minsumofproductsform
5
answers
10
GATE200347
Consider the following circuit composed of XOR gates and noninverting buffers. The noninverting buffers have delays $\delta_1 = 2 ns$ and $\delta_2 = 4 ns$ as shown in the figure. Both XOR gates and all wires have zero delays. Assume that all gate inputs, outputs, ... many transition(s) (change of logic levels) occur(s) at $B$ during the interval from $0$ to $10$ ns? $1$ $2$ $3$ $4$
answer edited
Jun 28
in
Digital Logic

3.6k
views
gate2003
digitallogic
logicgates
digitalcircuits
2
answers
11
GATE198713a
The below figure shows four Dtype flipflops connected as a shift register using a $XOR$ gate. The initial state and three subsequent states for three clock pulses are also given. State $Q_{A}$ $Q_{B}$ $Q_{C}$ $Q_{D}$ Initial $1$ $1$ $1$ $1$ After the first clock ... clock $0$ $0$ $0$ $1$ The state $Q_{A} Q_{B} Q_{C} Q_{D}$ after the fourth clock pulse is $0000$ $1111$ $1001$ $1000$
edited
Jun 27
in
Digital Logic

643
views
gate1987
digitallogic
circuitoutput
shiftregisters
5
answers
12
GATE200346
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$ $A + B$, but not $A  B$ or $A + 1$ $A + B$, and $A  B$, and $A + 1$
edited
Jun 27
in
Digital Logic

3.6k
views
gate2003
digitallogic
normal
adder
4
answers
13
GATE2017105
Consider the following table: Algorithms Design Paradigms Kruskal Divide and Conquer Quicksort Greedy FloydWarshall Dynamic Programming Match the algorithms to the design paradigms they are based on. $(P) \leftrightarrow (ii), (Q) \leftrightarrow (iii), (R) \leftrightarrow (i) ... R) \leftrightarrow (iii)$ $(P) \leftrightarrow (i), (Q) \leftrightarrow (ii), (R) \leftrightarrow (iii)$
edited
Jun 25
in
Algorithms

2.2k
views
gate20171
algorithms
algorithmdesigntechniques
4
answers
14
GATE20011.16
Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct? $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$ $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$ $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$ $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$
answer edited
Jun 25
in
Algorithms

2.2k
views
gate2001
algorithms
asymptoticnotations
timecomplexity
normal
3
answers
15
GATE19971.5
The correct matching for the following pairs is All pairs shortest path Greedy Quick Sort DepthFirst Search Minimum weight spanning tree Dynamic Programming Connected Components Divide and Conquer $\text{A2 B4 C1 D3}$ $\text{A3 B4 C1 D2}$ $\text{A3 B4 C2 D1}$ $\text{A4 B1 C2 D3}$
edited
Jun 25
in
Algorithms

1k
views
gate1997
algorithms
normal
algorithmdesigntechniques
3
answers
16
GATE201534
Consider the equality $\displaystyle{\sum_{i=0}^n} i^3 = X$ and the following choices for $X$: $\Theta(n^4)$ $\Theta(n^5)$ $O(n^5)$ $\Omega(n^3)$ The equality above remains correct if $X$ is replaced by Only I Only II I or III or IV but not II II or III or IV but not I
edited
Jun 25
in
Algorithms

2.6k
views
gate20153
algorithms
asymptoticnotations
normal
3
answers
17
GATE200775
Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states: $1$ $2$ $3$ $4$
edited
Jun 25
in
Theory of Computation

921
views
normal
gate2007
theoryofcomputation
finiteautomata
4
answers
18
GATE200774
Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression $b^*ab^*ab^*ab^*$ $(a + b)^*$ $b^*a(a+b)^*$ $b^*ab^*ab^*$
edited
Jun 25
in
Theory of Computation

1.9k
views
gate2007
theoryofcomputation
finiteautomata
normal
1
answer
19
GATE 2018 GA  6(Electrical Engineering)
commented
Jun 25
in
Numerical Ability

343
views
gate2018
numericalability
normal
3
answers
20
ISI201712
Which of the following statements is true? $\text{There are three consecutive integers with sum 2015}$ $\text{There are four consecutive integers with sum 2015}$ $\text{There are five consecutive integers with sum 2015}$ $\text{There are three consecutive integers with product 2015}$
commented
Jun 10
in
Numerical Ability

125
views
isi2017
numericalability
numericalcomputation
4
answers
21
GATE201818
The chromatic number of the following graph is _____
commented
Jun 7
in
Graph Theory

1.7k
views
graphtheory
graphcoloring
numericalanswers
gate2018
4
answers
22
ISI201721
There are four machines and it is known that exactly two of them are faulty. They are tested one by one in a random order till both the faulty machines are identified. The probability that only two tests are required is $\left(\dfrac{1}{2}\right)$ $\left(\dfrac{1}{3}\right)$ $\left(\dfrac{1}{4}\right)$ $\left(\dfrac{1}{6}\right)$
comment edited
May 16
in
Probability

313
views
engineeringmathematics
isi2017
probability
1
answer
23
# Self doubt
To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going uphill and then get a nice breeze at the end of your run as you ... Assuming that every road segment is either uphill or downhill, give an efficient algorithm to find out shortest route that meets above specification??
answer selected
Apr 26
in
Algorithms

90
views
algorithms
2
answers
24
True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included ... edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
answer selected
Apr 12
in
Graph Theory

153
views
graphs
graphalgorithms
algorithms
3
answers
25
BARC 2018
$\textbf{VPN}$ Works at which layer? Application layer Transport layer Network layer Datalink layer
answer selected
Apr 8
in
Computer Networks

225
views
computernetworks
networksecurity
barc2018
0
answers
26
Admission Query
Hi, I am 2016 B.Tech pass out.I currently do not have my degree certificate(I will take it from the university in some days). Is it alright to upload my provisional degree certificate in online pg admission forms?
commented
Apr 1
in
IISc/IITs

53
views
gate2018admissions
1
answer
27
****** Test Series
What will be the output of the following program? Void main() { int a = 5; a >> = 2; a << = 2; printf(“%d”,a); }
commented
Mar 31
in
Programming

155
views
0
answers
28
geeksforgeeks IP Addressing
An Internet Service Provider (ISP) has the following chunk of CIDRbased IP addresses available with it: $245.248.128.0/20$. The ISP wants to give half of this chunk of addresses to Organization $A$, and a quarter to Organization $B$, while retaining the remaining with itself. ... .132.0/22 \text{ and } 245.248.132.0/21$ $245.248.136.0/24 \text{ and } 245.248.132.0/21$
closed
Mar 31
in
Computer Networks

126
views
computernetworks
ipaddressing
networkaddressing
ip
subnetting
0
answers
29
computer organization
A computer has a cache, main memory and a disk used for virtual memory. If reference word is in cache $15\hspace{0.1cm} ns$ are required to access it. If it is in main memory but not in cache, $50\hspace{0.1cm} nsec$ are needed to load it into cache and ... on this system will be____________. (in μsec) is this correct equation .$90*15 + .10*(.50*(50+15)+.50*(10000000+50))$
edited
Mar 31
in
CO & Architecture

35
views
coandarchitecture
2
answers
30
Virtual GATE Question
Let $L$ be a given contextfree language over the alphabet $\{a, b\}$. Construct $L1, L2$ as follows. Let $L1 = L − \{xyx \mid x, y \in \{a, b\}^*\}$, and $L2 = L·L$. Then, Both $L1$ and $L2$ are regular. Both $L1$ and $L2$ are context free but not necessarily regular. $L1$ is regular and $L2$ is context free. $L1$ and $L2$ both may not be context free.
edited
Mar 31
in
Theory of Computation

85
views
virtualgate
testseries
theoryofcomputation
0
answers
31
ME TEST
The format of double operand instruction of a CPU consist of $5$ bits opcode and $6$ bits for source and destination. $26$ double operand instructions and $184$ single operand instructions must be implemented. What will be the total number of zero operand instructions can be implemented? How to solve such questions? I always get confused.
retagged
Mar 31
in
CO & Architecture

59
views
coandarchitecture
1
answer
32
me test
Let $f (n) = Ο(n), g(n) = \Omega(n)$ and $h(n) = \theta(n)$. Then $g(n) + f(n).h(n)$ is ______ How to solve such examples. Rules for math of asymptotic notations(mul,div,add,sub of diif notations)
retagged
Mar 31
in
Algorithms

61
views
algorithms
1
answer
33
ugc net 2004
What item is at the root after the following sequence of insertions into an empty splay tree: $1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2 ?$ $1$ $2$ $4$ $8$
edited
Mar 31
in
IS&Software Engineering

195
views
datastructure
splaytree
1
answer
34
time complexity
let $S$ be a String containing either $0$ or $1$ .further there are no two consecutive $0s$ in $S$. No of solution on an input size $S(N)$ is bounded by $O(n^2)$ $O(nlogn)$ $O(2^n)$ $O(n)$
edited
Mar 31
in
Algorithms

87
views
2
answers
35
time complexity
$t(n)= 2t(\sqrt n) +c $; if $n>2$ $\qquad =1$; if $n<=2$ $O(logn n) $ $O(log log n)$ $O(nlog n)$ $O(n)$
retagged
Mar 31
in
Algorithms

68
views
algorithms
1
answer
36
Test series
$\text{What is three address code representation of this ?}$ a+bc^d^e*fg
edited
Mar 31
in
Compiler Design

142
views
compiler
compilerdesign
2
answers
37
Time & work
$A$ does half as much work as $B$ in threefourths of the time. If together they take $18$ days to complete a work, how much time shall $A$ & $B$ take to do it individually ?
edited
Mar 31
in
Numerical Ability

130
views
numericalability
worktime
1
answer
38
Profit & loss
A cloth merchant announces $25$ percent rebate in prices. If one needs to have a rebate of $Rs. 40$, then how many shirts each costing $Rs. 32$, he should purchase ?
edited
Mar 31
in
Numerical Ability

81
views
numericalability
profitloss
1
answer
39
Radix Sort Problem
The complexity of Radix Sort is $O(wn)$, for $n$ keys which are integers of word size $w$. Here, $w=log_2(n^k)=k\times log_2(n)$ So, the complexity is $O(wn)=O(k\times log_2(n)\times n)$ For instance if size is $n^3$ the complexity ... nlogn)$ Then why we say radix sort sorts the input in linear time? Similar Concept used to solve : https://gateoverflow.in/3353/gate2008it43
retagged
Mar 31
in
Algorithms

101
views
algorithms
radixsort
timecomplexity
sorting
0
answers
40
Sheldon Ross
Determine the number of vectors $\{x_{1}...x_{n}\}$, such that each $x_{i}$ is either $0$ or $1$ and $\displaystyle{\sum_{i=1}^{n}x_{i}\geq k}$
edited
Mar 31
in
Combinatory

107
views
sheldonross
permutationsandcombinations
42,491
questions
48,518
answers
154,892
comments
63,254
users