What is an algorithm? Types of Algorithms

Introduction

An algorithm is a set of steps involved in solving a problem. An algorithm consists of various steps that define how a work needs to be done in order to get the expected result. The term algorithm was coined after the name of a mathematician of the 9th century named Ibn Musa Al-Khwarizmi.

An algorithm could be a solution to anything, a solution to a mathematical problem, or a solution to complete a task in our daily life. For example- If you want to make a coffee, you would probably take the following steps.

• Take a utensil.
• Pour some water into it.
• Turn on the gas stove and keep the utensil over it.
• Add coffee powder to the water kept in the utensil.
• Add some sugar.
• Add milk.
• Boil the mixture.

Example in Mathematics

The word ‘algorithm’ is very popular and is widely used in the fields of mathematics and computer science. For instance, in mathematics, if we need to expand (2x + 4)(4 + x), then the following algorithm would be used.

• Multiply the first terms of both the brackets i.e., 2x * 4 = 8x.
• Multiply the first term of the first bracket to the second term of the second bracket i.e., 2x * x = 2×2.
• Multiply the second term of the first bracket to the first term of the second bracket, i.e., 4 * 4 = 16.
• Multiply the second term of the first bracket to the second term of the second bracket, i.e., 4 * x = 4x.
• Add all the results, i.e. 8x + 2×2 + 16 + 4x

Algorithm in Computer Science

In computer programming, an algorithm is a set of steps in a program or a script to generate the desired output. To get the computer to perform every single task, we need to give it some step-by-step instructions in the form of a computer program or script. A program or a script is a set of steps the computer should take in order to achieve the goal.

While you tell the computer what to do, you can also choose how it’s going to do it. That’s where computer algorithms come into the picture. The algorithm is the basic technique used to get the job done. Let’s see another example that would help to understand the concept of algorithms in computer programming.

For example – If you need to find the average of two integers selected by a user, then you should follow these steps.

• Take two integer numbers from the user.
• Add the numbers.
• divide the result by 2.

Here is a C++ program to demonstrate this algorithm-

#include <iostream>
using namespace std;
int main()
{
  	int num1, num2, result; 
	cout<<"Enter a number : ";
	cin>>num1;
        cout<<"Enter second number : ";
	cin>>num2;
	result = (num1 + num2)/2;
	cout<<"The average is "<<result;
	return 0;
}

Output :

Enter a number : 4

Enter second number : 12

The average is 8

Some Common Types of Algorithm

An algorithm is a key feature of computer programming. An algorithm is widely used for sorting in programming. Although there are a bunch of different algorithms, here are some of the most common and fundamental algorithms-

Recursive algorithm

This algorithm works on recursion(One of the concepts used in programming). In this algorithm, a function is repeatedly calling itself until a solution is found. A well-known puzzle called as Tower of Hanoi can be solved easily by this algorithm.

Divide and conquer algorithm

Divide and conquer algorithm consists of two parts. The first part contains the smaller sub-problems. In the second part, these subproblems are solved and the solutions are added together to get the final solution.

Dynamic Programming Algorithm

This algorithm uses the results of past execution to find the solution to new problems. It breaks the problem into multiple subproblems, solves each of them, and stores the results for future usage.

Greedy Algorithm

This algorithm is quite useful in optimization problems. It tries to make a solution in pieces and chooses the next piece that has the most obvious beneficial outcome.

Brute Force Algorithm

A brute force algorithm tries every single possibility to solve a problem. For example, if you forgot your password that is of two digits from 1-5, then you have to try with 11, 12, 13, and so on until you find the correct password. It could take 52 or 25 attempts to find the correct password in the worst case. The brute force algorithm works in the same manner.

Backtracking Algorithm

It is an algorithm that is used more often to solve a variety of puzzles. This algorithm builds smaller candidates, tries each, and avoids(backtracks) a candidate if it finds that the particular candidate cannot lead to the correct solution.

Have a look at the picture given below –

Suppose you are at point O and there are four different paths. There is an ice cream parlor at the end of one of the four paths, but you don’t know where it is. Suppose you start walking on path A, but the parlor is not there. So you will return back to point O and try another path. You would try different paths and avoid the paths that do not lead to your destination. You would repeat the process until you reach the ice cream parlor.

The backtracking algorithm works exactly in the same manner. It tries every single possibility and backtracks those which could not lead to the solution.