Introduction of Dynamic Programming
Dynamic Programming is the most powerful design technique for solving optimization problems.
Dynamic Programming is a method for solving a complex problem by breaking it down into a
collection of simpler subproblems, solving each of those subproblems just once, and storing their
solutions using a memory-based data structure (array, map,etc).
Dynamic programming is both a mathematical optimization method and a computer
programming method. The method was developed by Richard Bellman in the 1950s and has
found applications in numerous fields, from aerospace engineering to economics. In both
contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-
problems in a recursive manner. While some decision problems cannot be taken apart this way,
decisions that span several points in time do often break apart recursively. Likewise, in computer
science, if a problem can be solved optimally by breaking it into sub-problems and then
recursively finding the optimal solutions to the sub-problems, then it is said to have optimal
substructure.
Divide & Conquer algorithm partition the problem into disjoint subproblems solve the
subproblems recursively and then combine their solution to solve the original problems.
Dynamic Programming is a Bottom-up approach- we solve all possible small problems and
then combine to obtain solutions for bigger problems.
Characteristics of Dynamic Programming:
Dynamic Programming works when a problem has the following features:-
Optimal Substructure: If an optimal solution contains optimal sub solutions then a
problem exhibits optimal substructure.
Overlapping subproblems: When a recursive algorithm would visit the same
subproblems repeatedly, then a problem has overlapping subproblems.
If a problem has optimal substructure, then we can recursively define an optimal solution. If a
problem has overlapping subproblems, then we can improve on a recursive implementation by
computing each subproblem only once.
Elements of Dynamic Programming
There are basically three elements that characterize a dynamic programming algorithm:-
1. Substructure: Decompose the given problem into smaller subproblems. Express the
solution of the original problem in terms of the solution for smaller problems.
2. Table Structure: After solving the sub-problems, store the results to the sub problems in
a table. This is done because subproblem solutions are reused many times, and we do not
want to repeatedly solve the same problem over and over again.
3. Bottom-up Computation: Using table, combine the solution of smaller subproblems to
solve larger subproblems and eventually arrives at a solution to complete problem.
Note: Bottom-up means:-
i. Start with smallest subproblems.
ii. Combining their solutions obtain the solution to sub-problems of increasing size.
iii. Until solving at the solution of the original problem.
Development/Steps of Dynamic Programming Approach
Dynamic Programming algorithm is designed using the following four steps −
Characterize the structure of an optimal solution.
Recursively define the value of an optimal solution.
Compute the value of an optimal solution, typically in a bottom-up fashion.
Construct an optimal solution from the computed information.
Applications of dynamic programming
1. 0/1 knapsack problem
2. Mathematical optimization problem
3. All pair Shortest path problem
4. Reliability design problem
5. Longest common subsequence (LCS)
6. Flight control and robotics control
7. Time-sharing: It schedules the job to maximize CPU usage
Greedy algorithm
A greedy algorithm, as the name suggests, always makes the choice that seems to be the best
at that moment. This means that it makes a locally-optimal choice in the hope that this choice
will lead to a globally-optimal solution.
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the
next piece that offers the most obvious and immediate benefit. So the problems where choosing
locally optimal also leads to global solution are best fit for Greedy.
Definition
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of
making the locally optimal choice at each stage with the hope of finding a global optimum.
Components of greedy algorithms:
In general, greedy algorithms have five components:
Candidate set: An answer is created from this set.
Selection function: It selects the best candidate to be included in the solution.
Feasibility function: This section calculates if a candidate can be used to contribute to
the solution.
An objective function: It assigns a value to a complete or a partial solution.
A solution function: This is used to indicate if a proper solution has been met.
The applications of Greedy algorithms
Minimum spanning tree (Minimization) - Prim's and Kruskal Algorithms
Fractional Knapsack Problem (Maximization)
Optimal Merging
Topological Sort
In Huffman/Shannon encoding- data compression
In gaming
A real life example is Internal Scheduling- if you want to maximize the number of
customers that an use a meeting room, you can use the Internal Scheduling Algo.
Many countries coin values are such that a Greedy approach to returning change works.(
Always returning the largest possible coin until you are done)