# Recent questions tagged cmi2019

1 vote
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
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.$
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$
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 same likes ... . What is the maximum number of guests possible? $5^{2}$ $\binom{5}{2}$ $2^{5}$ $2^{2^{5}}$
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)}$
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}$
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 requires a ... to solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
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 know an ... a polynomial time algorithm for B. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for 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
1 vote
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]$ ... ; } return; } The number of times the test $A[ j ] > A[ m ]$ is executed is: $4950$ $5050$ $10000$ Depends on the contents of $A$
11
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.$
1 vote
12
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.$
13
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.
14
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).
1 vote
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 ... Suspect $3:$ My lawyer always tells the truth. Which of the above suspects are innocent, and which are guilty? Explain your reasoning.
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 column $j$ ... $2n$ values in $A.$ Justify the complexity of your algorithm. For both algorithms, describe a worst-case input where $k$ is present in $A.$
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 based on the ... programming, the score the professor needs to award each student. Describe the space and time complexity of your dynamic programming algorithm.