Answers by soujanyareddy13 / GATE Overflow for GATE CSE

0 votes

211

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$

1.1k views

answered May 4, 2021

0 votes

212

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

743 views

answered May 4, 2021

0 votes

213

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

708 views

answered May 4, 2021

0 votes

214

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

692 views

answered May 4, 2021

0 votes

215

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

720 views

answered May 4, 2021

0 votes

216

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

681 views

answered May 4, 2021

0 votes

217

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

368 views

answered May 4, 2021

0 votes

218

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

1.6k views

answered May 4, 2021

0 votes

219

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

635 views

answered May 4, 2021

0 votes

220

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

922 views

answered May 4, 2021

0 votes

221

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

656 views

answered May 4, 2021

0 votes

222

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

800 views

answered May 4, 2021

0 votes

223

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

1.9k views

answered May 4, 2021

0 votes

224

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

662 views

answered May 4, 2021

0 votes

225

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

2.4k views

answered May 4, 2021

0 votes

226

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

876 views

answered May 4, 2021

0 votes

227

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

884 views

answered May 4, 2021

0 votes

228

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

699 views

answered May 4, 2021

0 votes

229

CMI2020-B: 7
We are given an array of $N$ words $W[1\dots N],$ and a length array $L[1\dots N]$, where each $L[i]$ denotes the length (number of characters) of $W[i]$. We are also given a line width $M$ ... $N$?

We are given an array of $N$ words $W[1\dots N],$ and a length array $L[1\dots N]$, where each $L[i]$ denotes the length (number of characters) of $W[i]$. We are also giv...

210 views

answered May 4, 2021

0 votes

230

CMI2020-B: 6
A password contains exactly $6$ characters. Each character is either a lowercase letter $\{a,b,\dots,z\}$ or a digit $\{ 0,1,\dots,9\}$. A valid password should contain at least one digit. What is the total number of valid passwords? Here is an incorrect ... a justification for your answer. You do not need to simplify your expressions (for example, you can write $26^5, 5!, etc.$).

A password contains exactly $6$ characters. Each character is either a lowercase letter $\{a,b,\dots,z\}$ or a digit $\{ 0,1,\dots,9\}$. A valid password should contain a...

360 views

answered May 4, 2021

1 votes

231

CMI2020-B: 5
Let $\Sigma=\{a,b\}.$ For two non-empty languages $L_1$ and $L_2$ over $\Sigma$, we define $Mix(L_1,L_2)$ to be $\{w_1\;u\;w_2\;v\;w_3|\;u\in L_1,v\in L_2,w_1,w_2,w_3\in \Sigma^*\}$. Give two languages $L_1$ and $L_2$ ... are regular, the language $Mix(L_1,L_2)$ is also regular. Provide languages $L_1$ and $L_2$ that are not regular, for which $Mix(L_1,L_2)$ is regular.

Let $\Sigma=\{a,b\}.$ For two non-empty languages $L_1$ and $L_2$ over $\Sigma$, we define $Mix(L_1,L_2)$ to be $\{w_1\;u\;w_2\;v\;w_3|\;u\in L_1,v\in L_2,w_1,w_2,w_3\in ...

152 views

answered May 4, 2021

0 votes

232

CMI2020-B: 4
Consider the procedure $\text{MYSTERY}$ described in pseudocode below. The procedure takes two non-negative integers as arguments. For a real number $x$ the notation $[x]$ denotes the largest integer which is not larger than $x$. $\text{MYSTERY (p,q)}$ ... $MYSTERY(m,n)$ return for $m,n\underline> 0?$ Justify your answer with a proof.

Consider the procedure $\text{MYSTERY}$ described in pseudocode below. The procedure takes two non-negative integers as arguments. For a real number $x$ the notation $[x]...

183 views

answered May 4, 2021

0 votes

233

CMI2020-B: 3
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Prove or disprove: There exists a finite, undirected, simple graph with at least two vertices in which each vertex has a different degree. To give ... draw an example of such a graph. To disprove the result, you should provide an argument as to why such a graph cannot exist.

A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges.Prove or disprove: There exists a finite, undirected, simple...

146 views

answered May 4, 2021

0 votes

234

CMI2020-B: 2
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Assume we are dealing with finite, undirected, simple graphs with at least two vertices. A graph is connected if there is a path between any two ... there exist a graph $G$ with at least two vertices such that both $G$ and $\overline G$ are connected? Justify your answer.

A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Assume we are dealing with finite, undirected, simple graph...

176 views

answered May 4, 2021

0 votes

235

CMI2020-B: 1
There are two cities, City $X$ and City $Y$. Each city has a metro system consisting of three different lines - red line, blue line, and green line. Each station (in both cities) is classified as either $interesting\; or\; uninteresting,$ depending on ... colours following which one can reach an interesting destination from the City Centre in $X$, but not from the City Centre in $Y$.

There are two cities, City $X$ and City $Y$. Each city has a metro system consisting of three different lines – red line, blue line, and green line. Each station (in bo...

172 views

answered May 4, 2021

0 votes

236

CMI2020-A: 10
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $R(m)$, which runs in exponential time in $m$. Thankfully, $P$ is ... is proportional to $log\;n.$ $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<log \;n.$

We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$...

284 views

answered May 4, 2021

0 votes

237

CMI2020-A: 9
A fair coin is repeatedly tossed. Each time a head appears, $1$ rupee is added to the first bag. Each time a tail appears, $2$ rupees are put in the second bag. What is the probability that both the bags have the same amount of money after $6$ coin tosses? $\frac{1}{2^6}$ $\frac{6!}{2!\cdot 4!\cdot 2^6}$ $\frac{2^2}{2^6}$ $\frac{6!}{2^6}$

A fair coin is repeatedly tossed. Each time a head appears, $1$ rupee is added to the first bag. Each time a tail appears, $2$ rupees are put in the second bag.What is th...

215 views

answered May 4, 2021

0 votes

238

CMI2020-A: 8
Basketball shots are classified into $close-range,\;mid-range$ and $long-range$ shots. Long range shots are worth $3$ points, while close-range and the mid-range shots are worth $2$ points. Of the shots that LeBron James attempts, $45\%$ are close-range, $25\%$ ... attempt by LeBron is a close-range shot? $\frac{2}{5}$ $\frac{3}{5}$ $\frac{3}{7}$ $\frac{3}{4}$

Basketball shots are classified into $close-range,\;mid-range$ and $long-range$ shots. Long range shots are worth $3$ points, while close-range and the mid-range shots a...

144 views

answered May 4, 2021

0 votes

239

CMI2020-A: 7
Basketball shots are classified into $close-range,\;mid-range$ and $long-range$ shots. Long range shots are worth $3$ points, while close-range and mid-range shots are worth $2$ points. Of the shots that LeBron James attempts, $45\%$ are close-range, $25\%$ ... that a LeBron shot attempt is successful? $\frac{1}{2}$ $\frac{4}{5}$ $\frac{3}{5}$ $\frac{4}{7}$

Basketball shots are classified into $close-range,\;mid-range$ and $long-range$ shots. Long range shots are worth $3$ points, while close-range and mid-range shots are w...

137 views

answered May 4, 2021

0 votes

240

CMI2020-A: 6
There are $n$ songs segregated into $3$ playlists. Assume that each playlist has at least one song. For all $n$, the number of ways of choosing three songs consisting of one song from each playlist is: $>\frac{n^3}{27}$ $\underline<\frac{n^3}{27}$ $\begin{pmatrix} n\\3 \end{pmatrix}$ $n^3$

There are $n$ songs segregated into $3$ playlists. Assume that each playlist has at least one song. For all $n$, the number of ways of choosing three songs consisting of ...

230 views

answered May 4, 2021

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true