What is Algorithm | Introduction to Algorithms

The word Algorithm means ” A set of rules to be followed in calculations or other

problem-solving operations ” Or ” A procedure for solving a mathematical problem in a
finite number of steps that frequently involves recursive operations”.
Therefore Algorithm refers to a sequence of finite steps to solve a particular problem.
Algorithms can be simple and complex depending on what you want to achieve.

It can be understood by taking the example of cooking a new recipe. To cook a new
recipe, one reads the instructions and steps and executes them one by one, in the given
sequence. The result thus obtained is the new dish cooked perfectly. Every time you use
your phone, computer, laptop, or calculator you are using Algorithms. Similarly,
algorithms help to do a task in programming to get the expected output.
The Algorithm designed are language-independent, i.e. they are just plain instructions
that can be implemented in any language, and yet the output will be the same, as
expected.
What are the Characteristics of an Algorithm?
As one would not follow any written instructions to cook the recipe, but only the
standard one. Similarly, not all written instructions for programming is an algorithms.
In order for some instructions to be an algorithm, it must have the following
characteristics:
 Clear and Unambiguous: The algorithm should be clear and unambiguous. Each of
its steps should be clear in all aspects and must lead to only one meaning.
 Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined
inputs.
 Well-Defined Outputs: The algorithm must clearly define what output will be
yielded and it should be well-defined as well.
 Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
 Feasible: The algorithm must be simple, generic, and practical, such that it can be
executed with the available resources. It must not contain some future technology or
anything.
 Language Independent: The Algorithm designed must be language-independent,
i.e. it must be just plain instructions that can be implemented in any language, and
yet the output will be the same, as expected.
Properties of Algorithm:
 It should terminate after a finite time.
 It should produce at least one output.
 It should take zero or more input.
 It should be deterministic means giving the same output for the same input case.
 Every step in the algorithm must be effective i.e. every step should do some work.
Types of Algorithms:
There are several types of algorithms available. Some important algorithms are:
1. Brute Force Algorithm: It is the simplest approach for a problem. A brute force
algorithm is the first approach that comes to finding when we see a problem.
2. Recursive Algorithm: A recursive algorithm is based on recursion. In this case, a
problem is broken into several sub-parts and called the same function again and again.
3. Backtracking Algorithm: The backtracking algorithm basically builds the solution
by searching among all possible solutions. Using this algorithm, we keep on building
the solution following criteria. Whenever a solution fails we trace back to the failure
point and build on the next solution and continue this process till we find the solution or
all possible solutions are looked after.
4. Searching Algorithm: Searching algorithms are the ones that are used for searching
elements or groups of elements from a particular data structure. They can be of different
types based on their approach or the data structure in which the element should be
found.
5. Sorting Algorithm: Sorting is arranging a group of data in a particular manner
according to the requirement. The algorithms which help in performing this function are
called sorting algorithms. Generally sorting algorithms are used to sort groups of data in
an increasing or decreasing manner.
6. Hashing Algorithm: Hashing algorithms work similarly to the searching algorithm.
But they contain an index with a key ID. In hashing, a key is assigned to specific data.
7. Divide and Conquer Algorithm: This algorithm breaks a problem into sub-
problems, solves a single sub-problem and merges the solutions together to get the final
solution. It consists of the following three steps:
 Divide
 Solve
 Combine
8. Greedy Algorithm: In this type of algorithm the solution is built part by part. The
solution of the next part is built based on the immediate benefit of the next part. The
one solution giving the most benefit will be chosen as the solution for the next part.
9. Dynamic Programming Algorithm: This algorithm uses the concept of using the
already found solution to avoid repetitive calculation of the same part of the problem. It
divides the problem into smaller overlapping sub problems and solves them.
10. Randomized Algorithm: In the randomized algorithm we use a random number so
it gives immediate benefit. The random number helps in deciding the expected
outcome.
To learn more about the types of algorithms refer to the article about “Types of
Algorithms“.
Advantages of Algorithms:
 It is easy to understand.
 An algorithm is a step-wise representation of a solution to a given problem.
 In Algorithm the problem is broken down into smaller pieces or steps hence, it is
easier for the programmer to convert it into an actual program.
Disadvantages of Algorithms:
 Writing an algorithm takes a long time so it is time-consuming.
 Understanding complex logic through algorithms can be very difficult.
 Branching and Looping statements are difficult to show in Algorithms(imp).
How to Design an Algorithm?
In order to write an algorithm, the following things are needed as a pre-requisite:

1. The problem that is to be solved by this algorithm i.e. clear problem definition.
2. The constraints of the problem must be considered while solving the problem.
3. The input to be taken to solve the problem.
4. The output to be expected when the problem is solved.
5. The solution to this problem, is within the given constraints.
Then the algorithm is written with the help of the above parameters such that it solves
the problem.
Example: Consider the example to add three numbers and print the sum.

 Step 1: Fulfilling the pre-requisites

As discussed above, in order to write an algorithm, its pre-requisites must be
fulfilled.
1. The problem that is to be solved by this algorithm: Add 3 numbers and print
their sum.
2. The constraints of the problem that must be considered while solving the
problem: The numbers must contain only digits and no other characters.
3. The input to be taken to solve the problem: The three numbers to be added.
4. The output to be expected when the problem is solved: The sum of the three
numbers taken as the input i.e. a single integer value.
5. The solution to this problem, in the given constraints: The solution consists of
adding the 3 numbers. It can be done with the help of ‘+’ operator, or bit-wise, or
any other method.
 Step 2: Designing the algorithm
Now let’s design the algorithm with the help of the above pre-requisites:
Algorithm to add 3 numbers and print their sum:
1. START
2. Declare 3 integer variables num1, num2 and num3.
3. Take the three numbers, to be added, as inputs in variables num1, num2, and
num3 respectively.
4. Declare an integer variable sum to store the resultant sum of the 3 numbers.
5. Add the 3 numbers and store the result in the variable sum.
6. Print the value of the variable sum
7. END
 Step 3: Testing the algorithm by implementing it.
In order to test the algorithm, let’s implement it in your choice language.
Algorithms Design Techniques
What is an algorithm?
An Algorithm is a procedure to solve a particular problem in a finite number of
steps for a finite-sized input.
The algorithms can be classified in various ways. They are:

1. Implementation Method
2. Design Method
3. Design Approaches
4. Other Classifications
In this article, the different algorithms in each classification method are
discussed.
Classification by Implementation Method: There are primarily three main
categories into which an algorithm can be named in this type of classification.
They are:

1. 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.
2. 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.
3. 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:

1. 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.
2. 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.
3. 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.
4. 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
5. 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.
6. 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.
7. 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
1. Top-Down Approach :
2. Bottom-up approach
 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.
Other Classifications: Apart from classifying the algorithms into the above
broad categories, the algorithm can be classified into other broad categories
like:

1. Randomized Algorithms: Algorithms that make random choices for faster

solutions are known as randomized algorithms.
Example: Randomized Quicksort Algorithm.
2. Classification by complexity: Algorithms that are classified on the basis of
time taken to get a solution to any problem for input size. This analysis is
known as time complexity analysis.
Example: Some algorithms take O(n), while some take exponential time.
3. Classification by Research Area: In CS each field has its own problems
and needs efficient algorithms.
Example: Sorting Algorithm, Searching Algorithm, Machine Learning etc.
4. Branch and Bound Enumeration and Backtracking: These are mostly
used in Artificial Intelligence.

Performance Analysis
What is Performance Analysis of an algorithm?

If we want to go from city "A" to city "B", there can be many ways of doing this. We can go by flight,

by bus, by train and also by bicycle. Depending on the availability and convenience, we choose the

one which suits us. Similarly, in computer science, there are multiple algorithms to solve a problem.

When we have more than one algorithm to solve a problem, we need to select the best one.

Performance analysis helps us to select the best algorithm from multiple algorithms to solve a

problem.
When there are multiple alternative algorithms to solve a problem, we analyze them and pick the one

which is best suitable for our requirements. The formal definition is as follows...

Performance of an algorithm is a process of making evaluative judgement about algorithms.

It can also be defined as follows...

Performance of an algorithm means predicting the resources which are required to an

algorithm to perform its task.

That means when we have multiple algorithms to solve a problem, we need to select a suitable

algorithm to solve that problem.

We compare algorithms with each other which are solving the same problem, to select the best

algorithm. To compare algorithms, we use a set of parameters or set of elements like memory

required by that algorithm, the execution speed of that algorithm, easy to understand, easy to

implement, etc.,

Generally, the performance of an algorithm depends on the following elements...

1. Whether that algorithm is providing the exact solution for the problem?

2. Whether it is easy to understand?

3. Whether it is easy to implement?

4. How much space (memory) it requires to solve the problem?

5. How much time it takes to solve the problem? Etc.,

When we want to analyse an algorithm, we consider only the space and time required by that

particular algorithm and we ignore all the remaining elements.

Based on this information, performance analysis of an algorithm can also be defined as follows...
Performance analysis of an algorithm is the process of calculating space and time required

by that algorithm