---

An algorithm is a clearly specified set of instructions a computer follows to solve a problem. Once an algorithm is given for a problem and determined to be correct, the next step is to determine the number of resources, such as time and space, that the algorithm will require. This step is called algorithm analysis. An algorithm that requires several gigabytes of main memory is not useful for most current machines, even if it is completely correct.

This tutorial describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 17 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored.

Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they solve have become larger and more complex, thus requiring the development of more intricate programs to solve the problems. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency.

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing. It is formally a type of effective method in which a list of well-defined instructions for completing a task will, when given an initial state, proceed through a well-defined series of successive states, eventually terminating in an end-state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as probabilistic algorithms, incorporate randomness.
A step-by-step method of solving a problem or making decisions, as in making a diagnosis. An established mechanical procedure for solving certain mathematical problems.

In programming, algorithm are the set of well defined instruction in sequence to solve a program. An algorithm should always have a clear stopping point.

The characteristics of a good algorithm are:

1.  Finiteness: An algorithm must always terminate after a finite number of steps.
2. Definiteness: Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
3. Input: An algorithm has zero or more inputs, i.e, quantities which are given to it initially before the algorithm begins.
4. Output: An algorithm has one or more outputs i.e, quantities which have a specified relation to the inputs.
5. Effectiveness: An algorithm is also generally expected to be effective. This means that all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time.

For those who are lazy

1. Precision – the steps are precisely stated(defined).
2. Uniqueness – results of each step are uniquely defined and only depend on the input and the result of the preceding steps.
3. Finiteness – the algorithm stops after a finite number of instructions are executed.
4. Input – the algorithm receives input.
5. Output – the algorithm produces output.
6. Generality – the algorithm applies to a set of inputs.

Examples Of Algorithms In Programming

Write an algorithm to add two numbers entered by user.

Step 1: Start
Step 2: Declare variables num1, num2 and sum. 
Step 3: Read values num1 and num2. 
Step 4: Add num1 and num2 and assign the result to sum.
        sum?num1+num2 
Step 5: Display sum 
Step 6: Stop

Program implementation from algorithm

#include<stdio.h>
void main()
{
int num1, num2, sum;
num1 = 21;
num2 = 22; 
sum= num1 + num2;
printf("Result= %d \n",sum);
}

Output

Result= 43
Press any key to continue . . .

Write an algorithm to find the largest among three different numbers entered by user.

Step 1: Start
Step 2: Declare variables a,b and c.
Step 3: Read variables a,b and c.
Step 4: If a>b
           If a>c
              Display a is the largest number.
           Else
              Display c is the largest number.
        Else
           If b>c
              Display b is the largest number.
           Else
              Display c is the greatest number.  
Step 5: Stop

Program implementation from algorithm

#include<stdio.h>
void main()
{
int a, b, c;
a = 2, b = 3, c = 4;
if(a>b){
	if(a>c)
	{
    printf("a is larhest Number \n");
	}
	else{
	printf("c is largest Number \n");
	}
  }
  else
  {
  	if(b>c)
	{
    printf("b is larhest Number \n");
	}
	else{
	printf("C is largest Number \n");
	}
  
  }
  
}

Output

C is largest Number
Press any key to continue . . .

Complexity of Algorithm

It is very convenient to classify algorithms based on the relative amount of time or relative amount of space they require and specify the growth of time /space requirements as a function of the input size. Thus, we have the notions of:

1. Time Complexity: Running time of the program as a function of the size of input

2.  Space Complexity: Amount of computer memory required during the program execution, as a function of the input size.

Space Complexity

Its the amount of memory space required by the algorithm, during the course of its execution. Space complexity must be taken seriously for multi-user systems and in situations where limited memory is available.

An algorithm generally requires space for following components :

• Instruction Space : Its the space required to store the executable version of the program. This space is fixed, but varies depending upon the number of lines of code in the program.
• Data Space : Its the space required to store all the constants and variables value.
• Environment Space : Its the space required to store the environment information needed to resume the suspended function.

Time Complexity

Time Complexity is a way to represent the amount of time needed by the program to run till its completion. We will study this in details in later sections.

---