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 cmi2011
+1
vote
2
answers
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
(
105k
points)

144
views
cmi2011
descriptive
graphtheory
graphconnectivity
+1
vote
1
answer
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, \text{ 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
(
105k
points)

82
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, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the ... $\text{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
(
105k
points)

97
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$ ... such that we cannot find three distinct vertices $u_1, u_2, u_3$ such that each of $G − u_1,\: G − u_2,$ and $G − u_3$ is connected.
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
105k
points)

122
views
cmi2011
descriptive
graphtheory
graphconnectivity
+1
vote
1
answer
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
(
105k
points)

109
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
(
105k
points)

115
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, \text{ 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
DS
by
jothee
Veteran
(
105k
points)

98
views
cmi2011
descriptive
linkedlists
+11
votes
3
answers
8
CMI2011B06a
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the ... or $\text{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
(
105k
points)

491
views
cmi2011
descriptive
algorithms
sorting
+1
vote
1
answer
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
(
105k
points)

84
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 \}$ ... 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
(
105k
points)

88
views
cmi2011
descriptive
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
1
answer
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, \dots , M$. You have $N$ players, numbered $1, 2, \dots , N$ from which to choose your team, where $N \geq M$. Each of the ... Propose an efficient algorithm to solve this problem and analyse its complexity.
asked
May 19, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

96
views
cmi2011
descriptive
algorithms
timecomplexity
+2
votes
1
answer
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
(
105k
points)

105
views
cmi2011
descriptive
graphconnectivity
proof
+1
vote
1
answer
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
(
105k
points)

90
views
cmi2011
descriptive
graphcoloring
+4
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 parallelthat is, at each step we either execute one ... 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
(
105k
points)

100
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
(
105k
points)

195
views
cmi2011
theoryofcomputation
contextsensitive
nongate
+10
votes
3
answers
16
CMI2011A08
In programming languages like C, C++, Python $\dots$ 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 not. ... $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
(
105k
points)

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

688
views
cmi2011
graphtheory
graphconnectivity
+1
vote
2
answers
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
(
105k
points)

133
views
cmi2011
logicalreasoning
+2
votes
2
answers
19
CMI2011A05
A $\text{3ary}$ boolean function is a function that takes three boolean arguments and produces a boolean output. Let $f$ and $g$ be $\text{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 ... $\text{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
(
105k
points)

175
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 complete. ... 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
(
105k
points)

342
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 ... are 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
(
105k
points)

173
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 ... 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
(
105k
points)

140
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$ ... . $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
(
105k
points)

182
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged cmi2011
Recent Blog Comments
When will the results be declared based on...
For the questions with two answers as per the...
@MiNiPanda Congrax mate for this success !
Mostly authentic links, it can be Stackoverflow,...
While raising objections what works as...
50,737
questions
57,324
answers
198,408
comments
105,173
users