Introduction to Algorithm

What is an algorithm?

An algorithm is a step by step procedure to solve a problem. In normal language, algorithm is defined as a sequence of statements which are used to perform a task. In computer science, an algorithm can be defined as follows...

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which forms a program. This program is executed by computer to produce solution. Here, program takes required data as input, processes data according to the program instructions and finally produces result as shown in the following picture.

Algorithm Specifications

Every algorithm must satisfy the following specifications...

  1. Input - Every algorithm must take zero or more number of input values from external.
  2. Output - Every algorithm must produce an output as result.
  3. Definiteness - Every statement/instruction in an algorithm must be clear and unambiguous (only one interpretation)
  4. Finiteness - For all different cases, the algorithm must produce result within a finite number of steps.
  5. Effectiveness - Every instruction must be basic enough to be carried out and it also must be feasible.

Example of Algorithm

Let us consider the following problem for finding the largest value in a given list of values.

Problem Statement : Find the largest number in the given list of numbers?
Input : A list of positive integer numbers. (List must contain at least one number).
Output : The largest number in the given list of positive integer numbers.

Consider the given list of numbers as 'L' (input), and the largest number as 'max' (Output).

Algorithm

  • Step 1: Define a variable 'max' and initialize with '0'.
  • Step 2: Compare first number (say 'x') in the list 'L' with 'max', if 'x' is larger than 'max', set 'max' to 'x'.
  • Step 3: Repeat step 2 for all numbers in the list 'L'.
  • Step 4: Display the value of 'max' as a result.

Code in C Programming


int findMax(L)
{
   int max = 0,i;
   for(i=0; i < listSize; i++)
   {
      if(L[i] > max)
         max = L[i];
   }
   return max;
}

Recursive Algorithm

In computer science, all algorithms are implemented with programming language functions. We can view a function as something that is invoked (called) by another function. It executes its code and then returns control to the calling function. Here, a function can call themselves (by itself) or it may call another function which again call same function inside it.

The function which calls by itself is called as Direct Recursive function (or Recursive function)

A recursive algorithm can also be defined as follows...

The function which calls a function and that function calls its called function is called Indirect Recursive function (or Recursive function)

Most of the computer science students think that recursive is a technique useful for only a few special problems like computing factorials, Ackermann's function etc., This is unfortunate because any function implemented using assignment or if-else or while or looping statements can also be implemented using recursive functions. This recursive function is very easier to understand when compared to its iterative counterpart.