Greedy algorithms are algorithms that provide decisions based on available information without any foresight. They work best in optimization problems and are easy to implement. The general steps for their design are:
1. Create a collection(list, set, etc) of candidates (C)
2. Find a Subset (S) from the collection of candidates(C)
3. Specify the criteria that S must satisfy.
4. If it meets that criteria (feasible), go ahead to Optimize S
5. Optimizing S means selecting to minimize or maximize, depending on the particular problem. In the process we may select the largest or smallest solution.
Divide-and-Conquer algorithms follow a top-down approach in algorithm design. They sub-divide the problem into smaller problems and finally reassemble the solutions to the component problems.The general steps for their design are:
1. Define the problem
2. Create an instance of the problem
3. Divide this instance into smaller sub-instances of the same problem
4. Solve each of the sub-instances on its own
5. Integrate and combine the solutions of the sub-instances so as to obtain a solution for the original instance.
Dynamic programming algorithms are a variant of the divide-and-conquer algorithm. While the divide-and-conquer algorithms which are recursive follow a top-down approach to solving optimization problems, dynamic programming follows a bottom-up technique. The general steps for their design are:
1. Define the problem
2. Create instances of the problem
3. Construct a table of all sub-instances
4. Start with the smallest sub-instances
5. Continue with increasing sub-instance size adding results of entries already computed
6. Continue till the last sub-instance. The final obtained solution is the solution to the initially defined problem.
This method is iterative while the divide-and-conquer approach is recursive.
The backtracking algorithm systematically searches for a solution from available options, on the assumption that a solution exists. The general steps for their design are:
1. Start with an empty vector
2. Let the solution be represented by vectors (Vi......Vm)
3. Traverse the vectors, extending the partial vectors with a new value
4. Backtrack if a vector cant represent a partial solution
5. Remove the trailing value from the vector
6. Then proceed to extend the vector with alternative values
7. Continue the process until a solution is found.