Greedy Method | Design & Algorithms | Lec-38 | Bhanu Priya

Greedy algorithm, features & applications

[anaibrahim]

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

[aaryapradeep]

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

[shakthirathi]

Really ur notes is so clear and easy to understand

[bonty]

Your content is very very important before the exam day❤

[rajeshnimmaturi]

Super video mam.i understand very well

[anonymousz]

i love ur channel so much thank youuuu a lot

[RKRK-pini]

From Tutorialpoints...but Nice Xplanation

[AmitKumar]

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

[RohitBeniwal]

Ma'am some of your videos are private.. plz public them

[nidhishettigar]

where can i get some solved problems based on greedy algorithm ?

[SaqibAli-doyg]

Where is the connected graph Tutorial.Kindly share

[singarapuprabitha]

Greedy method algorithm aa technique aa clarity ga cheppandi

[abhijeetthorat]

how to see your private video in this topic ie lecture 3, 15, 21, 36, 37, 44, 48, 55

[pavankumarbasani]

Hi mam i am pavan kumar
Mam in our college the DAA class in not going on can u pls tell me this for pls mam