The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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 algorithmdesign
+1
vote
1
answer
1
CMI2019B6
Let $A$ be an $n\times n $ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If $k$ is present, we should report its position  that is, the row $i$ and ... $A.$ Justify the complexity of your algorithm. For both algorithms, describe a worstcase input where $k$ is present in $A.$
asked
Sep 13, 2019
in
Algorithms
by
gatecse
Boss

74
views
cmi2019
algorithms
algorithmdesign
descriptive
+2
votes
1
answer
2
CMI2018B4
You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by $2$ positions. Give an $O(\log n)$ time algorithm to find the largest element in a circularly shifted array. (The number of positions through which it has been shifted is unknown to you.)
asked
Sep 13, 2019
in
Algorithms
by
gatecse
Boss

87
views
cmi2018
algorithmdesign
descriptive
+1
vote
1
answer
3
CMI2018B6
You are playing an oldstyle video game in which you have to shoot down alien spaceships as they fly across the screen from left to right. Each spaceship flies across the screen at a specified height. You have an antiaircraft gun set to shoot down all ... space ships. Each gun can be initialized separately to a firing height and each gun can be separately reset to a lower value.
asked
Sep 13, 2019
in
Algorithms
by
gatecse
Boss

71
views
cmi2018
descriptive
algorithmdesign
0
votes
1
answer
4
ISI2018PCBCS6
The following function computes an array $SPF$, where, for any integer $1 < i < 1000$, $SPF[i]$ is the smallest prime factor of $i$. For example, $SPF[6]$ is $2$, and $SPF[11]$ is $11$. There are five missing parts in the following code, commented as $/* Blank */$. For each of them ... < 1000; j+= i) { /* Blank 4 */ if (SPF[j] == j) { SPF[j] = _____; /* Blank 5 */ } } } } }
asked
May 12, 2019
in
Algorithms
by
akash.dinkar12
Boss

97
views
isi2018pcbcs
algorithmdesign
descriptive
0
votes
0
answers
5
ISI2018PCBCS5
Consider a maxheap of $n$ distinct integers, $n ≥ 4$, stored in an array $\mathcal{A}[1 . . . n]$. The second minimum of $\mathcal{A}$ is the integer that is less than all integers in $\mathcal{A}$ except the minimum of $\mathcal{A}$. Find all possible array indices of $\mathcal{A}$ in which the second minimum can occur. Justify your answer.
asked
May 12, 2019
in
Algorithms
by
akash.dinkar12
Boss

106
views
isi2018pcbcs
algorithms
algorithmdesign
heap
descriptive
0
votes
0
answers
6
ISI2018PCBCS1
Consider an array of length n consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only a constant amount of extra space.
asked
May 12, 2019
in
Algorithms
by
akash.dinkar12
Boss

74
views
isi2018pcbcs
algorithms
algorithmdesign
descriptive
+9
votes
6
answers
7
GATE201925
Consider a sequence of $14$ elements: $A=[5, 10, 6, 3, 1, 2, 13, 4, 9, 1, 4, 12, 3, 0]$. The sequence sum $S(i,j) = \Sigma_{k=i}^j A[k]$. Determine the maximum of $S(i,j)$, where $0 \leq i \leq j <14$. (Divide and conquer approach may be used.) Answer: ___________
asked
Feb 7, 2019
in
Algorithms
by
Arjun
Veteran

4.8k
views
gate2019
numericalanswers
algorithms
algorithmdesign
+3
votes
1
answer
8
TIFR2019A5
Asha and Lata play a game in which Lata first thinks of a natural number between $1$ and $1000$. Asha must find out that number by asking Lata questions, but Lata can only reply by saying Yes or no . Assume that Lata always tells the truth. What is the least ... within which she can always find out the number Lata has thought of? $10$ $32$ $100$ $999$ $\text{None of the above}$
asked
Dec 18, 2018
in
Algorithms
by
Arjun
Veteran

801
views
tifr2019
algorithmdesign
binarysearch
0
votes
0
answers
9
ISI2016PCBCS7
Let $A$ be a sorted array of $n$ positive integers, such that $A[1] \leq A[2] \leq \dots \leq A[n]$. Given an integer $x$ as input, the goal is to find two array indices $k$ and $l$ such that $A[k]+A[l] =x$, if such indices exist; otherwise, the goal is to report 'Failure". Design an algorithm for this problem, that works in $O(n)$ time.
asked
Sep 18, 2018
in
Algorithms
by
jothee
Veteran

50
views
isi2016pcbcs
algorithmdesign
descriptive
+6
votes
1
answer
10
CMI2010  6
You are given a list of positive integers along with a sequence of operations from the set $\left \{ *,+\right \}$ .You construct expressions from these two lists so that: The numbers in the expression are drawn from the first list, without repetition and ... assume that the length of the first list is more than the length of the second list. Describe an algorithm to solve this problem.
asked
Apr 30, 2018
in
Algorithms
by
Sammohan Ganguly

821
views
algorithms
descriptive
cmi2010
algorithmdesign
0
votes
1
answer
11
ISI2017PCBC6
Let $A = \{a_1,a_2, \dots ,a_n\}$ be an array of $n$ distinct numbers. The array may not be sorted. The first element $a_1$ is said to be a blip if $a_1 > a_2$. Similar, the last element an is said to be a blip if $a_n > a_{n1}$. Among the ... $O(\log n)$ time algorithm for finding a blip in $A$. Justify the complexity of your algorithm.
asked
Apr 28, 2018
in
Algorithms
by
Tesla!
Boss

184
views
isi2017
algorithms
algorithmdesign
descriptive
+2
votes
0
answers
12
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

133
views
cmi2017
algorithms
algorithmdesign
+1
vote
1
answer
13
CMI2016B6
An automatic spelling checker works as follows. Given a word $w$, first check if $w$ is found in the dictionary. If $w$ is not in the dictionary, compute a dictionary entry that is close to $w$. For instance if the user types $\mathsf{ocurrance}$, the spelling checker ... alignments of $x$ and $y$. What is the running time of your algorithm (in terms of the lengths of $x$ and $y)?$
asked
Dec 31, 2016
in
Algorithms
by
jothee
Veteran

106
views
cmi2016
dynamicprogramming
algorithmdesign
descriptive
+1
vote
0
answers
14
CMI2016B1
A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as $B$, see picture below) and the ... and assuming that soldiers do not change their locations ($Hint$: Model this as a graph, with soldiers represented by the vertices.)
asked
Dec 30, 2016
in
Algorithms
by
jothee
Veteran

315
views
cmi2016
algorithms
descriptive
algorithmdesign
+2
votes
1
answer
15
ISI2014PCBA2b
Let $A$ be a 30 40 matrix having 500 nonzero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of nonzero entries in the $i$th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of nonzero entries in the $j$th column ... of the stack contains the value $max_{1\leq i \leq 30} r_i$. Write pseudocode for creating such a stack using a single scan of the matrix $A$.
asked
Jun 8, 2016
in
Algorithms
by
Arjun
Veteran

185
views
isi2014
algorithms
algorithmdesign
+2
votes
0
answers
16
ISI2011PCBA4b
Consider the following intervals on the real line: $A_1 = (13.3, 18.3) \: A_3 = (8.3, 23.3) − A_1 \cup A_2$ $A_2 = (10.8, 20.8) − A_1 \: A_4 = (5.8, 25.8) − A_1 \cup A_2 \cup A_3$ where $(a, b) = \{x : a < x < b\}$. Write pseudocode that ... given input $x \in (5.8, 25.8)$ belongs to, i.e., your pseudocode should calculate $i \in \{1, 2, 3, 4\}$ such that $x \in A_i$.
asked
Jun 3, 2016
in
Algorithms
by
jothee
Veteran

141
views
descriptive
isi2011
algorithms
algorithmdesign
+1
vote
1
answer
17
ISI2012PCBA3
Given an array $A = \{a_1, a_2, \dots, a_n\}$ of unsorted distinct integers, write a program in pseudocode for the following problem: given an integer $u$, arrange the elements of the array $A$ such that all the elements in A which are less than or equal to ... which are greater than $u$ are at the end of the array. You may use at most 5 extra variables apart from the array $A$.
asked
Jun 2, 2016
in
Algorithms
by
jothee
Veteran

134
views
descriptive
isi2012
algorithms
algorithmdesign
+1
vote
0
answers
18
ISI2013PCBCS7
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source vertex $s$ and a designated destination vertex $t$. Let $P(v)$ ... .]
asked
Jun 1, 2016
in
Algorithms
by
jothee
Veteran

150
views
descriptive
isi2013pcbcs
algorithms
graphtheory
algorithmdesign
+1
vote
0
answers
19
ISI2013PCBCS3
Let $M$ be an $(n \times n)$ matrix where each element is a distinct positive integer. Construct another matrix $M'$ by permuting the rows and/or permuting the columns, such that the elements of one row appear in increasing order ( ... structure that supports your algorithm. Clearly explain how much additional storage, other than the matrix itself, is required in your algorithm.
asked
Jun 1, 2016
in
Algorithms
by
jothee
Veteran

108
views
descriptive
isi2013pcbcs
algorithms
algorithmdesign
+2
votes
0
answers
20
ISI2013PCBCS2a
Draw a complete binary tree $T$ with $(N − 1)$ nodes where $N = 2^n$. Suppose each node in $T$ is a processor and each edge of $T$ is a physical link between two processors through which they can communicate. Given $M$ ... architecture to compute the sum of each array $SUM_i = \Sigma^N_{j=1} e_{ji}$ for all $i$ in $O(\log N + M)$ time.
asked
Jun 1, 2016
in
Algorithms
by
jothee
Veteran

137
views
descriptive
isi2013pcbcs
algorithms
algorithmdesign
+1
vote
0
answers
21
ISI2013PCBCS1a,b
Consider the $fast \: square$ and $multiply \: algorithm$ to calculate $x^y \: mod \: N$ as given below, where $x, \: y,\: N$ are positive integers and $1 \leq x, y < N$. Input: $x, \:y, \:N$ ... , all of which are of type $unsigned long long$ (i.e., 64bit unsigned integers). Discuss whether your program works perfectly for all possible input combinations.
asked
May 31, 2016
in
Algorithms
by
jothee
Veteran

65
views
descriptive
isi2013pcbcs
algorithms
algorithmdesign
+1
vote
1
answer
22
ISI2014PCBCS3a
Let $A$ and $B$ be two arrays, each containing $n$ distinct integers. Each of them is sorted in increasing order. Let $C = A \cup B$. Design an algorithm for computing the median of $C$ as efficiently as you can.
asked
May 31, 2016
in
Algorithms
by
jothee
Veteran

148
views
isi2014pcbcs
algorithms
algorithmdesign
+1
vote
0
answers
23
ISI2014PCBCS1
Assume you have a chocolate bar containing a number of small identical squares arranged in a rectangular pattern. Our job is to split the bar into small squares by breaking along the lines between the squares. We obviously want to do it with the minimum ... m as inputs and print the line numbers along the length and the breadth according to your strategy of breaking the chocolate.
asked
May 31, 2016
in
Algorithms
by
jothee
Veteran

118
views
isi2014pcbcs
descriptive
algorithms
algorithmdesign
+10
votes
2
answers
24
ISI2015PCBCS2a
You are given two strings $S$ and $T$, each of length $\alpha$, consisting only of lower case English letters $(a,b, \dots ,z)$. Propose an $O(\alpha)$time algorithm to decide whether $S$ can be obtained by permuting the symbols of $T$ ... $\text{YES}$; but if $S \: = \text{ trainee}$, $T\: = \text{ retinaa}$, your algorithm should return $\text{NO}$.
asked
May 29, 2016
in
Algorithms
by
jothee
Veteran

336
views
descriptive
isi2015pcbcs
algorithms
algorithmdesign
+2
votes
1
answer
25
ISI2015PCBA1
Given an array $A$ of n positive integers, write a program segment / pseudocode to print the histogram of $A$ using the hash character ($\#$). Your histogram should consist of $n$ vertical columns of $\#$ with the $i$th vertical bar containing $A[i]$ number of $\#$'s. For example, ...
asked
May 29, 2016
in
Algorithms
by
jothee
Veteran

152
views
isi2015pcba
descriptive
algorithms
algorithmdesign
+11
votes
4
answers
26
CMI2012B03b
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.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran

657
views
descriptive
cmi2012
algorithms
algorithmdesign
+1
vote
1
answer
27
CMI2010B01b
An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same ... should say feasible if it is feasible, otherwise output the minimum number of frequencies needed to utilise all 100 towers.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran

141
views
cmi2010
descriptive
algorithms
algorithmdesign
+2
votes
0
answers
28
CMI2015B05
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.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran

94
views
cmi2015
descriptive
algorithms
algorithmdesign
+2
votes
0
answers
29
CMI2014B06b
Let $A$ be array of $n$ integers that is not assumed to be sorted. You are given a number $x$. The aim is to find out if there are indices $k,\: l$ and $m$ such that $A[k] + A[l] + A[m] = x$. Design an algorithm for this problem that works in time $O(n^2)$.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran

54
views
cmi2014
descriptive
algorithms
algorithmdesign
+2
votes
0
answers
30
CMI2014B06a
Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots \leq A[n]$. You are given a number $x$x. The aim is to find out if there are indices $k$ and $l$ such that $A[k] + A[l] = x$. Design an algorithm for this problem that works in time $O(n)$.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran

58
views
cmi2014
descriptive
algorithms
algorithmdesign
Page:
1
2
next »
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
GATE Overflow Test Series  GATE CSE 2021
IIT gandhinagar mtech cse2020
IIT Delhi Research Interview Shortlists out
IIT Gandhinagar interview experience
IIT Gandhinagar Interview 2020
Subjects
All categories
General Aptitude
(1.9k)
Engineering Mathematics
(8.2k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged algorithmdesign
Recent Blog Comments
Verification will automatically expire after 400...
My Verification is showing as "Not verified Yet"...
The point calculation formula is changed. We were...
Keep doing problems. Chances are high that you...
The price will be the same till June 30th.
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,215
questions
59,981
answers
201,180
comments
94,644
users