In computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculations, data processing and automated reasoning tasks.
An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing “output” and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.
There are certain requirements that an algorithm must abide by:
- Definiteness: Each step in the process is precisely stated.
- Effective Computability: Each step in the process can be carried out by a computer.
- Finiteness: The program will eventually successfully terminate.
Some common types of algorithms include sorting algorithms, search algorithms, and compression algorithms. Classes of algorithms include Graph, Dynamic Programming, Sorting, Searching, Strings, Math, Computational Geometry, Optimization, and Miscellaneous. Although technically not a class of algorithms, Data Structures are often grouped with them.
There are different approaches used for writing an algorithm depending on the type of problem
- Brute force Approach: A straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.
- Divide and Conquer Approach: This approach works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
- Decrease and Conquer Approach: This technique works by dividing a given problem into subproblem, finding the solutions to that subproblem, and finally extending the solution of sub-problem to arrive at the solution of the original problem.
- Greedy Technique: Greedy approach solves a given problem by making a locally optimal choice at each step which will lead to a globally optimal solution.
- Backtracking: Backtracking can be defined as a technique for solving problems recursively by trying to find a solution incrementally i.e. step by step and by removing those solutions that fail to satisfy the constraints of the problem at any point of time.
- Dynamic Programming: It is a technique for solving a complex problem by breaking it into subproblems in a recursive manner. This technique differs from the divide and conquer approach by recording the results of subproblems in a table and uses those table results to arrive at the solution of the original problem.