ALGORITHM DESIGN TECHNIQUES | Introduction | What are algorithm design techniques? | Divide and conquer | Greedy algorithm | Dynamic programming | Brute Force Backtracking and branch-and-bound
List of topics that we are going to cover in this article:
- What are algorithm design techniques?
- Divide and conquer
- Greedy algorithm
- Dynamic programming
- Brute Force
- Backtracking and branch-and-bound
ALGORITHM DESIGN TECHNIQUES
Algorithm design techniques are used to solve different types of complex problems. We can also apply more than one technique to solve a single problem the most important thing is to choose a suitable technique to a problem. We must choose a best technique based upon the problem. We get efficient solution when we use a proper technique to a problem. Now let’s see what the different types techniques are.
- Different types of techniques:
- Divide and conquer:
Divide and conquer is the most popular algorithm in the data structure. The working of divide and conquer algorithm is to divide the problem into subproblems and solve the problems in easy manner and after combine all the subproblems to get final solution.
- Let’s see how divide and conquer problem works:
Divide: Divide the problem into subproblems
Conquer: now we will get solution to all the problems
Combine: Here all the subproblems are combined to solve the complex problem.
- Examples:Merge sort, quick sort.
- Greedy algorithm:
The main goal of greedy algorithm is to gain optimal solution for the problem. We always choose a solution which is closest that provide optimal solution.
Minimal spanning tree
Shortest distance in graphs
Coin exchange problem
Greedy algorithm for knapsack problem
- Dynamic programming:
The working of dynamic programming is same as the divide and conquer but the difference in dynamic programming is breaking down the problems into subproblems and those problems into smaller subproblems after store the results to avoid unnecessary computations. And dynamic programming solves different types of problems.
- Brute Force:
Brute force is used to solve small-size of a problem. It is one of the easiest techniques to solve the problem based on the problems statement.
For example, consider some of the brute force algorithms.
- Backtracking and branch-and-bound:
The technique is mainly used for state-space search problems. State-space search problems looks like the following:
- Initial state
- Goal state
- Set of intermediate states
- Set of operators that are transferred from one state to another state.
- Cost function
- Utility function
- In state-space-tree whose nodes represent states, the root represents initial state leaves as goal states. Each edge is labelled with some operator.
- We will get the solution only when we find the goal state.
- Depth first search uses Backtracking
- Initial state is stored in the stack
- If stack is not empty, then:
Read the value from the stack
While there are operators do:
- To generate a child, apply an operator
- Suppose if child is goal state then stop
- Else if it is a new state, push the child into the stack.
- If children are not get generated from a node then we perform a backtracking.
- Branch and Bound:
In Branch and bound we used to evaluate each node using cost and utility functions. At every step we prefer best node. Basically Branch-and-Bound are worked based upon priority queue.e
- Example : 8 puzzle problem.
Mainly problems can be solved by many approaches. Firstly, understand the problem and later apply which technique is most suitable to the problem that gives efficient solution. Finally, on should have a good knowledge in all algorithm design techniques.