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 cmi2012
4
votes
1
answer
1
CMI2012-B-02b
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$ Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$. Construct a finite automaton that accepts exactly those strings $(a_0, b_0)(a_1, b_1) \dots (a_{n−1}, b_{n−1}) \in \Sigma^*$ such that $val(b_0b_1 \dots b_{n−1}) = 4 · val(a_0a_1 \dots a_{n−1})$.
go_editor
asked
in
Theory of Computation
May 27, 2016
by
go_editor
1.1k
views
descriptive
cmi2012
theory-of-computation
finite-automata
7
votes
1
answer
2
CMI2012-B-05b
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to ... claim the statement is true or a counterexample if the statement is false. All the shortest paths from $s$ to the other vertices are unchanged.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
1.2k
views
cmi2012
descriptive
algorithms
graph-algorithms
minimum-spanning-tree
12
votes
4
answers
3
CMI2012-B-03b
Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ and $l$ such that $A[k]+A[l] = x$. Design an $O(n)$ algorithm for this problem.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
1.4k
views
descriptive
cmi2012
algorithms
algorithm-design
8
votes
1
answer
4
CMI2012-B-07
We use the notation $[x1,x2,...,xn]$ to denote a list of integers. $[]$ denotes the empty list, and $[n]$ is the list consisting of one integer $n$. For a nonempty list l, $head(l)$ returns the first element of $l$, and $tail(l)$ returns the list ... (tail(l)) then return g(tail(l)) else return(false) When does $f(l)$ return the value true for an input $l$? Explain your answer.
go_editor
asked
in
DS
May 23, 2016
by
go_editor
1.0k
views
cmi2012
descriptive
data-structures
linked-list
1
vote
0
answers
5
CMI2012-B-06
A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes $n$ units of time for a string of length $n$, regardless of the location of the cut. Suppose, now ... pieces. You may assume that all m locations are in the interior of the string so each split is non-trivial.
go_editor
asked
in
Algorithms
May 23, 2016
by
go_editor
1.4k
views
cmi2012
descriptive
algorithms
dynamic-programming
1
vote
1
answer
6
CMI2012-B-05a
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other ... if you claim the statement is true or a counterexample if the statement is false. $T$ is still a minimum cost spanning tree of $G$.
go_editor
asked
in
Algorithms
May 23, 2016
by
go_editor
460
views
cmi2012
descriptive
algorithms
graph-algorithms
minimum-spanning-tree
1
vote
1
answer
7
CMI2012-B-04
You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way - i.e., you can check $A[i] == A[j]$ and $A[i] != A[j]$ ... elements are equal to each other. Use divide and conquer to come up with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.
go_editor
asked
in
Algorithms
May 23, 2016
by
go_editor
1.1k
views
cmi2012
algorithms
divide-and-conquer
5
votes
1
answer
8
CMI2012-B-03a
Let $A$ be an array of $n$ integers, sorted, so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there are indices $k$ and $l$ such that $A[k]+A[l] = x$. Design an $O(n \log n)$ time algorithm for this problem.
go_editor
asked
in
Algorithms
May 23, 2016
by
go_editor
957
views
cmi2012
descriptive
algorithms
algorithm-design
14
votes
1
answer
9
CMI2012-B-02a
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$ Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$. Construct a finite automaton that accepts the set of all strings $(a_0, b_0)(a_1, b_1) \dots (a_{n−1}, b_{n−1}) \in \: \Sigma^*$ such that $val(b_0b_1 \dots b_{n−1}) = 2 · val(a_0a_1 \dots a_{n−1})$.
go_editor
asked
in
Theory of Computation
May 23, 2016
by
go_editor
1.8k
views
cmi2012
descriptive
theory-of-computation
finite-automata
11
votes
1
answer
10
CMI2012-B-01
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Consider a path of maximum length in $G$.)
go_editor
asked
in
Graph Theory
May 23, 2016
by
go_editor
951
views
cmi2012
descriptive
graph-theory
graph-connectivity
16
votes
2
answers
11
CMI2012-A-10
Consider the following functions $f$ and $g$. f(){ x = x-50; y = y+50; } g( ) { a = a+x; a = a+y; } Suppose we start with initial values of $100$ for $x, 200$ for $y$, and $0$ for $a$, and then execute $f$ and $g$ in parallel - that ... either execute one statement from $f$ or one statement from $g$. Which of the following is not a possible final value of $a$? $300$ $250$ $350$ $200$
go_editor
asked
in
Operating System
May 22, 2016
by
go_editor
1.3k
views
cmi2012
operating-system
process-synchronization
14
votes
2
answers
12
CMI2012-A-09
Consider the following programming errors: Type mismatch in an expression. Array index out of bounds. Use of an uninitialized variable in an expression. Which of these errors will typically be caught at compile-time by a modern compiler. I, II and III I and II I and III None of them
go_editor
asked
in
Compiler Design
May 22, 2016
by
go_editor
2.9k
views
cmi2012
compiler-design
compilation-phases
normal
3
votes
1
answer
13
CMI2012-A-08
You are given two sorting algorithms A and B that work in time $O(n \log n)$ and $O(n^2)$, respectively. Consider the following statements: Algorithm $A$ will sort any array faster than algorithm $B$. On an average, algorithm $A$ will sort a given array faster ... be preferable to algorithm $B$. Which of the statements above are true? I, II and III I and III II and III None of them
go_editor
asked
in
Algorithms
May 22, 2016
by
go_editor
1.3k
views
cmi2012
algorithms
sorting
time-complexity
asymptotic-notation
8
votes
5
answers
14
CMI2012-A-07
A man has three cats. At least one is male. What is the probability that all three are male? $\frac{1}{2}$ $\frac{1}{7}$ $\frac{1}{8}$ $\frac{3}{8}$
go_editor
asked
in
Probability
May 22, 2016
by
go_editor
1.9k
views
cmi2012
probability
7
votes
2
answers
15
CMI2012-A-06
A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number of pieces of fruit that should be put in the basket in order to guarantee that either there are at least $8$ apples or at least $6$ bananas or at least $9$ oranges? $9$ $10$ $20$ $21$
go_editor
asked
in
Quantitative Aptitude
May 22, 2016
by
go_editor
2.1k
views
cmi2012
quantitative-aptitude
pigeonhole-principle
5
votes
1
answer
16
CMI2012-A-05
Amma baked a cake and left it on the table to cool. Before going for her bath, she told her four children that they should not touch the cake as it was to be cut only the next day. However when she got back from her bath she found that someone had ... truth and exactly one of them actually ate the piece of cake, who is the culprit that Amma is going to punish? Lakshmi Ram Aruna Varun
go_editor
asked
in
Analytical Aptitude
May 22, 2016
by
go_editor
884
views
cmi2012
logical-reasoning
2
votes
1
answer
17
CMI2012-A-04
The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder. mystery(a,b){ if (b == 0) return a; if (a < b) return mystery(b,a); if (eo(a ... $a,\: b$ is $O(n)$ $O(\log \log n)$ $O(\log n)$ $O(n^{\frac{1}{2}})$
go_editor
asked
in
Algorithms
May 22, 2016
by
go_editor
579
views
cmi2012
algorithms
identify-function
time-complexity
2
votes
1
answer
18
CMI2012-A-03
The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder. mystery(a,b){ if (b == 0) return a; if (a < b) return mystery(b,a); ... = a and (b/2)*2 < b) return 2; end; return 3; } $\text{mystery}(75,210)$ returns $2$ $6$ $10$ $15$
go_editor
asked
in
Algorithms
May 22, 2016
by
go_editor
480
views
cmi2012
algorithms
identify-function
4
votes
2
answers
19
CMI2012-A-02
Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following is true? $s=99$ $s=198$ $99 \: < \: s \: < \: 198$ None of the above
go_editor
asked
in
Graph Theory
May 22, 2016
by
go_editor
830
views
cmi2012
graph-theory
tree
19
votes
3
answers
20
CMI2012-A-01
Let $L \subseteq \{0,1\}^*$. Which of the following is true? If $L$ is regular, all subsets of $L$ are regular. If all proper subsets of $L$ are regular, then $L$ is regular. If all finite subsets of $L$ are regular, then $L$ is regular. If a proper subset of $L$ is not regular, then $L$ is not regular.
go_editor
asked
in
Theory of Computation
May 22, 2016
by
go_editor
5.7k
views
cmi2012
theory-of-computation
regular-language
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged cmi2012
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...