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 Tesla!
User Tesla!
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Tesla!
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
+1
vote
2
answers
1
Sheldon Ross
From 10 married couples, we want to select group of 6 that is not allowed to contain a married couple. How many choices are there?
asked
4 days
ago
in
Combinatory

50
views
sheldonross
permutationsandcombinations
+1
vote
1
answer
2
Sheldon Ross
Prove $\binom{m+n}{r}$ = $\binom{n}{0}\binom{m}{r}+\binom{n}{1}\binom{m}{r1}+... +\binom{n}{r}\binom{m}{0}$
asked
4 days
ago
in
Combinatory

42
views
sheldonross
permutationsandcombinations
0
votes
0
answers
3
Sheldon Ross
Determine the number of vectors ($x_{1}...x_{n}$}, such that each x$_{i}$ is either 0 or 1 and $\sum_{i=1}^{n}x_{i}\geq k$
asked
5 days
ago
in
Combinatory

49
views
sheldonross
permutationsandcombinations
0
votes
1
answer
4
CMI2017B8
Consider the following function that takes as input a sequence A of integers with n elements, A[1], A[2], . . . , A[n] and an integer k and returns an integer value. The function length(S) returns the length of sequence S. Comments ... algorithm in terms of the length of the input sequence A? (c) Give an example of a worstcase input for this algorithm.
asked
Feb 5
in
Algorithms

89
views
cmi2017
algorithms
0
votes
1
answer
5
CMI2017B6
We are given a sequence of pairs of integers (a1, b1),(a2, b2), . . .(an, bn). We would like to compute the largest k such that there is a sequence of numbers ci1 ≤ ci2 ≤ . . . ≤ cik with 1 ≤ i1 < i2 < ... < ik ≤ n and for each j ≤ k, cij = aij or cij = bij . Describe an algorithm to solve this problem and explain its complexity.
asked
Feb 5
in
Algorithms

60
views
cmi2017
algorithms
timecomplexity
0
votes
1
answer
6
CMI2017B5
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has ... , u ∈ V1 and v ∈ V2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.
asked
Feb 5
in
Graph Theory

66
views
cmi2017
graphtheory
0
votes
2
answers
7
CMI2017B4
In a party there are 2n participants, where n is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than n2
asked
Feb 5
in
Combinatory

54
views
cmi2017
handshake
permutationsandcombinations
0
votes
1
answer
8
CMI2017B3
Let Σ = {a, b}. Given words u, v ∈ Σ* , we say that v extends u if v is of the form xuy for some x, y ∈ Σ* . Given a fixed word u, we are interested in identifying whether a finite state automaton accepts some word that extends u. ... Σ* and reports Yes if some word in the language of A extends u and No if no word in the language of A extends u.
asked
Feb 5
in
Theory of Computation

53
views
cmi2017
theoryofcomputation
+1
vote
1
answer
9
CMI2017B2
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and has a name. Due to lack of coordination, the same name may be allotted to multiple ... are carrying a GoMad pass or a GoCrazy pass, you can start at s and arrive at t using the sequence σ.
asked
Feb 5
in
Algorithms

32
views
cmi2017
algorithms
0
votes
1
answer
10
CMI2017B1
Let Σ = {a, b, c}. Let Leven be the set of all even length strings in Σ* (a) Construct a deterministic finite state automaton for L$_{EVEN}$. (b) We consider an operation Erase$_{ab}$ that takes as input a string w ∈ Σ* and erases all occurrences ... Erease$_{ab}$(L):= { Erease$_{ab}$(w)  w$\in$ L} Show that Erase$_{ab}$(L$_{even}$) is a regular language.
asked
Feb 5
in
Theory of Computation

53
views
cmi2017
theoryofcomputation
+1
vote
1
answer
11
CMI2017A10
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference? (a) If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A (b) If the best ... we don't know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
asked
Feb 5
in
Algorithms

46
views
cmi2017
algorithms
theoryofcomputation
+1
vote
1
answer
12
CMI2017A09
Suppose we constructed the binary search tree shown below by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the ... (c) 1 came after 12 and 29 came before 42. (d) 3 came before 14 and 16 came before 28.
asked
Feb 5
in
Algorithms

57
views
cmi2017
algorithms
0
votes
1
answer
13
CMI2017A08
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)]. We sort these in ascending order by the second coordinate. Which of the ... , 9)] (d) [(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]
asked
Feb 5
in
Algorithms

101
views
cmi2017
algorithms
sorting
0
votes
1
answer
14
CMI2017A07
Consider the following functions f() and g(). f(){ g(){ w=5; z=w+1; w=2*z+2; z=3*zw; } print(z); } We start with w and z set to 0 and execute f() and g() in parallel—that is, at each step we either execute one statement from f() or one statement from g(). Which of the following is not a possible value printed by g()? (a) 2 (b) 1 (c) 2 (d) 4
asked
Feb 5
in
Programming

52
views
cmi2017
output
programming
0
votes
1
answer
15
CMI2017A06
What does the following function compute in terms of n and d, for integer values of d? Note that the operation / denotes floating point division, even if the arguments are both integers. function foo(n,d){ if (d == 0){ return 1; }else{ if (d < 0){ return foo(n,d ... $n^{d}$ for all values of d (c) n*d if d>0, n/d if d<0 (d) n*d for all values of d
asked
Feb 5
in
Programming

71
views
programminginc
programming
cmi2017
+1
vote
1
answer
16
CMI2017A05
Let G be an arbitrary graph on n vertices with 4n − 16 edges. Consider the following statements: I There is a vertex of degree smaller than 8 in G. II There is a vertex such that there are less than 16 vertices at distance exactly 2 from it. Which of the following is true: (a) I only (c) Both I and II (b) II only (d) Neither I nor II
asked
Feb 5
in
Graph Theory

50
views
graphtheory
cmi2017
0
votes
1
answer
17
CMI2017A04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be ... Find a spanning tree with minimum (c) Find a minimal coloring. (d) Find a minimum size vertex cover.
asked
Feb 5
in
Graph Theory

36
views
algorithms
graphalgorithms
cmi2017
+1
vote
1
answer
18
CMI2017A03
Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a Tshirt, then Aditi gets bangles. If Abhay does not get shoes or Aditi gets bangles, the mother will be happy. Which of the following is ... is not happy, then Asha did not get a necklace and Arun did not get a Tshirt. (d) None of the above.
asked
Feb 5
in
Mathematical Logic

64
views
mathematicallogic
cmi2017
+2
votes
1
answer
19
CMI2017A02
An FM radio channel has a repository of 10 songs. Each day, the channel plays 3 distinct songs that are chosen randomly from the repository. Mary decides to tune in to the radio channel on the weekend after her exams. What is the probability that no song gets ... 3 \end{pmatrix}*\begin{pmatrix} 7\\ 3 \end{pmatrix}*\begin{pmatrix} 10\\ 6 \end{pmatrix}^{1}$
asked
Feb 5
in
Probability

88
views
permutationsandcombinations
probability
cmi2017
+3
votes
1
answer
20
CMI2017A01
The regular expression (a*+b)* is equivalent to which of the following regular expressions: (a) a*b* (b) (a*b+b)* (c) (a+b*)* (d) (a*b)*
asked
Feb 5
in
Theory of Computation

178
views
theoryofcomputation
regularexpressions
cmi2017
+2
votes
0
answers
21
Hamacher
7.14 A pipeline processor uses the delayed branch technique. You are asked to recommend one of the two possibilities for the design of this processor. In the first possibility, the processor has a four stage pipeline and one delay slot, and in ... single delay slot. For the second alternative, the compiler is able to fill the second slot 25 percent of the time.
asked
Dec 19, 2017
in
CO & Architecture

66
views
carlhamacher
pipelining
coandarchitecture
+5
votes
1
answer
22
Gilbert Strang
How many n*n (0,1) matrix are invertable ? PS: original question in book is for 2*2
asked
Oct 23, 2017
in
Linear Algebra

106
views
matrix
gilbertstrang
linearalgebra
+1
vote
0
answers
23
Self Doubt
Let < G, * > be a finite group and let H1 and H2 be it's sub group as per lagrange theorem we know order of sub group divides order of group, my doubt is, is it possible that we can have multiple subgroup of same cardinality for a particular group ? $\left  H1 \right =\left  H2 \right $
asked
Oct 21, 2017
in
Set Theory & Algebra

50
views
groups
#grouptheory
#discrete
+1
vote
1
answer
24
Tremblay and Manohar
S={2,a,{3},4} and R={{a},3,4,1} indicate whether the following are true or false 1) $\varnothing \subset R$ 2)$\varnothing \subseteq \left \{ \left \{ a \right \} \right \}\subseteq R\subseteq E$ E=Universal Set 3) $\left \{ \varnothing \right \}\subseteq S$ 4) $\varnothing \in R$ I think 1,2 are true and 3 is false and about 4 nothing is clear
asked
Jul 26, 2017
in
Set Theory & Algebra

132
views
discretemathematics
settheory&algebra
+1
vote
1
answer
25
Set Theory Doubt
Want to verify let set $\left  A \right =n$ and $\left  B \right =m$ Then $max(m,n)\leq \left  A\cup B \right \leq (m+n)$ $0\leq \left  A\cap B \right \leq min(m,n)$ $0\leq \left  A B \right \ ... here $\bigoplus$ is symmetric difference $0\leq \left  \overline{A} \right \leq U$ here $\overline{A}$ is compliment of A and U is universal Set
asked
Jul 25, 2017
in
Set Theory & Algebra

84
views
discretemathematics
settheory&algebra
sets
0
votes
1
answer
26
IIITHPGEE 2017
Consider 3 card one having both side painted red another having both side printed black and last having one side black and another side red, 3 cards are put in a hat and are mixed properly, now one card in picked and put down on table, its face up color is red what is probability that another side will be black.
asked
Apr 30, 2017
in
Probability

204
views
iiithpgee
probability
0
votes
1
answer
27
PGEE 2017
P1: Number of onetoone function from A$\bigotimes A$ is 1. P2: Function A>B is bijective C>D is bijective then AC and BD is also bijective. P3: Consider set A,B,C,D then ($A\cup B\cap C\cup D) == (A\cap B\cup C\cap D$) which of above statement are true and which are false
asked
Apr 30, 2017
in
Set Theory & Algebra

150
views
iiithpgee
discretemathematics
settheory&algebra
0
votes
2
answers
28
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y What would be maximum path length between any two vertices of graph ?
asked
Apr 30, 2017
in
Graph Theory

151
views
iiithpgee
graphtheory
+1
vote
1
answer
29
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Which vertex will have highest in degree ?
asked
Apr 30, 2017
in
Graph Theory

79
views
iiithpgee
graphtheory
0
votes
0
answers
30
PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Find number of strongly connected components
asked
Apr 30, 2017
in
Graph Theory

85
views
iiithpgee
graphtheory
connectedcomponents
Page:
1
2
next »
33,715
questions
40,263
answers
114,377
comments
38,899
users