Some simple Algorithm
Chapter 3
Some Simple Algorithm.
A
A
lgorithm is a blueprint, the program follows to achieve the end result. The end result thus depends
on the proper understanding of the logic constructs rather than the programming constructs specific
to the programming language. In this chapter we present some simple problems and discuss the
issues in solving the problem and finally design the algorithms for the same.
3.1 ADDITION OF TWO NUMBER.
In a programming situation if we need to add two numbers , we require two memory locations to take
the input and one more memory location to store the result, totally three memory locations.
Consider the following example :
3 + 6 = 9
a b c
The ‘a’ ,‘b’ ,‘c’ are the memory locations from now on called the variables. When we generalize this,
it appears as
c= a + b
To make it even more simple, we have two inputs and one output. To store one output and two inputs
we need three variables or memory locations. The Algorithm to add two numbers is now given below.
Chapter 3 - Some Simple Algorithms
BSIT 41 Algorithms
Algorithm : Add_two_numbers
Input : a, b, two numbers to be added
Output : c updated
Method
c= a + b
Display c
Algorithm ends
3.2 INPUT THREE NUMBERS AND OUTPUT THEM I.
ASCENDING ORDE.
The problem of sorting is major computer science problem. The problem of sorting is dealt in depth in
the next chapter, but here only the problem of sorting of three numbers is presented.
To sort three numbers in ascending order, one has to follow the procedure described here. Find the
smallest among the three numbers, that becomes the first element in the sorted list, and find the smallest
among the remaining two elements and that becomes the second element and remaining becomes the last
element.
Consider the following example: 3 , 1, 7 is the input
The smallest amongst these three is 1, therefore 1 becomes the first element in the sorted list. Amongst
3 and 7, 3 is smaller, hence 3 is the second element and 7 is left out and it becomes the last element. Hence
the sorted list becomes 1, 3, 7.
Algorithm : Sorting_3_Elements
Input : a, b, c, the three numbers to be sorted
Output : The Ascending order sequence of the 3 elements
Method:
small = a // Assign ‘a’ to small
k1 = b
k2 = c
if (small > b )
Chapter 3 - Some Simple Algorithms
b = small
k1 = a
k2 = c
end_if
if (small> c)
c = small
k1 = a
k2 = b
end_if
Display small
If (k1 > k2 )
Display k2
Display k1
Else
Display k1
Display k2
end_if
Algorithm ends
3.3 TO FIND THE QUADRANT OF A GIVEN CO-ORDINAT.
POSITIO.
The problem of finding the Quadrant in which a given co-ordinate position(x,y) lies is a Computer
Graphics problem. In a Cartesian system if both X and Y co-ordinates are positive then it is said to be First
Quadrant of the Cartesian plane. If X and Y are both negative then it said to be Third Quadrant of the
Cartesian plane. If X is negative and Y is positive then it is said to be Second Quadrant and in case if X
is positive and Y is negative then it said to be in the Fourth Quadrant of the Cartesian plane. The Diagram
of the Cartesian plane is given in Fig. 3.1 below to make facts more clearer.
BSIT 41 Algorithms
Fig. 3.1 Cartesian plane
The co-ordinate positions thus entered have to fall in either of those Quadrant based on the sign of the
X and Y co-ordinate positions.
Algorithm : Quadrant_Finder
Input : x, X co-ordinate
y, Y co-ordinate
Output : Corresponding Co-ordinate
Method
If( x >=0)
If(y>=0)
Display ‘I –Quadrant’
Else
Display ‘IV-Quadrant’
end_if
else
If(y>=0)
Display ‘II –Quadrant’
Else
Chapter 3 - Some Simple Algorithms
Display ‘III-Quadrant’
end_if
end_if
Algorithm ends
3.4 TO FIND THE ROOTS OF A QUADRATIC EQUATIO.
The general form of the Quadratic equation is ax2+bx+c=0.
2 -
- b + b 4ac
R1 =
2a
2 -
- b - b 4ac
R2 =
2a
And these are two roots of the equation.
The term (b2-4ac) in the solution to the root is called the discriminant of the root. Basically the roots
can be real or imaginary in nature. If the roots are real in nature then they can be either real and distinct,
or both of them can be equal. If they are imaginary the roots exists in complex conjugates.
The problem of identifying the nature of the roots is achieved in checking the nature of the discriminant.
The nature of the discriminant reflects the nature of the solution of the quadratic equation.
If the discriminant is negative then the roots will be of imaginary in nature.
i.e if (b2-4ac) = some –ve value.
And these are two roots of the equation.
The term (b2-4ac) in the solution to the root is called the discriminant of the root. Basically the roots
can be real or imaginary in nature. If the roots are real in nature then they can be either real and distinct,
or both of them can be equal. If they are imaginary the roots exists in complex conjugates.
The problem of identifying the nature of the roots is achieved in checking the nature of the discriminant.
The nature of the discriminant reflects the nature of the solution of the quadratic equation.
If the discriminant is negative then the roots will be of imaginary in nature.
i.e if (b2-4ac) = some –ve value.
Then,
b2 - 4ac is complex in nature, because square root of any negative number always results in
an imaginary result.
BSIT 41 Algorithms
Now the roots R1 and R2 has imaginary parts and hence they are imaginary in nature.
Now the other possibility is that the roots being real. For that to happen the disciminant (b2-4ac) = 0.
If it is equal to zero than the discriminant vanishes and hence the roots are real and equal,which are R1
= R2 = -b/2a.
In case (b2-4ac) > 0 , then the roots are real and distinct. The algorithm to find the solution to a
quadratic equation is given below.
Algorithm: Quadratic_solver
Input : a,b,c the co-efficients of the Quadratic Equation
Output : The two roots of the Equation
Method
disc = ((b*b) –(4*a*c))
if (disc = 0)
display ‘roots are real and equal’
r1 = -b/2a
r2 = -b/2a
display r1
display r2
else
if(disc>0)
display ‘ roots are real and distinct’
r1 = (-b+sqrt(disc))/2a
r2 = (-b-sqrt(disc))/2a
else
display ‘roots are complex’
display ‘real part’,-b/2a
Chapter 3 - Some Simple Algorithms
display ‘imaginary part’, sqrt(absolute_value_of(disc))
display ‘the two root exists in conjugates’
end_if
Algorithm ends
3.5 CHECKING FOR PRIM.
Prime number checking has been a very interesting problem for computer science for a very long
time. A prime number is divisible by either 1 or itself and not by any other number. Prime number checking
is technically called as Primality testing.
First Approac.
Here we keep dividing a number from 2 to half the value of that number. For ex: if 47 is the number
under consideration for primality testing then we would divide 47 form 2 to 47/2(23.5 approx. 24) and
check whether any number in this interval performs a division operation on 47 such that there is no
remainder. If so then the given number is not prime. But in the case of 47 no number between 2 and 24
performs such sort of division operation and hence it is declared as a prime number.
Algorithm: Primality_Testing (First approach)
Input: n , number
flag, test condition
Output: flag updated
Method
flag = 0
for(i=2 to n/2 in steps of +1 and flag = 0)
if( n % i = 0) // n mod i
flag = 1
end-if
end-for
if(flag = 0)
BSIT 41 Algorithms
display ‘Number is prime’
else
display ‘Number is not prime’
end_if
Algorithm ends
Second Approac.
It is proved in number theory that instead of setting the interval of divisor to n/2 we can simply set that
to square root of the given number under consideration of Primality and it would work perfectly fine as the
previous algorithm. Note that in this algorithm we achieve the same result with lesser number of operations
because we reduce the size of the interval.
Algorithm: Primality_Testing (Second approach)
Input : n , number
flag, test condition
Output : flag updated
Method
flag = 0
for(i=2 to square_root(n) in steps of +1 and flag = 0)
if( n % i = 0) // n mod i
flag = 1
end_if
end-for
if(flag = 0)
display ‘Number is prime’
else
display ‘Number is not prime’
end_if
Algorithm ends
Chapter 3 - Some Simple Algorithms
3.6 FACTORIAL OF A NUMBE.
Finding Factorial of a given number is another interesting problem. Mathematically represented as n! .
For ex: 5! = 5*4*3*2*1.
Not to forget that 1! = 1 and 0! = 1.
We can now generalize the factorial of a given number which is any thing other than zero and one as
the product of all the numbers ranging from given number to 1.
i.e n! = n * (n – 1) * (n – 2 ) * . . . *1
Algorithm : Factorial
Input : n
Output : Factorial of n
Method
fact = 1
for i = n to 1 in steps of –1 do
fact = fact*i
end_for
display ‘factorial = ‘,fact
Algorithm ends
In the above algorithm we have implemented the logic of the equation
n! = n * (n – 1) * (n – 2 ) * . . . *1.
The same can be achieved by the following algorithm which follows incremental steps rather than
decremental steps of the given algorithm.
Algorithm : Factorial
Input : n
Output : Factorial of n
BSIT 41 Algorithms
Method
fact = 1
for i = 1 to n in steps of 1 do
fact = fact*i
end_for
display ‘factorial = ‘,fact
Algorithm ends
3.7 TO GENERATE FIBONACCI SERIE.
The Fibonacci Series is as follows 0 , 1 , 1 , 2 , 3 , 5 , 8 , …
The property of this series is that any given element in the series after the third element is the sum of
its first and second predecessor. For example, consider 8. Its first and second predecessors are 5 and 3.
Therefore, 5 + 3 = 8. Consider 3. Its first and second predecessors are 2 and 1. 2 + 1 = 3. The property
of Fibonacci series holds.
The following is the algorithm to generate the Fibonacci series up to a given number of elements.
Algorithm : Fibonacci_Series
Input : n, the number of elements in the series
Output : fibonacci series upto the nth element
Method
a = -1
b = 1
for(i=1 to n in steps of +1 do)
c = a + b
display ‘c’
a = b
b = c
end_for
Algorithm ends
Chapter 3 - Some Simple Algorithms
3.8 SUM OF .N. NUMBERS AND AVERAG.
Consider the addition of five numbers 12 , 15 , 10 , 5 and 1.
Initially add 12 and 15 => 12 +15 = 27
Subsequently add 10 to 27 => 10 + 27 = 37
Subsequently add 5 to 37 => 37 + 5 = 42
And Finally add 1 to 42 => 42 + 1 = 43
Which is nothing but 12 + 15 + 10 + 5 + 1 = 43.
The following logic of adding two successive elements and iterating the same process over the other
remaining elements is described in the algorithm given below.
The resulting sum divided by the number of elements yields the average of the domain of input set.
Algorithm : Sum_and_Average
Input : n , number of elements
a(n) , array of n elements
Output : Sum and Average of ‘n’ array elements
Method
Display ‘Enter the number of elements ‘
Accept ‘n’
Display ‘ Enter the elements one by one’
For (i = 1 to n in steps of +1 do)
Accept a(i)
end_for
sum = 0
For (i = 1 to n in steps of +1 do)
sum = sum + a(i)
end_for
Display ‘Sum = ’,sum
Display ‘Average =’,sum/n
Algorithm ends
BSIT 41 Algorithms
3.9 TO ADD TWO MATRICE.
Consider
11a12a 13a
21a 22a 23a
31a 32a 33a
+
11b12b 13b 1111 ba + 1212 ba + 1313 ba +
21b 22b 23b = 2121 ba + 2222 ba + 2323 ba +
31b 32b 33b 3131 ba + 3232 ba + 3333 ba +
The above example is of matrix addition. Matrix addition is possible iff orders of the two matrices are
same. Respective matrix elements are added together in a third matrix and the results are thus obtained.
The procedure is thus described below.
The two Matrices has to read initially in a two dimensional array and then the respective row element
and column elements in the Matrices have to be added to get a third matrix, which leads to the realization
of Matrix addition.
Algorithm : Matrix Addition
Input : n , order of the matrices
a(n,n),b(n,n) the two input matrices
Output : c(n,n) the resultant Sum matrix
Method
{
Accept ‘n’
for(i = 1 to n in steps + 1 do)
for(j= 1 to n in steps of + 1do)
accept a(i,j)
end_for
end_for
for(i = 1 to n in steps + 1 do)
for(j= 1 to n in steps of + 1do)
accept b(i,j)
end_for
end_for
Chapter 3 - Some Simple Algorithms
for(i = 1 to n in steps + 1 do)
for(j= 1 to n in steps of + 1do)
c(i,j) = a(i,j) + b(i,j)
end_for
end_for
for(i = 1 to n in steps + 1 do)
for(j= 1 to n in steps of + 1do)
display c(i,j)
end_for
end_for
Algorithm ends
SUMMAR.
In this chapter some simple problems, the problem solving concepts and the concept of designing
algorithms for the problems has been presented. For the ease of students some simple problems are
considered and the algorithms are developed. The students are expected to implement all the above
explained algorithms and experience the way they work.
EXERCIS.
1.
Design and Develop algorithms for multiplying n integers.
Hint: Follow the algorithm to add n numbers given in the text
2.
Design and develop algorithm for finding the middle element in the three numbers.
3.
Develop algorithm to find the number of Permutations and Combinations for a given n and r
4.
Design a algorithm to generate all prime numbers within the limits l1 and l2.
5.
Design an algorithm to find the reverse of a number.
6.
A number if said to be a palindrome if the reverse of a number is same as the original. Design a algorithm to
check whether a number is palindrome or not
6.
Design a algorithm to check whether a given string is palindrome or not
7.
Implement all the devised algorithms and also the algorithms discussed in the chapter.