Design & Analysis of Algorithms
(BCAE0106)
Lec.-2: Basics of Algorithm
Presented by:
Akanksha
Assistant Professor
Dept. of Computer Engineering & Applications, IET,
GLA University, Mathura
Introduction
Algorithm
Need of an Algorithm
How to write an algorithm
Algorithm characteristics
Applications of an Algorithm
Good qualities of an Algorithm
Algorithm
An algorithm is defined as a finite number of steps to solve a problem.
A finite set of instruction that specifies a sequence of operation is to
be carried out in order to solve a specific problem or class of problems
is called an Algorithm.
An algorithm is a sequence of computational steps that transform
input to desired output.
(Thomas H. Coreman)
An algorithm is a finite set of instructions that, if followed,
accomplishes a particular task
(Sartaj Sahni)
The following algorithm is given below To Make a Cup of Tea
Step 1: Place the fresh water in a saucepan or a kettle.
Step 2: Boil the water.
Step 3: Put the black tea leaves in that pot.
Step 4: After that add some milk into that pot.
Step 5: Add some sugar.
Step 6: Boil for some time.
And it is ready to serve.
Need of an Algorithm?
To understand the basic idea of the
problem.
To find an approach to solve the problem.
To compare the performance of the
algorithm with respect to other techniques.
It is the best method of description without
describing the implementation detail.
The Algorithm gives a clear description of
requirements and goal of the problem to
the designer.
5
Need of an Algorithm?
To understand the flow of the problem.
To measure the behavior (or performance)
of the methods in all cases (best cases,
worst cases, average cases)
We can measure and analyze the
complexity (time and space) of the
problems concerning input size without
implementing and running it; it will reduce
the cost of design.
6
How to Write Algorithm?
Natural Language
Flow Chart
Programming Language
Pseudo code
7
Natural Language
Step 1: Start
Step 2: Declare variables Step 1 − START
a, b and sum.
Step 2 − Get values
Step 3: Read values for a
of a & b
and b.
Step 4: Add a and b and Step 3 − c ← a + b
assign the result to a
variable sum. Step 4 − Display c
Step 5: Display sum Step 5 − STOP
Step 6: Stop
8
Flow Chart
Step 1: Start
Step 2: Declare variables
a, b and sum.
Step 3: Read values for a
and b.
Step 4: Add a and b and
assign the result to a
variable sum.
Step 5: Display sum
Step 6: Stop
9
Example
Preparation of pizza and
try to build an
algorithm/flowchart to
represent how it can be
made.
Input: It takes inputs
(ingredients).
Output: Pizza, an output
(the completed dish).
10
Programming Language Pseudo
Code
int main()
{
int a, b, sum;
printf("Enter two numbers to BEGIN
add\n"); Read a, b
scanf("%d%d", &a, &b);
Set sum to a+b
sum = a + b;
END:
printf("Sum of the numbers =
%d\n", sum);
return 0;
}
11
Characteristics of algorithm
All algorithms must satisfy the following seven criterias:
Input
Output
Finiteness
Effectiveness
Unambiguous
Feasibility
Language Independent
Characteristics of Algorithm:
Input − An algorithm should have well-defined inputs that
determines the starting position. It may or may not take
input.
Output − An algorithm should have at least 1 or more well-
defined outputs, and should match the desired output.
Effectiveness – The Algorithm should be written in such a
manner that it fulfill the purpose for that it is designed.
Unambiguous − Algorithm should be clear and
unambiguous. Each of its steps (or phases), and their
inputs/outputs should be clear and must lead to only one
meaning.
13
Characteristics of Algorithm:
Finiteness − Algorithms must terminate after a finite
number of steps.
Feasibility − The algorithm must be simple, generic, and
practical, such that it can be executed using reasonable
constraints and resources.
Language Independent - Algorithm 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.
14
Applications of Algorithm:
Solving Everyday Problems
Recommendation System
Finding Route / Shortest Path
E-Commerce Categories
Recognizing Genetic Matching
15
Qualities of Good Algorithm:
What Makes a Good Algorithm?
Suppose you have two possible algorithms or data
structures that basically do the same thing; which is
better?
Faster?
Less space?
Easier to code?
Easier to maintain?
16
Qualities of Good Algorithm:
The factors that we need to consider while determining the
quality of a good Algorithm are:
Time: The amount of time it takes to run as a function of
the length of the input is known as time requirement.
Memory: The amount of memory utilized by the algorithm
(including the inputs) to execute and create the output is
referred to its memory requirement.
Accuracy: There can be more than one solution to the
given problem, but the one which is the most optimal is
termed as accurate.
17
