Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged cmi2022
1
votes
0
answers
1
CMI2022-B: 1
A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where: $\text{Q}$ is a finite set of states; $\text{I} \subseteq \text{Q}$ is the set of initial states; $\Sigma$ ... $a^{\ast}?$
A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where:$\text{Q}$ is a finite set of states;$\text{I} \subseteq \...
admin
344
views
admin
asked
Jul 22, 2022
Others
cmi2022
descriptive
+
–
0
votes
0
answers
2
CMI2022-B: 2
Consider the language $\text{L}$ over the alphabet $\left \{ a, b \right \}$ given below. $\text{L}= \{ w \mid w \;\text{has equal number of $a$'s and $b$'s, and there are no adjacent $a$'s.}\}$ For instance, the words $abba, abab$ are in language ... $baab$. Prove that $\text{L}$ does not contain any word that starts and ends with $a$ $b$. Give a context-free grammar for $\text{L}$.
Consider the language $\text{L}$ over the alphabet $\left \{ a, b \right \}$ given below.$$\text{L}= \{ w \mid w \;\text{has equal number of $a$’s and $b$’s, and the...
admin
219
views
admin
asked
Jul 22, 2022
Others
cmi2022
descriptive
+
–
0
votes
0
answers
3
CMI2022-B: 3
We say that an integer $a$ is co-prime to another integer $b$ if $\gcd(a, b) = 1$. For any integer $n, \varphi (n)$ is the number of integers from $1$ up to $|n|$ that are co-prime to $n$. Calculate $\varphi (5), \varphi (10)$ and $\varphi (20)$. Show that ... for any prime $p$. Prove that if $a$ is co-prime to $b$ then the remainder of $a$ when divided by $b$ is also co-prime to $b$.
We say that an integer $a$ is co-prime to another integer $b$ if $\gcd(a, b) = 1$. For any integer $n, \varphi (n)$ is the number of integers from $1$ up to $|n|$ that a...
admin
167
views
admin
asked
Jul 22, 2022
Others
cmi2022
descriptive
+
–
0
votes
0
answers
4
CMI2022-B: 4
You are organizing a party involving $2n$ diplomats. Each pair of diplomats are either friends or enemies. You have managed to invite an excellent set of guests, each of whom has more friends than enemies (among the other guests). Can you now seat ... as their neighbours. (Hint: Model this situation as an appropriate graph so that the desired seating arrangement is a Hamiltonian path.)
You are organizing a party involving $2n$ diplomats. Each pair of diplomats are either friends or enemies. You have managed to invite an excellent set of guests, each of ...
admin
190
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
5
CMI2022-B: 5
For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the following conditions: $\left ( i, j \right ) \in R \Rightarrow i < j$ ... any set $\text{S}$ of size $2^{k} - 1$ (for $k > 2)$ has a $2$-spanner of size $(k - 2) 2^{k} + 2$.
For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the followi...
admin
275
views
admin
asked
Jul 22, 2022
Others
cmi2022
descriptive
+
–
0
votes
0
answers
6
CMI2022-B: 6
There is a treasure hunt game in which parts of a treasure are hidden across $n$ islands, numbered $1$ to $n$. You start in island $1 ,$ and aim to collect all parts of the treasure, by hopping from island to island. Each island has a list of other islands you ... can succeed in collecting all parts of the treasure. The algorithm should run in time $O\left(n^{2} \cdot 2^{n}\right)$.
There is a treasure hunt game in which parts of a treasure are hidden across $n$ islands, numbered $1$ to $n$. You start in island $1 ,$ and aim to collect all parts of t...
admin
265
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
7
CMI2022-B: 7
Consider the following inventory problem. You are running a company that sells lorries. Predictions tell you the quantity of sales to expect over the next $n$ months. Let $d_{i}$ denote the number of sales expected in month $i$. We assume that sales happen on ... dynamic programming algorithm that computes $c_{1}(0)$. Your algorithm must run in time polynomial in $n$ and $\text{C}$.
Consider the following inventory problem. You are running a company that sells lorries. Predictions tell you the quantity of sales to expect over the next $n$ months. Let...
admin
222
views
admin
asked
Jul 22, 2022
Others
cmi2022
descriptive
+
–
1
votes
0
answers
8
CMI2022-A: 1
If Vinay finishes his homework and the school closes early, then he can play in the park or eat an ice cream. He will end up at the dispensary with tummy ache if he eats ice cream and plays in the park. Which of the following can be correctly inferred? If he doesn't ... dispensary with tummy ache, he didn't eat ice cream and he didn't play in the park. Both A and B. None of the above.
If Vinay finishes his homework and the school closes early, then he can play in the park or eat an ice cream. He will end up at the dispensary with tummy ache if he eats ...
admin
325
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
1
votes
1
answer
9
CMI2022-A: 2
There are $n$ members of Chennai Mathematical Institute. Most of them are very studious and like to own lots of books. Now the following facts have been learnt. No two members own exactly the same number of books. Each member owns strictly less than $n$ books. No ... books. Given the above information, which of the following is not a possible value of $n?$ $100$ $199$ $200$ $201$
There are $n$ members of Chennai Mathematical Institute. Most of them are very studious and like to own lots of books. Now the following facts have been learnt.No two mem...
admin
254
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
1
votes
0
answers
10
CMI2022-A: 3
Which of the following assertions about regular languages is incorrect? Every subset of a regular language is regular. For every regular language $\text{L}$, there is a subset of $\text{L}$ that is regular. For every language $\text{L}$, there is a superset of $\text{L}$ that is regular. The complement of every regular language is regular.
Which of the following assertions about regular languages is incorrect?Every subset of a regular language is regular.For every regular language $\text{L}$, there is a sub...
admin
209
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
11
CMI2022-A: 4
Consider the following languages over the alphabet $\left \{ a, b, c, d \right \}$ $\text{L}_{1} = \left\{ a^{n} b^{n} c^{m} d^{m} \mid n, m\geq 0\right\}$ $\text{L}_{2} = \left \{ a^{n} b^{m} c^{n} d^{m} \mid n, m\geq 0\right\}$ ... languages is/are context-free? None of them. Only $\text{L}_{1}$ and $\text{L}_{2}$. Only $\text{L}_{1}$ and $\text{L}_{3}$. All of them.
Consider the following languages over the alphabet $\left \{ a, b, c, d \right \}$$\text{L}_{1} = \left\{ a^{n} b^{n} c^{m} d^{m} \mid n, m\geq 0\right\}$$\text{L}_{2} ...
admin
200
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
1
votes
0
answers
12
CMI2022-A: 5
As part of a class activity, students in a class of $50$ were asked to keep track of the total number of hours that they spent looking at the screen of some digital device on a specific day. It was found that the average screentime for the class was $4$ hours. What is the maximum possible number of students with at least $16$ hours of screentime? $11$ $12$ $13$ $14$
As part of a class activity, students in a class of $50$ were asked to keep track of the total number of hours that they spent looking at the screen of some digital devic...
admin
186
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
2
votes
0
answers
13
CMI2022-A: 6
The Telvio mobile service provider allows each customer to choose a part of their $10$- digit mobile number when getting a new connection. The first two digits of the number are fixed by the company based on the customer's region. The customer can choose the last four digits as they wish. The ... when read from left to right? $\frac{1}{4}$ $\frac{1}{16}$ $\frac{1}{24}$ $\frac{1}{32}$
The Telvio mobile service provider allows each customer to choose a part of their $10$- digit mobile number when getting a new connection. The first two digits of the num...
admin
239
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
14
CMI2022-A: 7
Consider a random graph $\text{G}$ on $n$ vertices where for each pair of vertices $u, v,$ there is an edge $(u, v)$ with probability $p \in [0, 1]$. What is the expected number of cycles of length $3$ in this graph? $\binom{n}{3} \cdot p^{3}$ $\frac{p^{3}}{\binom{n}{3}}$ $n^{3}p^{3}$ None of the above.
Consider a random graph $\text{G}$ on $n$ vertices where for each pair of vertices $u, v,$ there is an edge $(u, v)$ with probability $p \in [0, 1]$. What is the expected...
admin
254
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
15
CMI2022-A: 8
Refer to the following two functions. int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a < m) { i = i + 1; a = a + 1; a = 2 * a; b = b + c; } int temp = d; return a; d = c; } c = temp; } return b; } What is the result of $\textsf{f (100)}?$ $100$ $5050$ $50$ $1$
Refer to the following two functions.int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a ...
admin
223
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
16
CMI2022-A: 9
Refer to the following two functions. int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a < m) { i = i + 1; a = a + 1; a = 2 * a; b = b + c; } int temp = d; return a; d = c; } c = temp; } return b; } If $\textsf{g(f(n)) = 32}$ which of the following is a possible value of $\textsf{n}?$ $8$ $11$ $5$ $64$
Refer to the following two functions.int f(int m) { int g(int m) { int a, b, c, d; int a = 1; a = 0; b = 0; int i = 0; c = 0; d = 1; while (i < m) { while (a ...
admin
224
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
0
votes
0
answers
17
CMI2022-A: 10
What can you conclude from the following statements about problems $\text{A}$ and $\text{B}?$ There is a polynomial-time algorithm to solve $\text {A}$. There is an exponential-time algorithm to solve $\text{B}$. $\text{B}$ can be reduced to $\text{A}$ in ... for $\text{B}$. A cannot be reduced to $\text{B}$ in polynomial-time. There is no exponential-time algorithm for $\text{A}$.
What can you conclude from the following statements about problems $\text{A}$ and $\text{B}?$There is a polynomial-time algorithm to solve $\text {A}$.There is an exponen...
admin
191
views
admin
asked
Jul 22, 2022
Others
cmi2022
+
–
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
