The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged cmi2012
+3
votes
1
answer
1
CMI2012B02b
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n1i}.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})$.
asked
May 27, 2016
in
Theory of Computation
by
jothee
Veteran
(
105k
points)

331
views
descriptive
cmi2012
theoryofcomputation
finiteautomata
+4
votes
1
answer
2
CMI2012B05b
Given an undirected weighted graph $G = (V, E)$ with nonnegative 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 ... 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.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

331
views
cmi2012
descriptive
algorithms
graphalgorithms
minimumspanningtrees
+11
votes
4
answers
3
CMI2012B03b
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.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

609
views
descriptive
cmi2012
algorithms
algorithmdesign
+8
votes
1
answer
4
CMI2012B07
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.
asked
May 23, 2016
in
DS
by
jothee
Veteran
(
105k
points)

390
views
cmi2012
descriptive
datastructures
linkedlists
+1
vote
0
answers
5
CMI2012B06
A certain stringprocessing 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 nontrivial.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

348
views
cmi2012
descriptive
algorithms
dynamicprogramming
+1
vote
1
answer
6
CMI2012B05a
Given an undirected weighted graph $G = (V, E)$ with nonnegative 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 vertex ... 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$.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

76
views
cmi2012
descriptive
algorithms
graphalgorithms
minimumspanningtrees
+1
vote
1
answer
7
CMI2012B04
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.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

148
views
cmi2012
algorithms
divideandconquer
+5
votes
1
answer
8
CMI2012B03a
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.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

308
views
cmi2012
descriptive
algorithms
algorithmdesign
+12
votes
1
answer
9
CMI2012B02a
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n1i}.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})$.
asked
May 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
105k
points)

698
views
cmi2012
descriptive
theoryofcomputation
finiteautomata
+10
votes
1
answer
10
CMI2012B01
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$.)
asked
May 23, 2016
in
Graph Theory
by
jothee
Veteran
(
105k
points)

336
views
cmi2012
descriptive
graphtheory
graphconnectivity
+15
votes
2
answers
11
CMI2012A10
Consider the following functions $f$ and $g$. f(){ x = x50; 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$
asked
May 23, 2016
in
Operating System
by
jothee
Veteran
(
105k
points)

471
views
cmi2012
operatingsystem
processsynchronization
+14
votes
3
answers
12
CMI2012A09
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 compiletime by a modern compiler. I, II and III I and II I and III None of them
asked
May 23, 2016
in
Compiler Design
by
jothee
Veteran
(
105k
points)

720
views
cmi2012
compilerdesign
compilationphases
normal
+3
votes
1
answer
13
CMI2012A08
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
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

275
views
cmi2012
algorithms
sorting
timecomplexity
asymptoticnotations
+6
votes
5
answers
14
CMI2012A07
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}$
asked
May 23, 2016
in
Probability
by
jothee
Veteran
(
105k
points)

499
views
cmi2012
probability
+6
votes
2
answers
15
CMI2012A06
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$
asked
May 23, 2016
in
Numerical Ability
by
jothee
Veteran
(
105k
points)

328
views
cmi2012
numericalability
pigeonholeprinciple
+4
votes
1
answer
16
CMI2012A05
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
asked
May 23, 2016
in
Numerical Ability
by
jothee
Veteran
(
105k
points)

237
views
cmi2012
logicalreasoning
+1
vote
1
answer
17
CMI2012A04
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}})$
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

74
views
cmi2012
algorithms
identifyfunction
timecomplexity
+1
vote
1
answer
18
CMI2012A03
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$
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

73
views
cmi2012
algorithms
identifyfunction
+4
votes
1
answer
19
CMI2012A02
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
asked
May 23, 2016
in
Graph Theory
by
jothee
Veteran
(
105k
points)

227
views
cmi2012
graphtheory
trees
+15
votes
3
answers
20
CMI2012A01
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.
asked
May 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
105k
points)

1.2k
views
cmi2012
theoryofcomputation
regularlanguages
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
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 Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged cmi2012
Recent Blog Comments
@cshub.....if you are branch computer engineering...
Hey all! I can't see the CS branch here? How...
it's depends year to year
What was the average cutoff that was maintained...
@Shivateja MST I don't think it will go high
50,741
questions
57,251
answers
198,057
comments
104,685
users