Question

What is an algorithm?

Answer 1

Algorithm is a step-by-step procedure for calculations.

For example:

Euclid’s Division Algorithm: In order to compute the HCF of two positive integers say a and b, with a > b by using Euclid’s algorithm, we follow the following steps:

STEP I : Apply Euclid’s Division Lemma to a and b and obtain whole numbers q and `r_1`, such that `a= bq_1+r_1`,` 0≤ r_1 < b`

STEP II: If `r_1 =0 `, b is the HCF of a and b.

STEP III: If  `r_1 `, apply Euclid’s division lemma to b and `r_1` and obtain whole numbers  `q_1` and  `r_2`,such that  `b= q_1r_1+r_2`

STEP IV: If  `r_2=0`, then  `r_1` is the HCF of a and b.

STEP V: If  `r_2=0 `, then apply Euclid’s division lemma to `r_1` and `r_2` and continue the above process till the remainder `r_n` is zero. The divisor at this stage i.e; `r_n-1` , or the non-zero remainder at the previous stage is the HCF of a and b.