search
Log In

Recent questions tagged greedy-algorithm

0 votes
2 answers
1
$0/1$-Knapsack is a well known problem where, it is desired to get the maximum total profit by placing $n$ items (each item is having some weight and associated profit) into a knapsack of capacity $W$. The table given below shows the weights and associated profits for $5$ items, where one unit of ... $19$ $18$ $17$ $20$
asked Mar 30, 2020 in Algorithms Lakshman Patel RJIT 605 views
3 votes
3 answers
2
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an optimal solution in bottom-up 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 Arjun 1.7k views
2 votes
3 answers
3
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 Hirak 771 views
4 votes
1 answer
4
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs with negative weight edges. (S) It ... Only P, Q, S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 473 views
0 votes
2 answers
6
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(n-1) + Fib(n-2)); } } 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 Lakshman Patel RJIT 663 views
2 votes
2 answers
7
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 Lakshman Patel RJIT 4.4k views
0 votes
2 answers
8
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 Vaishnavi01 429 views
1 vote
2 answers
9
Suppose that you implement Dijkstra’s algorithm using a priority queue algorithm that requires O(V ) time to initialize, worst-case f(V, E) time for each EXTRACT-MIN operation and worst-case g(V, E) time for each DECREASE-KEY operation. How much (worst-case) time does it take to run Dijkstra’s algorithm on an input graph G = (V, E)?.
asked Jul 30, 2018 in Algorithms Rishav Kumar Singh 314 views
1 vote
0 answers
10
Suppose you want to get from s to t on weighted graph G with nonnegative edge weights, but you would like to stop by u if it isn't too inconvenient. (Here too inconvenient means that it increases the length of your travel by more than 10%.) Describe an efficient ... if not too inconvenient. It should either return the shortest path from s to t, or the shortest path from s to t containing u.
asked Jul 30, 2018 in Algorithms Rishav Kumar Singh 128 views
0 votes
0 answers
11
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 convert the message ... $\frac{12}{30} $
asked Jul 26, 2018 in Algorithms Shaik Masthan 438 views
1 vote
2 answers
12
what is the time-complexity in kruskal algorithm for the overall step 2 where for each vertex Make-set function is called ? How come overall time for this step is O(v log v) ? We are performing this Operation for all the vertices in the Initial phase only so for ... Make-set operation only once 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 radha gogia 405 views
4 votes
1 answer
13
Show how to solve the fractional knapsack problem in $O(n)$ time.
asked Jul 22, 2018 in Algorithms Prince Sindhiya 379 views
1 vote
1 answer
14
1 vote
1 answer
15
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 Aarvi Chawla 759 views
0 votes
1 answer
16
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 cycle ABD then the edge weight a should ... cant be 10) 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 Na462 327 views
0 votes
1 answer
17
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 Na462 2.3k views
28 votes
5 answers
18
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{Weight (in Kgs) }& \textbf{Value (in rupees)} \\\hline \text{$1$} & \text{$10$} & \text{$ ... the ordered 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 gatecse 11.4k views
2 votes
0 answers
19
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)? P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T PLEASE EXPLAIN.
asked Jan 8, 2018 in Algorithms ankit_thawal 693 views
1 vote
1 answer
21
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution. Is the above statement correct?
asked Dec 13, 2017 in Algorithms Tuhin Dutta 2.5k views
2 votes
1 answer
22
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 VIKAS TIWARI 2.1k views
0 votes
1 answer
23
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 Parshu gate 1.3k views
2 votes
2 answers
24
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 set2018 308 views
4 votes
1 answer
25
problem of making change for n cents using the fewest number of coins
asked Aug 10, 2017 in Algorithms Pavan Kumar Munnam 431 views
0 votes
1 answer
26
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 LavTheRawkstar 1.5k views
1 vote
1 answer
27
$\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 using greedy approach. \\It is Weighted Adjacency Matrix \\It is 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 LavTheRawkstar 649 views
4 votes
3 answers
28
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 LavTheRawkstar 1k views
...