search
Log In

Recent questions tagged cmi2012

3 votes
1 answer
1
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$ Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$. Construct a finite automaton that accepts exactly those strings $(a_0, b_0)(a_1, b_1) \dots (a_{n−1}, b_{n−1}) \in \Sigma^*$ such that $val(b_0b_1 \dots b_{n−1}) = 4 · val(a_0a_1 \dots a_{n−1})$.
asked May 27, 2016 in Theory of Computation jothee 428 views
5 votes
1 answer
2
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other ... you claim the statement is true or a counterexample if the statement is false. All the shortest paths from $s$ to the other vertices are unchanged.
asked May 27, 2016 in Algorithms jothee 403 views
11 votes
4 answers
3
Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ and $l$ such that $A[k]+A[l] = x$. Design an $O(n)$ algorithm for this problem.
asked May 27, 2016 in Algorithms jothee 684 views
8 votes
1 answer
4
We use the notation $[x1,x2,...,xn]$ to denote a list of integers. $[]$ denotes the empty list, and $[n]$ is the list consisting of one integer $n$. For a nonempty list l, $head(l)$ returns the first element of $l$, and $tail(l)$ returns the list obtained by ... head(tail(l)) then return g(tail(l)) else return(false) When does $f(l)$ return the value true for an input $l$? Explain your answer.
asked May 23, 2016 in DS jothee 451 views
1 vote
0 answers
5
A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes $n$ units of time for a string of length $n$, regardless of the location of the cut. Suppose, now, that you ... $m + 1$ pieces. You may assume that all m locations are in the interior of the string so each split is non-trivial.
asked May 23, 2016 in Algorithms jothee 478 views
1 vote
1 answer
6
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other vertex in ... argument if you claim the statement is true or a counterexample if the statement is false. $T$ is still a minimum cost spanning tree of $G$.
asked May 23, 2016 in Algorithms jothee 102 views
1 vote
1 answer
7
You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way - i.e., you can check $A[i] == A[j]$ and $A[i] != A[j]$ ... its elements are equal to each other. Use divide and conquer to come up with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.
asked May 23, 2016 in Algorithms jothee 205 views
5 votes
1 answer
8
Let $A$ be an array of $n$ integers, sorted, so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there are indices $k$ and $l$ such that $A[k]+A[l] = x$. Design an $O(n \log n)$ time algorithm for this problem.
asked May 23, 2016 in Algorithms jothee 404 views
13 votes
1 answer
9
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$ Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$. Construct a finite automaton that accepts the set of all strings $(a_0, b_0)(a_1, b_1) \dots (a_{n−1}, b_{n−1}) \in \: \Sigma^*$ such that $val(b_0b_1 \dots b_{n−1}) = 2 · val(a_0a_1 \dots a_{n−1})$.
asked May 23, 2016 in Theory of Computation jothee 856 views
10 votes
1 answer
10
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Consider a path of maximum length in $G$.)
asked May 23, 2016 in Graph Theory jothee 387 views
15 votes
2 answers
11
Consider the following functions $f$ and $g$. f(){ x = x-50; y = y+50; } g( ) { a = a+x; a = a+y; } Suppose we start with initial values of $100$ for $x, 200$ for $y$, and $0$ for $a$, and then execute $f$ and $g$ in parallel - that is, ... step we either execute one statement from $f$ or one statement from $g$. Which of the following is not a possible final value of $a$? $300$ $250$ $350$ $200$
asked May 23, 2016 in Operating System jothee 552 views
15 votes
3 answers
12
Consider the following programming errors: Type mismatch in an expression. Array index out of bounds. Use of an uninitialized variable in an expression. Which of these errors will typically be caught at compile-time by a modern compiler. I, II and III I and II I and III None of them
asked May 23, 2016 in Compiler Design jothee 998 views
3 votes
1 answer
13
You are given two sorting algorithms A and B that work in time $O(n \log n)$ and $O(n^2)$, respectively. Consider the following statements: Algorithm $A$ will sort any array faster than algorithm $B$. On an average, algorithm $A$ will sort a given array faster than ... always be preferable to algorithm $B$. Which of the statements above are true? I, II and III I and III II and III None of them
asked May 23, 2016 in Algorithms jothee 361 views
7 votes
5 answers
14
A man has three cats. At least one is male. What is the probability that all three are male? $\frac{1}{2}$ $\frac{1}{7}$ $\frac{1}{8}$ $\frac{3}{8}$
asked May 23, 2016 in Probability jothee 682 views
7 votes
2 answers
15
A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number of pieces of fruit that should be put in the basket in order to guarantee that either there are at least $8$ apples or at least $6$ bananas or at least $9$ oranges? $9$ $10$ $20$ $21$
asked May 23, 2016 in Numerical Ability jothee 409 views
5 votes
1 answer
16
Amma baked a cake and left it on the table to cool. Before going for her bath, she told her four children that they should not touch the cake as it was to be cut only the next day. However when she got back from her bath she found that someone had eaten a ... the truth and exactly one of them actually ate the piece of cake, who is the culprit that Amma is going to punish? Lakshmi Ram Aruna Varun
asked May 23, 2016 in Numerical Ability jothee 303 views
2 votes
1 answer
17
The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder. mystery(a,b){ if (b == 0) return a; if (a < b) return mystery(b,a); if (eo(a,b) == 0){ ... to $\text{mystery}$ on input $a,\: b$ is $O(n)$ $O(\log \log n)$ $O(\log n)$ $O(n^{\frac{1}{2}})$
asked May 23, 2016 in Algorithms jothee 145 views
1 vote
1 answer
18
The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder. mystery(a,b){ if (b == 0) return a; if (a < b) return mystery(b,a); if (eo(a,b) ... 2)*2 == a and (b/2)*2 < b) return 2; end; return 3; } $\text{mystery}(75,210)$ returns $2$ $6$ $10$ $15$
asked May 23, 2016 in Algorithms jothee 117 views
4 votes
1 answer
19
Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following is true? $s=99$ $s=198$ $99 \: < \: s \: < \: 198$ None of the above
asked May 23, 2016 in Graph Theory jothee 288 views
17 votes
3 answers
20
Let $L \subseteq \{0,1\}^*$. Which of the following is true? If $L$ is regular, all subsets of $L$ are regular. If all proper subsets of $L$ are regular, then $L$ is regular. If all finite subsets of $L$ are regular, then $L$ is regular. If a proper subset of $L$ is not regular, then $L$ is not regular.
asked May 23, 2016 in Theory of Computation jothee 1.6k views
To see more, click for the full list of questions or popular tags.
...