Register

Recent questions tagged greedy-algorithm

4 votes
1 answer
32
Clrs 16.2-6
Show how to solve the fractional knapsack problem in $O(n)$ time.
Show how to solve the fractional knapsack problem in $O(n)$ time.
User Avatar
0 votes
1 answer
36
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 :-
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 st...
User Avatar
38 votes
5 answers
37
GATE CSE 2018 | Question: 48
Consider the weights and values of items listed below. Note that there is only one unit of each item. ... The total value of items picked by the greedy algorithm is denoted by $V_{greedy}$. The value of $V_{opt}-V_{greedy}$ is ____
Consider the weights and values of items listed below. Note that there is only one unit of each item.$$\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weigh...
User Avatar
0 votes
3 answers
38
Gate 2018
Value of V GREEDY - V OPT
Value of V GREEDY - V OPT
User Avatar
1 votes
1 answer
41
Greedy vs Dynamic
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution. Is the above statement correct?
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.Is the above statement correct?
User Avatar
0 votes
1 answer
42
Knapsack
The following Knapsack bag. The Knapsack bag maximum Capacity is 50. Find out the maximum profit for Fractional Knapsack. P Q R S T U V W Weight 18 12 16 14 16 20 10 15 Profit 34 15 22 16 17 22 18 26 90 80.25 85.50 91.2
The following Knapsack bag. The Knapsack bag maximum Capacity is 50. Find out the maximum profit for Fractional Knapsack. PQRSTUVWWeight1812161416201015Profit341522161722...
User Avatar
2 votes
2 answers
43
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 ____________
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 techni...
User Avatar
4 votes
1 answer
45
algorithms practice question
problem of making change for n cents using the fewest number of coins
problem of making change for n cents using the fewest number of coins
User Avatar
1 votes
1 answer
46
algorithm
worst case time complexity of job sequencing with deadline using greedy algorithm
worst case time complexity of job sequencing with deadline using greedy algorithm
User Avatar
0 votes
3 answers
47
Optimal Merge Pattern
What will be the time complexity to obtain optimal merge pattern to merge files using greedy technique?
What will be the time complexity to obtain optimal merge pattern to merge files using greedy technique?
User Avatar
0 votes
0 answers
49
Doubt regarding Activity selection problem
Given n activities with their start and finish times.Select d mad no of activities dat can be performed by a single​ person assuming tat a person can only work on a single activity at a time
Given n activities with their start and finish times.Select d mad no of activities dat can be performed by a single​ person assuming tat a person can only work on a sin...
User Avatar
0 votes
1 answer
50
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.
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 apply...
User Avatar
1 votes
1 answer
51
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) ?
$\begin{bmatrix} 0& 29& 19& 25& 22\\ 20& 0& 21& 23& 21\\ 19& 21& 0& 21& 20\\ 25& 23& 21& 0& 32\\ 22& 21& 20& 22& 0 \end{bmatrix}$Find the shortest tour for given graph us...
User Avatar
1 votes
1 answer
52
Consider the Knapsack incidence with n=3(items) with weights {w1,w2,w3}={2,3,4} and profits are {p1,p2,p3}={1,2,5}
Consider the Knapsack incidence with n=3(items) with weights {w1,w2,w3}={2,3,4} and profits are {p1,p2,p3}={1,2,5}Given the capacity is 5,{W/M = 5 } Find the optimal solu...
User Avatar
2 votes
1 answer
54
Test by Bikram | Mock GATE | Test 3 | Question: 35
Consider the following set of messages with their frequencies: ... The percentage improvement for total binary stream transmission using Huffman Encoding over simple encoding is _______ %.
Consider the following set of messages with their frequencies: $$\begin{array}{|c|c|c|} \hline \textbf{Message} & \textbf{Frequency} \\ \hline A & 50\: \text{million} \...
User Avatar
3 votes
3 answers
57
Time complexity of fractionak knapsack using greedy algorithm is O(n^2)??TRUE/FALSE
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..
User Avatar
Page: