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 greedyalgorithm
+3
votes
2
answers
1
UGCNETJune2019II68
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an optimal solution in bottomup fashion Which of the following step(s) is/are common to both dynamic programming and greedy algorithms? Only $S_1$ Only $S_2$ Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$
asked
Jul 2, 2019
in
Algorithms
by
Arjun
Veteran
(
431k
points)

209
views
ugcnetjune2019ii
optimalsolution
dynamicprogramming
greedyalgorithm
0
votes
2
answers
2
GEEKS FOR GEEKS GATE 2017 MOCK
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
asked
Jun 9, 2019
in
Algorithms
by
Hirak
Active
(
3.6k
points)

149
views
kruskalsalgorithm
graphalgorithms
greedyalgorithm
datastructures
0
votes
1
answer
3
MadeEasy Test Series: Algorithms  Minimum Spanning Trees
asked
Dec 18, 2018
in
Algorithms
by
mitesh kumar
Junior
(
605
points)

195
views
madeeasytestseries
algorithms
greedyalgorithm
minimumspanningtrees
0
votes
1
answer
4
Fibonacci number time complexity
Consider the following code segment to find the $n^{th}$ Fibonacci number: Fib(n) { if(n==0) {return 0;} if(n==1) {return 1;} else { return(Fib(n1) + Fib(n2)); } } The time complexity of the above code and time complexity of the same problem solved using dynamic programming is______ $A)O(n^{2}),O(n)$ $B)O(2^{n}),O(n)$ $C)O(2^{n}),O(n^{2})$ $D)$None of the above
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

243
views
algorithms
greedyalgorithm
dynamicprogramming
0
votes
2
answers
5
Job Sequencing Problem (Greedy Algorithm)
If job $J=(J_{1},J_{2},J_{3},J_{4})$ are given their processing time $T_{i}=(1,1,2,3)$ and deadline are $D_{i}=(3,4,2,3)$ maximum how many job can be done$?$ $A)1$ $B)2$ $C)3$ $D)All$
asked
Nov 10, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

557
views
algorithms
greedyalgorithm
deadlines
0
votes
1
answer
6
Greedy Method Algorithm
Single source shortest path problems can be implemented by greedy algorithms using A. Singly linked list B. Min heap C. AVL tree D. All of the above
asked
Sep 25, 2018
in
Algorithms
by
Vaishnavi01
(
153
points)

147
views
greedyalgorithm
+1
vote
1
answer
7
Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
asked
Jul 30, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.7k
points)

139
views
greedyalgorithm
dijkstrasalgorithm
+1
vote
0
answers
8
Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
asked
Jul 30, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.7k
points)

64
views
greedyalgorithm
0
votes
0
answers
9
self doubt on HUFFMAN
in Huffman Code, we get extract the minimum at each time, but my minimum is creating duplicate, then which one i choose? i am getting the same avg.no.of bits for every Huffman tree, but the problem is my tree is changing therefore representing the character also changed, if some one asks ... $\frac{12}{30} $
asked
Jul 26, 2018
in
Algorithms
by
Shaik Masthan
Veteran
(
65.8k
points)

163
views
greedyalgorithm
huffmancode
0
votes
0
answers
10
What is the time complexity of Makeset function in kruskal algorithm ?
what is the timecomplexity in kruskal algorithm for the overall step 2 where for each vertex Makeset function is called ? How come overall time for this step is O(v log v) ? We are performing this Operation for all the ... right because after we come out of loop we have v sets of 1 vertex each . Please explain this clearly .
asked
Jul 22, 2018
in
Algorithms
by
radha gogia
Loyal
(
6.4k
points)

130
views
algorithms
greedyalgorithm
+4
votes
1
answer
11
Clrs 16.26
Show how to solve the fractional knapsack problem in $O(n)$ time.
asked
Jul 22, 2018
in
Algorithms
by
Prince Sindhiya
Loyal
(
5.9k
points)

183
views
algorithms
greedyalgorithm
+1
vote
1
answer
12
Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithmspacetimecomplexity) But how ????
asked
Jul 5, 2018
in
Algorithms
by
Hardik Maheshwari
(
101
points)

636
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
0
votes
1
answer
13
cormen 3rd edition Q. 16.26
Show how to solve the fractional knapsack problem in O(n) time. The solution include that we can find the median in O(n) time and then solving the fractional knapsack problem on input of size n/2, but the pi/wi is not sorted, so how do we have the equation T(n) = T(n/2) + cn?
asked
Jun 19, 2018
in
Algorithms
by
Aarvi Chawla
(
375
points)

239
views
greedyalgorithm
0
votes
1
answer
14
MadeEasy Test Series: Algorithms  Greedy Algorithm
Consider the following graph: If the edge weight of minimum spanning tree are given and edge weight of each edge is distinct, then the minimum value of sum (a, b, c, d, e, f, g) is __________. My Strategy : According to me a = 11 (because if we see the ... and likewise g = 11,f = 12,b = 8,e = 8,d = 9,c = 6.Hence Sum is = 65 Made Easy Solution :
asked
Apr 30, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

137
views
madeeasytestseries
algorithms
greedyalgorithm
0
votes
1
answer
15
MadeEasy Test Series: Algorithms  Greedy Algorithm
Consider the following message: The number of bits required for huffman encoding of the above message are __________? My Strategy: But the answer given is 52bits i used standard Algorithem Made Easy Solution :
asked
Apr 30, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

284
views
madeeasytestseries
huffmancode
greedyalgorithm
algorithms
+18
votes
5
answers
16
GATE201848
Consider the weights and values of items listed below. Note that there is only one unit of each item. $\begin{array}{ccc}\hline \textbf{Item number} & \textbf{Weight (in Kgs) }& \textbf{Value (in rupees)} \\\hline \text{$1$} & \text{$10 ... list. The total value of items picked by the greedy algorithm is denoted by $V_{greedy}$. The value of $V_{opt}V_{greedy}$ is ____
asked
Feb 14, 2018
in
Algorithms
by
gatecse
Boss
(
17.5k
points)

5.6k
views
gate2018
algorithms
greedyalgorithm
numericalanswers
+2
votes
0
answers
17
TEST SERIES
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? PQ, QR, RW, RS, VX, VU, WV, ST PQ, QR, RW, WV, VX, VU, RS, ST PQ, PX, XV, VU, UR, RS, RW, ST PQ, PX, XV, VU, UR, RW, RS, ST PLEASE EXPLAIN.
asked
Jan 8, 2018
in
Algorithms
by
ankit_thawal
Active
(
1.4k
points)

286
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+1
vote
0
answers
18
MadeEasy Test Series: Algorithms  Spanning Tree
can someone provide a detailed solution of this??
asked
Jan 1, 2018
in
Algorithms
by
Kalpataru Bose
(
413
points)

267
views
madeeasytestseries
algorithms
graphalgorithms
spanningtree
minimumspanningtrees
greedyalgorithm
+1
vote
1
answer
19
Greedy vs Dynamic
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution. Is the above statement correct?
asked
Dec 13, 2017
in
Algorithms
by
Tuhin Dutta
Boss
(
10.6k
points)

646
views
algorithms
greedyalgorithm
dynamicprogramming
+2
votes
1
answer
20
Optimal Merge Pattern
Given a set of sorted files f1,f2,f3,f4,f5 of lengths 99,27,71,199,259 we need to merge these files into a single sorted file Using Optimal Merge Pattern.
asked
Dec 13, 2017
in
Algorithms
by
VIKAS TIWARI
Junior
(
727
points)

1.5k
views
optimalmergepattern
algorithms
greedyalgorithm
0
votes
1
answer
21
Knapsack
The following Knapsack bag. The Knapsack bag maximum Capacity is 50. Find out the maximum profit for Fractional Knapsack. 90 80.25 85.50 91.2
asked
Nov 17, 2017
in
Algorithms
by
Parshu gate
Active
(
3.1k
points)

625
views
algorithms
knapsack
greedyalgorithm
fractional
+2
votes
2
answers
22
greedy technique
Assume coins with denominator 20,15,5 and 1 are available ,we are required to make a sum of 33,using minimum number of coins.Difference between answer using greedy technique and correct answer will be ____________
asked
Nov 11, 2017
in
Algorithms
by
set2018
Loyal
(
7.9k
points)

187
views
algorithms
greedyalgorithm
+4
votes
1
answer
23
algorithms practice question
problem of making change for n cents using the fewest number of coins
asked
Aug 10, 2017
in
Algorithms
by
Pavan Kumar Munnam
Boss
(
10.7k
points)

239
views
algorithms
greedyalgorithm
0
votes
1
answer
24
Fractional Knapsack(Greedy Method)
Consider the following instance of the knapsack problem: n=3 , W=50 , (v1,v2,v3) = (60,100,120) and weight (w1,w2,w3) = (10,20,30) . solve the given knapsack problem applying greedy algorithm.
asked
Apr 15, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

556
views
algorithms
knapsack
greedyalgorithm
+1
vote
1
answer
25
Find the shortest tour for given graph using greedy approach
... directed graph as forward /backward distances are not same. But how to solve using Greedy Approach using TravelSalesman Problem(TSP) ?
asked
Mar 1, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

447
views
algorithms
greedyalgorithm
travellingsalesmanproblem
+4
votes
2
answers
26
Greedy Algorithm Confusing Question
US portal Denominations are 1,10,21,34,70 , 100 and 350 . A) Make 140 Cents . Verify whether Greedy choice fails or not B) Make 182 Cents. Verify whether greedy choice fails or not. 1)Greedy fails in A 2) Greedy fails in B 3)Greedy does not fails in A 4)Greedy does not fails in B
asked
Feb 28, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

616
views
algorithms
greedyalgorithm
+2
votes
0
answers
27
Testbook Test Series: Algorithms  Greedy Algorithm
The optimal time required in merging the list of size 11, 21, 33, 34,45,54,60 is my answer (11+21)*4+ 33*3 +(34+45)*3 + (54+60)*2 but the provided answer is 269 to 282 I don't think I have solved it wrong but just want to confirm is there any other way to do this?
asked
Jan 22, 2017
in
Algorithms
by
Pankaj Joshi
Active
(
2.7k
points)

380
views
testbooktestseries
testseries
merging
algorithms
greedyalgorithm
+6
votes
2
answers
28
KnapsackGreedy
asked
Jan 21, 2017
in
Algorithms
by
Sarvottam Patel
Junior
(
987
points)

598
views
greedyalgorithm
knapsack
algorithms
+3
votes
3
answers
29
Time complexity of fractionak knapsack using greedy algorithm is O(n^2)??TRUE/FALSE
asked
Jan 12, 2017
in
Algorithms
by
firki lama
Junior
(
681
points)

4.2k
views
greedyalgorithm
algorithms
+20
votes
2
answers
30
GATE200584b
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ ... $} & \text{$3$} \\\hline \end{array}$ What is the maximum profit earned? $147$ $165$ $167$ $175$
asked
Nov 15, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

1.1k
views
gate2005
algorithms
greedyalgorithm
processschedule
normal
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 greedyalgorithm
Recent Blog Comments
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
Cut off will be between 95115 not more than that.
50,737
questions
57,378
answers
198,522
comments
105,314
users