# Recent questions tagged greedy-algorithm

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$
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$
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)
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
5
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
1 vote
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$
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
1 vote
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)?.
1 vote
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.
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}$
1 vote
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 .
13
Show how to solve the fractional knapsack problem in $O(n)$ time.
1 vote
14
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
1 vote
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?
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 :-
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 :-
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 ____
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.
1 vote
20
can someone provide a detailed solution of this??
1 vote
21
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution. Is the above statement correct?
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.
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
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 ____________
25
problem of making change for n cents using the fewest number of coins
$\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) ?