Recently I’ve attended a two-day workshop on “**Dynamic Programming**” under the mentorship of **Mr. Vimal Daga** Sir..!!

# Key Takeaways:

- TC of an algorithm determines the amount of time taken for an algorithm to run as a function of the length of its input
- whereas the SC of an algorithm determines the amount of space required for an algorithm
- Richard Bellman was the one to give the concept of DP for solving large mathematic computational problems
- In python we have a library called time_profiler, this produces the execution time info in steps
- Similarly for measuring SC we use the library memory_profiler
- In a multi-staged decision problem, the N variable problem is represented by N single variable problems
- These are solved in a cascade/successive approach in order to produce an optimal value from the original problem for getting optimal solution successively of each of these N single variable problems
- Such given problems have Optimal Substructure property, the solution for such a given problem is obtained by using the effective solutions of the sub-sequent problems
- Backward induction is the one in which the processor reasoning is done in backward (in time)
- it's done from the end of the problem, in order to determine an optimal approach
- Overlapping substructure problem is the one in which multiple sub-problems consist of the same approach
- The memorized program is similar to the recursion approach but with a small modification, it makes it look like a loop-up table before the solution is computed
- when a solution is needed to a subproblem, it reaches for the look-up table, when it finds a precomputed value suited, it’ll return it else it will calculate it
- understood its limitations :
- 1. slows down by a margin in initial execution.
- 2. very high memory usage.
- Merits: tabulation method won't take extra space in the stack, and consumes less time
- Demerits: consists of a complex decision-making process
- divide and conquer is the approach in which we divide a problem into subproblems to solve them individually, this has chances of coming across repetitive substructures
- A greedy Algorithm is the one in which the decision is taken in a step by assuming the solution is correct while not reconfirming it

I would like to thank Vimal Daga Sir, Preeti Mam, and the whole LinuxWorld Informatics Pvt Ltd team for organizing such a great session.