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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
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. For hardcopy of previous year questions please see
here
Recent questions tagged cmi2015
+2
votes
1
answer
1
CMI2015A02
A binary relation $R ⊆ (S S)$ is said to be Euclidean if for every $a, b, c ∈ S, (a, b) ∈ R$ and $(a, c) ∈ R$ implies $(b, c) ∈ R$. Which of the following statements is valid? If $R$ is Euclidean, $(b, a) ∈ R$ and $(c, a) ∈ R$, then $(b, c) ∈ R$ ... $R$ is Euclidean, $(a, b) ∈ R$ and $(b, c) ∈ R$, then $(a, c) ∈ R$, for every $a, b, c ∈ S$ None of the above.
asked
May 12, 2018
in
Set Theory & Algebra
by
Mk Utkarsh
Boss
(
34.8k
points)

163
views
cmi2015
relations
settheory&algebra
+2
votes
0
answers
2
CMI2015A04d
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... with an overlapping audience. In this setting, the graph theoretic question to be answered is: Find a maximum size independent set.
asked
May 29, 2016
in
Graph Theory
by
jothee
Veteran
(
98.7k
points)

109
views
cmi2015
descriptive
graphtheory
independentset
+3
votes
0
answers
3
CMI2015A04c
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... tree with minimum number of edges. Find a minimal colouring. Find a minimum size vertex cover. Find a maximum size independent set
asked
May 29, 2016
in
Graph Theory
by
jothee
Veteran
(
98.7k
points)

61
views
cmi2015
descriptive
graphtheory
vertexcover
+2
votes
0
answers
4
CMI2015A04b
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is: Find a minimal colouring.
asked
May 29, 2016
in
Graph Theory
by
jothee
Veteran
(
98.7k
points)

164
views
cmi2015
descriptive
graphtheory
graphcoloring
+2
votes
0
answers
5
CMI2015B07
There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products ... a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before checking bigger subsequences.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

116
views
cmi2015
descriptive
algorithms
dynamicprogramming
+4
votes
1
answer
6
CMI2015B06c
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n1); } } How much time does it take to compute $f(m, n)$ and $g(m, n)$?
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

149
views
cmi2015
descriptive
algorithms
timecomplexity
+5
votes
1
answer
7
CMI2015B06b
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n1); } } What does $g(m, n)$ compute, for nonnegative numbers $m$ and $n$?
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

79
views
descriptive
cmi2015
algorithms
identifyfunction
+2
votes
1
answer
8
CMI2015B06a
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n1); } } Compute $g(3, 7), \: g(345, 1), \: g(345, 4) \text{ and } \: g(345, 0)$.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

69
views
descriptive
cmi2015
algorithms
identifyfunction
+2
votes
0
answers
9
CMI2015B05
An airline runs flights between several cities of the world. Every flight connects two cities. A millionaire wants to travel from Chennai to Timbuktu by changing at most $k_1$ flights. Being a millionaire with plenty of time and money, he does not mind revisiting ... flights at most $k_1$ times. You can assume that the procedure can add or multiply two numbers in a single operation.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

62
views
cmi2015
descriptive
algorithms
+14
votes
1
answer
10
CMI2015B04
You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than $0$. Design a greedy algorithm to test whether these integers correspond to the degrees of some $n$vertex simple undirected graph $G = (V, E)$. [A simple graph has no selfloops and at most one edge between any pair of vertices].
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

454
views
cmi2015
descriptive
algorithms
greedyalgorithm
+2
votes
0
answers
11
CMI2015B03b
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more ... If she starts at the top with $P$ paans and 1 rupee, what is the minimum and maximum amount of money she can have at the end?
asked
May 27, 2016
in
Numerical Ability
by
jothee
Veteran
(
98.7k
points)

49
views
cmi2015
descriptive
numericalability
+3
votes
1
answer
12
CMI2015B03a
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more rotis. Suppose the cook starts at the top with $R$ rupees. What are all the possible amounts of money she can have at the end?
asked
May 27, 2016
in
Numerical Ability
by
jothee
Veteran
(
98.7k
points)

58
views
cmi2015
numericalability
descriptive
+1
vote
1
answer
13
CMI2015B02
Consider a social network with $n$ persons. Two persons $A$ and $B$ are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons $F_1, \dots, F_m$ such that $A$ and ... . It is known that there are $k$ persons such that no pair among them is connected. What is the maximum number of friendships possible?
asked
May 27, 2016
in
Combinatory
by
jothee
Veteran
(
98.7k
points)

83
views
descriptive
cmi2015
permutationandcombination
+3
votes
1
answer
14
CMI2015A10
The school athletics coach has to choose 4 students for the relay team. He calculates that there are 3876 ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order of the ... taken into account? Between 12,000 and 25,000 Between 75,000 and 99,999 Between 30,000 and 60,000 More than 100,000
asked
May 27, 2016
in
Combinatory
by
jothee
Veteran
(
98.7k
points)

87
views
cmi2015
permutationandcombination
+10
votes
2
answers
15
CMI2015A09
Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true: If $L_2$ is regular, then $L_1$ must also be regular. If $L_1$ is regular, then $L_2$ must also be regular. Either both $L_1$ and $L_2$ are regular, or both are not regular. None of the above.
asked
May 27, 2016
in
Theory of Computation
by
jothee
Veteran
(
98.7k
points)

487
views
cmi2015
theoryofcomputation
regularlanguages
+10
votes
4
answers
16
CMI2015A08
How many times is the comparison $i >= n$ performed in the following program? int i=85, n=5; main() { while (i >= n) { i=i1; n=n+1; } } $40$ $41$ $42$ $43$
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

637
views
cmi2015
algorithms
timecomplexity
+6
votes
2
answers
17
CMI2015A07
You arrive at a snack bar and you can't decide whether to order a lime juice or a lassi. You decide to throw a fair $6$sided die to make the choice, as follows. If you throw $2$ or $6$ you order a lime juice. If you throw a $4$, you order a lassi. Otherwise, you throw ... is the probability that you end up ordering a lime juice? $\frac{1}{3}$ $\frac{1}{2}$ $\frac{2}{3}$ $\frac{3}{4}$
asked
May 27, 2016
in
Probability
by
jothee
Veteran
(
98.7k
points)

345
views
cmi2015
probability
+6
votes
2
answers
18
CMI2015A06
Suppose we have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following can we infer from this fact? If the best algorithm for $B$ takes exponential time, there is no polynomial time algorithm for $A$. If the best ... we don't know whether there is a polynomial time algorithm for $B$, there cannot be a polynomial time algorithm for $A$.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.7k
points)

285
views
cmi2015
algorithms
pnpnpcnph
+13
votes
1
answer
19
CMI2015A05
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What is the degree of vertex $10$ ? $5$ $6$ $7$ $8$
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
98.7k
points)

351
views
cmi2015
graphtheory
degreeofgraph
easy
+2
votes
0
answers
20
CMI2015A04a
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... audience. In this setting, the graph theoretic question to be answered is: Find a spanning tree with minimum number of edges.
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
98.7k
points)

116
views
cmi2015
descriptive
graphtheory
spanningtree
+3
votes
1
answer
21
CMI2015A03
Suppose each edge of an undirected graph is coloured using one of three colours  red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not ... endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. (A) and (C).
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
98.7k
points)

135
views
cmi2015
graphtheory
graphcoloring
+4
votes
1
answer
22
CMI2015A01
Twin primes are pairs of numbers $p$ and $p+2$ such that both are primesfor instance, 5 and 7, 11 and 13, 41 and 43. The Twin Prime Conjecture says that there are infinitely many twin primes. Let $TwinPrime(n)$ be a predicate that is true if $n$ and $n+2$ are twin primes. ... $∃m. ∀n. n ≤ m$ implies TwinPrime(n) $∀m. ∃n. n ≤ m$ and TwinPrime(n) $∃m. ∀n.$ TwinPrime(n) implies $n ≤ m$
asked
May 27, 2016
in
Mathematical Logic
by
jothee
Veteran
(
98.7k
points)

206
views
cmi2015
mathematicallogic
firstorderlogic
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged cmi2015
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,807
answers
189,530
comments
80,837
users