Greedy Method | DAA | Design & Analysis of Algorithms | Lec-38

Greedy Method | DAA | Design & Analysis of Algorithms | Lec-38 | Bhanu Priya

Рет қаралды 157,277

Күн бұрын

Пікірлер: 28

@anaibrahim4361 3 жыл бұрын

hey Mam once i entered the university and discovered your channel i start follow your lessons one by one , i call you my teacher you really helped me a lot much much more than what they teach us in the university great work and lot of benefits from this channel keep up the good work and i am here if in any time you wanted a help in presenting those courses and for free !!! you are a mercy Mam thanks again

@thapartrio 2 жыл бұрын

same bro......exam me mam hi bchaari h mujhe nhi toh fail hojau

@AmitKumar77794 8 ай бұрын

00:00 hi students coming to the next topic 00:02 that is a greedy method so when compared 00:05 to all algorithm approach whatever we 00:07 have so far discuss the simplest and 00:09 straightforward approach you call it as 00:11 a greedy method this Brede method is the 00:14 simplest and straightforward 00:22 straightforward approach so actually 00:25 this is not an algorithm just it is just 00:28 simply technique so greedy method is a 00:32 technique you can call it as a technique 00:37 rather than calling as an algorithm it's 00:39 better to call it as a technique so 00:41 actually what this approach will do what 00:45 the main function of this approach 00:46 actually in this approach the decision 00:50 is taken their greedy method the 00:54 decision is taken on basis of current 01:01 available information okay so in the 01:07 greedy method the decision is taken on 01:09 the basis of current available 01:11 information whatever the values that 01:13 whatever the information that is present 01:15 at present so the decision will be taken 01:20 based on that values so and it does not 01:26 know without worrying about worrying 01:33 about the effect of current to decision 01:40 in feature means it doesn't bother about 01:44 the future work so it just discuss what 01:47 is the present work is going on so a 01:49 bream method is a decision the decision 01:52 is taken on the basis of current 01:54 available information without worrying 01:57 without worrying about the effect of 02:00 current decision in future so it doesn't 02:03 think about whether suppose if I insert 02:06 these values it will at present it is 02:09 working but in future it may or may not 02:12 works so it doesn't bother 02:13 about that it think about the present 02:16 decision so this technique is used to 02:19 determine a feasible solution this 02:23 technique is determined to a feasible 02:26 solution that may or may not be optimal 02:30 that may or may not optimal okay so what 02:38 is a feasible solution what is an 02:39 optimal solution actually feasible 02:42 solution is any subset that satisfies 02:45 the given criteria you call it as a 02:46 feasible solution means suppose if you 02:49 take any n put n inputs its solution 02:53 contains a subset of inputs so whatever 02:55 the n inputs you're taking this a 02:57 solution contains a subset of inputs 03:00 which satisfies a given condition so if 03:03 you take any subset any subset that 03:10 satisfy the condition you call it as a 03:18 feasible solution means in all the 03:21 subsets its if any subset is satisfied 03:23 then you call it a that solution that 03:26 subset is a feasible solution what is an 03:28 optimal solution optimal is nothing but 03:31 it takes the best or most favorable 03:33 solution best or most favorable solution 03:39 so here in the feasible solution if any 03:41 subset satisfies the condition you can 03:43 take any one so if all the solutions 03:45 tell me you take you just take any one 03:47 of the solution but in optimal it takes 03:50 only the best and the most favorable 03:52 solution that is present in the 03:54 objective function so it is just like a 03:56 feasible solution but where objective 03:59 function reaches its maximum or minimum 04:01 value then you call it as a optimal 04:05 solution now let us see what are the 04:08 characteristics of Bri method 04:14 characteristics and features of greedy 04:20 method so to construct the solution in 04:24 octave optimal way this algorithm 04:27 maintains two sets so the first point is 04:30 to construct them to construct the 04:35 solution in an optimal optimal way this 04:43 algorithm maintains this algorithm 04:47 maintains two sub two sets so that is 04:52 one contains choosen items one set 04:58 contains choosen items means which are 05:02 having the solution chosen items and the 05:05 next other contains another set contains 05:09 rejected items so whatever you're taking 05:16 the to construct a solution if you want 05:18 to construct an solution by using the 05:20 building method to make it as an optimal 05:23 thing you have to select two sets one 05:26 the selected items and another is a 05:29 rejected items means one gives the best 05:31 and minimum value and another gives a 05:33 maximum value and the second characters 05:37 this greedy algorithm makes good local 05:39 choice in the hope that the results in 05:41 optimal solution and the feasible 05:44 solution so greedy algorithm make good 05:54 local choices means it's shellack the 05:58 choices in the hope they result in a an 06:01 optimal solution optimal solution or a 06:07 feasible solution feasible solution so 06:13 these are the features and 06:15 characteristics now let us see the 06:19 components that are present in 06:22 components of greedy algorithm 06:26 so in this video I am just giving the 06:28 overview of greedy algorithm what this 06:31 greedy algorithm contains what it mainly 06:33 bases on so it's just selects resolution 06:36 that the things about the present not 06:38 about the future it takes the best value 06:41 that is related to the present value so 06:46 next the components that are present in 06:48 the brady alga rhythm is first as a 06:50 candidate set it candidate set so 06:57 candidates that means here a solution is 06:59 created based on this set so whatever 07:03 the solution that the greedy method is 07:04 creating that is a solution is created 07:07 by using the candidate set from this set 07:12 and the second point is and the second 07:18 component is a selection function so 07:22 what's the use of selection function in 07:24 the greedy algorithm so this selection 07:26 function is used to choose the best 07:31 candidate the best candidate to be added 07:39 to the solution means you are selecting 07:43 the best subset and next third one the 07:48 third component that is present is a 07:50 feasible functional if feasibility 07:54 function so what is the use of this 08:00 feasibility function it is used to 08:03 determine whether a candidate can be 08:13 used to contribute the solution so 08:17 whether the candidate is used to 08:19 contribute the solution is not is 08:21 decided by the feasibility function and 08:24 coming to the next the fourth component 08:26 that is present in the greedy algorithm 08:29 is a objective function objective 08:34 function so what is the use of this 08:36 objective function actually this is user 08:38 to 08:40 to function is used to assign a value 08:43 just it has science a value to a 08:47 solution or a partial solution so 08:50 whether it is a partial solution or the 08:52 solution so this objective function is 08:54 used to assign a value and the next 08:58 component that is is a solution function 09:01 the final is a solution function so what 09:05 is the use of the solution function and 09:07 the greedy algorithm it is used to it is 09:13 used to indicate indicate whether a 09:20 complete solution has been reached or 09:26 not so it's just a solution function is 09:30 final decision it is used to indicate 09:32 whether a complete solution has been 09:34 reached or not that will be decided by 09:36 the solution function so these are the 09:38 five components that are present in the 09:40 video algorithm it candidates it a 09:42 selection function a feasibility 09:43 function objective function and a 09:46 solution function now coming to the 09:49 applications that are used in the greedy 09:50 algorithm what are the areas of 09:52 application so let me write that areas 09:58 of applications so in which fills it's 10:06 greedy method is used actually the 10:07 greedy method is used to solve many 10:09 problems so what type of problems it is 10:12 used to solve so it is used to solve the 10:15 shortest path finding shortest path 10:20 finding shortest path and it is used to 10:25 finding the minimum spanning tree 10:28 finding minimum spanning tree by using 10:31 the prims algorithm or the kruskal's 10:32 algorithm and the next application is 10:35 job sequencing job sequencing with 10:42 deadlines 10:44 and fractional knapsack problems 10:48 fractional knapsack problems so these 10:55 are the different applications of the 10:57 greedy method so in this greedy method 11:02 topic we'll discuss about each and every 11:04 application clearly so let me explain 11:06 the pseudocode of the greedy algorithm 11:08 so after that we will continue with the 11:10 applications so pseudocode pseudocode 11:18 for greedy algorithm writing here 11:27 already them greedy so a comma and a is 11:34 an array and n is the number of inputs 11:36 that we are giving so let us take the 11:40 solution a solution is equal to 0 means 11:43 we are just initializing the solution to 11:45 0 now checking fir I easy I is equal to 11:51 1 to n do X should be select a means we 12:01 are selecting the array elements or 12:03 whatever the elements that are present 12:04 in that so that elements we have to 12:06 select it and that should be assigned to 12:09 X value and we have to check if the 12:12 feasible solution is present or not 12:14 feasible solution comma X sorry right 12:18 solution solution comma X so this is 12:22 starting the solution should be 0 and 12:24 the item the first select element in the 12:27 array so if feasible solution comma X 12:31 then you have to combine that the 12:34 solution is equal to Union of solution 12:40 comma X finally you have to return the 12:44 solution written solution 12:49 okay so this is the pseudocode for the 12:52 greedy algorithm so in the next video 12:54 we'll discuss about the each and every 12:56 application finding shortest path 12:58 finding minimum spanning tree job 12:59 sequencing with the deadline and 13:01 fractional knapsack problems thank

@HarikaVlogs20 6 ай бұрын

❤

@AmitKumar77794 6 ай бұрын

@@HarikaVlogs20 I am happy that this helped you and I will try to share the Google Drive link of the notes I have on this. I am hopeful that it will help you all a lot.🤗

@satvika7819 Ай бұрын

Bane extral mingutunnav ga@@AmitKumar77794

@satvika7819 Ай бұрын

Explain the general structure of a greedy algorithm. What are the key components that make an algorithm “greedy”?

@bonty4210 9 ай бұрын

Your content is very very important before the exam day❤

@aaryapradeep1694 5 жыл бұрын

Mam ur videos are very helpful for my studies.actually i am not even getting clg notes.so i prefer ur lecture notes..so thanku very much..😍😍plz continue this work.it will be very helpful for the students like me..

@unknownman1 5 жыл бұрын