Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
soujanyareddy13
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Answers by soujanyareddy13
0
votes
181
CMI2017-B-6
We are given a sequence of pairs of integers $(a_1, b_1),(a_2, b_2), \dots ,(a_n, b_n)$. We would like to compute the largest $k$ such that there is a sequence of numbers $c_{i_1} \leq c_{i_2} \leq \dots \leq c_{i_k}$ ... each $j \leq k$, $c_{i_j}=a_{i_j}$ or $c_{i_j} = b_{i_j}$ . Describe an algorithm to solve this problem and explain its complexity.
We are given a sequence of pairs of integers $(a_1, b_1),(a_2, b_2), \dots ,(a_n, b_n)$. We would like to compute the largest $k$ such that there is a sequence of numbers...
700
views
answered
May 6, 2021
Algorithms
cmi2017
algorithms
time-complexity
descriptive
+
–
0
votes
182
CMI2017-B-5
An undirected graph is $\text{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 $\text{leaf}$ in a tree is a vertex that ... $ \in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.
An undirected graph is $\text{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 co...
1.3k
views
answered
May 6, 2021
Graph Theory
cmi2017
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
descriptive
+
–
0
votes
183
CMI2017-B-4
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 $n^2.$
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 partic...
1.0k
views
answered
May 6, 2021
Combinatory
cmi2017
engineering-mathematics
discrete-mathematics
combinatory
descriptive
+
–
0
votes
184
CMI2017-B-3
Let $Σ = \{a, b\}$. Given words $u, v \in Σ*$ , we say that $v$ extends $u$ if $v$ is of the form $xuy$ for some $x, y ∈ Σ^*$ . Given a fixed word $u$ ... Yes if some word in the language of $\mathcal{A}$ extends $u$ and No if no word in the language of $\mathcal{A}$ extends $u$.
Let $Σ = \{a, b\}$. Given words $u, v \in Σ*$ , we say that $v$ extends $u$ if $v$ is of the form $xuy$ for some $x, y ∈ Σ^*$ . Given a fixed word $u$, we are inter...
450
views
answered
May 6, 2021
Theory of Computation
cmi2017
theory-of-computation
finite-automata
descriptive
+
–
0
votes
185
CMI2017-B-2
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 routes. To make matters ... are carrying a GoMad pass or a GoCrazy pass, you can start at $s$ and arrive at $t$ using the sequence $σ$.
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 ...
411
views
answered
May 6, 2021
Algorithms
cmi2017
algorithms
algorithm-design
+
–
0
votes
186
CMI2017-B-1
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 \in Σ^*$ and erases all occurrences of the ... $L:$ $Erase_{ab}(L)$:= $\{ Erase_{ab}(w)\ |\ w\in L\}$ Show that $Erase_{ab}(L_{even}$) is a regular language.
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 a...
460
views
answered
May 6, 2021
Theory of Computation
cmi2017
theory-of-computation
finite-automata
+
–
0
votes
187
CMI2017-A-10
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference? If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$ ... don't know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference?If the best algorithm for $B$ takes exponenti...
2.2k
views
answered
May 6, 2021
Algorithms
cmi2017
algorithms
reduction
p-np-npc-nph
+
–
0
votes
188
CMI2017-A-09
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 input sequence $cannot$ be ... came after $12$ and $29$ came before $42$. $3$ came before $14$ and $16$ came before $28$.
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...
753
views
answered
May 6, 2021
DS
cmi2017
data-structures
binary-search-tree
+
–
0
votes
189
CMI2017-A-08
A $\text{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 following ... $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
A $\text{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, ...
2.0k
views
answered
May 6, 2021
Algorithms
cmi2017
algorithms
sorting
+
–
0
votes
190
CMI2017-A-07
Consider the following functions f() and g(). f(){ g(){ w=5; z=w+1; w=2*z+2; z=3*z-w; } 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()$ ? $-2$ $-1$ $2$ $4$
Consider the following functions f() and g(). f(){ g(){ w=5; z=w+1; w=2*z+2; z=3*z-w; } print(z); }We start with $w$ and $z$ set to $0$ and execute $f()$ and $g()$ in par...
564
views
answered
May 6, 2021
Programming in C
cmi2017
programming
output
+
–
1
votes
191
CMI2017-A-06
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+1)/n; ... values of $d$. $n \times d$ if $d>0$ ,$n\div d$ if $d<0$. $n \times d$ for all the values of $d$.
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 arg...
679
views
answered
May 6, 2021
Programming in C
cmi2017
programming
output
+
–
0
votes
192
CMI2017-A-04
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 located at ... number of edges. Find a spanning tree with minimum cost. Find a minimal coloring. Find a minimum size vertex cover.
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 an...
1.0k
views
answered
May 6, 2021
Graph Theory
cmi2017
graph-connectivity
easy
+
–
0
votes
193
CMI2017-A-03
Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a T-shirt, then Aditi gets bangles. If Abhay does not get shoes or Aditi gets bangles, the mother will be happy. Which of the following is TRUE? If the ... shoes. If the mother is not happy, then Asha did not get a necklace and Arun did not get a T-shirt. None of the above.
Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a T-shirt, then Aditi gets bangles. If Abhay does not ge...
829
views
answered
May 4, 2021
Analytical Aptitude
cmi2017
logical-reasoning
+
–
1
votes
194
CMI2017-A-02
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 repeated during ...
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...
1.1k
views
answered
May 4, 2021
Probability
cmi2017
engineering-mathematics
probability
+
–
0
votes
195
CMI2017-A-01
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$ $(a^*b+b)^*$ $(a+b^*)^*$ $(a^*b)^*$
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$$(a^*b+b)^*$ $(a+b^*)^*$$(a^*b)^*$
896
views
answered
May 4, 2021
Theory of Computation
cmi2017
theory-of-computation
regular-expression
+
–
0
votes
196
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...
911
views
answered
May 4, 2021
DS
cmi2018
data-structures
queue
descriptive
+
–
0
votes
197
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...
608
views
answered
May 4, 2021
Algorithms
cmi2018
descriptive
algorithm-design
+
–
0
votes
198
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\...
425
views
answered
May 4, 2021
Graph Theory
cmi2018
graph-theory
undirected-graph
graph-connectivity
connected-components
descriptive
+
–
0
votes
199
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 ...
584
views
answered
May 4, 2021
Algorithms
cmi2018
algorithm-design
descriptive
+
–
0
votes
200
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...
625
views
answered
May 4, 2021
Graph Theory
cmi2018
graph-theory
graph-connectivity
descriptive
+
–
0
votes
201
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...
533
views
answered
May 4, 2021
Analytical Aptitude
cmi2018
descriptive
logical-reasoning
+
–
0
votes
202
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 ...
621
views
answered
May 4, 2021
Theory of Computation
cmi2018
finite-automata
descriptive
+
–
0
votes
203
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,$...
833
views
answered
May 4, 2021
Programming in C
cmi2018
identify-function
+
–
0
votes
204
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 ...
976
views
answered
May 4, 2021
Probability
cmi2018
conditional-probability
+
–
0
votes
205
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...
577
views
answered
May 4, 2021
Probability
cmi2018
conditional-probability
balls-in-bins
+
–
1
votes
206
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...
739
views
answered
May 4, 2021
Probability
cmi2018
conditional-probability
+
–
0
votes
207
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...
604
views
answered
May 4, 2021
Combinatory
cmi2018
combinatory
+
–
0
votes
208
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.$ ...
752
views
answered
May 4, 2021
Graph Theory
cmi2018
graph-theory
shortest-path
+
–
0
votes
209
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....
664
views
answered
May 4, 2021
Analytical Aptitude
cmi2018
logical-reasoning
+
–
0
votes
210
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 ...
459
views
answered
May 4, 2021
Analytical Aptitude
cmi2018
logical-reasoning
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register