Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged cmi2017
5
votes
2
answers
1
CMI2017-B-7
Consider the following function that takes as input a sequence $A$ of integers with n elements,$A[1],A[2], \dots ,A[n]$ and an integer $k$ and returns an integer value. The function length$(S)$ returns the length of the sequence $S$. Comments ... complexity of this algorithm in terms of the length of the input sequence $A$? Give an example of a worst-case input for this algorithm.
Consider the following function that takes as input a sequence $A$ of integers with n elements,$A ,A , \dots ,A[n]$ and an integer $k$ and returns an integer value. The f...
Tesla!
1.5k
views
Tesla!
asked
Feb 5, 2018
Algorithms
cmi2017
algorithms
time-complexity
descriptive
+
–
1
votes
2
answers
2
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...
Tesla!
731
views
Tesla!
asked
Feb 5, 2018
Algorithms
cmi2017
algorithms
time-complexity
descriptive
+
–
1
votes
3
answers
3
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...
Tesla!
1.3k
views
Tesla!
asked
Feb 5, 2018
Graph Theory
cmi2017
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
descriptive
+
–
2
votes
3
answers
4
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...
Tesla!
1.0k
views
Tesla!
asked
Feb 5, 2018
Combinatory
cmi2017
engineering-mathematics
discrete-mathematics
combinatory
descriptive
+
–
0
votes
1
answer
5
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...
Tesla!
469
views
Tesla!
asked
Feb 5, 2018
Theory of Computation
cmi2017
theory-of-computation
finite-automata
descriptive
+
–
2
votes
1
answer
6
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 ...
Tesla!
429
views
Tesla!
asked
Feb 5, 2018
Algorithms
cmi2017
algorithms
algorithm-design
+
–
0
votes
2
answers
7
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...
Tesla!
489
views
Tesla!
asked
Feb 5, 2018
Theory of Computation
cmi2017
theory-of-computation
finite-automata
+
–
3
votes
2
answers
8
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...
Tesla!
2.3k
views
Tesla!
asked
Feb 4, 2018
Algorithms
cmi2017
algorithms
reduction
p-np-npc-nph
+
–
1
votes
2
answers
9
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...
Tesla!
795
views
Tesla!
asked
Feb 4, 2018
DS
cmi2017
data-structures
binary-search-tree
+
–
7
votes
2
answers
10
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, ...
Tesla!
2.1k
views
Tesla!
asked
Feb 4, 2018
Algorithms
cmi2017
algorithms
sorting
+
–
0
votes
2
answers
11
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...
Tesla!
598
views
Tesla!
asked
Feb 4, 2018
Programming in C
cmi2017
programming
output
+
–
1
votes
3
answers
12
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...
Tesla!
717
views
Tesla!
asked
Feb 4, 2018
Programming in C
cmi2017
programming
output
+
–
2
votes
2
answers
13
CMI2017-A-05
Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements: There is a vertex of degree smaller than $8$ in $G$. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is true: I Only II Only Both I and II Neither I nor II
Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements:There is a vertex of degree smaller than $8$ in $G$.There is a ver...
Tesla!
1.2k
views
Tesla!
asked
Feb 4, 2018
Graph Theory
cmi2017
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
+
–
0
votes
2
answers
14
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...
Tesla!
1.1k
views
Tesla!
asked
Feb 4, 2018
Graph Theory
cmi2017
graph-connectivity
easy
+
–
9
votes
2
answers
15
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...
Tesla!
855
views
Tesla!
asked
Feb 4, 2018
Analytical Aptitude
cmi2017
logical-reasoning
+
–
8
votes
2
answers
16
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...
Tesla!
1.1k
views
Tesla!
asked
Feb 4, 2018
Probability
cmi2017
engineering-mathematics
probability
+
–
7
votes
3
answers
17
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)^*$
Tesla!
923
views
Tesla!
asked
Feb 4, 2018
Theory of Computation
cmi2017
theory-of-computation
regular-expression
+
–
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