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 algorithms
Webpage for Algorithms
0
votes
1
answer
1
For loop
Q. Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 (a) Half of the product of the 3 consecutive ... (b) Onethird of the product of the 3 consecutive integers (c) Onesixth of the product of the 3 consecutive integers (d) None of the above
asked
17 hours
ago
in
Algorithms
by
EKANSH
(
75
points)

5
views
algorithms
0
votes
2
answers
2
trees
Given a preorder, postorder and inorder traversal of a tree, is it always possible to obtain a tree that satisfies each of the three conditions? Or is it possible to not obtain a tree at all?
asked
1 day
ago
in
DS
by
Parimal Paritosh
(
227
points)

20
views
binarytree
algorithms
spanningtree
binarysearchtree
0
votes
0
answers
3
Radix Sort Problem
The complexity of Radix Sort is O(wn), for n keys which are integers of word size w. Here, w=log2(n^k)=k log2(n) So, the complexity is O(wn)=O(k log2(n) n) For instance if size is n^3 the complexity would be O( ... ) Then why we say radix sort sorts the input in linear time? Similar Concept used to solve : https://gateoverflow.in/3353/gate2008it43
asked
1 day
ago
in
Algorithms
by
Na462
Active
(
1.3k
points)

6
views
algorithms
radix
sorting
timecomplexity
radixsort
+1
vote
0
answers
4
Minimum Spanning Tree Problem
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then: 1. Shortest path will remain same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
asked
1 day
ago
in
Algorithms
by
Na462
Active
(
1.3k
points)

14
views
minimumspanningtrees
algorithms
mst
graphalgorithms
0
votes
0
answers
5
DFSAlgorithm
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2. In such case in the graph there will be two cycles : One Cycle will ... one v. There cannot be a graph containig a single cycle and containing both u and v and also satisfy above Constraint. Am I right?
asked
1 day
ago
in
Algorithms
by
Na462
Active
(
1.3k
points)

46
views
dfs
algorithms
graphalgorithms
0
votes
0
answers
6
Heap Smallest Element
My question is in Question like find 5th Smallest element in a heap: It requires O(logn) time if we do only Delete operation 5 Times.But what if the array contains no 5th smallest element say our array contain [1,1,1,1, ... min operation n number of times which would give nlogn time? Plz Clear my doubt https://gateoverflow.in/1110/gate200323
asked
2 days
ago
in
Algorithms
by
Na462
Active
(
1.3k
points)

55
views
heap
binaryheap
algorithms
+1
vote
1
answer
7
Binary Tree
I have doubt when its asked to know number of labelled and unlabelled binary tree : For labelled = (On basis of labelling) T(n) = 2nCn/(n+1) * n! For unlabelled = (On Basis of Geometric Sturucture) T(n) = (2n)Cn/n+1 Right? What if its Asked for BST what will be the answer in both the above cases and Why?
asked
3 days
ago
in
Algorithms
by
Na462
Active
(
1.3k
points)

45
views
datastructure
binarytree
binarysearchtree
algorithms
+5
votes
3
answers
8
GATE201848
Consider the weights and values of items listed below. Note that there is only one unit of each item. Item number Weight (in Kgs) Value (in rupees) 1 10 60 2 7 28 3 4 20 4 2 24 The task is to pick a subset of these items such that ... The total value of items picked by the greedy algorithm is denoted by $V_{greedy}$. The value of $V_{opt}V_{greedy}$ is ____
asked
6 days
ago
in
Algorithms
by
gatecse
Veteran
(
18k
points)

1.5k
views
gate2018
algorithms
greedyalgorithm
numericalanswers
+6
votes
4
answers
9
GATE201847
Consider the following undirected graph G: Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ____
asked
6 days
ago
in
Algorithms
by
gatecse
Veteran
(
18k
points)

1.2k
views
gate2018
algorithms
graphalgorithms
minimumspanningtrees
numericalanswers
+2
votes
1
answer
10
GATE201843
Let $G$ be a graph with 100! vertices!, with each vertex labelled by a distinct permutation od the numbers 1, 2, ..., 100. There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two ... $y$ denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then $y+10z$ = ____
asked
6 days
ago
in
Algorithms
by
gatecse
Veteran
(
18k
points)

999
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
+2
votes
5
answers
11
GATE201831
Assume that multiplying a matrix $G_1$ of dimension $ p \times q$ with another matrix $G_2$ of dimension $q \times r$ requires $pqr$ scalar multiplications. Computing the product of $n$ matrices $G_1G_2G_3 \ dots G_n$ can ... , the explicitly computed pairs is/are $F_1F_2$ and $F_3F_4$ only $F_2F_3$ only $F_3F_4$ only $F_2F_2$ and $F_4F_5$ only
asked
6 days
ago
in
Algorithms
by
gatecse
Veteran
(
18k
points)

1.1k
views
gate2018
algorithms
dynamicprogramming
+3
votes
2
answers
12
GATE20183
A queue is implemented using a noncircular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $n$ denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be ... (1), \theta(1)$ $\theta(1), \theta(n)$ $\theta(n), \theta(1)$ $\theta(n), \theta(n)$
asked
6 days
ago
in
DS
by
gatecse
Veteran
(
18k
points)

1.2k
views
gate2018
algorithms
datastructure
queues
normal
linkedlists
0
votes
1
answer
13
Constants In Analysis Of Algorithms
asked
Feb 10
in
Algorithms
by
bvarun
(
15
points)

33
views
algorithms
0
votes
1
answer
14
linked list
the sorage requirements of a linked stack with n elements will be what
asked
Feb 9
in
DS
by
kd.....
(
33
points)

53
views
linkedlists
datastructure
algorithms
programminginc
0
votes
1
answer
15
CMI2017B8
Consider the following function that takes as input a sequence A of integers with n elements, A[1], A[2], . . . , A[n] and an integer k and returns an integer value. The function length(S) returns the length of sequence S. Comments ... algorithm in terms of the length of the input sequence A? (c) Give an example of a worstcase input for this algorithm.
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.2k
points)

87
views
cmi2017
algorithms
0
votes
1
answer
16
CMI2017B6
We are given a sequence of pairs of integers (a1, b1),(a2, b2), . . .(an, bn). We would like to compute the largest k such that there is a sequence of numbers ci1 ≤ ci2 ≤ . . . ≤ cik with 1 ≤ i1 < i2 < ... < ik ≤ n and for each j ≤ k, cij = aij or cij = bij . Describe an algorithm to solve this problem and explain its complexity.
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.2k
points)

59
views
cmi2017
algorithms
timecomplexity
+1
vote
1
answer
17
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 ... are carrying a GoMad pass or a GoCrazy pass, you can start at s and arrive at t using the sequence σ.
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.2k
points)

31
views
cmi2017
algorithms
+1
vote
1
answer
18
CMI2017A10
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference? (a) If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A (b) If the best ... we don't know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.2k
points)

43
views
cmi2017
algorithms
theoryofcomputation
+1
vote
1
answer
19
CMI2017A09
Suppose we constructed the binary search tree shown below by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the ... (c) 1 came after 12 and 29 came before 42. (d) 3 came before 14 and 16 came before 28.
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.2k
points)

55
views
cmi2017
algorithms
0
votes
1
answer
20
CMI2017A08
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)]. We sort these in ascending order by the second coordinate. Which of the ... , 9)] (d) [(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.2k
points)

97
views
cmi2017
algorithms
sorting
0
votes
1
answer
21
CMI2017A04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be ... Find a spanning tree with minimum (c) Find a minimal coloring. (d) Find a minimum size vertex cover.
asked
Feb 5
in
Graph Theory
by
Tesla!
Veteran
(
14.2k
points)

34
views
algorithms
graphalgorithms
cmi2017
0
votes
1
answer
22
Finding max value of X in MST
I have this doubt that if the maximum value of x is to be found so that it is included in MST, then will it be 3 or 4? Because if it is 3 then there is no doubt that it would be included in the MST but if it is 4 then ... I consider? If the opposite was asked i.e. the minimum value of x so that it never gets included in MST then it is 5.
asked
Feb 2
in
Algorithms
by
MiNiPanda
Boss
(
5.7k
points)

63
views
algorithms
0
votes
0
answers
23
virtual gate sorting algo
An array of n distinct elements is said to be unsorted if for every index i such that 2 ≤ i ≤ n − 1, either A[i] > max{A[i − 1], A[i + 1]}, or A[i] < min{A[i − 1], A[i + 1]}. What is the timecomplexity of the fastest algorithm that takes as ... n) but not O(n) (B) O(n) but not O( √n) (C) O( √n) but not O(log n) (D) O(log n) but not O(1)
asked
Jan 31
in
Algorithms
by
Utsav09
Active
(
1.4k
points)

32
views
sorting
testseries
virtualgate
algorithms
0
votes
0
answers
24
Time complexity
#include<stdio.h> int main() { int sum =0; for(limit=1;limit<=n;limit*=2) { for(i=0;i<limit;i++) { for(j=0;j<n;j+=2) { sum+=j; } for(j=1;j<n;j*=2) { sum*=j; } } } }
asked
Jan 31
in
Programming
by
junaid ahmad
Veteran
(
12.5k
points)

67
views
timecomplexity
algorithms
0
votes
0
answers
25
Merge Sort
Let A,B,C,D,E are sorted sequences having length 70,74,80,85,102 respectively.They are merged into a single sequence by merging together two sequences at a time.The minimum number of comparisons that will be needed by algorithm in best case for going merging is _________.
asked
Jan 31
in
Algorithms
by
VS
Boss
(
7.9k
points)

95
views
mergesort
algorithms
sorting
+2
votes
0
answers
26
Equivalent Complexity
Given f(n) = ω(n2). Which of the following can never hold? a. f(n) = O (n3) b. f(n) = Ω (n2) c. f(n) = θ (n2) d. f(n) = ω (n)
asked
Jan 30
in
Algorithms
by
Tuhin Dutta
Boss
(
7.6k
points)

34
views
algorithms
asymptoticnotations
timecomplexity
+2
votes
1
answer
27
#distinct MSTs
......................................................
asked
Jan 28
in
Algorithms
by
Tuhin Dutta
Boss
(
7.6k
points)

65
views
algorithms
mst
spanningtree
+1
vote
0
answers
28
Gate_2018_Mock_Test
is there is any short cut ? I am using prism algoritham ...its tak too much time
asked
Jan 28
in
Algorithms
by
Harikesh Kumar
Active
(
1.7k
points)

27
views
algorithms
+1
vote
0
answers
29
Huffman Coding
Which of the following statements is/are correct? P:In Huffman Coding, the item with the second lowest probability is always at the leaf that is furthest from the root Q: In Huffman Coding, the item with the highest probability is always at the leaf that ... is the child of the root Edit :Answer is P and Q R is not always true and always word i missed :(
asked
Jan 27
in
Algorithms
by
sunil sarode
Active
(
1.3k
points)

61
views
huffmancode
algorithms
+2
votes
1
answer
30
Back edge,tree edge,forward edges in BFS
asked
Jan 27
in
DS
by
MIRIYALA JEEVAN KUMA
Active
(
1.5k
points)

86
views
algorithms
bfs
dfs
graphalgorithms
programminginc
datastructure
Page:
1
2
3
4
5
6
...
55
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
NIELIT(17 Dec 2017) Result Out
Contest/challenge GATE201825
IISC admission
Admission in IITS through COAPS
IITKanpur
Follow @csegate
Gatecse
Recent questions tagged algorithms
Recent Blog Comments
iam getting 65 in sta ,my serial number is ...
Yes..this is the list of candidates who secured ...
But this is not Final list.
Yes, Generally Data Science should be preferred. ...
Those who answered 35 must challenge  and even 1 ...
33,620
questions
40,170
answers
114,128
comments
38,554
users