UNIT-1
ALGORITHM
• The word algorithm came from the name of a Persian mathematician Abu Jafar Mohammed
Ibn Musa Al Khowarizmi (ninth century). An algorithm is simply s set of rules used to
perform some calculations either by hand or more usually on a machine (computer).
• Definition: An algorithm is a finite set of instructions that accomplishes a particular task.
Another definition is a sequence of unambiguous instructions for solving a problem i.e. for
obtaining a required output for any legitimate (genuine) input in a finite amount of time.
An algorithm is a step by step procedure for solving the problems or complete task.
CHARASTERISTICS OR PROPERTIES OF AN ALGORITHM:
In addition, all algorithms must satisfy the following characteristics/properties
1. Input: Each algorithm considers 0, 1, or more quantities should be given as input and
algorithm produce at least one quantity as output.
Consider Fibonacci numbers program, here aim of the problem is to display ten Fibonacci
numbers. No input is required; in the problem itself this is clearly mentioned as ten
Fibonacci values. So, zero items required for input. In the case of Fibonacci numbers
program after executing the program, first ten Fibonacci values displayed as output.
Another problem is displaying given numbers of evens, so user should accept how many
evens required. Based on the user input it should display given number of evens. So, one
data item is required as input. An input of negative number is wrong, should display proper
error message as output. So, this program displays at least one output as error message, or
number if outputs that show given number of steps.
2. Definiteness: Each instruction is clear and unambiguous i.e. each step must be easy to
understand and convey only a single meaning.
3. Finiteness: An algorithm should terminate after some finite number of steps. If we can
trace out the instructions of an algorithm then for all cases, the algorithm terminate after a
finite number of steps.
Either in the case of Fibonacci or even numbers problem should be solved in some number
of steps. For example, continuous display or Fibonacci series without termination leads to
abnormal termination.
4. Effectiveness: an algorithm should contain only necessary steps. It should not contain
unnecessary steps. each instruction of an algorithm should be feasible, so that it can be
carried out by a person using only pencil and paper. Each instruction should be complete,
that instruction can take finite amount of time and memory.
This step is common in both Fibonacci and primes. For example, if user enters a negative
number as input in evens, if you have a step like
Step: If N < 0 then Go to ERROR
A wrong instruction given as go to ERROR, those kinds of instructions should not be there
in an algorithm.
5. Generality: An algorithm should run for any type of input and data.
Process for Design and analysis of algorithms:
1. Understand the problem: This is very crucial phase. If we did any mistake in this step
the entire algorithm becomes wrong. So before designing an algorithm is to understand the
problem first.
2. Solution as an algorithm (Exact vs approximation solving): Solve the problem exactly if
possible. Even though some problems are solvable by exact method, but they are not faster
when compared to approximation method. So in that situation we will use approximation
method.
3. Algorithm techniques: In this we will use different design techniques like,
i. Divide-and-conquer
ii. Backtracking
iii. Dynamic programming
iv. Greedy method
v. Branch and bound…. etc.,
4. Prove correctness: once algorithm has been specified, next we have to prove its
correctness. Usually testing is used for proving correctness.
5. Analyze an algorithm: Analyzing an algorithm means studying the algorithm behavior
ie., calculating the time complexity and space complexity. If the time complexity of
algorithm is more then we will use one more designing technique such that time complexity
should be minimum.
6. Coding an algorithm: after completion of all phases successfully then we will code an
algorithm. Coding should not depend on any program language. We will use general
notation (pseudo-code) and English language statement. Ultimately algorithms are
implemented as computer programs.
Types of Algorithms:
There are four types of algorithms
1. Approximate Algorithm: An algorithm is said to approximate if it is infinite and
repeating. Ex: √2 = 1.414 and √3 = 1.713
2. Probabilistic algorithm: If the solution of a problem is uncertain then it is called as
probabilistic algorithm. Ex: Tossing of a coin.
3. Infinite Algorithm: An algorithm which is not finite is called as infinite algorithm. Ex: A
complete solution of a chessboard, division by zero.
4. Heuristic algorithm: Giving fewer inputs getting more outputs is called the Heuristic
algorithms. Ex: All Business Applications.
Criteria’s (or) Issues for algorithm:
There are various issues in the study of algorithms:
1. How to devise algorithms: The creation of an algorithm is a logical activity which may never
be fully automated.
2. How to express algorithms: We shall express all of our algorithms using the best principles
of structuring.
3. How to validate algorithms: After creation of algorithms is to validate algorithms. The
process of checking an algorithm computes the correct answer for all possible legal inputs is
called algorithm validation. The purpose of validation of algorithm is to find whether algorithm
works properly without being dependent upon programming languages.
4. How to analyze algorithms: Analysis of algorithm is a task of determining how much
computing time and storage is required by an algorithm. Analysis of algorithms is also called
performance analysis. The behavior of algorithm in best case, worst case and average case
needs to be obtained.
5. How to test a program: Testing a program really consists of two phases:
i). Debugging: While debugging a program, it is checked whether program produces faulty
results for valid set of input and if it is found then the program has to be corrected.
ii). Profiling or performance measuring: Profiling is a process of measuring time and space
required by a corrected program for valid set of inputs.
Specification of algorithm:
There are various ways by which we can specify an algorithm.
Using Natural Language: It is very easy to specify an algorithm using natural language. But
many times, specification of algorithm by using natural language is not clear, and may require
brief description.
Example: Write an algorithm to perform addition of two numbers.
Step 1: Read the first number, say ‘a’.
Step 2: Read the second number, say ‘b’.
Step 3: Add the two numbers and store the result in a variable ‘c’.
Step 4: Display the result.
Such a specification creates difficulty, while actually implementing it (difficulty in converting into
source code). Hence many programmers prefer to have specification of algorithm by means of
pseudo-code.
Flowchart: Another way of representing the algorithm is by flow chart. Flow chart is a graphical
representation of an algorithm, but flowchart method works well only if the algorithm is small
and simple. Some of the symbols are used in flowchart is given below.
Pseudo-Code for expressing Algorithms: Based on algorithm pseudo-code is a representation of
algorithm in which instruction sequence can be given with the help of programming constructs. It
is not a programming language since no pseudo language compiler exists. Pseudo code is
combination of natural language and program code. Pseudo code is informal or artificial language
that helps programmers to develop the algorithm. Informal language is a user-friendly language
and artificial language is man made language like C, C++, Java, etc.
The general procedure for writing the pseudo-code is presented below-
1. Comments begin with // and continue until the end of line.
2. A block of statements (compound statement) are represented using { and } for example if
statement, while loop, functions etc.,.
Example
{
Statement 1;
Statement 2;
.........
.........
}
3. The delimiters [;] are used at the end of each statement.
4. An identifier begins with a letter. Example: sum, sum5, a; but not in 5sum, 4a etc.
5. Assignment of values to the variables is done using the assignment operators as := or .
6. There are two Boolean values: TRUE and FALSE.
Logical operators: AND, OR, NOT.
Relational operators: <, >, <, ≥, =, ≠.
Arithmetic operators: +, -, *, /, %;
7. The conditional statement if-then or if-then-else is written in the following form. If
(condition) then (statement)
If (condition) then (statement-1) else (statement-2)
‘If’ is a powerful statement used to make decisions based as a condition. If a condition is
true the particular block of statements was executed.
Example
if(a>b) then
{
write("a is big");
}
else
{
write("b is big");
}
8. Case statement
switch(expression)
{
:(condition -1): (statement-1)
:(condition -2): (statement-2)
:(condition -n): (statement-n)
..............
..............
default: (statement n+1);
}
If condition -1 is true, statement -1 executed and the case statement is exited. If statement-1 is
false, condition-2 is evaluated. If condition-2 is true, statement-2 executed and so on. If none of
the conditions are true, statement-(n+1) is executed and the case statement is exited. The else
clause is optional.
9. Loop statements:
For loop: The general form of the for loop is
Syntax: Example:
for variable:=value-1 to value-n step do for i:=1 to 10 do
{ {
Statement -1; write(i); //displaying numbers from 1 to 10 i:=i+1;
Statement -1; }
.......
.......
Statement -n;
}
While loop: The general form of the while loop is
Syntax: Example:
while <condition> do i:=1;
{ while(i<=10)do
<statement 1> {
<statement 2> write (i);//displaying numbers from 1 to 10
........ i:=1+1;
........ }
<statement n>
}
Note that the statements of while loop are executed as long as <condition> is true.
Repeat-until loop: The general form of repeat-until is
Syntax: Example:
repeat i:=1;
{ repeat
<statement 1> {
<statement 2> write (i); i:=i+1;
...... }
...... until (i>10);
<statement n>
}until <condition>
Note that the statements are executed as long as <condition> is false.
10. Break: This statement is exit from the loop.
11. Elements of array are accessed using [ ].
For example, if A is an one-dimensional array, then ith element can be accessed using A[i]. If
A is two-dimensional array, then (i, j)th element can be accessed using A[i,j].
12. Procedures (functions): There is only one type of procedure: An algorithm consists of a
heading and a body.
Algorithm Name (<parameter list>)
{
body of the procedure
}
13. Compound data-types can be formed with records
Syntax: Example
Name = record Employee =record
{ {
data-type -1 data 1; int no;
data-type -2 data 2; char name[10]; float salary;
data-type -n data n; }
}
Example1: Write an algorithm to find the sum of n numbers.
Algorithm sum(n)
{
total:=0;
for i:=1 to n do
total:= total + i;
i:=i+1;
}
Example 2: Write an algorithm to perform Multiplication of two matrices.
Algorithm Multiplication (A, B, n)
{
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];
}
