Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged cmi2011
1
vote
2
answers
1
CMI2011-B-01b
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.
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
747
views
cmi2011
descriptive
graph-theory
graph-connectivity
1
vote
1
answer
2
CMI2011-B-07b
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(n-1),g1(n)) endif What is the value of $g2(256)$ and $g2(257)$?
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
494
views
descriptive
cmi2011
algorithms
identify-function
1
vote
1
answer
3
CMI2011-B-06b
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?
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
477
views
descriptive
cmi2011
algorithms
sorting
1
vote
1
answer
4
CMI2011-B-02c
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.
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
546
views
cmi2011
descriptive
graph-theory
graph-connectivity
1
vote
1
answer
5
CMI2011-B-02b
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.
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
637
views
descriptive
cmi2011
graph-theory
graph-connectivity
1
vote
1
answer
6
CMI2011-B-04b
Let $L \subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic 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$?
go_editor
asked
in
Theory of Computation
May 27, 2016
by
go_editor
460
views
descriptive
cmi2011
theory-of-computation
regular-language
2
votes
0
answers
7
CMI2011-B-07a
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(n-1),g1(n)) endif What is the value of $g2(7)$ and $g2(8)$?
go_editor
asked
in
DS
May 20, 2016
by
go_editor
381
views
cmi2011
descriptive
linked-list
12
votes
3
answers
8
CMI2011-B-06a
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.
go_editor
asked
in
Algorithms
May 19, 2016
by
go_editor
1.7k
views
cmi2011
descriptive
algorithms
sorting
1
vote
1
answer
9
CMI2011-B-05
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?
go_editor
asked
in
Algorithms
May 19, 2016
by
go_editor
600
views
cmi2011
descriptive
algorithms
graph-algorithms
time-complexity
1
vote
1
answer
10
CMI2011-B-04a
Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic 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$.
go_editor
asked
in
Theory of Computation
May 19, 2016
by
go_editor
487
views
cmi2011
descriptive
theory-of-computation
regular-language
finite-automata
1
vote
1
answer
11
CMI2011-B-03
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.
go_editor
asked
in
Algorithms
May 19, 2016
by
go_editor
608
views
cmi2011
descriptive
algorithms
time-complexity
3
votes
1
answer
12
CMI2011-B-02a
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.
go_editor
asked
in
Set Theory & Algebra
May 19, 2016
by
go_editor
539
views
cmi2011
descriptive
graph-connectivity
proof
1
vote
2
answers
13
CMI2011-B-01a
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?
go_editor
asked
in
Graph Theory
May 19, 2016
by
go_editor
672
views
cmi2011
descriptive
graph-coloring
5
votes
1
answer
14
CMI2011-A-10
Consider the following functions $f$ and $g$: f(){ x = x+1; x = y*y; x = x-y; } g(){ y = y+1; y = x*x; y = y-x; } 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 ... 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$
go_editor
asked
in
Operating System
May 19, 2016
by
go_editor
517
views
cmi2011
operating-system
concurrency
1
vote
1
answer
15
CMI2011-A-09
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
go_editor
asked
in
Theory of Computation
May 19, 2016
by
go_editor
1.1k
views
cmi2011
theory-of-computation
context-sensitive
non-gate
10
votes
3
answers
16
CMI2011-A-08
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.
go_editor
asked
in
Compiler Design
May 19, 2016
by
go_editor
1.7k
views
cmi2011
compiler-design
runtime-environment
24
votes
4
answers
17
CMI2011-A-07
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
go_editor
asked
in
Graph Theory
May 19, 2016
by
go_editor
1.8k
views
cmi2011
graph-theory
graph-connectivity
1
vote
2
answers
18
CMI2011-A-06
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
go_editor
asked
in
Analytical Aptitude
May 19, 2016
by
go_editor
4.9k
views
cmi2011
logical-reasoning
2
votes
2
answers
19
CMI2011-A-05
A $\text{3-ary}$ boolean function is a function that takes three boolean arguments and produces a boolean output. Let $f$ and $g$ be $\text{3-ary}$ 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{3-ary}$ boolean function $h$. How many neighbours does $h$ have? $128$ $132$ $254$ $256$
go_editor
asked
in
Set Theory & Algebra
May 19, 2016
by
go_editor
1.0k
views
cmi2011
functions
1
vote
1
answer
20
CMI2011-A-04
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$
go_editor
asked
in
Analytical Aptitude
May 19, 2016
by
go_editor
1.0k
views
cmi2011
analytical-aptitude
logical-reasoning
1
vote
3
answers
21
CMI2011-A-03
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.
go_editor
asked
in
Probability
May 19, 2016
by
go_editor
1.1k
views
cmi2011
probability
1
vote
1
answer
22
CMI2011-A-02
You have two six-sided 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.
go_editor
asked
in
Probability
May 19, 2016
by
go_editor
574
views
cmi2011
probability
1
vote
1
answer
23
CMI2011-A-01
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).
go_editor
asked
in
Theory of Computation
May 19, 2016
by
go_editor
881
views
cmi2011
theory-of-computation
regular-language
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged cmi2011
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...