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