Recent questions tagged cmi2012 / GATE Overflow for GATE CSE

4 votes

1 answer

1

CMI2012-B-02b
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})$.

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 fin...

go_editor

1.2k views

go_editor asked May 27, 2016

7 votes

1 answer

2

CMI2012-B-05b
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 ... 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.

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 give...

go_editor

1.2k views

go_editor asked May 27, 2016

12 votes

4 answers

3

CMI2012-B-03b
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.

Let $A$ be an array of $n$ integers, sorted so that $A \leq A \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ a...

go_editor

1.5k views

go_editor asked May 27, 2016

8 votes

1 answer

4

CMI2012-B-07
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 ... (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.

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...

go_editor

1.1k views

go_editor asked May 23, 2016

1 votes

0 answers

5

CMI2012-B-06
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 ... pieces. You may assume that all m locations are in the interior of the string so each split is non-trivial.

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 tak...

go_editor

1.5k views

go_editor asked May 23, 2016

1 votes

1 answer

6

CMI2012-B-05a
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 ... 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$.

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 give...

go_editor

487 views

go_editor asked May 23, 2016

1 votes

1 answer

7

CMI2012-B-04
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]$ ... 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.

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...

go_editor

1.1k views

go_editor asked May 23, 2016

5 votes

1 answer

8

CMI2012-B-03a
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.

Let $A$ be an array of $n$ integers, sorted, so that $A \leq A \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there are indices $k$ an...

go_editor

999 views

go_editor asked May 23, 2016

14 votes

1 answer

9

CMI2012-B-02a
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})$.

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 fin...

go_editor

1.8k views

go_editor asked May 23, 2016

11 votes

1 answer

10

CMI2012-B-01
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$.)

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: Cons...

go_editor

979 views

go_editor asked May 23, 2016

16 votes

2 answers

11

CMI2012-A-10
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 ... 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$

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 ...

go_editor

1.3k views

go_editor asked May 22, 2016

14 votes

2 answers

12

CMI2012-A-09
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

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...

go_editor

3.0k views

go_editor asked May 22, 2016

3 votes

1 answer

13

CMI2012-A-08
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 ... 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

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 arr...

go_editor

1.4k views

go_editor asked May 22, 2016

8 votes

5 answers

14

CMI2012-A-07
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}$

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}$

go_editor

2.0k views

go_editor asked May 22, 2016

7 votes

2 answers

15

CMI2012-A-06
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$

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 guara...

go_editor

2.2k views

go_editor asked May 22, 2016

5 votes

1 answer

16

CMI2012-A-05
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 ... 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

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...

go_editor

928 views

go_editor asked May 22, 2016

2 votes

1 answer

17

CMI2012-A-04
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 ... $a,\: b$ is $O(n)$ $O(\log \log n)$ $O(\log n)$ $O(n^{\frac{1}{2}})$

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$ i...

go_editor

617 views

go_editor asked May 22, 2016

2 votes

1 answer

18

CMI2012-A-03
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); ... = a and (b/2)*2 < b) return 2; end; return 3; } $\text{mystery}(75,210)$ returns $2$ $6$ $10$ $15$

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$ i...

go_editor

510 views

go_editor asked May 22, 2016

4 votes

2 answers

19

CMI2012-A-02
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

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...

go_editor

857 views

go_editor asked May 22, 2016

19 votes

3 answers

20

CMI2012-A-01
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.

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 regula...

go_editor

5.8k views

go_editor asked May 22, 2016

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