💠HELLO EVERYONE !!!
Recently, I have attended a 2 days live workshop on Dynamic Programming by Mr. Vimal Daga sir.
Here are some key points of the workshop…………..
🔰What is Dynamic Programming?
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.
🔰What is Multi stage decision process?
In sequential optimization, a problem is approached by dividing it into smaller subproblems and optimization is done for these subproblems without losing the integrity of the original problem. Sequential decision problems are those in which decisions are made in multiple stages. These are also called multistage decision problems since decisions are made at a number of stages. In multistage decision problems, an N variable problem is represented by N single variable problems. These problems are solved successively such that the optimal value of the original problem can be obtained from the optimal solutions of these N single variable problems. The N single variable problems are connected in series so that the output of one stage will be the input to the succeeding stage. This type of problem is called serial multistage decision process.
🔰What are the principles of optimality?
A problem is said to satisfy the Principle of Optimality if the subsolutions of an optimal solution of the problem are themesleves optimal solutions for their subproblems.
Examples:
- The shortest path problem satisfies the Principle of Optimality.
- This is because if a,x1,x2,…,xn,b is a shortest path from node a to node b in a graph, then the portion of xi to xj on that path is a shortest path from xi to xj.
- The longest path problem, on the other hand, does not satisfy the Principle of Optimality. Take for example the undirected graph G of nodes a, b, c, d, and e, and edges (a,b) (b,c) (c,d) (d,e) and (e,a). That is, G is a ring. The longest (noncyclic) path from a to d to a,b,c,d. The sub-path from b to c on that path is simply the edge b,c. But that is not the longest path from b to c. Rather, b,a,e,d,c is the longest path. Thus, the subpath on a longest path is not necessarily a longest path.
🔰What is mean by Overlapping Subproblems?
Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again. For example, Binary Search doesn’t have common subproblems. If we take an example of following recursive program for Fibonacci Numbers, there are many subproblems which are solved again and again.
🔰Explain Top down method / Memorization & Bottom up method / Tabulation Approach & Which approach is better?
It is up to your comfort. Both give the same solutions. In very large problems, bottom up is beneficial as it does not lead to stack overflow. If you choose a input of 10000, the top-down approach will give maximum call stack size exceeded, but a bottom-up approach will give you the solution. But do remember that you cannot eliminate recursive thinking completely. You will always have to define a recursive relation irrespective of the approach you use.
a) Memoization (Top Down): The memoized program for a problem is similar to the recursive version with a small modification that it looks into a lookup table before computing solutions. We initialize a lookup array with all initial values as NIL. Whenever we need the solution to a subproblem, we first look into the lookup table. If the precomputed value is there then we return that value, otherwise, we calculate the value and put the result in the lookup table so that it can be reused later.
b) Tabulation (Bottom Up): The tabulated program for a given problem builds a table in bottom up fashion and returns the last entry from table. For example, for the same Fibonacci number, we first calculate fib(0) then fib(1) then fib(2) then fib(3) and so on. So literally, we are building the solutions of subproblems bottom-up.
🔰Explain Complexity in Dynamic Programming ?
Time Complexity:
In Dynamic programming problems, Time Complexity is the number of unique states/subproblems * time taken per state. In this problem, for a given n, there are n unique states/subproblems. For convenience, each state is said to be solved in a constant time. Hence the time complexity is O(n * 1).
This can be easily cross verified by the for loop we used in the bottom-up approach. We see that we use only one for loop to solve the problem. Hence the time complexity is O(n ) or linear.
This is the power of dynamic programming. It allows such complex problems to be solved efficiently.
Space Complexity:
We use one array called cache to store the results of n states. Hence the size of the array is n. Therefore the space complexity is O(n).
🔰What is Memory Profiler?
This is a python module for monitoring memory consumption of a process as well as line-by-line analysis of memory consumption for python programs. It is a pure python module which depends on the psutil module.
Installation:
Install via pip:
pip install -U memory_profiler
Usage:
line-by-line memory usage
The line-by-line memory usage mode is used much in the same way of the line_profiler: first decorate the function you would like to profile with @profile and then run the script with a special script (in this case with specific arguments to the Python interpreter).
I would like to thanks Mr. Vimal Daga sir &LinuxWorld Informatics Pvt Ltd for organizing such a informative workshop.
THANK YOU FOR READING😊
