What is Algorithm?

The algorithm is a set of rules defined in specific order to do certain computation and carry out some predefined task. It is a step by step procedure to solve the problem.

Evolution of algorithm has gone through lone way. The term Algorithm was coined by the Persian mathematician Al-Khwarizmi in the ninth century.

Given the algorithm, it is easy to program the solution. It bridges the gap between natural language description of the solution and syntax of programming language. It is a set of rules which are used to solve real-life problems. It provides a loose form of a solution in a pseudo-programming language. We can treat it as a set of finite instructions which solves a particular problem when applied it is applied to that problem with legal inputs.

The first-ever algorithm was developed by Babylonians for factorization of a number and to find roots of the equation. Euclid had proposed a famous algorithm for finding Greatest Common Divisor (GCD) of two numbers.

Initially, the solution to the problem is thought as a natural language description, whose syntax is too far from the programming language. Before the actual problem solved in a programming language, natural language description of the solution is first represented as an algorithm. It is then converted to programming syntax. The process of solving a problem is depicted in following figure

problem solving using algorithm
Problem Solving using Algorithm

If the algorithm is correct, then the program should produce correct output on valid input, otherwise, it should produce an appropriate error message. For example, to find the division A/B, correctly written program would return value of A/B for B > 0, and it would show the error message like “Invalid divisor” for B = 0.

Properties of Algorithm

A good algorithm should have the following properties/characteristics:

Properties of Algorithm
Properties of Algorithm

Input: The algorithm may take zero or more input arguments. Depending on the problem, the input may be a scalar, vector, array, tree, graph or some other data structures

Output: The algorithm reads input, processes it and produces at least one output. Depending on the problem being solved, the output may of the form scalar, vector, array, tree, graph or some other data structures.

Definiteness: All instructions should be unambiguous and simple to interpret. There should not be multiple ways to interpret the same instruction. Each instruction should be precise and concise

Finiteness: Every algorithm must terminate after a finite number of steps. If the algorithm contains a loop, the upper bound of the loop must be finite. Recursive calls should have a well-defined base case for the termination

Effectiveness: The algorithm should be written with a basic set of instructions. The operations should be basic enough to perform exactly using a basic set, just like one can perform them with pen and paper. Complex operations should be performed using a combination of basic instruction. For example, multiplication should be performed using loop and addition, sorting should be carried out using looping, comparison, swapping etc.

Types of Algorithmic Complexities

Algorithms are analyzed using two types of complexities

Types of algorithmic complexity
Types of algorithmic complexity

Time complexity: It is the amount of time taken by the algorithm to solve the given problem.

Space complexity: It is the amount of memory required by the algorithm to solve the given problem.

Problems Solved by Algorithms

Algorithms are not developed just to solve problems like sorting, factorial, GCD etc. The scope of the algorithm is much wider than that. Few of the real-life problems are listed here for which the design of an efficient algorithm matters a lot

Such problems may not be solved effectively using traditional approaches and even if they are solvable, the answer may not be optimal or it may take a too long time. Various class of algorithms are :

  • String matching algorithms: Can be useful in text search, editors, compilers etc.
  • Number theory and numerical algorithms: Useful in the statistical analysis of data.
  • Divide and conquer: Used to solve sorting, convex hull, min-max problem.
  • Linear programming: Can be useful in solving many optimization problems.
  • Dynamic programming: Solves the optimization problems like subsequence, super sequence, assembly line scheduling, cruise scheduling etc.
  • Greedy methods: Provides a suboptimal solution to the problems like make a change, minimum spanning tree, Huffman code, job sequencing etc.
  • Sorting: Useful to sort numerical or string data.

However, the list is far more exhaustive, but we listed here a few of the most common problems appear in real life.

How to Write Algorithm?

The algorithm consists of two parts:

Head and body. Head part consists of name, description of the problem being solved, input to the problem and expected output. It may also include the explanation of the input argument and output variable. The description provides a clear idea to the user about the functionality of the algorithm.

Body part includes a logical sequence of statements involving various constructs like conditional statements, expressions, loops, breaks, function calls etc.

Structure of Algorithm
Structure of Algorithm

An algorithm is a lucid form of program and it does not have rigid restrictions on the syntax. One can write it using his own terminology and syntax

However, some of the common rules followed for writing algorithms, which are stated below :

  • The algorithm should start with the keyword Algorithm, followed by its name, followed by a list of arguments to be passed.
Algorithm FIND_SUM(A, B)
  • Comments start with // sign. In the very next line, we should specify the description and input-output.
// Problem Description : Add two integer numbers.
// Input: Two numbers A and B on which sum is to be performed.
// Output: Sum of given two numbers.
  • Next comes the body part, which contains various logical statements in the proper sequence. These statements may contain control statements, loops, expressions etc.
  • Compound statements are enclosed within the opening and closing curly brace i.e. { … }
  • Use the left arrow for assignment
C ← A + B
  • Array index usually starts with index 0 or 1.
  • Relational operations are performed using relational operators like <, >, ==, !=, ?= and <=
  • Logical operations are performed using logical operators like and or and not
  • Input and output are performed using read and write a statement.
read (A) / read “A”
write (A) / write “A” 
print (A) / print “A”
  • Control statements are written as follows :
if (condition) then 
    Statement 
end

if (condition) then 
    Statement 
else 
    Statement 
end
  • Multiple statements are enclosed within { … }
  • While loop is written as follows :
while (condition) do
{
    Do some work
}
  • Sometimes curly braces are omitted and a block is closed with the end keyword
while (condition) do
 Do some work
end
  • For loop is written as follows:
for index ← FirstIndex to LastIndex do
{
    Do some work 
}
  • Sometimes curly braces are omitted and a block is closed with the end keyword
for index ← FirstIndex to LastIndex do
    Do some work 
end

Examples:

Write an algorithm for finding the factorial of number n.

Algorithm FACTORIAL(n)
// Description: Find factorial of a given number
// Input: Number n whose factorial is to be computed
// Output : Factorial of n = n x (n – 1) x … x 2 x 1

if (n == 1) then
	return 1
else
	return n * FACTORIAL(n – 1)
end

Write an algorithm to perform matrix multiplication

Algorithm MATRIX_MULTIPLICATION(A, B)
// Description: Perform matrix multiplication of two matrices.
// Input : Two matrices A and B of size n x n.
// Output : Resultant matrix containing multiplication of A and B

for i ← 1 to n do
	for j ← 1 to n do
		C[i][j] ← 0
		for k ← 1 to n do
			C[i][j] ← C[i][j] + A[i][k] * B[k][j]
		end
	end
end

However, there is no strict rule to follow these standards. Its syntax may vary from person to person.


Additional Resource: History of development of algorithm