search
Log In

Recent questions tagged cmi2016

1 vote
1 answer
1
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following$: M(101)$
asked Dec 31, 2016 in Calculus jothee 115 views
1 vote
0 answers
2
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Give a constant time algorithm that computes $M(n)$ on input $n$. (A constant-time algorithm is one whose running time is independent of the input $n$)
asked Dec 31, 2016 in Calculus jothee 78 views
0 votes
1 answer
3
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following$: M(87)$
asked Dec 31, 2016 in Calculus jothee 100 views
1 vote
2 answers
4
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following$: M(99)$
asked Dec 31, 2016 in Calculus jothee 110 views
1 vote
1 answer
5
An automatic spelling checker works as follows. Given a word $w$, first check if $w$ is found in the dictionary. If $w$ is not in the dictionary, compute a dictionary entry that is close to $w$. For instance if the user types $\mathsf{ocurrance}$, the spelling checker should ... all alignments of $x$ and $y$. What is the running time of your algorithm (in terms of the lengths of $x$ and $y)?$
asked Dec 31, 2016 in Algorithms jothee 188 views
0 votes
2 answers
6
For a string $x=a_0a_1 \ldots a_{n-1}$ over the alphabet $\{0, 1, 2\}$, define $val(x)$ to be the value of $x$ interpreted as a ternary number, where $a_0$ is the most significant digit. More formally, $val(x)$ is given by $ \Sigma_{0 \leq i < n} 3^{n-1-i} \cdot a_i.$ Design a finite automaton that accepts exactly the set of strings $ x \in \{0, 1, 2\}^*$ such that $val(x)$ is divisible by 4.
asked Dec 30, 2016 in Theory of Computation jothee 128 views
1 vote
0 answers
7
Let $\Sigma = \{0, 1\}$. Let $A, \: B$ be arbitrary subsets of $\Sigma^\ast$. We define the following operations on such sets: $ A+B := \{ w \in \Sigma^\ast \mid w \in A \text{ or } w \in B \}$ ... $A$ and $B$? If yes, give a proof. If not, provide suitable $A$ and $B$ for which this equation fails.
asked Dec 30, 2016 in Theory of Computation jothee 101 views
1 vote
1 answer
8
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example: Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.
asked Dec 30, 2016 in Graph Theory jothee 286 views
1 vote
0 answers
9
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple cycle of length at least $k+1$.
asked Dec 30, 2016 in Graph Theory jothee 99 views
1 vote
1 answer
10
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple path of length at least $k$.
asked Dec 30, 2016 in Graph Theory jothee 123 views
1 vote
0 answers
11
A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as $B$, see picture below) and the prison ... , and assuming that soldiers do not change their locations ($Hint$: Model this as a graph, with soldiers represented by the vertices.)
asked Dec 30, 2016 in Algorithms jothee 363 views
2 votes
1 answer
12
Which of the following relationships holds in general between the $\text{scope}$ of a variable and the $\text{lifetime}$ of a variable (in a language like C or Java)? The scope of a variable is contained in the lifetime of the variable The scope of a variable is same as the lifetime of the variable The lifetime of a variable is disjoint from the scope of the variable None of the above
asked Dec 30, 2016 in Programming jothee 149 views
1 vote
1 answer
13
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain connected if $any$ single link fails. What is the minimum number of links that ScamTel needs to set up? $34$ $32$ $17$ $16$
asked Dec 30, 2016 in Graph Theory jothee 231 views
1 vote
1 answer
14
An advertisement for a tennis magazine states, "If I'm not playing tennis, I'm watching tennis. And If I'm not watching tennis, I'm reading about tennis." We can assume that the speaker can do at most one of these activities at a time. What is the speaker doing? Playing tennis Watching tennis Reading about tennis None of the above
asked Dec 30, 2016 in Quantitative Aptitude jothee 179 views
2 votes
1 answer
15
Varsha lives alone and dislikes cooking, so she goes out for dinner every evening. She has two favourite restaurants, $\text{Dosa Paradise}$ and $\text{Kababs Unlimited}$, to which she travels by local train. The train to $\text{Dosa Paradise}$ runs every $10$ minutes, at $0, 10, 20, 30, 40$ ... ends up eating in $\text{Kababs Unlimited}$? $\frac{1}{5}$ $\frac{1}{3}$ $\frac{2}{5}$ $\frac{1}{2}$
asked Dec 30, 2016 in Probability jothee 207 views
2 votes
1 answer
16
In the code fragment given below, $\mathsf{start}$ and $\mathsf{end}$ are integer values and $\mathsf{prime(x)}$ is a function that returns $\mathsf{true}$ if $\mathsf{x}$ is a prime number and $\mathsf{false}$ otherwise. i:=0; j:=0; k:=0; from (m := start; m <= end; m := m+1){ if ( ... } } At the end of the loop: $k == i-j.$ $k == j-i.$ $k == -j-i.$ Depends on $\mathsf{start}$ and $\mathsf{end}$
asked Dec 30, 2016 in Programming jothee 119 views
1 vote
1 answer
17
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices? $60$ edges and $20$ vertices $30$ edges and $20$ vertices $60$ edges and $50$ vertices $30$ edges and $50$ vertices
asked Dec 30, 2016 in Graph Theory jothee 105 views
0 votes
1 answer
18
Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight $53$ and the shortest path from $s$ to $v$ has weight $65.$ Which of the statements is always true? Weight ... $(u, v) = 12$ Weight of $(u, v) \geq 12$ Nothing can be said about the weight of $(u, v)$
asked Dec 30, 2016 in Graph Theory jothee 236 views
2 votes
1 answer
19
For a regular expression $e$, let $L(e)$ be the language generated by $e$. If $e$ is an expression that has no Kleene star $\ast$ occurring in it, which of the following is true about $e$ in general? $L(e)$ is empty $L(e)$ is finite Complement of $L(e)$ is empty Both $L(e)$ and its complement are infinite
asked Dec 30, 2016 in Theory of Computation jothee 176 views
1 vote
1 answer
20
The symbol $\mid$ reads as "divides", and $\nmid$ as "does not divide". For instance, $2 \: \mid \:6$ and $2 \: \nmid \: 5$ are both true. Consider the following statements. There exists a positive integer $a$ such that $(2 \mid (a^3 -1))$ and $( 2 \mid a)$. ... . What can you say about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true
asked Dec 30, 2016 in Quantitative Aptitude jothee 136 views
1 vote
1 answer
21
In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: there exists a vertex that is a neighbour of all other vertices. Consider the following statements: If $P$ ... can you say about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true
asked Dec 30, 2016 in Graph Theory jothee 206 views
To see more, click for the full list of questions or popular tags.
...