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 cmi2017
+5
votes
1
answer
1
CMI2017B7
Consider the following function that takes as input a sequence $A$ of integers with n elements,$A[1],A[2], \dots ,A[n]$ and an integer $k$ and returns an integer value. The function length$(S)$ returns the length of the sequence $S$. Comments ... complexity of this algorithm in terms of the length of the input sequence $A$? Give an example of a worstcase input for this algorithm.
asked
Feb 5, 2018
in
Algorithms
by
Tesla!
Boss
(
18.4k
points)

401
views
cmi2017
algorithms
timecomplexity
descriptive
+1
vote
1
answer
2
CMI2017B6
We are given a sequence of pairs of integers $(a_1, b_1),(a_2, b_2), \dots ,(a_n, b_n)$. We would like to compute the largest $k$ such that there is a sequence of numbers $c_{i_1} \leq c_{i_2} \leq \dots \leq c_{i_k}$ ... each $j \leq k$, $c_{i_j}=a_{i_j}$ or $c_{i_j} = b_{i_j}$ . Describe an algorithm to solve this problem and explain its complexity.
asked
Feb 5, 2018
in
Algorithms
by
Tesla!
Boss
(
18.4k
points)

153
views
cmi2017
algorithms
timecomplexity
descriptive
+1
vote
2
answers
3
CMI2017B5
An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle. A $\text{leaf}$ in a tree is a vertex that ... $ \in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.
asked
Feb 5, 2018
in
Graph Theory
by
Tesla!
Boss
(
18.4k
points)

189
views
cmi2017
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
descriptive
+2
votes
2
answers
4
CMI2017B4
In a party there are $2n$ participants, where $n$ is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than $n^2.$
asked
Feb 5, 2018
in
Combinatory
by
Tesla!
Boss
(
18.4k
points)

174
views
cmi2017
engineeringmathematics
discretemathematics
permutationandcombination
descriptive
0
votes
0
answers
5
CMI2017B3
Let $Σ = \{a, b\}$. Given words $u, v \in Σ*$ , we say that $v$ extends $u$ if $v$ is of the form $xuy$ for some $x, y ∈ Σ^*$ . Given a fixed word $u$ ... Yes if some word in the language of $\mathcal{A}$ extends $u$ and No if no word in the language of $\mathcal{A}$ extends $u$.
asked
Feb 5, 2018
in
Theory of Computation
by
Tesla!
Boss
(
18.4k
points)

86
views
cmi2017
theoryofcomputation
finiteautomata
descriptive
+2
votes
0
answers
6
CMI2017B2
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and has a name. Due to lack of coordination, the same name may be allotted to multiple routes. To make matters ... are carrying a GoMad pass or a GoCrazy pass, you can start at $s$ and arrive at $t$ using the sequence $σ$.
asked
Feb 5, 2018
in
Algorithms
by
Tesla!
Boss
(
18.4k
points)

102
views
cmi2017
algorithms
algorithmdesign
0
votes
1
answer
7
CMI2017B1
Let $Σ = \{a, b, c\}$. Let Leven be the set of all even length strings in $Σ^*$ $(a)$ Construct a deterministic finite state automaton for $L_{even}$. $(b$) We consider an operation $Erase_{ab}$ that takes as input a string $w \in Σ^*$ and erases all occurrences of the ... $L:$ $Erase_{ab}(L)$:= $\{ Erase_{ab}(w)\ \ w\in L\}$ Show that $Erase_{ab}(L_{even}$) is a regular language.
asked
Feb 5, 2018
in
Theory of Computation
by
Tesla!
Boss
(
18.4k
points)

130
views
cmi2017
theoryofcomputation
finiteautomata
+3
votes
1
answer
8
CMI2017A10
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference? If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$ ... don't know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.
asked
Feb 5, 2018
in
Algorithms
by
Tesla!
Boss
(
18.4k
points)

333
views
cmi2017
algorithms
reduction
pnpnpcnph
+1
vote
1
answer
9
CMI2017A09
Suppose we constructed the binary search tree shown below by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the input sequence $cannot$ be ... came after $12$ and $29$ came before $42$. $3$ came before $14$ and $16$ came before $28$.
asked
Feb 5, 2018
in
DS
by
Tesla!
Boss
(
18.4k
points)

119
views
cmi2017
datastructures
binarysearchtree
+4
votes
1
answer
10
CMI2017A08
A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of threedimensional points $[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].$ We sort these in ascending order by the second coordinate. Which of the following ... $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
asked
Feb 5, 2018
in
Algorithms
by
Tesla!
Boss
(
18.4k
points)

388
views
cmi2017
algorithms
sorting
0
votes
1
answer
11
CMI2017A07
Consider the following functions f() and g(). f(){ g(){ w=5; z=w+1; w=2*z+2; z=3*zw; } print(z); } We start with $w$ and $z$ set to $0$ and execute $f()$ and $g()$ in parallel—that is, at each step we either execute one statement from $f()$ or one statement from $g()$. Which of the following is not a possible value printed by $g()$ ? $2$ $1$ $2$ $4$
asked
Feb 5, 2018
in
Programming
by
Tesla!
Boss
(
18.4k
points)

106
views
cmi2017
programming
output
+1
vote
2
answers
12
CMI2017A06
What does the following function compute in terms of $n$ and $d$, for integer values of $d$ ? Note that the operation $/$ denotes floating point division, even if the arguments are both integers. function foo(n,d){ if (d == 0){ return 1; }else{ if (d < 0){ return foo(n,d+1)/n; ... values of $d$. $n \times d$ if $d>0$ ,$n\div d$ if $d<0$. $n \times d$ for all the values of $d$.
asked
Feb 5, 2018
in
Programming
by
Tesla!
Boss
(
18.4k
points)

132
views
cmi2017
programming
output
+2
votes
1
answer
13
CMI2017A05
Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements: There is a vertex of degree smaller than $8$ in $G$. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is true: I Only II Only Both I and II Neither I nor II
asked
Feb 5, 2018
in
Graph Theory
by
Tesla!
Boss
(
18.4k
points)

148
views
cmi2017
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
1
answer
14
CMI2017A04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at ... number of edges. Find a spanning tree with minimum cost. Find a minimal coloring. Find a minimum size vertex cover.
asked
Feb 5, 2018
in
Graph Theory
by
Tesla!
Boss
(
18.4k
points)

116
views
cmi2017
graphconnectivity
easy
+8
votes
1
answer
15
CMI2017A03
Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a Tshirt, then Aditi gets bangles. If Abhay does not get shoes or Aditi gets bangles, the mother will be happy. Which of the following is TRUE? If the ... shoes. If the mother is not happy, then Asha did not get a necklace and Arun did not get a Tshirt. None of the above.
asked
Feb 5, 2018
in
Numerical Ability
by
Tesla!
Boss
(
18.4k
points)

284
views
cmi2017
logicalreasoning
+5
votes
1
answer
16
CMI2017A02
An FM radio channel has a repository of $10$ songs. Each day, the channel plays $3$ distinct songs that are chosen randomly from the repository. Mary decides to tune in to the radio channel on the weekend after her exams. What is the probability that no song gets repeated during ...
asked
Feb 5, 2018
in
Probability
by
Tesla!
Boss
(
18.4k
points)

303
views
cmi2017
engineeringmathematics
probability
+7
votes
1
answer
17
CMI2017A01
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$ $(a^*b+b)^*$ $(a+b^*)^*$ $(a^*b)^*$
asked
Feb 5, 2018
in
Theory of Computation
by
Tesla!
Boss
(
18.4k
points)

418
views
cmi2017
theoryofcomputation
regularexpressions
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 cmi2017
Recent Blog Comments
Click on the computer science link .In the opened...
Guys where is the objection link? I can't find...
@smsubham. Are bhai bhai bhai !!! pura paper...
For Huffman encoding...
nops, ME was correct for addressing mode
50,737
questions
57,312
answers
198,342
comments
105,035
users