Recent questions tagged cmi2016

0 votes

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 Others by jothee Veteran (92.5k points) | 31 views

0 votes

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 contant-time algorithm is one whose running time is independent of the input $n$)

asked Dec 31, 2016 in Others by jothee Veteran (92.5k points) | 14 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 Others by jothee Veteran (92.5k points) | 22 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 Others by jothee Veteran (92.5k points) | 43 views

0 votes

0 answers

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 ... 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 Others by jothee Veteran (92.5k points) | 18 views

0 votes

0 answers

6

CMI2016-B-5
For a string $x=a_0a_1 \ cdots 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 ... 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 Others by jothee Veteran (92.5k points) | 18 views

0 votes

0 answers

7

CMI2016-B-4
Let $\Sigma - \{0, 1\}$. Let $A, \: B$ be arbitrary subsets of $\Sigma^*$. We define the following operatins on such sets: $$ A+B := \{ w \in \Sigma^* \mid w \in A \text{ or } w \in B \}$$ $$A \cdot B := \{ uv \in \ ... B +2(A \cdot B)$ for all choices of $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 Others by jothee Veteran (92.5k points) | 16 views

0 votes

0 answers

8

CMI2016-B-3
An undirected graph canbe 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 Others by jothee Veteran (92.5k points) | 37 views

0 votes

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 os repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let ... 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 Others by jothee Veteran (92.5k points) | 10 views

0 votes

0 answers

10

CMI2016-B-2a
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex os 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 path of length at least $k$.

asked Dec 30, 2016 in Others by jothee Veteran (92.5k points) | 15 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 teh escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as $B$, see ... 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 Others by jothee Veteran (92.5k points) | 30 views

0 votes

1 answer

12

CMI2016-A-10
Which of the following relationships holds in general between the $scope$ of a variable and the $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 ... 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 Others by jothee Veteran (92.5k points) | 28 views

0 votes

0 answers

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 otehr city. The cotract ... 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 Others by jothee Veteran (92.5k points) | 13 views

0 votes

0 answers

14

CMI2016-A-8
An advertisement for a tennis magazine states, "If I'm not playin 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 Watcging tennis Reading about tennis None of the above

asked Dec 30, 2016 in Others by jothee Veteran (92.5k points) | 18 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, $\textit{Dosa Paradise}$ and $\textit{Kababs Unlimited}$, to which she travels by local train. The train to $\textit{Dosa Paradise}$ runs every 10 minutes, ... textit{Kababs Unlimited}$? $\frac{1}{5}$ $\frac{1}{3}$ $\frac{2}{5}$ $\frac{1}{2}$

asked Dec 30, 2016 in Others by jothee Veteran (92.5k points) | 43 views

+1 vote

0 answers

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; ... 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 Others by jothee Veteran (92.5k points) | 10 views

0 votes

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 Others by jothee Veteran (92.5k points) | 25 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 to $v$ has weight 65. Which of the statements is ... of $(u, v) = 12$ Weight of $(u, v) \geq 12$ Nothing can be said about the weight of $(u, v)$

asked Dec 30, 2016 in Others by jothee Veteran (92.5k points) | 44 views

0 votes

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 $*$ occuring 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 Others by jothee Veteran (92.5k points) | 21 views

0 votes

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$ such that $(2 ... 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 Others by jothee Veteran (92.5k points) | 34 views

0 votes

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: $\textit{there exists a vertex that is a neighbour of all other vertices}$. ... 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 Others by jothee Veteran (92.5k points) | 38 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

Recent Badges