Dark Mode

Recent questions tagged greedy-algorithm

0 votes

1 answer

1

Which one is right ? what will be the right answer assigning 0 to the left edges or right?

Nisha Bharti asked in Algorithms Nov 26, 2022

by Nisha Bharti

201 views

0 votes

1 answer

2

Applied Test Series
Consider the following items with their associated weights and values. If a knapsack of capacity 25 units of weight is available and we are allowed to take either the item completely or leave it the maximum possible profit if we follow the greedy approach by being greedy about profit is _____

LRU asked in Algorithms Dec 28, 2021

by LRU

881 views

0 votes

1 answer

3

Testbook Test Series

rsansiya111 asked in Algorithms Dec 17, 2021

198 views

0 votes

2 answers

4

NIELIT 2017 July Scientist B (IT) - Section B: 60
$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 ... $19$ $18$ $17$ $20$

Lakshman Patel RJIT asked in Algorithms Mar 30, 2020

by Lakshman Patel RJIT

2.0k views

2 votes

3 answers

5

UGC NET CSE | June 2019 | Part 2 | Question: 68
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$

Arjun asked in Algorithms Jul 2, 2019

by Arjun

4.2k views

0 votes

1 answer

6

ME Test Series Question
Consider the following statements given below: S1 : If a graph contain a negative weight cycle then Dijkstra’s algorithm may or may not terminate. S2 : Bellman Ford algorithm for every weighted graph which contain two vertices u and v always produces a shortest path. Which of the above statements are incorrect? Only S1 Only S2 Both S1 and S2 None of these

Shankar Kakde asked in Algorithms Jan 25, 2019

by Shankar Kakde

2.4k views

0 votes

1 answer

7

UPPCL AE 2018:12
Given below are some famous algorithms and some algorithm design paradigms ... $\text{1-(c), 2-(b), 3-(a), 4-(b)}$

Lakshman Patel RJIT asked in Algorithms Jan 5, 2019

by Lakshman Patel RJIT

190 views

4 votes

1 answer

8

GATE Overflow | Mock GATE | Test 1 | Question: 47
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 ... , S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct

Ruturaj Mohanty asked in Algorithms Dec 27, 2018

by Ruturaj Mohanty

1.2k views

0 votes

1 answer

9

MadeEasy Test Series: Algorithms - Minimum Spanning Trees

mitesh kumar asked in Algorithms Dec 18, 2018

by mitesh kumar

735 views

0 votes

2 answers

10

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(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

Lakshman Patel RJIT asked in Algorithms Nov 13, 2018

by Lakshman Patel RJIT

2.2k views

0 votes

1 answer

11

Self doubt
What is the difference between Dijkstra and Bellman Ford algorithm? Will the shortest path given by both be same in following conditions : a) All positive edge weights b) Some negative edge weights without negative edge cycle c) With negative edge cycles

Vipin Rai asked in Algorithms Nov 11, 2018

409 views

3 votes

3 answers

12

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$

Lakshman Patel RJIT asked in Algorithms Nov 10, 2018

by Lakshman Patel RJIT

9.7k views

0 votes

2 answers

13

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

Vaishnavi01 asked in Algorithms Sep 25, 2018

1.0k views

1 vote

2 answers

14

Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
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- ... (worst-case) time does it take to run Dijkstra's algorithm on an input graph G = (V, E)?.

Rishav Kumar Singh asked in Algorithms Jul 30, 2018

by Rishav Kumar Singh

487 views

1 vote

0 answers

15

Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
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 ... It should either return the shortest path from s to t, or the shortest path from s to t containing u.

Rishav Kumar Singh asked in Algorithms Jul 30, 2018

by Rishav Kumar Singh

256 views

0 votes

0 answers

16

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} $

Shaik Masthan asked in Algorithms Jul 26, 2018

by Shaik Masthan

910 views

1 vote

2 answers

17

What is the time complexity of Make-set function in kruskal algorithm ?
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 ... right because after we come out of loop we have v sets of 1 vertex each . Please explain this clearly .

radha gogia asked in Algorithms Jul 22, 2018

772 views

4 votes

1 answer

18

Clrs 16.2-6
Show how to solve the fractional knapsack problem in $O(n)$ time.

Prince Sindhiya asked in Algorithms Jul 22, 2018

by Prince Sindhiya

766 views

2 votes

1 answer

19

Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????

Hardik Maheshwari asked in Algorithms Jul 5, 2018

by Hardik Maheshwari

2.7k views

1 vote

1 answer

20

cormen 3rd edition Q. 16.2-6
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?

Aarvi Chawla asked in Algorithms Jun 19, 2018

by Aarvi Chawla

2.0k views

0 votes

1 answer

21

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 :-

Na462 asked in Algorithms Apr 30, 2018

by Na462

650 views

0 votes

1 answer

22

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 :-

Na462 asked in Algorithms Apr 30, 2018

by Na462

3.9k views

33 votes

5 answers

23

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 ____

gatecse asked in Algorithms Feb 14, 2018

17.0k views

Page:

1
2
3
next »

Recent questions tagged greedy-algorithm