What and Why?
Algorithms are a well-ordered sequence of instructions that are used to solve a particular problem. The algorithm design technique is a strategy of developing an efficient algorithm to solve a problem or to do any computations. Various algorithm techniques are implemented to reach higher performance which is measured in terms of efficiencies. Here, the efficiency of an algorithm can be defined in terms of
- Time Complexity
- Space Complexity
The algorithm should be time-efficient or memory efficient. It’s important to remember that the algorithm can never be time-efficient and memory-efficient at the same time. We need to compromise with one of them and select the best one.
The following are the popular design techniques:
- Brute Force
- Decrease and Conquer
- Divide and Conquer
- Transform and Conquer
- Dynamic Programming
- Greedy Technique
- Space and Time Trade-off
- Randomized Algorithms
- Backtracking
Note: There are many other techniques like a branch and bound, linear programming etc.
1. BRUTE FORCE
It is an exhaustive straightforward algorithm that is used to solve a problem, usually, directly based on the problem statement and definitions of the concepts involved.
Basic Algorithm:
c <- first(P)
while c != NULL do
if valid(P, c)
then output(P, c)
c <- next (P, c)
end while
Example: Imagine you forget your mobile lock screen password which is of 5 digits. To know the password we need to try various combinations of a 5 digit number, digits ranging from 0-9. We can use brute force to solve this issue. Using brute force we can generate various combinations of digits and find out the password. Total 100000 combinations can be generated.
How do we speed up?
- Reduce search-space.
- Re-order the search space.
- Use alternatives to brute force.
Examples:
- Bubble Sort
- Brute Force String Match
- Selection Sort
- Sequential Search
- Travelling sales Problem
- Knapsack Problem
2. DECREASE AND CONQUER
It is based on exploiting the relationship between a solution to a given instance of a problem and a solution to a smaller instance of the same problem. Once the relationship is established, it can be either exploited by a top-down approach using recursion or a bottom-up approach without recursion.
The technique has following variations:
- Decrease by a constant.
- Decrease by a constant factor.
- Variable size decreases.
Example: for the problem to compute an ,
Top down approach is:
f(n) = f(n-1)*a if n>1
a if n = 1
Examples:
- Insertion Sort
- Depth First Search and Breadth First Search
- Topological Sorting
- The Game of Nim
- Interpolation Search
3. DIVIDE AND CONQUER
It is based on multi-branched recursion.
This technique follows 3 steps:
1. Divide-Break:
The main problem breaks down into smaller sub-problems i.e. the main is divided into subproblems until it the subproblem becomes easy to solve.
2. Conquer/Solve
The smaller subproblems are solved independently.
3. Merge-Combine
This step takes place once all the subproblems are solved. It recursively combines all the solutions of the subproblems to generate a single solution to the original problem.
Examples:
- Quick Sort
- Merge Sort
- Binary Search
- Strassen’s Matrix Multiplication
4. TRANSFORM AND CONQUER
A problem instance is transformed to one of the below before the solution is obtained.
Instance simplification: transform to a simpler or more convenient instance of the same problem
Representation change: transform to a different representation of the same instance
Problem reduction: transform to an instance of a different problem for which an algorithm is already available.
Examples:
- 2-3 Trees
- AVL Trees
- Heap Sort
5. DYNAMIC PROGRAMMING
Dynamic Programming is an optimization method that is used to solve complex problems by breaking the problem into a collection of subproblems and storing the solution for every subproblem. If the same problem occurs that was previously solved, then the same solution is looked upon which saves the computational time. Storing the solutions to subproblems instead of recomputing them is called “memoization”.
Examples:
- Bellman-Ford Algorithm
- Warshall’s Algorithm
- Floyd’s Algorithm
6. GREEDY TECHNIQUE
A greedy algorithm follows the problem-solving heuristic of making the locally optimal choice at every stage of the given problem to find a global optimum. In Dijkstra’s Algorithm, Greedy Techniques are used to find the shortest distance between two nodes in a graph.
Examples:
- Huffman Trees
- Prim’s Algorithm
- Dijkstra’s Algorithm
- Kruskal’s Algorithm
7. SPACE AND TIME TRADE-OFF
In space and time trade-off, space refers to the memory space consumed to perform a particular task whereas time refers to the time consumed to perform a particular task.
Examples:
- Hashing
- Boyer-Moore Algorithm
8. RANDOMIZED ALGORITHMS
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. In this algorithm, we use random numbers to decide what is the next step that has to be taken in order to solve. For example, in the case of Quick Sort to select the next pivot element we make use of random variables.
Examples:
- Bloom Filter
- Skip List
- Random Binary Trees
9. BACKTRACKING
A backtracking algorithm is used to solve the problems recursively. In the backtracking algorithm, n number of decisions are carried out until we arrive at the decision which works the best for the given problem. As mentioned before backtracking in a recursive algorithm that the function is called multiple times until the feasible solution is found out.
Examples: N Queen’s Problem