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 cmi2011
+1
vote
1
answer
1
CMI2011B01b
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. ... preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

66
views
cmi2011
descriptive
graphtheory
graphconnectivity
+1
vote
0
answers
2
CMI2011B07b
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$—for example, $[0,1,0], [1,0,1,1], \dots$ $[]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \: head(l)$ returns the first ... g2(n) if (n == 0) then return(0) else return f2(g2(n1),g1(n)) endif What is the value of $g2(256)$ and $g2(257)$?
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

43
views
descriptive
cmi2011
algorithms
identifyfunction
+1
vote
1
answer
3
CMI2011B06b
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $dosas$ or $chapatis$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is ... $dosas$ or $chapatis$ between two big spoons and flipping the stack.) How many steps will your algorithm take in the worst case?
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

57
views
descriptive
cmi2011
algorithms
sorting
+1
vote
1
answer
4
CMI2011B02c
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are ... distinct vertices $u_1, u_2, u_3$ such that each of $G − u_1,\: G − u_2,\: \text{ and } \: G − u_3$ is connected.
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

61
views
cmi2011
descriptive
graphtheory
graphconnectivity
+1
vote
0
answers
5
CMI2011B02b
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Given a good graph, devise a linear time algorithm to find two such vertices.
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

58
views
descriptive
cmi2011
graphtheory
graphconnectivity
+1
vote
1
answer
6
CMI2011B04b
Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a nondeterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\}^* \mid \text{ reverse}(w) \in L \}$  here $reverse(w)$ denotes the ... where $x=yz, \: y \in L, \: z \in L^R \}$ is regular. How can you use $N$ to construct an automata for $L.L^R$?
asked
May 27, 2016
in
Theory of Computation
by
jothee
Veteran
(
112k
points)

79
views
descriptive
cmi2011
theoryofcomputation
regularlanguages
+2
votes
0
answers
7
CMI2011B07a
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$—for example, $[0,1,0], [1,0,1,1], \dots$ $[]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \: head(l)$ returns the first ... g2(n) if (n == 0) then return(0) else return f2(g2(n1),g1(n)) endif What is the value of $g2(7)$ and $g2(8)$?
asked
May 20, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

51
views
cmi2011
descriptive
algorithms
linkedlists
+5
votes
2
answers
8
CMI2011B06a
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $dosas$ or $chapatis$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk ... $dosas$ or $chapatis$ between two big spoons and flipping the stack.) Give an algorithm for sorting the disks using this operation.
asked
May 19, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

146
views
cmi2011
descriptive
algorithms
sorting
+1
vote
0
answers
9
CMI2011B05
Let $G=(V,E)$ be a undirected graph. We say $S \subseteq V$ is a clique if and only if for all $u,\: v \: \in S$, the edge $(u, v)$ is in $E$. Now let $G=(V,E)$ be a graph in which each vertex has degree at most 5. Give an algorithm to find the largest clique in $G$. What is the complexity of your algorithm?
asked
May 19, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

35
views
cmi2011
descriptive
algorithms
graphalgorithms
timecomplexity
+1
vote
1
answer
10
CMI2011B04a
Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a nondeterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\}  \text{ reverse}(w) \in L \}$  here ... in reverse. For example $reverse(0001) = 1000$. Show that $L^R$ is regular, How can you use $N$ to construct an automata to recognize $L^R$.
asked
May 19, 2016
in
Theory of Computation
by
jothee
Veteran
(
112k
points)

56
views
cmi2011
descriptive
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
0
answers
11
CMI2011B03
Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of M players, numbered 1, 2, . . . , M. You have N players, numbered 1, 2, . . . , N from which to choose your team, where N $\geq$ M. Each of the ... ; 2 + 4 − 9 + 1 − 2 = 6$ Propose an efficient algorithm to solve this problem and analyse its complexity.
asked
May 19, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

39
views
cmi2011
descriptive
algorithms
timecomplexity
+1
vote
0
answers
12
CMI2011B02a
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Show that for any subgraph $H$ of $G$, $H$ is good if and only if $G$ is good.
asked
May 19, 2016
in
Set Theory & Algebra
by
jothee
Veteran
(
112k
points)

41
views
cmi2011
descriptive
graphtheory
graphconnectivity
+1
vote
0
answers
13
CMI2011B01a
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road ... it always possible to colour each building with either red or blue so that every road connects a red and blue building?
asked
May 19, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

47
views
cmi2011
descriptive
graphcoloring
+2
votes
1
answer
14
CMI2011A10
Consider the following functions $f$ and $g$: f(){ x = x+1; x = y*y; x = xy; } g(){ y = y+1; y = x*x; y = yx; } Suppose we start with initial values of 1 for x and 2 for y and then execute $f$ and $g$ in parallel—that is, at each step we either execute one ... Which of the following is not a possible final state? x = 2, y = 2 x = 5, y = 1 x = 63, y = 72 x = 32, y = 5
asked
May 19, 2016
in
Operating System
by
jothee
Veteran
(
112k
points)

58
views
cmi2011
operatingsystem
concurrency
+1
vote
1
answer
15
CMI2011A09
You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your laptop? Turing machine Linear bounded automaton Pushdown automaton Finite state automaton
asked
May 19, 2016
in
Theory of Computation
by
jothee
Veteran
(
112k
points)

89
views
cmi2011
theoryofcomputation
contextsensitive
nongate
+7
votes
2
answers
16
CMI2011A08
In programming languages like C, C++, Python . . . the memory used by a program is typically separated into two parts, the stack and the heap. Consider the following statements: A stack is efficient for managing nested function calls. Stack space is limited while heap space is ... false. 1 and 3 are true but 2 is false. 2 and 3 are true but 1 is false. All three statements are true.
asked
May 19, 2016
in
Compiler Design
by
jothee
Veteran
(
112k
points)

223
views
cmi2011
compilerdesign
runtimeenvironments
+13
votes
3
answers
17
CMI2011A07
Let $G=(V, E)$ be a graph. Define $\bar{G}$ to be $(V, \bar{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \bar{E}$ if and only if $(u, v) \notin E$. Then which of the following is true? $\bar{G}$ is always connected. $\bar{G}$ is connected if $G$ is not connected. At least one of $G$ and $\bar{G}$ connected. $G$ is not connected or $\bar{G}$ is not connected
asked
May 19, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

301
views
cmi2011
graphtheory
graphconnectivity
+1
vote
1
answer
18
CMI2011A06
A valuable sword belonging to the Grand King was stolen, and the three suspects were Ibn, Hasan, and Abu. Ibn claimed that Hasan stole it, and Hasan claimed that Abu stole it. It was not clear that one of them stole it, but it was later learnt that no innocent ... had lied. It was also learnt that the sword was stolen by only one person. Who stole the sword? Ibn Hasan Abu None of them
asked
May 19, 2016
in
Numerical Ability
by
jothee
Veteran
(
112k
points)

56
views
cmi2011
logicalreasoning
+1
vote
1
answer
19
CMI2011A05
A 3ary boolean function is a function that takes three boolean arguments and produces a boolean output. Let $f$ and $g$ be 3ary boolean functions. We say that $f$ and $g$ are $neighbours$ if $f$ and $g$ agree on at least one input and disagree on at least one input: that ... g(x',y',z')$. Suppose we fix a 3ary boolean function $h$. How many neighbours does $h$ have? 128 132 254 256
asked
May 19, 2016
in
Set Theory & Algebra
by
jothee
Veteran
(
112k
points)

59
views
cmi2011
functions
+1
vote
1
answer
20
CMI2011A04
Lavanya has to complete 12 courses for her degree. There are six compulsory courses: Basic and Advanced Mathematics, Basic and Advanced Physics and Basic and Advanced Electronics. She also has to complete six Optional Courses. Each course takes one semester to ... these constraints, what is the minimum number of semesters that Lavanya needs to complete her course requirements. 3 4 5 6
asked
May 19, 2016
in
Numerical Ability
by
jothee
Veteran
(
112k
points)

256
views
cmi2011
numericalability
logicalreasoning
+1
vote
2
answers
21
CMI2011A03
You have a bag with 347 black balls and 278 white balls. Without looking, you pick up two balls from the bag and apply the following rule. If both balls are of the same colour, you throw them both away. Otherwise, you throw away the black ball ... possible, but the probability of it being white is greater. Both colours are possible, but the probability of it being black is greater.
asked
May 19, 2016
in
Probability
by
jothee
Veteran
(
112k
points)

91
views
cmi2011
probability
+1
vote
1
answer
22
CMI2011A02
You have two sixsided cubic dice but they are numbered in a strange manner. On the first die, two opposite faces are numbered 1, two opposite faces are numbered 3 and the last pair of opposite faces are numbered 6. On the second die, the three pairs of opposing ... than 7. The probability that the sum is a multiple of 5 is the same as the probability that the sum is a prime number.
asked
May 19, 2016
in
Probability
by
jothee
Veteran
(
112k
points)

75
views
cmi2011
probability
+1
vote
1
answer
23
CMI2011A01
Let L $\subseteq \{0, 1\}^∗$ be a language accepted by a finite automaton. Let $F$ be some subset of $\{0, 1\}^∗$, containing 2011 strings. Which of the following statements is true? Justify your answer. $L \: \: \cup \:\: F$ is always regular ... string. $L \: \cup \: F$ is never regular. $L \: \cup \: F$ is regular only if $L$ contains $\in$ (the empty string).
asked
May 19, 2016
in
Theory of Computation
by
jothee
Veteran
(
112k
points)

111
views
cmi2011
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 cmi2011
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