search
Log In

Recent questions tagged cmi2010

6 votes
1 answer
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.
asked Apr 30, 2018 in Algorithms Sammohan Ganguly 1.2k views
7 votes
1 answer
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)}$?
asked May 27, 2016 in Algorithms jothee 483 views
11 votes
2 answers
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$.
asked May 27, 2016 in Theory of Computation jothee 598 views
18 votes
6 answers
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$.
asked May 27, 2016 in Theory of Computation jothee 1.7k views
1 vote
1 answer
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.
asked May 27, 2016 in Algorithms jothee 234 views
2 votes
1 answer
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.
asked May 19, 2016 in Algorithms jothee 380 views
1 vote
2 answers
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$
asked May 19, 2016 in Operating System jothee 230 views
7 votes
1 answer
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.
asked May 19, 2016 in Compiler Design jothee 569 views
3 votes
2 answers
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
asked May 19, 2016 in Quantitative Aptitude jothee 382 views
1 vote
0 answers
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
asked May 19, 2016 in Graph Theory jothee 429 views
1 vote
1 answer
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.
asked May 19, 2016 in Probability jothee 185 views
4 votes
2 answers
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)$
asked May 19, 2016 in Mathematical Logic jothee 308 views
2 votes
2 answers
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
asked May 19, 2016 in Quantitative Aptitude jothee 335 views
19 votes
3 answers
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$
asked May 19, 2016 in Combinatory jothee 1.2k views
8 votes
2 answers
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
asked May 19, 2016 in Theory of Computation jothee 622 views
3 votes
1 answer
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.
asked May 19, 2016 in Graph Theory jothee 310 views
2 votes
2 answers
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$.
asked May 19, 2016 in Graph Theory jothee 279 views
2 votes
1 answer
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.
asked May 19, 2016 in Algorithms jothee 277 views
4 votes
1 answer
19
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$.
asked May 19, 2016 in Theory of Computation jothee 1.1k views
4 votes
1 answer
20
Sales have slumped at the Siruseri noodle factory and the management may need to terminate the contracts of some employees. Every employee has one immediate boss. The seniormost person in the company is the president, who has no boss. For legal reasons, if an employee's contract is not terminated, then his boss's contract cannot be ...
asked May 19, 2016 in Combinatory jothee 205 views
1 vote
0 answers
21
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)$?
asked May 19, 2016 in DS jothee 218 views
To see more, click for the full list of questions or popular tags.
...