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. For hardcopy of previous year questions please see
here
Recent questions tagged greedyalgorithm
+1
vote
1
answer
1
Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
asked
Jul 30
in
Algorithms
by
Rishav Kumar Singh
Active
(
2k
points)

43
views
greedyalgorithm
dijkstrasalgorithm
+1
vote
0
answers
2
Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
asked
Jul 30
in
Algorithms
by
Rishav Kumar Singh
Active
(
2k
points)

13
views
greedyalgorithm
0
votes
0
answers
3
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 ... 1}{30},\frac{2}{30},\frac{3}{30},\frac{5}{30},\frac{5}{30}$ and $\frac{12}{30} $
asked
Jul 26
in
Algorithms
by
Shaik Masthan
Boss
(
15.5k
points)

56
views
greedyalgorithm
huffmancode
0
votes
0
answers
4
What is the time complexity of Makeset function in kruskal algorithm ?
asked
Jul 22
in
Algorithms
by
radha gogia
Loyal
(
7.2k
points)

48
views
algorithms
greedyalgorithm
+4
votes
1
answer
5
Clrs 16.26
Show how to solve the fractional knapsack problem in $O(n)$ time.
asked
Jul 22
in
Algorithms
by
Prince Sindhiya
Active
(
1.9k
points)

54
views
algorithms
greedyalgorithm
0
votes
0
answers
6
Space Complexity of Dijkastra's algorithm
asked
Jul 5
in
Algorithms
by
Hardik Maheshwari
(
59
points)

89
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
0
votes
1
answer
7
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
in
Algorithms
by
Aarvi Chawla
(
37
points)

55
views
greedyalgorithm
+9
votes
4
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
Feb 14
in
Algorithms
by
gatecse
Boss
(
18.1k
points)

2.6k
views
gate2018
algorithms
greedyalgorithm
numericalanswers
+2
votes
0
answers
9
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
in
Algorithms
by
ankit_thawal
Active
(
2.1k
points)

156
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+1
vote
1
answer
10
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
Loyal
(
7.9k
points)

405
views
algorithms
greedyalgorithm
dynamicprogramming
+1
vote
1
answer
11
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
(
451
points)

610
views
optimalmergepattern
algorithms
greedyalgorithm
0
votes
1
answer
12
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
(
4.9k
points)

346
views
algorithms
knapsack
greedyalgorithm
fractional
+2
votes
2
answers
13
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.8k
points)

123
views
algorithms
greedyalgorithm
+4
votes
1
answer
14
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.9k
points)

158
views
algorithms
greedyalgorithm
+1
vote
1
answer
15
Find the shortest tour for given graph using greedy approach
asked
Mar 1, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
5.1k
points)

339
views
algorithms
greedyalgorithm
travellingsalesmanproblem
+3
votes
2
answers
16
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
(
5.1k
points)

364
views
algorithms
greedyalgorithm
+5
votes
2
answers
17
KnapsackGreedy
asked
Jan 21, 2017
in
Algorithms
by
Sarvottam Patel
Active
(
1.1k
points)

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

3k
views
greedyalgorithm
algorithms
+17
votes
2
answers
19
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$ is earned if the task is completed before ... $18$ $18$ $10$ $23$ $16$ $25$ Deadline $7$ $2$ $5$ $3$ $4$ $5$ $2$ $7$ $3$ What is the maximum profit earned? $147$ $165$ $167$ $175$
asked
Nov 15, 2016
in
Algorithms
by
jothee
Veteran
(
99.8k
points)

658
views
gate2005
algorithms
greedyalgorithm
processschedule
normal
+1
vote
1
answer
20
UGCNETJune2014III62
Consider the fractional knapsack instance $n = 4, (p_{1} , p_{2} , p_{3} , p_{4} ) = (10, 10, 12, 18), (w_{1} , w_{2} , w_{3} , w_{4} ) = (2, 4, 6, 9)$ and $M = 15$. The maximum profit is given by (Assume $p$ and $w$ denotes profit and weight of objects respectively) $40$ $38$ $32$ $30$
asked
Jul 11, 2016
in
Others
by
makhdoom ghaya
Boss
(
40.1k
points)

1.2k
views
ugcnetjune2014iii
algorithms
greedyalgorithm
knapsack
+5
votes
1
answer
21
Optimal Substructure
asked
Jun 29, 2016
in
Algorithms
by
geet.m
(
203
points)

227
views
algorithms
greedyalgorithm
optimal
substructure
+13
votes
1
answer
22
CMI2015B04
You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than $0$. Design a greedy algorithm to test whether these integers correspond to the degrees of some $n$vertex simple undirected graph $G = (V, E)$. [A simple graph has no selfloops and at most one edge between any pair of vertices].
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
99.8k
points)

306
views
cmi2015
descriptive
algorithms
greedyalgorithm
+14
votes
2
answers
23
GATE200777
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$? $3$ $2.1875$ $2.25$ $1.9375$
asked
Apr 23, 2016
in
Algorithms
by
jothee
Veteran
(
99.8k
points)

1.4k
views
gate2007
algorithms
greedyalgorithm
normal
huffmancode
+2
votes
1
answer
24
AlGO: Madeeasy:TS Greedy Method How to approach
asked
Jan 29, 2016
in
Algorithms
by
Prasanna
Active
(
4.7k
points)

571
views
algorithms
greedyalgorithm
madeeasytestseries
+2
votes
1
answer
25
Optimal solution with greedy algorithm
Q: There are n white dots and n black dots, equally spaced in a line. We want to each white dot with some black dot in ontoone fashion with a minimum total length of the wire. (See diagram above). Greedy algo. gives optimal solution for.. A) Only i B) Only ii C) Both D) None How to approach to such type of questions ?
asked
Jan 18, 2016
in
Algorithms
by
Tushar Shinde
Active
(
2.6k
points)

566
views
algorithms
greedyalgorithm
madeeasytestseries
+4
votes
1
answer
26
In Optimal merge pattern when do we get more than one tree?
asked
Dec 16, 2015
in
Algorithms
by
Shashank Chavan
Active
(
3.3k
points)

1.1k
views
algorithms
greedyalgorithm
+5
votes
2
answers
27
What is the time complexity of job sequencing with deadline using greedy algorithm?
asked
Dec 1, 2015
in
Algorithms
by
Akash Kanase
Boss
(
42.6k
points)

3.8k
views
greedyalgorithm
activityselection
deadlines
algorithms
+19
votes
1
answer
28
GATE2006IT48
The characters $a$ to $h$ have the set of frequencies based on the first $8$ Fibonacci numbers as follows $a : 1$, $b : 1$, $c : 2$, $d : 3$, $e : 5$, $f : 8$, $g : 13$, $h : 21$ A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? $110111100111010$ $fdheg$ $ecgdf$ $dchfg$ $fehdg$
asked
Nov 1, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
19.1k
points)

2.1k
views
gate2006it
algorithms
greedyalgorithm
normal
+19
votes
2
answers
29
GATE200584a
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$ is earned if the task is completed before ... that gives maximum profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out
asked
Sep 23, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.5k
points)

1.8k
views
gate2005
algorithms
greedyalgorithm
processschedule
normal
+14
votes
2
answers
30
GATE200776
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. Which of the following is the Huffman code for the letter $a, ... $10$, $110$, $1110$, $11110$, $11111$ $11$, $10$, $011$, $010$, $001$, $000$ $11$, $10$, $01$, $001$, $0001$, $0000$ $110$, $100$, $010$, $000$, $001$, $111$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.5k
points)

1.7k
views
gate2007
algorithms
greedyalgorithm
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
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged greedyalgorithm
Recent Blog Comments
gate overflow books are awesome; every one should ...
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
Yes, their tracking system is incomplete. ...
38,094
questions
45,587
answers
132,148
comments
49,126
users