Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged cmi2019
2
votes
3
answers
1
CMI2019-A-1
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not context-free context-free, but not regular both regular and context-free neither regular nor context-free
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$The language $L_{1}\cup L_{2}$ is:regular...
gatecse
844
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2019
regular-language
context-free-language
closure-property
+
–
1
votes
2
answers
2
CMI2019-A-2
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true? The shortest word in $L(A)$ has length at most $n-1.$ The shortest word in $L(A)$ has length at least $n.$ The shortest word not in $L(A)$ has length at most $n-1.$ The shortest word not in $L(A)$ has length at least $n.$
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true?The shortest word in $L(A)$ has length at most $n-1.$The shortest word in $L(A)$ has lengt...
gatecse
850
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2019
finite-automata
+
–
5
votes
4
answers
3
CMI2019-A-3
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node $A?$ $D$ $H$ $I$ $M$
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, i...
gatecse
2.3k
views
gatecse
asked
Sep 13, 2019
DS
cmi2019
data-structures
tree
binary-search-tree
+
–
2
votes
2
answers
4
CMI2019-A-4
There are five buckets, each of which can be open or closed. An arrangement is a specification of which buckets are open and which bucket are closed. Every person likes some of the arrangements and dislikes the rest. You host a party, and amazingly, no two people on the guest list have the ... What is the maximum number of guests possible? $5^{2}$ $\binom{5}{2}$ $2^{5}$ $2^{2^{5}}$
There are five buckets, each of which can be open or closed. An arrangement is a specification of which buckets are open and which bucket are closed. Every person likes s...
gatecse
689
views
gatecse
asked
Sep 13, 2019
Combinatory
cmi2019
combinatory
arrangements
+
–
3
votes
3
answers
5
CMI2019-A-5
Let $\pi=[x_{1},x_{2},\cdots,x_{n}]$ be a permutation of $\{1,2,\cdots,n\}.$ For $k<n,$ we say that $\pi$ has its first ascent at $k$ if $x_{1}>x_{2}\cdots>x_{k}$ and $x_{k}<x_{k+1}.$ How many permutations have their first ascent at $k?$ $\binom{n}{k}-\binom{n}{(k+1)}$ $\frac{n!}{k!}-\frac{n!}{(k+1)!}$ $\frac{n!}{(k+1)!}-\frac{n!}{(k+2)!}$ $\binom{n}{(k+1)}-\binom{n}{(k+2)}$
Let $\pi=[x_{1},x_{2},\cdots,x_{n}]$ be a permutation of $\{1,2,\cdots,n\}.$ For $k<n,$ we say that $\pi$ has its first ascent at $k$ if $x_{1}>x_{2}\cdots>x_{k}$ and $x_...
gatecse
644
views
gatecse
asked
Sep 13, 2019
Combinatory
cmi2019
combinatory
+
–
3
votes
3
answers
6
CMI2019-A-6
Suppose you alternate between throwing a normal six-sided fair die and tossing a fair coin. You start by throwing the die. What is the probability that you will see a $5$ on the die before you see tails on the coin? $\frac{1}{12}$ $\frac{1}{6}$ $\frac{2}{9}$ $\frac{2}{7}$
Suppose you alternate between throwing a normal six-sided fair die and tossing a fair coin. You start by throwing the die. What is the probability that you will see a $5$...
gatecse
1.8k
views
gatecse
asked
Sep 13, 2019
Probability
cmi2019
probability
+
–
4
votes
2
answers
7
CMI2019-A-7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered ...
gatecse
769
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2019
graph-theory
graph-coloring
spanning-tree
vertex-cover
descriptive
+
–
0
votes
2
answers
8
CMI2019-A-8
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario? We know of polynomial time algorithms for both A and B. We only know of exponential time algorithms for both A and B. We only ... polynomial time algorithm for B. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario?We know of polynomial time algorithms for b...
gatecse
625
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2019
reduction
p-np-npc-nph
+
–
4
votes
3
answers
9
CMI2019-A-9
The next two questions refer to the following program. In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment $A[i],A[i+1],\cdots,A[j].$ ... } reverse(A,i,m); } return; } When the procedure terminates, the array A has been: Sorted in descending order Sorted in ascending order Reversed Left unaltered
The next two questions refer to the following program.In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment ...
gatecse
880
views
gatecse
asked
Sep 13, 2019
Programming in C
cmi2019
identify-function
+
–
1
votes
3
answers
10
CMI2019-A-10
The next two questions refer to the following program. In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment $A[i],A[i+1],\cdots,A[j].$ For instance if $A=[0,1,2,3,4,5,6,7]$ then, after we ... return; } The number of times the test $A[ j ] > A[ m ]$ is executed is: $4950$ $5050$ $10000$ Depends on the contents of $A$
The next two questions refer to the following program.In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment ...
gatecse
607
views
gatecse
asked
Sep 13, 2019
Programming in C
cmi2019
identify-function
+
–
3
votes
3
answers
11
CMI2019-B-1
Consider an alphabet $\Sigma=\{a,b\}.$ Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}b.$ Define $L:=\{u\in\Sigma^{\ast}\mid \exists w\in L_{2}\: s.t.\: uw\in L_{1}\}.$ Give an example of a word in $L.$ Give an example of a word not in $L.$ Construct an NFA for $L.$
Consider an alphabet $\Sigma=\{a,b\}.$Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}...
gatecse
1.5k
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2019
regular-expression
regular-language
finite-automata
+
–
1
votes
1
answer
12
CMI2019-B-2
Let us assume a binary alphabet $\Sigma=\{a,b\}.$ Two words $u,v\in \Sigma^{\ast}$ are said to be conjugates if there exist $w_{1},w_{2}\in \Sigma^{\ast}$ such that $u=w_{1}w_{2}$ and $v=w_{2}w_{1}.$ Prove that $u$ and $v$ are conjugates if and only if there exists $w\in \Sigma^{\ast}$ such that $uw=wv.$
Let us assume a binary alphabet $\Sigma=\{a,b\}.$ Two words $u,v\in \Sigma^{\ast}$ are said to be conjugates if there exist $w_{1},w_{2}\in \Sigma^{\ast}$ such that $u=w_...
gatecse
356
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2019
theory-of-computation
conjugates
strings
+
–
0
votes
1
answer
13
CMI2019-B-3
There is a party of $n$ people. Each attendee has at most $r$ friends in the party. The friend circle of a person includes the person and all her friends. You are required to pick some people for a party game, with the restriction that at most one person is picked from each friend circle. Show that you can pick $\dfrac{n}{r^{2}+1}$ people for the game.
There is a party of $n$ people. Each attendee has at most $r$ friends in the party. The friend circle of a person includes the person and all her friends. You are require...
gatecse
664
views
gatecse
asked
Sep 13, 2019
Combinatory
cmi2019
combinatory
pigeonhole-principle
+
–
0
votes
2
answers
14
CMI2019-B-4
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph....
gatecse
687
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2019
graph-connectivity
+
–
2
votes
2
answers
15
CMI2019-B-5
In the land of Twitter, there are two kinds of people: knights (also called outragers), who always tell the truth, and knaves (also called trolls), who always lie. It so happened that a person with handle @anand tweeted something offensive. It was not known ... $3:$ My lawyer always tells the truth. Which of the above suspects are innocent, and which are guilty? Explain your reasoning.
In the land of Twitter, there are two kinds of people: knights (also called outragers), who always tell the truth, and knaves (also called trolls), who always lie. It so ...
gatecse
691
views
gatecse
asked
Sep 13, 2019
Mathematical Logic
cmi2019
mathematical-logic
logical-reasoning
descriptive
+
–
1
votes
2
answers
16
CMI2019-B-6
Let $A$ be an $n\times n $ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If $k$ is present, we should report its position - that is, the row $i$ and ... $A.$ Justify the complexity of your algorithm. For both algorithms, describe a worst-case input where $k$ is present in $A.$
Let $A$ be an $n\times n $ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If ...
gatecse
661
views
gatecse
asked
Sep 13, 2019
Algorithms
cmi2019
algorithms
algorithm-design
descriptive
+
–
1
votes
1
answer
17
CMI2019-B-7
A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated ... , the score the professor needs to award each student. Describe the space and time complexity of your dynamic programming algorithm.
A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award mark...
gatecse
727
views
gatecse
asked
Sep 13, 2019
Algorithms
cmi2019
algorithms
dynamic-programming
descriptive
non-gate
+
–
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