Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged cmi2018
4
votes
4
answers
1
CMI2018-A-1
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$?$aba$$bab$$abba$$aabb$
gatecse
1.1k
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2018
regular-language
regular-expression
easy
+
–
3
votes
3
answers
2
CMI2018-A-2
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend. If Deepa does not attend, which of the following is true? Chetan does not attend Akash does not attend either (A) or (B) none of the above
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend....
gatecse
693
views
gatecse
asked
Sep 13, 2019
Analytical Aptitude
cmi2018
logical-reasoning
+
–
1
votes
2
answers
3
CMI2018-A-3
In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional information that can determine the winner? Geetha finishes ahead of Divya and Vani finishes ahead of Shalini. Aparna finishes ahead of Shalini. Divya finishes ahead of Geetha. None of the above.
In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional ...
gatecse
492
views
gatecse
asked
Sep 13, 2019
Analytical Aptitude
cmi2018
logical-reasoning
+
–
6
votes
3
answers
4
CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...
gatecse
794
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
shortest-path
+
–
1
votes
2
answers
5
CMI2018-A-5
How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$ $\binom{2m}{n}$ $\binom{m}{n}$ $\binom{m+n}{n}$ $m^{n}$
How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$$\binom...
gatecse
648
views
gatecse
asked
Sep 13, 2019
Combinatory
cmi2018
combinatory
+
–
3
votes
2
answers
6
CMI2018-A-6
You are given two coins $A$ and $B$ that look identical. The probability that coin $A$ turns up heads is $\frac{1}{4}$, while the probability that coin $B$ turns up heads is $\frac{3}{4}.$ You choose one of the coins at random and toss it twice. If both the outcomes are heads, what is the probability that you chose coin $B?$ $\frac{1}{16}$ $\frac{1}{2}$ $\frac{9}{16}$ $\frac{9}{10}$
You are given two coins $A$ and $B$ that look identical. The probability that coin $A$ turns up heads is $\frac{1}{4}$, while the probability that coin $B$ turns up heads...
gatecse
776
views
gatecse
asked
Sep 13, 2019
Probability
cmi2018
conditional-probability
+
–
5
votes
2
answers
7
CMI2018-A-7
Let $C_{n}$ be the number of strings $w$ consisting of $n$ $X's$ and $n$ $Y's$ such that no initial segment of $w$ has more $Y's$ than $X's.$ Now consider the following problem. A person stands on the edge of a swimming pool holding a bag of $n$ red and $n$ blue ... $\frac{C_{n}}{\binom{2n}{n}}$ $\frac{n\cdot C_{n}}{(2n)!}$ $\frac{n\cdot C_{n}}{\binom{2n}{n}}$
Let $C_{n}$ be the number of strings $w$ consisting of $n$ $X's$ and $n$ $Y's$ such that no initial segment of $w$ has more $Y's$ than $X's.$ Now consider the following p...
gatecse
603
views
gatecse
asked
Sep 13, 2019
Probability
cmi2018
conditional-probability
balls-in-bins
+
–
4
votes
2
answers
8
CMI2018-A-8
There are $7$ switches on a switchboard, some of which are on and some of which are off. In one move, you pick any $2$ switches and toggle each of them-if the switch you pick is currently off, you turn it on, if it is on, you turn it off. Your aim is to execute a sequence of ... (off,on,off,on,off,off,on) (off,on,on,on,on,on,off) (on,off,on,on,on,on,on) (off,off,off,off,off,on,off)
There are $7$ switches on a switchboard, some of which are on and some of which are off. In one move, you pick any $2$ switches and toggle each of them-if the switch you ...
gatecse
1.0k
views
gatecse
asked
Sep 13, 2019
Probability
cmi2018
conditional-probability
+
–
1
votes
1
answer
9
CMI2018-A-9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes plac...
gatecse
804
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
graph-connectivity
graph-matching
independent-set
descriptive
+
–
4
votes
3
answers
10
CMI2018-A-10
What does the following function compute in terms of $n$ and $d$, for integer value of $n$ and $d,d>1?$ Note that $a//b$ denotes the quotient(integer part) of $a \div b,$ for integers $a$ and $b$. For instance $7//3$ is $2.$ function foo(n,d) ... $n.$ The number of digits in the base $d$ representation of $n.$ The number of ways of partitioning $n$ elements into groups of size $d.$
What does the following function compute in terms of $n$ and $d$, for integer value of $n$ and $d,d>1?$ Note that $a//b$ denotes the quotient(integer part) of $a \div b,$...
gatecse
882
views
gatecse
asked
Sep 13, 2019
Programming in C
cmi2018
identify-function
+
–
1
votes
2
answers
11
CMI2018-B-1
Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$Give an example ...
gatecse
644
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2018
finite-automata
descriptive
+
–
0
votes
2
answers
12
CMI2018-B-2
A student requests a recommendation letter from a professor. The professor gives three sealed envelopes. Each envelope contains either a good recommendation letter or a bad recommendation letter. Make a list of all the possible scenarios. Suppose now the professor tells ... and the other two are false. Can the student find out the contents of the envelopes without breaking their seals?
A student requests a recommendation letter from a professor. The professor gives three sealed envelopes. Each envelope contains either a good recommendation letter or a b...
gatecse
557
views
gatecse
asked
Sep 13, 2019
Analytical Aptitude
cmi2018
descriptive
logical-reasoning
+
–
1
votes
2
answers
13
CMI2018-B-3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...
gatecse
657
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
graph-connectivity
descriptive
+
–
2
votes
2
answers
14
CMI2018-B-4
You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by $2$ positions. Give an $O(\log n)$ time algorithm to find the largest element in a circularly shifted array. (The number of positions through which it has been shifted is unknown to you.)
You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by ...
gatecse
605
views
gatecse
asked
Sep 13, 2019
Algorithms
cmi2018
algorithm-design
descriptive
+
–
1
votes
1
answer
15
CMI2018-B-5
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if ... any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\...
gatecse
443
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
undirected-graph
graph-connectivity
connected-components
descriptive
+
–
1
votes
2
answers
16
CMI2018-B-6
You are playing an old-style video game in which you have to shoot down alien spaceships as they fly across the screen from left to right. Each spaceship flies across the screen at a specified height. You have an antiaircraft gun set to shoot down all ... space ships. Each gun can be initialized separately to a firing height and each gun can be separately reset to a lower value.
You are playing an old-style video game in which you have to shoot down alien spaceships as they fly across the screen from left to right. Each spaceship flies across the...
gatecse
650
views
gatecse
asked
Sep 13, 2019
Algorithms
cmi2018
descriptive
algorithm-design
+
–
2
votes
3
answers
17
CMI2018-B-7
A First In First Out queue is a data structure supporting the operation Enque, Deque, Print, Enque(x) adds the item $x$ to the tail of the queue. Deque removes the element at the head of the queue and returns its value. Print prints the head of the ... reverse order. If the queue had $n$ elements to begin with, how many statements would you need to print the queue in reverse order?
A First In First Out queue is a data structure supporting the operation Enque, Deque, Print, Enque(x) adds the item $x$ to the tail of the queue. Deque removes the elemen...
gatecse
944
views
gatecse
asked
Sep 13, 2019
DS
cmi2018
data-structures
queue
descriptive
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register