The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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.
Recent questions tagged cmi2013
+2
votes
1
answer
1
CMI2013B06b
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so ... to compute the maximum number of complete matches you can watch next week. Analyze the worsecase complexity of your algorithm.
asked
Jun 8, 2016
in
Algorithms
by
Arjun
Veteran
(
347k
points)

154
views
cmi2013
descriptive
algorithms
dynamicprogramming
+2
votes
2
answers
2
CMI2013B07
Consider the code below, defining the function $mystery:$ mystery(a,b){ if (a < 0 or b < 0) return 0; else if (a == 0) return b+1; else if (b == 0) return mystery(a1,1); else return mystery(a1, mystery(a,b1)); } Express ... )$ as a function of $n$. Express $mystery(2,\: n)$ as a function of $n$. Compute $mystery(3, \:2)$ and $mystery(3, 3)$.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

128
views
cmi2013
descriptive
recursion
+1
vote
0
answers
3
CMI2013B06a
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, ... starting time is strictly later than the finishing time of the current match? Analyze the worsecase complexity of your algorithm.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

33
views
cmi2013
descriptive
algorithms
+3
votes
0
answers
4
CMI2013B05
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by ... this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worstcase complexity of your algorithm.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

33
views
cmi2013
descriptive
algorithms
graphalgorithms
+4
votes
0
answers
5
CMI2013B04
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$th smallest element in the union of the two lists in time $O(\log m + \log n)$.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

185
views
cmi2013
algorithms
sorting
divideandconquer
descriptive
+1
vote
2
answers
6
CMI2013B03
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.
asked
May 23, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

100
views
cmi2013
descriptive
graphtheory
graphconnectivity
+2
votes
1
answer
7
CMI2013B02
A complete graph on $n$ vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let $G$ be a complete graph on 10 vertices. Let $u, \: v, \: w$ be three distinct vertices in $G$. How many simple paths are there from $u$ to $v$ going through $w$?
asked
May 23, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

131
views
cmi2013
descriptive
graphtheory
counting
+2
votes
1
answer
8
CMI2013B01
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be the value of $x$ interpreted as a binary number, where $a_0$ is the most significant bit. More formally, $val(x)$ is given by $\Sigma_{0 \leq i < n} 2^ ... a_i$ Design a finite automaton that accepts exactly the set of binary strings $x$ such that $val(x)$ is divisible by either 4 or 5.
asked
May 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
112k
points)

50
views
cmi2013
descriptive
theoryofcomputation
finiteautomata
+5
votes
2
answers
9
CMI2013A10
The below question is based on following program: procedure mystery (A : array [1..100] of int) int i,j,position,tmp; begin for j := 1 to 100 do position := j; for i := j to 100 do if (A[i] > A[position]) then position ... tmp; endfor end The number of times the test $A[i] > A[position]$ is executed is: $100$ $5050$ $10000$ Depends on contents of $A$
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

142
views
cmi2013
algorithms
timecomplexity
+7
votes
2
answers
10
CMI2013A09
The below question is based on the following program. procedure mystery (A : array [1..100] of int) int i,j,position,tmp; begin for j := 1 to 100 do position := j; for i := j to 100 do if (A[i] > A[ ... ] := tmp; endfor end When the procedure terminates, the array A has been: Reversed Sorted in descending order Left unaltered Sorted in ascending order
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

124
views
cmi2013
algorithms
identifyfunction
+2
votes
1
answer
11
CMI2013A08
In the passing out batch, 54 students know Java, 39 know Python and 43 know C++. Of these, 15 know both Java and Python, 17 know both Python and C++ and 23 know both Java and C++ and 11 know all three languages. If there are 100 students in the class, how many know none of these three languages? 3 8 17 19
asked
May 23, 2016
in
Numerical Ability
by
jothee
Veteran
(
112k
points)

49
views
cmi2013
numericalability
sets
+8
votes
3
answers
12
CMI2013A07
Consider the following two statements. There are infinitely many interesting whole numbers. There are finitely many uninteresting whole numbers. Which of the following is true? Statements 1 and 2 are equivalent. Statement 1 implies statement 2. Statement 2 implies statement 1. None of the above.
asked
May 23, 2016
in
Mathematical Logic
by
jothee
Veteran
(
112k
points)

300
views
cmi2013
mathematicallogic
logicalreasoning
+3
votes
2
answers
13
CMI2013A06
A simple graph is one in which there are no selfloops and each pair of distinct vertices is connected by at most one edge.Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
asked
May 23, 2016
in
Graph Theory
by
jothee
Veteran
(
112k
points)

229
views
cmi2013
graphtheory
normal
degreeofgraph
+14
votes
2
answers
14
CMI2013A05
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time: $O(nm \log m)$ $O(mn \log n)$ $O(m + n)$ $O(mn)$
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
112k
points)

431
views
cmi2013
algorithms
sorting
+1
vote
1
answer
15
CMI2013A04
Consider the set of all words over the alphabet $\{x, y, z\}$ where the number of $y$’s is not divisible by 2 or 7 and no $x$ appears after a $z$. This language is: regular not known to be regular contextfree but not regular recursively enumerable but not contextfree
asked
May 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
112k
points)

31
views
cmi2013
theoryofcomputation
identifyclasslanguage
+1
vote
1
answer
16
CMI2013A03
When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the ... . A good data structure for accumulating the scores and ranking them is: a queue a heap a stack a binary search tree
asked
May 23, 2016
in
DS
by
jothee
Veteran
(
112k
points)

50
views
cmi2013
datastructure
+6
votes
4
answers
17
CMI2013A02
10% of all email you receive is spam. Your spam filter is 90% reliable: that is, 90% of the mails it marks as spam are indeed spam and 90% of spam mails are correctly labelled as spam. If you see a mail marked spam by your filter, what is the probability that it really is spam? 10% 50% 70% 90%
asked
May 23, 2016
in
Probability
by
jothee
Veteran
(
112k
points)

508
views
cmi2013
probability
conditionalprobability
bayestheorem
+1
vote
0
answers
18
CMI2013A01
Ball Mart has $10^7$ different items in stock across all its stores worldwide. The company has collected billing data for $10^{10}$ customer transactions. Each individual bill has at most 10 distinct items in it. Ball Mart’s CEO ... the most precise upper bound one can compute for the number of such items, given the data? 500 1000 5000 20000
asked
May 23, 2016
in
Numerical Ability
by
jothee
Veteran
(
112k
points)

27
views
cmi2013
numericalability
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
Applying to NUS
THANK U GO !!
need advice
A journey with GO from Air: 2494 to Air: 223
Thanks to GATE Overflow.
Follow @csegate
Gatecse
Recent questions tagged cmi2013
Recent Blog Comments
kafi badjiya likhe ho ....... Congrats once again ...
every year many companies visit ...
congratulations
Yes. That is Go pdf
Congrats Ankush :) :)
34,210
questions
40,895
answers
116,086
comments
39,794
users