Few words about algorithm on data structure in C Programming

Before we proceed in data structure through c, First of all we must have some knowledge about algorithm. Algorithm is the back bone of programing.

 An Algorithm is a precise specification of a sequence of instructions to be carried out in order to solve a given problem.Each instruction tells what task to be performed.

Suppose we have an array value of int type and the size of the array is n.values are to be inserted in the array and then we have to find the maximum value in the array and it's position in the array. An algorithm for such program would be like :

Step 1 : create variables 'k' 'max' and 'i'

['k' for holding the position of the maximum value , 'max' will hold the maximum value and 'i' is the loop control variable]

Step 2: create an array named 'value' of size 'n'

Step 3: i=0

[initialization of loop control variable]

Step 4: if 'i' is less than 'n' then [condition checking] go on executing Step 5 to Step 8 otherwise go to step 9. 

Step 5: Take a value from the user and store it in the position 'i' of the array value .

Step 6: if 'i' is 0 then

max=value[i]

k=i

Otherwise if value[i] is greater than max then

max=value[i]

k=i

Step 7: i=i+1 [Reinitialization of loop control variable 'i']

[ input is completed]

Step 8: Go to Step 4.

Step 9: display 'max' and 'k'

Step 10: stop

Technical analysis of the algorithm

In the first two steps [Step 1 and Step 2] three variables and an integer type array is created.

In Step 3 , the loop control variable 'i' is initialized with 0.

In Step 4 , condition of the loop is checked and if the condition if found true then the execution of the loop body starts [Step 5 to Step 8].In Step 5 the program will take a value from the user and it will be stored in value[i].In Step 6 the program will assign the current value of the array ( value[i] ) to the variable max if the value of i is 0.Also the value of 'i' will be stored on k. If 'i' is not equal to zero then a conditioned is checked whether the current value of the array is greater than max and if it is true then the current value of the array is assigned on max (max=value[i] ) and the value of 'i' is assigned on k.

In Step 7 , the value of the loop control variable 'i' is incremented by 1.

From Step 8 the control is redirected to Step 4.

When the condition becomes false , control will skip all the steps between Step 5 and Step 8 and Step 9 will be executed.

Lastly Step 10 will be executed.

An Algorithm is defined as a finite sequence of instructions which has the following properties. 

A number of quantities are provided to an Algorithm before the Algorithm begins.These quantities are called inputs which are processed in the Algorithm.

The processing instructions in an Algorithm must be precise and unambiguous.

Each instruction must be sufficiently basic so that a person with a paper and pencil can carry out it in finite time.

An algorithm must have one or more output.

After writing an algorithm one has to analyze it.The first type of analysis is of the correctness of an algorithm.Reading the algorithm for logical correctness , testing the algorithm on some data can do this testing.Next type of analysis is the simplicity of the algorithm.The algorithm must be as simple as possible and straightforward. However , the simplest and most straightforward algorithm may not be perfect all the time.Sometimes , the simplest approach may require much computer time and space. The programmer must be aware of several interrelated efficiency considerations while designing an algorithm.Three of the most important considerations are:-

1. The length of time that must be spend by the programmer in coding a program.

2. The amount of machine time required for running the program.

3. The amount of space required for that program.

If a particular program will be executed only once and there is sufficient machine time and space , it would not be wise for a programmer to spend several days investigating the best algorithm for saving machine time and space.However programming time is never a valid excuse for a incorrect program.A program that will run only once may be able to afford the luxury of an inefficient technique , but it cannot afford an incorrect one. We know that functions save memory space as all the calls to the function cause the same code to be executed , the function body need not to be duplicated in memory. But this will cost the time efficiency.Bacause each function call generates a jump to the function body , then after executing the function body again a back jump to the instructions following the call.If the function returns any value then the return value must also be dealt with.All these processes takes a lot of time and slow down the program.So to save space , time efficiency is sacrificed here.If the function body is not large ( statements within the function body is not more ) then it is advisible to use statements as simple codes inside the program rather than using them in a function .This will save the time.Large sections of repeated codes are generally better off as functions.Here the saving of memory space at the sacrifice of execution speed is worthy.By making a short section code into a function will result in little save in memory space but will impose time penalty.

So there are two efficiency considerations - time and space.Often programmers optimized one of these at the cost of the other.Let's see some relation between time and space efficiency.

It is generally not possible to find the exact machine time required by analyzing the algorithm.To execute an algorithm of size n we do not concern ourselves with the actual time units.Rather we relate the machine time with the size of the program. The exact amount of time depends on the machine itself and the amount of input data. An algorithm that finds the maximum value among 1000 values must take more machine time than doing the same work with 100 values.

Often we measure the time efficiency of a program by the number of critical operations performed.Critical operations are those which takes much time compared to other operations.Examples of such critical operations are comparisions among values.A comparison takes much more time than a simple increment operation of a loop control variable.Also the number of critical operations are proportional to the simple operations in a program.For this reason , the number of critical operations rather than the size of a program is a measure of the time efficiency of an algorithm.