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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Answers by Arkaprava
User Arkaprava
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Arkaprava
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
+2
votes
1
TIFR2019B13
A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses? $199$ $683$ $1365$ $3^{10}2^{10}$ $3^{10}$
answered
Jun 26
in
Combinatory

557
views
tifr2019
engineeringmathematics
discretemathematics
permutationandcombination
medium
0
votes
2
Cormen Edition 3 Exercise 2.3 Question 7 (Page No. 39)
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.
answered
Jun 26
in
Algorithms

11
views
cormen
algorithms
algorithmdesigntechniques
descriptive
difficult
+1
vote
3
A FIRST COURSE IN PROBABILITY (SHELDON ROSS),CHAPTER 4 RANDOM VARIABLES, QUESTION#43
answered
Jun 26
in
Probability

94
views
probability
sheldonross
randomvariable
+2
votes
4
GATE198812iic
Using Armstrong’s axioms of functional dependency derive the following rules: $\{ x \rightarrow y, \: z \subset y \} \mid= x \rightarrow z$ (Note: $x \rightarrow y$ denotes $y$ is functionally dependent on $x$, $z \subseteq y$ denotes $z$ is subset of $y$, and $\mid =$ means derives).
answered
Jun 14
in
Databases

145
views
gate1988
normal
descriptive
databases
functionaldependencies
0
votes
5
Goschedule information
As per Gate Overflow Schedule for 2020 for the first week we have to study " Logical Reasoning and Data Interpretation: Verbal reasoning deriving conclusion from passage, conclusions as in puzzles (can be in mathematical logic also) ". So which topics are covered under this and what questions to practice from GO PDF?
answered
Jun 12
in
Verbal Ability

146
views
goclassroom
verbalability
+3
votes
6
Self doubt DIGITAL LOGIC
Is Y' + Z' same as (YZ)' ? Please explain this concept of compliments..!!
answered
Jun 11
in
Digital Logic

74
views
+2
votes
7
TIFR2011A13
If $z=\dfrac{\sqrt{3}i}{2}$ and $\large(z^{95}+ i^{67})^{97}= z^{n}$, then the smallest value of $n$ is? $1$ $10$ $11$ $12$ None of the above.
answered
Jun 10
in
Numerical Ability

320
views
tifr2011
numericalability
complexnumber
0
votes
8
Theory of Computation: Context Free Languages
Hi, I am having a doubt understanding the result of CFL  Regular: Here's my approach: CFL  Regular = CFL INTERSECTION Regular' = CFL INTERSECTION Regular = CFL Suppose some CFL L1= {a^n b^n  n>=1} and some Regular R1= (a+b)* ... to say CFL  Regular = Regular or CFL  Regular = CFL ? If both are separate options, which one should I go for? Thanks
answered
Jun 9
in
Theory of Computation

51
views
theoryofcomputation
contextfreelanguage
selfdoubt
+1
vote
9
GEEKS FOR GEEKS GATE 2017 MOCK
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
answered
Jun 9
in
Algorithms

123
views
kruskalsalgorithm
graphalgorithms
greedyalgorithm
datastructure
0
votes
10
GATE2017 CE2: GA9
Budhan covers a distance of $19$ km in $2$ hours by cycling one fourth of the time and walking the rest. The next day he cycles (at the same speed as before) for half the time and walks the rest (at the same speed as before) and covers $26$ km in $2$ hours. The speed in km/h at which Budhan walk is $1$ $4$ $5$ $6$
answered
Jun 7
in
Numerical Ability

129
views
gate2017ce2
speedtimedistance
numericalability
+1
vote
11
Self doubt in percentage and mixtures
In a mixture of 80 litres of milk and water, 25% of the mixture is milk. How much water should be added to the mixture so that milk becomes 20% of the mixture? (a) 20 litres (b) 15 litres (c) 25 litres (d) None of these
answered
Jun 4
in
Numerical Ability

46
views
+3
votes
12
Doubt on Bipartite Graph
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
answered
Jun 2
in
Algorithms

76
views
graphtheory
algorithms
+7
votes
13
GATE2015 EC1: GA8
Fill in the missing value
answered
May 28
in
Numerical Ability

185
views
gate2015ec1
generalaptitude
numericalability
sequenceseries
0
votes
14
GateBook Test Series: Digital Logic  Boolean Algebra
What is the time complexity for checking whether an assignment of truth values to variables $x_1,\dots ,x_n$ satisfies a given formula $f(x_1\dots,x_n)$? $O(2^n)$ $O(g(n))$ where $g$ is a polynomial $O(log(n))$ None of the above
answered
May 25
in
Digital Logic

213
views
gatebook
digitallogic
booleanalgebra
+1
vote
15
Ace Academy Question Bank: Automata
Find the no. of DFA’s that can be constructed over the alphabet Σ with 5 symbols, and with 10 states. (a) $2^5$^0$ × $50^5$ (b) $2^1$^0$ × $10^5$^0$ (c) $2^5$ × $10^5$^0$ (d) $2^5$^0$ × $50^5$
answered
May 22
in
Theory of Computation

87
views
theoryofcomputation
numberofdfa
0
votes
16
self doubt: TOC
is union of regular language and context free language always regular?
answered
May 22
in
Theory of Computation

55
views
theoryofcomputation
regularlanguages
contextfreelanguage
+1
vote
17
Discrete mathematics #TEST_BOOK
I Have doubt about the language. Is it asking about the sum of elements if we make the GBL set for the given lattice .
answered
May 20
in
Set Theory & Algebra

38
views
#discrete
#lattice
0
votes
18
GateBook Test Series: Digital Logic  Boolean Algebra
What is the time complexity for checking whether an assignment of truth values to variables $x_1,\dots ,x_n$ satisfies a given formula $f(x_1\dots,x_n)$? $O(2^n)$ $O(g(n))$ where $g$ is a polynomial $O(log(n))$ None of the above
answered
May 15
in
Digital Logic

213
views
gatebook
digitallogic
booleanalgebra
+2
votes
19
GATE2011 AG: GA3
Choose the most appropriate word from the options given below to complete the following sentence: It was her view that the country’s problem had been _________ by foreign technocrats, so that to invite them to come back would be counterproductive. identified ascertained exacerbated analysed
answered
May 14
in
Verbal Ability

70
views
generalaptitude
verbalability
gate2011ag
mostappropriateword
+1
vote
20
GATE2010 TF: GA3
Choose the most appropriate word from the options given below to complete the following sentence: The two child norm with _______ for the violators will have significant implications for oar demographic profile$.$ disincentives incitements restrictions restraints
answered
May 14
in
Verbal Ability

58
views
generalaptitude
verbalability
gate2010tf
mostappropriateword
+1
vote
21
GATE2010 TF: GA7
Consider the series $\frac{1}{2}+\frac{1}{3}\frac{1}{4}+\frac{1}{8}+\frac{1}{9}\frac{1}{16}+\frac{1}{32}+\frac{1}{27}\frac{1}{64}+\ldots.$ The sum of the infinite series above is$:$ $\infty$ $\frac{5}{6}$ $\frac{1}{2}$ $0$
answered
May 14
in
Numerical Ability

104
views
generalaptitude
numericalability
gate2010tf
numberseries
0
votes
22
#probability(self doubt)
An automobile showroom has 10 cars, 2 of which are defective. If you are going to buy the 6th car sold that day at random, then the probability of selecting a defective car is??
answered
May 13
in
Combinatory

50
views
probability
+2
votes
23
ISI2018PCBCS2
You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time. Formulate a recurrence relation for counting $a_n$, the number of distinct ways in which you can climb up the staircase. Mention the boundary conditions for your recurrence relation. Find a closed form expression for $a_n$ by solving your recurrence.
answered
May 13
in
Algorithms

47
views
isi2018pcbcs
algorithms
recurrenceeqation
descriptive
+1
vote
24
self doubt dfa
Given an algorithm to tell whether a regular language L contains at least 100 strings
answered
May 12
in
Theory of Computation

52
views
theoryofcomputation
+2
votes
25
ISI2018MMA20
Consider the set of all functions from $\{1, 2, . . . ,m\}$ to $\{1, 2, . . . , n\}$,where $n > m$. If a function is chosen from this set at random, the probability that it will be strictly increasing is $\binom{n}{m}/n^m\\$ $\binom{n}{m}/m^n\\$ $\binom{m+n1}{m1}/n^m\\$ $\binom{m+n1}{m}/m^n$
answered
May 12
in
Probability

97
views
isi2018mma
engineeringmathematics
probability
0
votes
26
ISI2018PCBCS3
An $n$variable Boolean function $f:\{0,1\}^n \rightarrow \{0,1\} $ is called symmetric if its value depends only on the number of $1’s$ in the input. Let $\sigma_n $ denote the number of such functions. Calculate the value of $\sigma_4$. Derive an expression for $\sigma_n$ in terms of $n$.
answered
May 12
in
Set Theory & Algebra

30
views
isi2018pcbcs
engineeringmathematics
discretemathematics
settheory&algebra
functions
descriptive
0
votes
27
ISI2018PCBA4
Let $A$ and $B$ are two nonempty finite subsets of $\mathbb{Z}$, the set of all integers. Define $A+B=\{a+b:a\in A,b\in B\}$.Prove that $\mid A+B \mid \geq \mid A \mid + \mid B \mid 1 $, where $\mid S \mid$ denotes the cardinality of finite set $S$.
answered
May 12
in
Set Theory & Algebra

30
views
isi2018pcba
engineeringmathematics
discretemathematics
settheory&algebra
descriptive
+1
vote
28
ISI2018MMA27
Number of real solutions of the equation $x^7 + 2x^5 + 3x^3 + 4x = 2018$ is $1$ $3$ $5$ $7$
answered
May 11
in
Numerical Ability

45
views
isi2018mma
generalaptitude
numericalability
0
votes
29
ISI2018MMA7
The greatest common divisor of all numbers of the form $p^2 − 1$, where $p \geq 7$ is a prime, is $6$ $12$ $24$ $48$
answered
May 11
in
Numerical Ability

18
views
isi2018mma
generalaptitude
numericalability
+3
votes
30
ISI2018MMA24
The sum of the infinite series $1+\frac{2}{3}+\frac{6}{3^2}+\frac{10}{3^3}+\frac{14}{3^4}+\dots $ is $2$ $3$ $4$ $6$
answered
May 11
in
Numerical Ability

55
views
isi2018mma
generalaptitude
numericalability
+2
votes
31
Made Easy Test Series:Algorithm Minimum Weight Path
Consider the following statement: $A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree. $B)$ ... minimum weight graph?? and what about B)?? Is it just saying each minimum path between $2$ vertices makes total shortest path??
answered
May 10
in
Algorithms

53
views
algorithms
madeeasytestseries
+1
vote
32
Made Easy Test Series:AlgorithmRecurrence Relation
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n1 \right )+n$
answered
May 10
in
Algorithms

144
views
algorithms
timecomplexity
recurrenceeqation
0
votes
33
Self doubt:Pumping Lemma
How by Pumping Lemma we can prove that “context free grammar generate an infinite number of strings” and here what could be pumping length ?
answered
May 9
in
Theory of Computation

59
views
theoryofcomputation
pumpinglemma
+1
vote
34
Made Easy Test Series:Algo Asymptotic Complexity
$1)n^{2019}=O\left (n^{2020} \right )$ $2)O(n^{2019})=O\left (n^{2020} \right )$ Which one is correct?? If $1)$ is correct, why $2)$ not correct?
answered
May 9
in
Algorithms

159
views
madeeasytestseries
algorithms
0
votes
35
Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
answered
May 8
in
Theory of Computation

26
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
36
Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$
answered
May 8
in
Theory of Computation

35
views
michaelsipser
theoryofcomputation
contextfreelanguages
cnf
proof
0
votes
37
Kenneth Rosen Edition 7th Exercise 2.3 Question 72 (Page No. 155)
Suppose that $f$ is a function from $A$ to $B$, where $A$ and $B$ are finite sets with $A=B$. Show that $f$ is onetoone if and only if it is onto.
answered
May 8
in
Set Theory & Algebra

37
views
kennethrosen
discretemathematics
settheory&algebra
0
votes
38
Michael Sipser Edition 3 Exercise 0 Question 11 (Page No. 27)
Let $S(n) = 1 + 2 + · · · + n$ be the sum of the first $n$ natural numbers and let $C(n) = 1^{3} + 2^{3} + · · · + n^{3}$ be the sum of the first $n$ cubes. Prove the following equalities by induction on $n,$ ... $C(n)=\frac{1}{4}(n^{4}+2n^{3}+n^{2}=\frac{1}{4}n^{2}(n+1)^{2}.$
answered
May 8
in
Theory of Computation

22
views
michaelsipser
theoryofcomputation
proof
+1
vote
39
Michael Sipser Edition 3 Exercise 1 Question 11 (Page No. 85)
Prove that every $\text{NFA}$ can be converted to an equivalent one that has a single accept state.
answered
May 8
in
Theory of Computation

45
views
michaelsipser
theoryofcomputation
nfa
proof
+2
votes
40
GATE2016EC_2
answered
May 8
in
Numerical Ability

54
views
generalaptitude
numericalability
worktime
Page:
1
2
next »
50,644
questions
56,516
answers
195,579
comments
101,139
users