Search results for cmi2015

1 votes

1 answer

1

CMI2015-B-01
Let $\Sigma=\{a,b\}.$ Given a language $L\underline\subset \Sigma^{\ast}$ and a word $w\in\Sigma^{\ast}$, define the languages: $Extend(L,w) :=\{xw\:|\:x\in L\}$ $Shrink(L,w) :=\{x\:|\:xw\in L\}$Show that if $L$ is regular, both $Extend(L,w)$ and $Shrink(L,w)$ are regular.

Let $\Sigma=\{a,b\}.$ Given a language $L\underline\subset \Sigma^{\ast}$ and a word $w\in\Sigma^{\ast}$, define the languages:$$Extend(L,w) :=\{xw\:|\:x\in L\}$$ $$Shrin...

soujanyareddy13

527 views

soujanyareddy13 asked May 10, 2021

13 votes

5 answers

2

CMI2015-A-08
How many times is the comparison $i \geq n$ performed in the following program? int i=85, n=5; main() { while (i >= n) { i=i-1; n=n+1; } } $40$ $41$ $42$ $43$

How many times is the comparison $i \geq n$ performed in the following program?int i=85, n=5; main() { while (i >= n) { i=i-1; n=n+1; } }$40$$41$$42$$43$

5.6k views

go_editor asked May 27, 2016

2 votes

1 answer

3

CMI2015-A-04a
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... a spanning tree with minimum number of edges Find a minimal coloring Find a minimum size vertex cover Find a maximum size independent

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint tim...

836 views

go_editor asked May 27, 2016

5 votes

2 answers

4

CMI2015-A-02
A binary relation $R ⊆ (S S)$ is said to be Euclidean if for every $a, b, c ∈ S, (a, b) ∈ R$ and $(a, c) ∈ R$ implies $(b, c) ∈ R$. Which of the following statements is valid? If $R$ is Euclidean, $(b, a) ∈ R$ and $(c, a) ∈ R$, then $(b, c) ∈ R$ ... $R$ is Euclidean, $(a, b) ∈ R$ and $(b, c) ∈ R$, then $(a, c) ∈ R$, for every $a, b, c ∈ S$ None of the above.

A binary relation $R ⊆ (S ×S)$ is said to be Euclidean if for every $a, b, c ∈ S, (a, b) ∈ R$ and $(a, c) ∈ R$ implies $(b, c) ∈ R$. Which of the following sta...

1.1k views

Mk Utkarsh asked May 12, 2018

16 votes

2 answers

5

CMI2015-A-05
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What is the degree of vertex $10$ ? $5$ $6$ $7$ $8$

An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What ...

2.2k views

go_editor asked May 27, 2016

16 votes

2 answers

6

CMI2015-B-04
You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than $0$. Design a greedy algorithm to test whether these integers correspond to the degrees of some $n$-vertex simple undirected graph $G = (V, E)$. [A simple graph has no self-loops and at most one edge between any pair of vertices].

You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than $0$. Design a greedy algorithm to test whether these integers correspond to the degrees of so...

1.6k views

go_editor asked May 27, 2016

7 votes

3 answers

7

CMI2015-A-06
Suppose we have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following can we infer from this fact? If the best algorithm for $B$ takes exponential time, there is no polynomial time algorithm for $A$. If the best ... we don't know whether there is a polynomial time algorithm for $B$, there cannot be a polynomial time algorithm for $A$.

Suppose we have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following can we infer from this fact?If the best algorithm for $B$ ...

2.1k views

go_editor asked May 27, 2016

13 votes

3 answers

8

CMI2015-A-09
Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true: If $L_2$ is regular, then $L_1$ must also be regular. If $L_1$ is regular, then $L_2$ must also be regular. Either both $L_1$ and $L_2$ are regular, or both are not regular. None of the above.

Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true:If $L_2$ is regular, then $L_1$ must also be regu...

1.2k views

go_editor asked May 27, 2016

11 votes

3 answers

9

CMI2015-A-07
You arrive at a snack bar and you can't decide whether to order a lime juice or a lassi. You decide to throw a fair $6$-sided die to make the choice, as follows. If you throw $2$ or $6$ you order a lime juice. If you throw a $4$, you order a lassi. Otherwise, you throw ... is the probability that you end up ordering a lime juice? $\frac{1}{3}$ $\frac{1}{2}$ $\frac{2}{3}$ $\frac{3}{4}$

You arrive at a snack bar and you can’t decide whether to order a lime juice or a lassi. You decide to throw a fair $6$-sided die to make the choice, as follows.If you ...

1.3k views

go_editor asked May 27, 2016

7 votes

2 answers

10

CMI2015-A-01
Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes-for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that there are infinitely many twin primes. Let $\text{TwinPrime}(n)$ ... $\exists m \cdot \forall n \cdot \text{TwinPrime}(n) \text{ implies }n \leq m$

Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes—for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that th...

1.5k views

go_editor asked May 27, 2016

5 votes

3 answers

11

CMI2015-A-10
The school athletics coach has to choose $4$ students for the relay team. He calculates that there are $3876$ ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order of the runners is to be ... $12,000$ and $25,000$ Between $75,000$ and $99,999$ Between $30,000$ and $60,000$ More than $100,000$

The school athletics coach has to choose $4$ students for the relay team. He calculates that there are $3876$ ways of choosing the team if the order in which the runners ...

734 views

go_editor asked May 27, 2016

4 votes

2 answers

12

CMI2015-B-06c
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n-1); } } How much time does it take to compute $f(m, n)$ and $g(m, n)$?

Consider the code below, defining the functions $f$ and $g$:f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n ...

716 views

go_editor asked May 27, 2016

5 votes

2 answers

13

CMI2015-B-06b
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n-1); } } What does $g(m, n)$ compute, for nonnegative numbers $m$ and $n$?

Consider the code below, defining the functions $f$ and $g$:f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n ...

565 views

go_editor asked May 27, 2016

3 votes

2 answers

14

CMI2015-A-03
Suppose each edge of an undirected graph is coloured using one of three colours - red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not ... endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. (A) and (C).

Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is t...

590 views

go_editor asked May 27, 2016

2 votes

2 answers

15

CMI2015-B-02
Consider a social network with $n$ persons. Two persons $A$ and $B$ are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons $F_1, \dots, F_m$ such that $A$ and ... . It is known that there are $k$ persons such that no pair among them is connected. What is the maximum number of friendships possible?

Consider a social network with $n$ persons. Two persons $A$ and $B$ are said to be connected if either they are friends or they are related through a sequence of friends:...

600 views

go_editor asked May 27, 2016

3 votes

1 answer

16

CMI2015-B-07
There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products ... a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before checking bigger subsequences.

There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new si...

511 views

go_editor asked May 27, 2016

3 votes

2 answers

17

CMI2015-B-03a
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more rotis. Suppose the cook starts at the top with $R$ rupees. What are all the possible amounts of money she can have at the end?

A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down th...

424 views

go_editor asked May 27, 2016

2 votes

2 answers

18

CMI2015-B-03b
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more ... she starts at the top with $P$ paans and $1$ rupee, what is the minimum and maximum amount of money she can have at the end?

A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down th...

568 views

go_editor asked May 27, 2016

2 votes

2 answers

19

CMI2015-B-06a
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n-1); } } Compute $g(3, 7), \: g(345, 1), \: g(345, 4) \text{ and } \: g(345, 0)$.

Consider the code below, defining the functions $f$ and $g$:f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n ...

520 views

go_editor asked May 27, 2016

2 votes

1 answer

20

CMI2015-B-05
An airline runs flights between several cities of the world. Every flight connects two cities. A millionaire wants to travel from Chennai to Timbuktu by changing at most $k_1$ flights. Being a millionaire with plenty of time and money, he does not mind revisiting ... flights at most $k_1$ times. You can assume that the procedure can add or multiply two numbers in a single operation.

An airline runs flights between several cities of the world. Every flight connects two cities. A millionaire wants to travel from Chennai to Timbuktu by changing at most ...

532 views

go_editor asked May 27, 2016

To see more, click for the full list of questions or popular tags.