# Recent questions tagged cmi2010

1
You are given a list of positive integers along with a sequence of operations from the set $\left \{ *,+\right \}$ .You construct expressions from these two lists so that: The numbers in the expression are drawn from the first list, without repetition and without ... assume that the length of the first list is more than the length of the second list. Describe an algorithm to solve this problem.
2
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$. For example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. The function $\text{length}(l)$ returns the ... ( mystery1(mystery2(s,tail(t)),mystery2(s,tail(t)))) endif Suppose $s=t=110100100$. What are the first two bits of $\text{mystery2(s,t)}$?
3
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers. If a language $L$ is accepted by an NFA with $n$ states then there is a DFA with no more than $2^n$ states accepting $L$.
4
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers. A DFA that has $n$ states and accepts an infinite language must accept at least one string $x$ such that $2n < |x| < 3n$, where $|x|$ denotes the length of $x$.
1 vote
5
An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same frequency ... should say feasible if it is feasible, otherwise output the minimum number of frequencies needed to utilise all 100 towers.
6
Consider the following statements. NP-complete problems are those that we know we can never solve efficiently. If we find an efficient algorithm for one NP-complete problem, then we can solve all NP-complete problems efficiently. Checking whether a number is a prime is an NP-complete problem. ... $2$ is true. $2$ and $3$ are true but $1$ is false. All three statements are false.
1 vote
7
Consider the following functions $f()$ and $g().$ f(){ w = 3; w = 4; } g(){ z = w; z = z + 2*w; print(z); } We start with $w$ set to $0$ and execute $f()$ and $g()$ in parallel-that is, at each step we either execute one statement from $f()$ or one statement from $g()$. What is the set of possible values printed by $g()?$ $0,9,12$ $0,8,9,12$ $0,6,8,9,11,12$ $0,4,6,9,10,12$
8
In programming language terminology, $\text{ call by value }$ refers to the fact that: A function call can return a value. When a function is called, arguments are copied into local storage. Functions can indirectly modify the value of external variables. Every argument passed to a function must have a value.
9
For integer values of $n$, the expression $\frac{n(5n + 1)(10n + 1)}{6}$ Is always divisible by $5$. Is always divisible by $3$. Is always an integer. None of the above
1 vote
10
A simple graph is one with no self-loops or multiple edges. Among the simple graphs with $n$ vertices and at most $20n − 3$ edges: There is always a graph with all vertices connected to at least $42$ other vertices. For all such graphs the number of vertices connected ... cn for some constant $c < 1$. There are no graphs with each vertex connected to at most $38$ other vertices. None of the above
1 vote
11
You have two normal, fair, dice, with faces labelled $1,2, \dots 6$. If you throw both dice, which of the following is true about the total value shown by the dice? The probability that the total is $6$ is less than the probability that the total is $9$. The ... the total is $9$. The probability that the total is $6$ is greater than the probability that the total is $9$. None of the above.
12
Let $m$ and $n$ range over natural numbers and let $\text{Prime}(n)$ be true if $n$ is a prime number. Which of the following formulas expresses the fact that the set of prime numbers is infinite? $(\forall m) (\exists n) (n > m) \text{ implies Prime}(n)$ ... $(\exists n) (\forall m) (n > m) \wedge \text{Prime}(n)$
13
The area of the largest square that can be drawn inside a circle with unit radius is $\sqrt{2}$ $2$ $1$ None of the above
14
We need to choose a team of $11$ from a pool of $15$ players and also select a captain. The number of different ways this can be done is $\begin{pmatrix} 15 \\ 11 \end{pmatrix}$ $11$ . $\begin{pmatrix} 15 \\ 11 \end{pmatrix}$ $15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5$ $(15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5) . 11$
15
Over the alphabet $\{0, 1\}$, consider the language $L = \{ w | \: w \text{ does not contain the substring } 0011\}$ Which of the following is true about $L$. $L$ is not context free $L$ is regular $L$ is not regular but it is context free $L$ is context free but not recursively enumerable
16
An international cellphone company provides service on $7$ different frequencies. They wish to set up business in TamilNadu and have fixed the locations of $100$ towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least $100$ km apart, so that there is no interference of signals. Model this problems using graphs.
17
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots , v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.
18
The Income-Tax Department had prepared a list D of names of defaulters on March $31$. However, the government extended the deadline to pay taxes till April $15$. The IT department has now received two additional lists of names: a list B of names of people who have paid their ... n, m and k respectively and that $n > m > k$. Describe the running time of your algorithm in terms of these parameters.
Indicate whether the following statements are true or false, providing a short explanation to substantiate your answers. A DFA with $n$ states must accept at least one string of length greater than $n$.
A finite sequence of bits is represented as a list with values from the set {0,1}&mdash;for example, [0,1,0], [1,0,1,1], . . . . [ ] denotes the empty list, and [b] is the list consisting of one bit b. The function $length(l)$ returns the length (number of bits) in the ... (s,tail(t)),mystery2(s,tail(t)))) endif What is the value of $length(mystery2(s,t))$ in terms of $length(s)$ and $length(t)$?