Algorithm

Getting Started with AlgorithmWhat is an Algorithm?

Characteristics of Algorithm1 Topic

Analysis Framework

Performance Analysis3 Topics

Mathematical Analysis2 Topics

Sorting AlgorithmSorting Algorithm10 Topics

Searching Algorithm6 Topics

Fundamental of Data StructuresStacks

Queues

Graphs

Trees

Sets

Dictionaries

Divide and ConquerGeneral Method

Binary Search

Recurrence Equation for Divide and Conquer

Finding the Maximum and Minimum

Merge Sort

Quick Sort

Stassen’s Matrix Multiplication

Advantages and Disadvantages of Divide and Conquer

Decrease and ConquerInsertion Sort

Topological Sort

Greedy MethodGeneral Method

Coin Change Problem

Knapsack Problem

Job Sequencing with Deadlines

Minimum Cost Spanning Trees2 Topics

Single Source Shortest Paths1 Topic

Optimal Tree Problem1 Topic

Transform and Conquer Approach1 Topic

Dynamic ProgrammingGeneral Method with Examples

Multistage Graphs

Transitive Closure1 Topic

All Pairs Shortest Paths6 Topics

BacktrackingGeneral Method

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
General Method with Examples
Dynamic Programming is the most powerful design technique for solving optimization problems.
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 used when the subproblems are not independent, e.g. when they share the same subproblems. In this case, divide and conquer may do more work than necessary, because it solves the same sub problem multiple times.
Dynamic Programming solves each subproblems just once and stores the result in a table so that it can be repeatedly retrieved if needed again.
Dynamic Programming is a Bottomup approach we solve all possible small problems and then combine to obtain solutions for bigger problems.
Dynamic Programming is a paradigm of algorithm design in which an optimization problem is solved by a combination of achieving subproblem solutions and appearing to the “principle of optimality“.
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.
If a problem doesn’t have optimal substructure, there is no basis for defining a recursive algorithm to find the optimal solutions. If a problem doesn’t have overlapping sub problems, we don’t have anything to gain by using dynamic programming.
If the space of subproblems is enough (i.e. polynomial in the size of the input), dynamic programming can be much more efficient than recursion.
Elements of Dynamic Programming
There are basically three elements that characterize a dynamic programming algorithm:
 Substructure: Decompose the given problem into smaller subproblems. Express the solution of the original problem in terms of the solution for smaller problems.
 Table Structure: After solving the subproblems, 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.
 Bottomup Computation: Using table, combine the solution of smaller subproblems to solve larger subproblems and eventually arrives at a solution to complete problem.
Note: Bottomup means:
 Start with smallest subproblems.
 Combining their solutions obtain the solution to subproblems of increasing size.
 Until solving at the solution of the original problem.
Components of Dynamic programming
 Stages: The problem can be divided into several subproblems, which are called stages. A stage is a small portion of a given problem. For example, in the shortest path problem, they were defined by the structure of the graph.
 States: Each stage has several states associated with it. The states for the shortest path problem was the node reached.
 Decision: At each stage, there can be multiple choices out of which one of the best decisions should be taken. The decision taken at every stage should be optimal; this is called a stage decision.
 Optimal policy: It is a rule which determines the decision at each stage; a policy is called an optimal policy if it is globally optimal. This is known as Bellman principle of optimality.
 Given the current state, the optimal choices for each of the remaining states does not depend on the previous states or decisions. In the shortest path problem, it was not necessary to know how we got a node only that we did.
 There exist a recursive relationship that identify the optimal decisions for stage j, given that stage j+1, has already been solved.
 The final stage must be solved by itself.
Development of Dynamic Programming Algorithm
It can be broken into four steps:
 Characterize the structure of an optimal solution.
 Recursively defined the value of the optimal solution. Like Divide and Conquer, divide the problem into two or more optimal parts recursively. This helps to determine what the solution will look like.
 Compute the value of the optimal solution from the bottom up (starting with the smallest subproblems)
 Construct the optimal solution for the entire problem form the computed values of smaller subproblems.
Applications of dynamic programming
 0/1 knapsack problem
 Mathematical optimization problem
 All pair Shortest path problem
 Reliability design problem
 Longest common subsequence (LCS)
 Flight control and robotics control
 Timesharing: It schedules the job to maximize CPU usage
Basic Example
EXAMPLE 1: Coinrow problem There is a row of n coins whose values are some positive integers c1, c2,…,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
Let F (n) be the maximum amount that can be picked up from the row of n coins. To derive a recurrence for F (n), we partition all the allowed coin selections into two groups: those that include the last coin and those without it. The largest amount we can get from the first group is equal to cn + F (n − 2)—the value of the nth coin plus the maximum amount we can pick up from the first n − 2 coins. The maximum amount we can get from the second group is equal to F (n − 1) by the definition of F (n). Thus, we have the following recurrence subject to the obvious initial conditions:
We can compute F (n) by filling the onerow table left to right in the manner similar to the way it was done for the nth Fibonacci number by Algorithm Fib(n).
ALGORITHM CoinRow(C[1..n])
//Applies formula 1 bottom up to find the maximum amount of money
//that can be picked up from a coin row without picking two adjacent coins
//Input: Array C[1..n] of positive integers indicating the coin values
//Output: The maximum amount of money that can be picked up
F[0]← 0; F[1]← C[1]
for i ← 2 to n do
F[i]← max(C[i] + F[i − 2], F[i − 1])
return F[n]
The application of the algorithm to the coin row of denominations 5, 1, 2, 10, 6, 2 is shown in Figure 1. It yields the maximum amount of 17. It is worth pointing out that, in fact, we also solved the problem for the first i coins in the row given for every 1 ≤ i ≤ 6. For example, for i = 3, the maximum amount is F (3) = 7.
To find the coins with the maximum total value found, we need to backtrace the computations to see which of the two possibilities—cn + F (n − 2) or F (n − 1)—produced the maxima in formula (8.3). In the last application of the formula, it was the sum c6 + F (4), which means that the coin c6 = 2 is a part of an optimal solution. Moving to computing F (4), the maximum was produced by the sum c4 + F (2), which means that the coin c4 = 10 is a part of an optimal solution as well. Finally, the maximum in computing F (2) was produced by F (1), implying that the coin c2 is not the part of an optimal solution and the coin c1 = 5 is. Thus, the optimal solution is {c1, c4, c6}. To avoid repeating the same computations during the backtracing, the information about which of the two terms in (8.3) was larger can be recorded in an extra array when the values of F are computed.