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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent questions tagged cmi2012
+1
vote
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_{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
(
112k
points)

93
views
descriptive
cmi2012
theoryofcomputation
finiteautomata
+2
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
(
112k
points)

98
views
cmi2012
descriptive
algorithms
graphalgorithms
minimumspanningtrees
+8
votes
3
answers
3
CMI2012B03b
Let $A$ be 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, \: 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
(
112k
points)

240
views
descriptive
cmi2012
algorithms
algorithmdesign
+5
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
(
112k
points)

115
views
cmi2012
descriptive
datastructure
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, ... + 1 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
(
112k
points)

233
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 ... argument 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
(
112k
points)

38
views
cmi2012
descriptive
algorithms
graphalgorithms
minimumspanningtrees
+1
vote
0
answers
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], but comparisons such as $A[i] < ... 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
(
112k
points)

77
views
cmi2012
algorithms
divideandconquer
+1
vote
1
answer
8
CMI2012B03a
Let $A$ be 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, \: 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
(
112k
points)

28
views
cmi2012
descriptive
algorithms
+3
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
(
112k
points)

107
views
cmi2012
descriptive
theoryofcomputation
finiteautomata
+3
votes
1
answer
10
CMI2012B01
Let $G=(V, E)$ be a graph where $V =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
(
112k
points)

109
views
cmi2012
descriptive
graphtheory
graphconnectivity
+9
votes
1
answer
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 is, at each step we 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
(
112k
points)

181
views
cmi2012
operatingsystem
concurrency
+9
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
(
112k
points)

273
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
(
112k
points)

186
views
cmi2012
algorithms
sorting
timecomplexity
asymptoticnotations
+4
votes
3
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
(
112k
points)

182
views
cmi2012
probability
+5
votes
1
answer
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
(
112k
points)

140
views
cmi2012
numericalability
pigeonhole
+3
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
(
112k
points)

85
views
cmi2012
logicalreasoning
+1
vote
0
answers
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 ... of recursive calls to $mystery$ on input $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
(
112k
points)

37
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); if (eo(a, ... if ((a/2)*2 == a and (b/2)*2 < b) return 2; end; return 3; } $mystery(75,210)$ returns 2 6 10 15
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

39
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
(
112k
points)

158
views
cmi2012
graphtheory
trees
+7
votes
2
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
(
112k
points)

412
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
My GATE journey
Believe..!!
Need a Serious Career Advice
Failure... ?
Applying to NUS
Follow @csegate
Gatecse
Recent questions tagged cmi2012
Recent Blog Comments
Congrats and Best of luck for life ahead :)
Congrats and Best of luck for life ahead :)
Congratulations @Hemant :) I am so happy for u. ...
Have u taken any online coaching ??
Same is for me. I am getting score 584. 2017 ...
34,239
questions
40,932
answers
116,230
comments
39,846
users