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 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
(
17.5k
points)

35
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
(
17.5k
points)

46
views
cmi2018
algorithmdesign
descriptive
+1
vote
0
answers
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
(
17.5k
points)

29
views
cmi2018
descriptive
algorithmdesign
0
votes
0
answers
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
(
42.4k
points)

35
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
(
42.4k
points)

44
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
(
42.4k
points)

36
views
isi2018pcbcs
algorithms
algorithmdesign
descriptive
+6
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
(
431k
points)

3.8k
views
gate2019
numericalanswers
algorithms
algorithmdesign
+2
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
(
431k
points)

551
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
(
105k
points)

23
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
(
323
points)

702
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
(
18.4k
points)

143
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
(
18.4k
points)

102
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
(
105k
points)

73
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
(
105k
points)

284
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
(
431k
points)

160
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
(
105k
points)

106
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
(
105k
points)

98
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
(
105k
points)

115
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
(
105k
points)

80
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
(
105k
points)

92
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
(
105k
points)

52
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
(
105k
points)

119
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
(
105k
points)

93
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
(
105k
points)

294
views
descriptive
isi2015pcbcs
algorithms
algorithmdesign
+2
votes
0
answers
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
(
105k
points)

123
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
(
105k
points)

610
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
(
105k
points)

103
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
(
105k
points)

71
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
(
105k
points)

40
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
(
105k
points)

33
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
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 algorithmdesign
Recent Blog Comments
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
absolutely right
50,737
questions
57,288
answers
198,197
comments
104,876
users