Dark Mode

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$

gatecse asked in Theory of Computation Sep 13, 2019

797 views

2 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

gatecse asked in Analytical Aptitude Sep 13, 2019

509 views

1 vote

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.

gatecse asked in Analytical Aptitude Sep 13, 2019

302 views

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$

gatecse asked in Graph Theory Sep 13, 2019

604 views

1 vote

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}$

gatecse asked in Combinatory Sep 13, 2019

404 views

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}$

gatecse asked in Probability Sep 13, 2019

517 views

3 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 balls. He draws a ... $\frac{C_{n}}{\binom{2n}{n}}$ $\frac{n\cdot C_{n}}{(2n)!}$ $\frac{n\cdot C_{n}}{\binom{2n}{n}}$

gatecse asked in Probability Sep 13, 2019

404 views

3 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)

gatecse asked in Probability Sep 13, 2019

750 views

1 vote

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

gatecse asked in Graph Theory Sep 13, 2019

503 views

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.$

gatecse asked in Programming Sep 13, 2019

559 views

1 vote

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}.$

gatecse asked in Theory of Computation Sep 13, 2019

497 views

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?

gatecse asked in Analytical Aptitude Sep 13, 2019

303 views

1 vote

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.

gatecse asked in Graph Theory Sep 13, 2019

437 views

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.)

gatecse asked in Algorithms Sep 13, 2019

351 views

1 vote

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.

gatecse asked in Graph Theory Sep 13, 2019

329 views

1 vote

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.

gatecse asked in Algorithms Sep 13, 2019

358 views

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?

gatecse asked in DS Sep 13, 2019

620 views

To see more, click for the full list of questions or popular tags.

Recent questions tagged cmi2018