What is Algorithm? – Nutshell Explanation
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
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:
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
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.
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
Statements
end
if (condition) then
Statements
else
Statements
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
Short Questions:
Define the term: 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
State the properties of Algorithm
Following are the properties of algorithm:
- Input
- Output
- Definiteness
- Finiteness
- Effectiveness
Define the term: Time Complexity
The amount of time required to solve the given problem is called the time complexity of that algorithm
Define the term: Space Complexity
The amount of memory required to solve the given problem is called the space complexity of that algorithm
Enlist few problem solving strategies
Following are some of the popular problem solving strategies:
- String matching algorithms
- Number theory and numerical algorithms
- Divide and conquer
- Linear programming
- Dynamic programming
- Greedy methods
- Sorting
Superb explained
Thanks for interaction and showing interest
Simply Super…
Thank you very much Shivang
Crystal Clear Explanation Sir
Thank you very much Daksh
It is very useful sir thank you
Wel come Nirav :-)
sir font can not easy to read mean eyes pe load ata hai than update font dark color ya other wise background color black and text color white jesa kuch But Content is so good ❤️
Thanks