Recent questions tagged cmi2016

+1 vote

1 answer

1

CMI2016-B-7ai
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 by jothee Veteran (105k points) | 69 views

+1 vote

0 answers

2

CMI2016-B-7b
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 by jothee Veteran (105k points) | 45 views

0 votes

1 answer

3

CMI2016-B-7aiii
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 by jothee Veteran (105k points) | 51 views

+1 vote

2 answers

4

CMI2016-B-7aii
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 by jothee Veteran (105k points) | 69 views

+1 vote

1 answer

5

CMI2016-B-6
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 ... 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 by jothee Veteran (105k points) | 73 views

0 votes

2 answers

6

CMI2016-B-5
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)$ ... $ x \in \{0, 1, 2\}^*$ such that $val(x)$ is divisible by 4.

asked Dec 30, 2016 in Theory of Computation by jothee Veteran (105k points) | 79 views

+1 vote

0 answers

7

CMI2016-B-4
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 by jothee Veteran (105k points) | 35 views

+1 vote

1 answer

8

CMI2016-B-3
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 by jothee Veteran (105k points) | 174 views

+1 vote

0 answers

9

CMI2016-B-2b
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 by jothee Veteran (105k points) | 33 views

+1 vote

1 answer

10

CMI2016-B-2a
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 by jothee Veteran (105k points) | 50 views

+1 vote

0 answers

11

CMI2016-B-1
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 ... 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 by jothee Veteran (105k points) | 286 views

+1 vote

1 answer

12

CMI2016-A-10
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 by jothee Veteran (105k points) | 47 views

+1 vote

1 answer

13

CMI2016-A-9
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 ... $34$ $32$ $17$ $16$

asked Dec 30, 2016 in Graph Theory by jothee Veteran (105k points) | 62 views

+1 vote

1 answer

14

CMI2016-A-8
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 Numerical Ability by jothee Veteran (105k points) | 86 views

0 votes

1 answer

15

CMI2016-A-7
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$ ... up eating in $\text{Kababs Unlimited}$? $\frac{1}{5}$ $\frac{1}{3}$ $\frac{2}{5}$ $\frac{1}{2}$

asked Dec 30, 2016 in Probability by jothee Veteran (105k points) | 100 views

+1 vote

1 answer

16

CMI2016-A-6
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 ... 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 by jothee Veteran (105k points) | 46 views

+1 vote

1 answer

17

CMI2016-A-5
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 by jothee Veteran (105k points) | 45 views

0 votes

1 answer

18

CMI2016-A-4
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? ... $(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 by jothee Veteran (105k points) | 99 views

+1 vote

1 answer

19

CMI2016-A-3
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 by jothee Veteran (105k points) | 73 views

+1 vote

1 answer

20

CMI2016-A-2
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$ ... . 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 Numerical Ability by jothee Veteran (105k points) | 63 views

+1 vote

1 answer

21

CMI2016-A-1
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 ... 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 by jothee Veteran (105k points) | 109 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged cmi2016

Recent Posts

Recent Blog Comments