4 Principle of Optimality - Dynamic Programming introduction

hi the topic is dynamic programming in this video and give you introduction to dynamic programming give you differences between dynamic programming and 3d method and also I will show the difference between memorization and tabular method by taking an example in detail let us know the difference between greedy method and dynamic programming which is very very important greedy matter and dynamic programming both are used for solving optimization problems both are different strategies but the purpose is same optimization problems are those which requires either minimum result or maximum result the methods are different in greedy method we try to follow predefined procedure to get optimal result the procedure is known to be optimal we follow the procedure to get best result like criticals method for finding minimum cost spanning tree always select a minimum cost edge and that gives us best result or Dijkstra shortest path algorithm always select our shortest path vertex and continue relaxing the vertices so you get a shortest path so there is a predefined procedure but in dynamic programming we'll try to find out all possible solutions and then pick up the best solution the optimal solution this approach is different and it is little time consuming compared to grading method for any problem there may be many solutions which are feasible so we'll try out all those solutions and then pick up the best one and mostly dynamic programming problems are solved by using the recursive formulas though we will not use a recursion of programming but the formulas are recursive if we want we can use recursion also but mostly they are so using iteration and dynamic programming follows principle of optimality principle of optimality says that a problem can be solved by taking sequence of decisions to get the optimal solution so now I can highlight one difference here in grading method decision is taken one time that we will do it like this and we follow that procedure in three dynamic programming every stage we take a decision so this point you can understand only while solving the problem so while solving the problem I will show you perfectly how dynamic programming is working there to solve a problem let us see how dynamic programming adopts tabulation method or memoization difference between tabulation and memorization I have an example function here this is the recursive definition of a fibonacci Tom and this is a function or an algorithm for finding fibonacci Tom and it is a recursive function the definition itself is recursive so the function is recursive so what is Fibonacci series it starts from 0 and 1 1 every term is obtained by adding previous two terms so 2 plus 1 that is 3 and 2 plus 3 that is 5 and 5 plus 3 that is 8 and this is 13 and so on so this is 0 at the term first term second third fourth fifth sixth seventh and goes on suppose I want to know 10 the term of Fibonacci series then call this function this function will give us n town now I will show you how this function works if I want to find out any term because the function is recursive so let us trace this function many call this function for Fibonacci of 5 system I want to find out if I trace this n is less than equal to 1 no it is not less than equal to 1 if so then it will return and only otherwise it will call two functions are their results and return the result so what are those two functions it is calling it is calling itself for Fibonacci of 3 and Fibonacci of 4 so first of all it will call this one right then that one so if we see this again it will enter inside and then it's not less than equal to 1 so it will call itself for two times for 3 minus 2 that is fib of 1 and then Freebo of then out of this it will pick up this call first for free both one directly we get dancer 1 so this is 1 then it will come this side so there are 2 calls here this is fib of 0 and fib of 1 for fib of 0 and fib of 1 there is no recursive call direct result is returned so here the functions terminates then it will add these two terms and give the result it will add these two terms and give the result then this side it has to continue so on this side again for super noxee of 4 it will call itself for fibonacci of 2 and this side for fibonacci of 3 but first of all this is done so this is faber of 0 and fib of 1 this side fib of 1 and fib of 2 again this is feeble for 0 and fib of 1 this will be the tracing tree of that particular function so for finding fib of 5 it is making total 15 calls now if I consider all the calls and find out the time complexity of this one so from the function if I see this is n minus 2 and that is n minus 1 if I assume roughly it is n minus 1 only then I can prepare a recurrence relation for this one what it will be T n is equals to it is calling itself for two time let us assume n minus 1 only so 2 T n minus 1 there is a sin - true but if we take n minus 2 we cannot come to the conclusion so I am taking it as 1 right approximately so this is 2 TN minus 1 and what it is doing every time just adding so this is the recurrence relation and by master's theorem for decreasing function if you take this is Big O of 2 power n like this is not exact it is n minus 2 it is less I have taken n minus 1 only so this upper bound for that function so the time taken by this function is Big O of 2 power n write recurrence relation how to prepare there is a video available you can watch that one so how to prepare a recurrence relation so this recurrence relation is Big O of to par n means if I call this Fibonacci function it will take so much time to pour an exponential time is there any way to reduce the time let us observe see in this function f of 1 fib of 1 1 1 so many times it is being called so many times so if I take C bofto it is called here and here and here Y to call the same function again and again for the same parameter why can't we reduce this one so yes with this idea we can reduce the function calls and reduce the time taken by this Fibonacci function so what I'll do is I'll try to store the result of Fibonacci functions so that once it is called for few both two it should not be called again so let me show you how it can be done we will take one global array let us say I have an array 0 1 2 3 4 5 I have an array initially I will fill this array with minus 1 because nothing is known now let me trace this 1 3 once again not function I have to modify the function but I will not modify it just from the tree I will show you first function is called fib of 5 minus 1 we don't know so make the calls so first call is this 1 fib of 3 minus 1 we do know call the function Sofie both 1 do we know this no so call the function so what is the result of the function when value is 1 it is 1 so mark it has 1 so this is completed then go back suppose to be do we know the answer for this one see both to know call this fib of 0 do reload answer for this one no fib of 0 function is called so it is less than n 1 so it will return 0 only so this becomes 0 then see boss 1 till here the calling is done fib of 1 we already know ship of 1 don't call this function then this result is how much 0 this values how much 1 so add this and return the results so this becomes fun so fib of 2 also becomes 1 now this one then this result freebo's 1 is 1 1 plus 1 we know this result so add this and get the result for this to fib of 3 is stored that is true now come to this site see one function was skipped fib of 4 do we know we don't know then let us call the function see boss - shall we call no we already know the result so don't call this function so all these functions will not be called this is already 1 then see what three do we know yes we know the answer don't call all these functions don't call this function so first of all this is not called so automatically these are also not called what is the result of this this is 2 then these 2 are added 1 plus 2 so this becomes 3 this becomes 3 now adding of these 2 is done 2 plus 3 that is 5 5 that's all if I count the number of calls now this is 1 2 3 4 5 this is not called 6 that's all total six calls so when I have given f of n so it is making how many calls and plus 1 calls so n plus 1 calls the sort order of n theta of n naught we go off n whatever you say notations so this is order of n see this is memoization this is the result of memoization by storing the results of the function we are avoiding the same call once again like fib of 2 all the restor don't call it again fib of 3 or the D form don't call it again how do you know it is already found we can store the result in summary so this function we can modify the calls are made here I can make them as conditional calls so based on condition the calls are made and the results are stored in an array so the number of calls are reduced we can see that memoization has reduced the time from 2 power - n so from to power n 2 n so exponential - polynomial back to linear so in this example there is a big change in other examples at least there will be some difference memoization will bring some difference does the approach of memorization and then this we can see this the tree is generated and the function calls are avoided and the result is obtained back right so from here we started so we say this is top-down approach so memoization follows top-down approach if we want we can follow this in the dynamic programming but we don't use this we use iterative method mostly that is stable ation method the same problem how I can solve it using tabulation method I will show you now here is an iterative function that is using loop same function for finding Fibonacci series or enter term of Fibonacci series see the formula for n minus 2 and n minus 1 the same formula is used but this is using loop let us see how this function works if I have to find out fib of 5 that is 5th third term I want to find out so it will enter inside here if n is less than equal to 1 it will return that same thing once if it is 0 or 1 directly I am returning otherwise it will fill f of 0 as 0 this is 0 as 0 F of 1 as 1 this is 1 then the loop starts from I value as 2 onwards so I will start from 2 onwards so 2 2 and N is what 5 in our example so 2 2 and it will go and every time for getting any I to term it will add previous two terms so for getting this term it will add these two terms so this is I minus 2 and this is I minus 1 add it so this is 1 next is I plus plus so I moves to next and add these two then I plus plus add these two then add these 2 so it returns f of n n is what 5 so f of 5 that is answer is 5/5 eight hours 5 only here this is how our table is generated by this function so this is how we write the algorithms for dynamic programming we died mostly iterative functions only which will fill up the table to get the values and the filling is done from which on where which value on were seized from smaller value onwards so we say this is bottom-up approach we want at 5 so we started from 0 onwards and we reach 5 whereas in recursion if you recall this was starting from 5 then it was calling Fabo for 3 and say before so from top it was starting then it was going till bottom then it was coming back again so it was a top-down but this is from 0 it has started first so this is bottom of approach so the approach are different mostly tabulation is used if you want to frame it as a recursion you can frame them as recursion also that's all this is the difference between tabulation method and previously I have already shown you memorization so any of these methods can be used but mostly the problems are solved using tabulation method in dynamic programming the main important thing in dynamic programming is that we should get the approach for solving the problem so if you get the idea how the strategy is working then you can solve any other problem which is suitable for dynamic programming you can devise your own approach right so I will be focusing on that one how to get the idea of solving a problem so watch the next video on problems of dynamic programming

Channel: Abdul Bari

Views: 541,610

Rating: 4.9370441 out of 5

Keywords: algorithms, algorithm, dynamic programming, memoization, abdul bari, bari, gate

Id: 5dRGRueKU3M

Length: 14min 52sec (892 seconds)

Published: Fri Feb 16 2018