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 cmi2015
1
vote
1
answer
1
CMI2015-B-01
Let $\Sigma=\{a,b\}.$ Given a language $L\underline\subset \Sigma^{\ast}$ and a word $w\in\Sigma^{\ast}$, define the languages: $Extend(L,w) :=\{xw\:|\:x\in L\}$ $Shrink(L,w) :=\{x\:|\:xw\in L\}$Show that if $L$ is regular, both $Extend(L,w)$ and $Shrink(L,w)$ are regular.
soujanyareddy13
asked
in
Theory of Computation
May 10, 2021
by
soujanyareddy13
377
views
cmi2015
regular-language
theory-of-computation
5
votes
2
answers
2
CMI2015-A-02
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.
Mk Utkarsh
asked
in
Set Theory & Algebra
May 12, 2018
by
Mk Utkarsh
654
views
cmi2015
relations
set-theory&algebra
3
votes
1
answer
3
CMI2015-B-07
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.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
329
views
cmi2015
descriptive
algorithms
dynamic-programming
4
votes
2
answers
4
CMI2015-B-06c
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), n-1); } } How much time does it take to compute $f(m, n)$ and $g(m, n)$?
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
461
views
cmi2015
descriptive
algorithms
time-complexity
5
votes
2
answers
5
CMI2015-B-06b
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), n-1); } } What does $g(m, n)$ compute, for nonnegative numbers $m$ and $n$?
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
312
views
descriptive
cmi2015
algorithms
identify-function
2
votes
2
answers
6
CMI2015-B-06a
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), n-1); } } Compute $g(3, 7), \: g(345, 1), \: g(345, 4) \text{ and } \: g(345, 0)$.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
336
views
descriptive
cmi2015
algorithms
identify-function
2
votes
1
answer
7
CMI2015-B-05
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.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
309
views
cmi2015
descriptive
algorithms
algorithm-design
16
votes
2
answers
8
CMI2015-B-04
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 self-loops and at most one edge between any pair of vertices].
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
1.1k
views
cmi2015
descriptive
algorithms
greedy-algorithm
2
votes
2
answers
9
CMI2015-B-03b
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 ... 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?
go_editor
asked
in
Quantitative Aptitude
May 27, 2016
by
go_editor
313
views
cmi2015
descriptive
quantitative-aptitude
3
votes
2
answers
10
CMI2015-B-03a
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?
go_editor
asked
in
Quantitative Aptitude
May 27, 2016
by
go_editor
283
views
cmi2015
quantitative-aptitude
descriptive
2
votes
2
answers
11
CMI2015-B-02
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?
go_editor
asked
in
Combinatory
May 27, 2016
by
go_editor
440
views
descriptive
cmi2015
combinatory
4
votes
3
answers
12
CMI2015-A-10
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 runners is to be ... $12,000$ and $25,000$ Between $75,000$ and $99,999$ Between $30,000$ and $60,000$ More than $100,000$
go_editor
asked
in
Combinatory
May 27, 2016
by
go_editor
468
views
cmi2015
combinatory
13
votes
3
answers
13
CMI2015-A-09
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.
go_editor
asked
in
Theory of Computation
May 27, 2016
by
go_editor
946
views
cmi2015
theory-of-computation
regular-language
13
votes
5
answers
14
CMI2015-A-08
How many times is the comparison $i \geq n$ performed in the following program? int i=85, n=5; main() { while (i >= n) { i=i-1; n=n+1; } } $40$ $41$ $42$ $43$
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
4.3k
views
cmi2015
algorithms
time-complexity
11
votes
3
answers
15
CMI2015-A-07
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}$
go_editor
asked
in
Probability
May 27, 2016
by
go_editor
928
views
cmi2015
probability
7
votes
3
answers
16
CMI2015-A-06
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$.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
1.4k
views
cmi2015
algorithms
p-np-npc-nph
16
votes
2
answers
17
CMI2015-A-05
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$
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
1.5k
views
cmi2015
graph-theory
degree-of-graph
easy
2
votes
1
answer
18
CMI2015-A-04a
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 ... a spanning tree with minimum number of edges Find a minimal coloring Find a minimum size vertex cover Find a maximum size independent
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
478
views
cmi2015
descriptive
graph-theory
spanning-tree
3
votes
2
answers
19
CMI2015-A-03
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).
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
413
views
cmi2015
graph-theory
graph-coloring
7
votes
2
answers
20
CMI2015-A-01
Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes-for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that there are infinitely many twin primes. Let $\text{TwinPrime}(n)$ ... $\exists m \cdot \forall n \cdot \text{TwinPrime}(n) \text{ implies }n \leq m$
go_editor
asked
in
Mathematical Logic
May 27, 2016
by
go_editor
847
views
cmi2015
mathematical-logic
first-order-logic
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(648)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(853)
Recent questions tagged cmi2015
Recent Blog Comments
What will be upper age limit for upcoming ISRO...
please add GO Classes 2023 Computer Networks...
Please upload 4th Mock Test, due date was 4th Dec.
The counts of answered, marked etc in the exam...
Tests have been sent and all tests will be...