Recent questions tagged cmi2017

+2 votes

1 answer

1

CMI2017-B-8
Consider the following function that takes as input a sequence $A$ of integers with n elements, $A\left [ A1 \right ], \left [ A2 \right ], \ldots, \left [ An \right ]$ and an integer $k$ and returns an integer value. The function length$(S)$ ... -case complexity of this algorithm in terms of the length of the input sequence $A$? Give an example of a worst-case input for this algorithm.

asked Feb 5 in Algorithms by Tesla! Boss (17.4k points) | 173 views

0 votes

1 answer

2

CMI2017-B-6
We are given a sequence of pairs of integers (a1, b1),(a2, b2), . . .(an, bn). We would like to compute the largest k such that there is a sequence of numbers ci1 ≤ ci2 ≤ . . . ≤ cik with 1 ≤ i1 < i2 < ... < ik ≤ n and for each j ≤ k, cij = aij or cij = bij . Describe an algorithm to solve this problem and explain its complexity.

asked Feb 5 in Algorithms by Tesla! Boss (17.4k points) | 110 views

0 votes

2 answers

3

CMI2017-B-5
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has degree 1. Prove that ... -that is, u ∈ V1 and v ∈ V2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.

asked Feb 5 in Graph Theory by Tesla! Boss (17.4k points) | 116 views

0 votes

2 answers

4

CMI2017-B-4
In a party there are 2n participants, where n is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than n2

asked Feb 5 in Combinatory by Tesla! Boss (17.4k points) | 122 views

0 votes

0 answers

5

CMI2017-B-3
Let Σ = {a, b}. Given words u, v ∈ Σ* , we say that v extends u if v is of the form xuy for some x, y ∈ Σ* . Given a fixed word u, we are interested in identifying whether a finite state automaton accepts some word that extends u. Describe an algorithm that takes ... u ∈ Σ* and reports Yes if some word in the language of A extends u and No if no word in the language of A extends u.

asked Feb 5 in Theory of Computation by Tesla! Boss (17.4k points) | 65 views

+1 vote

0 answers

6

CMI2017-B-2
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and has a name. Due to lack of coordination, the same name may be allotted to multiple routes. To make ... whether you are carrying a GoMad pass or a GoCrazy pass, you can start at s and arrive at t using the sequence σ.

asked Feb 5 in Algorithms by Tesla! Boss (17.4k points) | 60 views

0 votes

1 answer

7

CMI2017-B-1
Let Σ = {a, b, c}. Let Leven be the set of all even length strings in Σ* (a) Construct a deterministic finite state automaton for L$_{EVEN}$. (b) We consider an operation Erase$_{ab}$ that takes as input a string w ∈ Σ* and erases all occurrences of the pattern ab from w. Formally, ... $_{ab}$(L):= { Erease$_{ab}$(w) | w$\in$ L} Show that Erase$_{ab}$(L$_{even}$) is a regular language.

asked Feb 5 in Theory of Computation by Tesla! Boss (17.4k points) | 101 views

+1 vote

1 answer

8

CMI2017-A-10
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference? If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$ ... don't know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.

asked Feb 5 in Algorithms by Tesla! Boss (17.4k points) | 196 views

+1 vote

1 answer

9

CMI2017-A-09
Suppose we constructed the binary search tree shown below by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the input sequence cannot be ... 37. (c) 1 came after 12 and 29 came before 42. (d) 3 came before 14 and 16 came before 28.

asked Feb 5 in Algorithms by Tesla! Boss (17.4k points) | 86 views

+1 vote

1 answer

10

CMI2017-A-08
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)]. We sort these in ascending order by the second coordinate. Which of the following corresponds to a ... 7),(6, 5, 9)] [(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]

asked Feb 5 in Algorithms by Tesla! Boss (17.4k points) | 221 views

0 votes

1 answer

11

CMI2017-A-07
Consider the following functions f() and g(). f(){ g(){ w=5; z=w+1; w=2*z+2; z=3*z-w; } print(z); } We start with w and z 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(). Which of the following is not a possible value printed by g()? (a) -2 (b) -1 (c) 2 (d) 4

asked Feb 5 in Programming by Tesla! Boss (17.4k points) | 76 views

0 votes

1 answer

12

CMI2017-A-06
What does the following function compute in terms of n and d, for integer values of d? Note that the operation / denotes floating point division, even if the arguments are both integers. function foo(n,d){ if (d == 0){ return 1; }else{ if (d < 0){ return foo(n,d+1)/n; }else{ return n* ... ;0 (b) $n^{d}$ for all values of d (c) n*d if d>0, n/d if d<0 (d) n*d for all values of d

asked Feb 5 in Programming by Tesla! Boss (17.4k points) | 107 views

+1 vote

1 answer

13

CMI2017-A-05
Let G be an arbitrary graph on n vertices with 4n − 16 edges. Consider the following statements: I There is a vertex of degree smaller than 8 in G. II There is a vertex such that there are less than 16 vertices at distance exactly 2 from it. Which of the following is true: (a) I only (c) Both I and II (b) II only (d) Neither I nor II

asked Feb 5 in Graph Theory by Tesla! Boss (17.4k points) | 93 views

0 votes

1 answer

14

CMI2017-A-04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with ... (b) Find a spanning tree with minimum (c) Find a minimal coloring. (d) Find a minimum size vertex cover.

asked Feb 5 in Graph Theory by Tesla! Boss (17.4k points) | 64 views

+1 vote

1 answer

15

CMI2017-A-03
Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a T-shirt, then Aditi gets bangles. If Abhay does not get shoes or Aditi gets bangles, the mother will be happy. Which of the following is TRUE? If the ... shoes. If the mother is not happy, then Asha did not get a necklace and Arun did not get a T-shirt. None of the above.

asked Feb 5 in Mathematical Logic by Tesla! Boss (17.4k points) | 144 views

+3 votes

1 answer

16

CMI2017-A-02
An FM radio channel has a repository of $10$ songs. Each day, the channel plays $3$ distinct songs that are chosen randomly from the repository. Mary decides to tune in to the radio channel on the weekend after her exams. What is the probability that no song gets repeated during ...

asked Feb 5 in Probability by Tesla! Boss (17.4k points) | 166 views

+3 votes

1 answer

17

CMI2017-A-01
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$ $(a^*b+b)^*$ $(a+b^*)^*$ $(a^*b)^*$

asked Feb 5 in Theory of Computation by Tesla! Boss (17.4k points) | 267 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 cmi2017

Recent Posts

Recent Blog Comments