UNIT 1

ALGORITHM

An algorithm  is the sequence of and ambiguous instructions for solving a problem. i.e. for obtaining a required output for any legitimate input in a finite amount of time.

Characteristics of algorithm

• The  non-ambiguity requirement for each step of an algorithm can be compromised.

• The range of inputs for which an algorithm who works has to be specified carefully.

• The same algorithm can be represented in several different ways.

• There may exist several algorithms for solving the same problem.

• Algorithms for the same problem can we based on very different ideas and can solve the problem with dramatically different speeds.

Example:  The greatest common divisor of non-negative, not both zero  integers m and n,  denoted ged(m,n),  is defined as the largest integer that divides both m and n evenly, i.e with with a reminder of zero

Ex: 1. Euclids algorithm:

for gcd (60,24) = gcd(24,12) = gcd(12,0)=12

Euclid algorithm, for computing gcd(24,12) = gcd(12,0) = 12

Euclids algorithm for computing gcd (m,n)

Step 1: if n = 0,  return the value of M as the answer and stop; otherwise, process to step 2.

Step 2: divide m by n(m/n)  and assign the value of the reminder to r.

Step 3: Assign the value of n to m  and the value of r to n.

Go to Step 1