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 930 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 375 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 504 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.3k 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 164 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 304 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 191 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 441 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 Numerical Ability jothee 265 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 320 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 145 views
4 votes
1 answer
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 220 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 Numerical Ability jothee 250 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 966 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 505 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 209 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 213 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 238 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 765 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 155 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 158 views
To see more, click for the full list of questions or popular tags.
...