menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
GO Book for GATECSE 2022
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
Exact tag match
Recent Posts
A Short Guide to GATE
Seeking DRDO Scientist B previous year papers
STRATEGY TO EFFECTIVELY CREATE SHORT & MICRO NOTES FOR GATE EXAM AND BEST REVISION STRATEGY BY AIR-"152"
My Video Experience AIR-152 GATE_CS(Some More motivation)!!!!!!
AIR 33 IN GATE 2021 AND HOW I USED GATEOVERFLOW DURING MY PREPARATION
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3.1k)
Programming and DS
(5.2k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Follow @gateoverflow
GATE Overflow
Recent questions tagged cmi2013
Recent Blog Comments
A Wonderful journey and a Great compilation of...
@hitchh1ker Thank You :) I will share TOC and...
may i know ur emailID ...just want to ask few...
Congratulations !!👍 Were u preparing full...
Congrats and thanks for detailed guide.
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions tagged cmi2013
2
votes
1
answer
1
CMI2013-B-06b
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 your aim is ... dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.
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 your aim is to watch ... on dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.
asked
Jun 8, 2016
in
Algorithms
Arjun
451
views
cmi2013
descriptive
algorithms
dynamic-programming
3
votes
2
answers
2
CMI2013-B-07
Consider the code below, defining the function $\text{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(a-1,1); else return mystery(a-1, mystery(a,b-1)); } Express $\text{mystery}(1, \:n)$ ... of $n$. Express $\text{mystery}(2,\: n)$ as a function of $n$. Compute $\text{mystery}(3, \:2)$ and $\text{mystery}(3, 3)$.
Consider the code below, defining the function $\text{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(a-1,1); else return mystery(a-1, mystery(a,b-1)); } Express $\text{mystery}(1, \:n)$ as a function of $n$. Express $\text{mystery}(2,\: n)$ as a function of $n$. Compute $\text{mystery}(3, \:2)$ and $\text{mystery}(3, 3)$.
asked
May 23, 2016
in
Algorithms
jothee
336
views
cmi2013
descriptive
recurrence
1
vote
1
answer
3
CMI2013-B-06a
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 your aim is to ... match whose starting time is strictly later than the finishing time of the current match? Analyze the worse-case complexity of your algorithm.
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 your aim is to watch as ... next match whose starting time is strictly later than the finishing time of the current match? Analyze the worse-case complexity of your algorithm.
asked
May 23, 2016
in
Algorithms
jothee
330
views
cmi2013
descriptive
algorithms
algorithm-design
3
votes
0
answers
4
CMI2013-B-05
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 either you or any of ... . Model this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
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 either you or any of your ... constraints. Model this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
asked
May 23, 2016
in
Algorithms
jothee
114
views
cmi2013
descriptive
algorithms
graph-algorithms
6
votes
0
answers
5
CMI2013-B-04
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)$.
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
jothee
367
views
cmi2013
algorithms
sorting
divide-and-conquer
descriptive
1
vote
2
answers
6
CMI2013-B-03
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.
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
jothee
290
views
cmi2013
descriptive
graph-theory
graph-connectivity
14
votes
2
answers
7
CMI2013-B-02
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$?
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
jothee
1.5k
views
cmi2013
descriptive
graph-theory
graph-connectivity
2
votes
1
answer
8
CMI2013-B-01
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^{n-1-i} .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.
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^{n-1-i} .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
jothee
148
views
cmi2013
descriptive
theory-of-computation
finite-automata
6
votes
2
answers
9
CMI2013-A-10
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 := i; endfor tmp := A[j]; ... endfor end The number of times the test $A[i] > A[\text{position}]$ is executed is: $100$ $5050$ $10000$ Depends on contents of $A$
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 := i; endfor tmp := A[j]; A[j] := A[ ... := tmp; endfor end The number of times the test $A[i] > A[\text{position}]$ is executed is: $100$ $5050$ $10000$ Depends on contents of $A$
asked
May 23, 2016
in
Algorithms
jothee
667
views
cmi2013
algorithms
time-complexity
9
votes
2
answers
10
CMI2013-A-09
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[position]) then ... A[position] := tmp; endfor end When the procedure terminates, the array A has been: Reversed Sorted in descending order Left unaltered Sorted in ascending order
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[position]) then position := i; ... ]; A[position] := 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
jothee
554
views
cmi2013
algorithms
identify-function
3
votes
1
answer
11
CMI2013-A-08
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$
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
Quantitative Aptitude
jothee
167
views
cmi2013
numerical-ability
sets
16
votes
3
answers
12
CMI2013-A-07
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.
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
jothee
942
views
cmi2013
mathematical-logic
logical-reasoning
17
votes
3
answers
13
CMI2013-A-06
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. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
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. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of degree ... of 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
jothee
2.9k
views
cmi2013
graph-theory
normal
degree-of-graph
29
votes
4
answers
14
CMI2013-A-05
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)$
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
jothee
2.7k
views
cmi2013
algorithms
sorting
1
vote
1
answer
15
CMI2013-A-04
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 context-free but not regular recursively enumerable but not context-free
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 context-free but not regular recursively enumerable but not context-free
asked
May 23, 2016
in
Theory of Computation
jothee
125
views
cmi2013
theory-of-computation
identify-class-language
1
vote
1
answer
16
CMI2013-A-03
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 top k scores on the ... the user. A good data structure for accumulating the scores and ranking them is: a queue a heap a stack a binary search tree
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 top k scores on the screen, ... by the user. 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
jothee
227
views
cmi2013
data-structures
binary-search-tree
12
votes
4
answers
17
CMI2013-A-02
$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 labeled 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\%$
$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 labeled 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
jothee
2.9k
views
cmi2013
probability
conditional-probability
1
vote
0
answers
18
CMI2013-A-01
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 wants to optimize the company's ... the most precise upper bound one can compute for the number of such items, given the data? $500$ $1000$ $5000$ $20000$
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 wants to optimize the company's inventory ... is 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
Quantitative Aptitude
jothee
135
views
cmi2013
numerical-ability
To see more, click for the
full list of questions
or
popular tags
.
...