# Algorithms Classification

An Algorithm is a procedure to solve a particular problem in a finite number of steps for a finite-sized input.

## Algorithms Classification #

The algorithms can be classified in various ways. They are:

• Implementation Method

• Design Method

• Design Approaches

### Classification by Implementation Method #

There are primarily three main categories into which an algorithm can be named in this type of classification. They are:

#### Recursion or Iteration #

• A recursive algorithm is an algorithm which calls itself again and again until a base condition is achieved whereas iterative algorithms use loops and/or data structures like stacks, queues to solve any problem.

• Every recursive solution can be implemented as an iterative solution and vice versa.

##### Example #

The Tower of Hanoi is implemented in a recursive fashion while Stock Span problem is implemented iteratively.

#### Exact or Approximate #

• Algorithms that are capable of finding an optimal solution for any problem are known as the exact algorithm.

• For all those problems, where it is not possible to find the most optimized solution, an approximation algorithm is used.

• Approximate algorithms are the type of algorithms that find the result as an average outcome of sub outcomes to a problem.

##### Example #

For NP-Hard Problems, approximation algorithms are used. Sorting algorithms are the exact algorithms.

#### Serial or Parallel or Distributed Algorithms #

• In serial algorithms, one instruction is executed at a time while parallel algorithms are those in which we divide the problem into subproblems and execute them on different processors.

• If parallel algorithms are distributed on different machines, then they are known as distributed algorithms.

### Classification by Design Method #

There are primarily three main categories into which an algorithm can be named in this type of classification. They are:

#### Greedy Method #

In the greedy method, at each step, a decision is made to choose the local optimum, without thinking about the future consequences.

##### Example #

Fractional Knapsack, Activity Selection.

#### Divide and Conquer #

The Divide and Conquer strategy involves dividing the problem into sub-problem, recursively solving them, and then recombining them for the final answer.

##### Example #

Merge sort, Quicksort.

#### Dynamic Programming #

• The approach of Dynamic programming is similar to divide and conquer.

• The difference is that whenever we have recursive function calls with the same result, instead of calling them again we try to store the result in a data structure in the form of a table and retrieve the results from the table.

• Thus, the overall time complexity is reduced.

• `Dynamic` means we dynamically decide, whether to call a function or retrieve values from the table.

##### Example #

0-1 Knapsack, subset-sum problem.

#### Linear Programming #

In Linear Programming, there are inequalities in terms of inputs and maximizing or minimizing some linear functions of inputs.

##### Example #

Maximum flow of Directed Graph

#### Reduction(Transform and Conquer) #

• In this method, we solve a difficult problem by transforming it into a known problem for which we have an optimal solution.

• Basically, the goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithms.

##### Example #

Selection algorithm for finding the median in a list involves first sorting the list and then finding out the middle element in the sorted list. These techniques are also called transform and conquer.

#### Backtracking #

• This technique is very useful in solving combinatorial problems that have a single unique solution.

• Where we have to find the correct combination of steps that lead to fulfillment of the task.

• Such problems have multiple stages and there are multiple options at each stage.

• This approach is based on exploring each available option at every stage one-by-one.

• While exploring an option if a point is reached that doesn’t seem to lead to the solution, the program control backtracks one step, and starts exploring the next option.

• In this way, the program explores all possible course of actions and finds the route that leads to the solution.

##### Example #

N-queen problem, maize problem.

#### Branch and Bound #

• This technique is very useful in solving combinatorial optimization problem that have multiple solutions and we are interested in find the most optimum solution.

• In this approach, the entire solution space is represented in the form of a state space tree.

• As the program progresses each state combination is explored, and the previous solution is replaced by new one if it is not the optimal than the current solution.

##### Example #

Job sequencing, Travelling salesman problem.

### Classification by Design Approaches #

There are two approaches for designing an algorithm. these approaches include

#### Top-Down Approach #

In the top-down approach, a large problem is divided into small sub-problem and keep repeating the process of decomposing problems until the complex problem is solved.

#### Bottom-up approach #

The bottom-up approach is also known as the reverse of top-down approaches. In approach different, part of a complex program is solved using a programming language and then this is combined into a complete program.