Why Analysis of algorithms ?

Why Analysis of algorithms :

        An algorithm is a step by step procedure i.e. a set of instructions to solve the given problem. For a problem there can be many algorithms to solve it. But how to find the best algorithm among those?. Analysis of algorithms helps in determining the solution for it.

What does it mean?

        For example if a person wants to travel from one place A to another place B, there can be many routes to reach from A to B. Depending on the availability and convenience we can choose the best route in terms of short route (if we want to reach fast), Highway (Even though it is longer, but for convenience) etc.

        Similarly in Computer Science, there can be many algorithms for a same problem. Analysis of algorithms helps us in determining which of them is efficient in terms of space (memory) and running time by comparing the algorithms. But how to compare algorithms ?

How to compare algorithms ?

       Running time is best measure for comparing the algorithms. It is the process of determining the processing time increases as the size of input size (problem) increases. Input size may vary depending on the type of problems. In general we encounter the following types of inputs.

1)  Size of array

2)  No of elements in the matrix

3)  Polynomial degree

4)  Vertices and edges in a graph

     In general, the running time of a algorithm is expressed as a function of input size(n) i.e. f(n) and compare these functions corresponding with their running times. This is independent of machine time, processor, programme style (no of statements) etc.

Types of analysis :

        To analyse the algorithm, we need to represent the algorithm with multiple expressions: one for the case where it takes less time and the other for the case where it takes more time. The first case is called as Best case and the second case is called as Worst case for that algorithm. There are three types of analysis:

1)  Best case

2)  Average case

3)  Worst case

For a given algorithm, we can represent the best, worst, average cases in the form of expressions. For example

Let f(n) be the function represents the given algorithm and n is the input size,

                f(n) = n² + n + 100          ; for worst case

                f(n) = 5n + 200                ; for best case

The expressions defines the input for which the algorithm takes the less or average time (or memory). If both best and worst cases, points to one expression then that expression can be represented with average case.

                f(n) = 10n + 50                ; for best and worst case

then f(n) can be represented for average case.

                f(n) = 10n + 50                ; for average case

Read More

TYPEDEF - create variables by your name

Typedef:

          Typedef is a keyword used to assign new names to existing data types. This is same like defining alias for the commands.

typedef  existing_name alias_name;

After this statement, instead of existing_name we can use alias_name.

If we look at an example

          typedef int aj;

aj i , j;

The above statement define a term  aj  for an int type. Now this  aj  identifier can be used to define int type variables. This is also equal to int i , j;

          typedef unsigned long  int  ajj;

        ajj  i, j ;

After this type definition, the identifier ajj can be used as an abbreviation for the type unsigned long int.

Using typedef with structures :

You can use typedef to give a name to user defined data type as well. For example you can use typedef with structure to define a new data type and then use that data type to define structure variables directly as follows:

typedef struct book

{

           int x;

           float y;

           char c[10];

} Book;

         

         Here Book is the structure_variable name and book is tag_name. After this definition, we can create structure variables with Book word instead of struct book.

For example:

 #include <stdio.h>

 #include <string.h>

 typedef struct Books

 {

          char title[20];  

          int pages;

 } Book;

int main( )

           {

           Book  book;

           strcpy (book.title, "C Programme");

                     book.pages = 230;

                     printf( "Book title : %s\n", book.title);

           printf( "no of pages : %d\n", book.pages);

                     return 0;

           }

In the above program we have defined Book book instead of struct books book.

·       Typedef can be used for pointers also.

                    typedef int *x , y;

By this definition, we can use x for defining pointer variables and y can be used for integer variables.

#include <stdio.h>

 #include <string.h>

int main( )

     {

              typedef int  *x , y;

              y  a = 10;

              x  b;

              b = &a;

              printf("%d",a);              //output : 10 10

              printf("%d",*b);

               return 0;

     }

Read More