search
Log In

Recent questions tagged cmi2020

2 votes
2 answers
1
Which of the following languages over the alphabet $\{0,1\}$ are $not$ recognized by deterministic finite state automata $(DFA)$ with $three$ states? Words which do not have $11$ as a contiguous subword Binary representations of multiples of three Words that have $11$ as a suffix Words that do not contain $101$ as a contiguous subword
asked Jan 28 in Others soujanyareddy13 47 views
1 vote
0 answers
2
Consider the following regular expressions over alphabet$\{a,b\}$, where the notation $(a+b)^+$ means $(a+b)(a+b)^*$: $r_1=(a+b)^+a(a+b)^*$ $r_2=(a+b)^*b(a+b)^+$ Let $L_1$ and $L_2$ be the languages defined by $r_1$ and $r_2$, respectively. Which of the following regular expressions define $L_1\cap L_2$ ... $(a+b)^*a\;b(a+b)^*$ $(a+b)^*b(a+b)^*a(a+b)^*$ $(a+b)^*a(a+b)^*b(a+b)^*$
asked Jan 28 in Others soujanyareddy13 17 views
0 votes
0 answers
3
Some children are given boxes containing sweets. Harish is happy if he gets either gems or toffees. Rekha is happy if she gets both bubble gums and peppermints. Some of the boxes are special, which means that if the box contains either gems or toffees, then it also contains ... we infer? Harish is happy No bubble gums in Rekha's box No toffees in Harish's box There are peppermints in Rekha's box
asked Jan 28 in Others soujanyareddy13 20 views
0 votes
0 answers
4
In a class, every student likes exactly one novelist and one musician. If two students like the same novelist, they also like the same musician. The class can be divided into novelist groups, each group consisting of all the students who like one novelist. Similarly, ... For every musician group, there is a bigger novelist group For every novelist group, there is a musician group of the same size
asked Jan 28 in Others soujanyareddy13 10 views
0 votes
0 answers
5
A boolean function on $n$ variables is a function $f$ that takes an n-tuple of boolean values $x \in \{0,1\}^n$ as input and produces a boolean value $f(x)\in \{0,1\}$ as output. We say that a boolean function $f$ ... of symmetric boolean functions on $n$ variables? $n+1$ $n!$ $\displaystyle \sum^n_{i=0} \begin{pmatrix} n\\i \end{pmatrix}$ $2^{n+1}$
asked Jan 28 in Others soujanyareddy13 13 views
0 votes
0 answers
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$
asked Jan 28 in Others soujanyareddy13 13 views
0 votes
0 answers
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\%$ are mid-range, and $30\%$ ... probability that a LeBron shot attempt is successful? $\frac{1}{2}$ $\frac{4}{5}$ $\frac{3}{5}$ $\frac{4}{7}$
asked Jan 28 in Others soujanyareddy13 8 views
0 votes
0 answers
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\%$ are mid-range, and $30\%$ are ... shot attempt by LeBron is a close-range shot? $\frac{2}{5}$ $\frac{3}{5}$ $\frac{3}{7}$ $\frac{3}{4}$
asked Jan 28 in Others soujanyareddy13 10 views
1 vote
1 answer
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}$
asked Jan 28 in Others soujanyareddy13 15 views
0 votes
0 answers
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 still correct ... $log\;n.$ $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<log \;n.$
asked Jan 28 in Others soujanyareddy13 9 views
0 votes
0 answers
11
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 the places ... of colours following which one can reach an interesting destination from the City Centre in $X$, but not from the City Centre in $Y$.
asked Jan 28 in Others soujanyareddy13 12 views
0 votes
0 answers
12
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 vertices in ... there exist a graph $G$ with at least two vertices such that both $G$ and $\overline G$ are connected? Justify your answer.
asked Jan 28 in Others soujanyareddy13 16 views
0 votes
0 answers
13
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 a proof ... to draw an example of such a graph. To disprove the result, you should provide an argument as to why such a graph cannot exist.
asked Jan 28 in Others soujanyareddy13 11 views
0 votes
0 answers
14
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)}$ $\textbf{if}\;p==0$ ... $MYSTERY(100,150)$? In general, what does $MYSTERY(m,n)$ return for $m,n\underline> 0?$ Justify your answer with a proof.
asked Jan 28 in Others soujanyareddy13 13 views
0 votes
0 answers
15
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$ ... $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.
asked Jan 28 in Others soujanyareddy13 8 views
0 votes
1 answer
16
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 answer ... Provide a justification for your answer. You do not need to simplify your expressions (for example, you can write $26^5, 5!, etc.$).
asked Jan 28 in Others soujanyareddy13 15 views
0 votes
0 answers
17
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$, which is assumed to be greater than every $L[i]$. We ... $N$?
asked Jan 28 in Others soujanyareddy13 12 views
To see more, click for the full list of questions or popular tags.
...