Codes-N-Tricks

Firefox 7.0 is out : A good news to the FF-lovers

noreply@blogger.com (Soham) — Thu, 29 Sep 2011 10:05:00 +0530

Firefox has been the favourite browser of many users like me in spite of the fastest growth of Chrome. Many users move from FF to Chrome for its speed and light-weight.
Now, as a strategy to defend that, I've seen that FF is continuously releasing new versions since end of June . Through this releases, FF has become more light-weight browser than its previous versions. Some may complain that FF is copying Chrome. but I would say what do u expect guys. Light-weighting should come in either way. So, here it's coming in FF.
Now for it's latest release, I have experienced today that FF has improved its speed a lot in it 7.0 version.

Main Features of FF 7.0 :

Firefox 7.0 claims to be use 20% to 30% less memory than its predecessors. That means the browser runs a lot smoothly even if many tabs are open.
It supports faster HTML5 animations along with many improvements to the speed of the browser.
It has news tools which will help developers to create faster web apps that run on Firefox.

http://"-part

http://www.mozilla.org/en-US/firefox/fx/

Linear Sorts–Counting, Radix–C Programming

noreply@blogger.com (Soham) — Tue, 24 May 2011 08:14:00 +0530

I have implemented radix and counting sorts in this program where i take inputs as the number of the numbers you want to sort and the number of digits(at max).

Then the numbers, which will be sorted, are taken as random and sorted according to the corresponding algorithm.

Take a look at the C-Code.

Radix and Counting Sort
 #include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
 
void count_sort(int num[],int sortd[],int no,int rng);
void show(int inp[],int no);
void radixsort(int a[],int n,int d);
 
int cnt_rdx=0,cnt_cntsrt=0;
 
int main()
{
    int no,i,digt,rng;
    int *num,*cnt_srt_num;
    
    printf("\nHow many Numbers you want to sort:- ");
    scanf("%d",&no);
    printf("\nWhat is the Number of Digits(at max) in a number:- ");
    scanf("%d",&digt);
    rng=pow(10,digt);
 
    num=(int *)calloc(no,sizeof(int));
    cnt_srt_num=(int *)calloc(no,sizeof(int));
    srand(time(0));
    for(i=0;i<no;i++)
        num[i]=rand()%rng;
    printf("\nThe Unsorted Numbers are:");
    show(num,no);
    count_sort(num,cnt_srt_num,no,pow(10,digt));
    printf("\nThe Counting Sorted Numbers are:");
    show(cnt_srt_num,no);
    printf("Time Complexity : %d\n",cnt_rdx);
    radixsort(num,no,digt);
    printf("\nThe Radix Sorted Numbers are:");
    show(num,no);
    printf("Time Complexity : %d\n",cnt_cntsrt);
    getch();
    return 0;
}
 
void count_sort(int num[],int sortd[],int no,int rng)
{
    int i;
    int *indx_num;
 
    indx_num=(int *)calloc(rng,sizeof(int));
    for(i=0;i<no;i++)
        indx_num[num[i]]++;
    for(i=1;i<rng;i++)
        indx_num[i]=indx_num[i]+indx_num[i-1];
    for(i=no-1;i>=0;i--)
    {
        cnt_rdx++;
        sortd[indx_num[num[i]]-1]=num[i];
        indx_num[num[i]]--;
    }
}
 
void show(int inp[],int no)
{
    int i;
    for(i=0;i<no;i++)
        printf("  %d",inp[i]);
    printf("\n");
}
 
void radixsort(int a[],int n,int d)
{
    int end[10],start[10],first,p,q,exp,k,i,y,j;
    struct nd
    {
        int info;
        int next;
    };
 
    struct nd *node;
    node=(struct nd *)malloc(n*sizeof(struct nd)); 
 
 
    for(i=0;i<n-1;i++)
 
    {
        node[i].info=a[i];
        node[i].next=i+1;
    }
    node[n-1].info=a[n-1];
    node[n-1].next=-1;
    first=0;
 
    for(k=1;k<=d;k++)      //consider 3 digit number
    {
        for(i=0;i<10;i++)
        {
            start[i]=-1;
            end[i]=-1;
        }
 
    while(first!=-1)
    {
        cnt_cntsrt++;
        p=first;
        first=node[first].next;
        y=node[p].info;
        exp=pow(10,k-1);
        j=(y/exp)%10;
        q=end[j];
        if(q==-1)
            start[j]=p;
        else
            node[q].next=p;
        end[j]=p;
    }
    for(j=0;j<10&&start[j]==-1;j++)
    ;
    first=start[j];
    while(j<=9)
    {
        for(i=j+1;i<10&&start[i]==-1;i++)
        ;
        if(i<=9)
        {
            p=i;
            node[end[j]].next=start[i];
        }
        j=i;
    }
    node[end[p]].next=-1;
}
//copy into original array
for(i=0;i<n;i++)
{
    a[i]=node[first].info;
    first=node[first].next;
}
 
/*printf("Sorted Data:\n");
for(i=0;i<n;i++)
    printf("%d.  %d\n",i+1,a[i]);*/
}
 
/*void radixsort(int a[],int n)
{
int i,b[MAX],m=0,exp=1;
int bucket[10]={0};
for(i=0;i<n;i++)
{
if(a[i]>m)
m=a[i];
}
 
while(m/exp>0)
{
 
for(i=0;i<n;i++)
bucket[a[i]/exp%10]++;
for(i=1;i<10;i++)
bucket[i]+=bucket[i-1];
for(i=n-1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i];
for(i=0;i<n;i++)
a[i]=b[i];
exp*=10;
 
#ifdef SHOWPASS
printf("\nPASS : ");
print(a,n);
#endif
}
}*/
 

Discussions will be carried out later,if needed. Any suggestions are highly solicited.

Thank You.

Google CodeJam 2011–Magicka Problem Solved–C Programming

noreply@blogger.com (Soham) — Sun, 8 May 2011 19:50:00 +0530

Problem is Magicka on Google CodeJam 2011.
I have solved it in a iterative way.

Look at it.

Magicka Problem - CodeJam'2011
 #include<stdio.h>
#include<string.h>
 
char combo[36][4],opps[28][3];
int c,d;
char base[]="QWERASDF";
 
int search_combo(char buff[],char *tmp);
int search_opps(char inp[]);
 
char* strReverse(char* str)
{
     int i=0,j=0;
     while(str[j] != '\0')
     j++;
     j--;
     while(i<=j)
     {
                 char t = str[i];
                 str[i++] = str[j];
                 str[j--] = t;
     }
     return str;
}
 
void code_it(char inp[],char op[])
{
     int i,j;
     op[0]='[';op[1]='\0';
     for(i=0,j=1;i<strlen(inp);i++)
     {
          if(i) strcat(op,(char *)", ");
          sprintf(op,"%s%c",op,inp[i]);
     }
     strcat(op,(char *)"]");
}
 
int main()
{
    int t,cnt=0,n,i,j,k,l;
    char elm_list[101],op[101],otpt[700],buffer[3],tmp,tm_op[101];
    
    //freopen("B-large-practice.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    scanf("%d",&t);
    while(t--)
    {
              scanf("%d",&c);
              for(i=0;i<c;i++)
              {
                   scanf("%s",combo[i]);
              }
              scanf("%d",&d);
              for(i=0;i<d;i++)
              {
                   scanf("%s",opps[i]);
              }
              scanf("%d %s",&n,elm_list);
                            
              for(i=0,j=0;i<n;i++)
              {
                   op[j]=elm_list[i];
                   if(j>0)
                   {
                        buffer[0]=op[j-1];buffer[1]=op[j];buffer[2]='\0';
                        if(search_combo(buffer,&tmp)==1)
                             op[--j]=tmp;    
                   }
                   op[++j]='\0';
                   if(search_opps(op)==1)
                   {
                        j=0;
                        op[j]='\0';
                   }
              }
              code_it(op,otpt);
              printf("Case #%d: %s\n",++cnt,otpt);
    }
}
 
int search_combo(char buff[],char *tmp)
{
    int i,j,fl=0;
    char tm[3];
    tm[2]='\0';
    for(i=0;i<c;i++)
    {
         for(j=0;j<2;j++) tm[j]=combo[i][j];
         if(strcmp(tm,buff)==0||strcmp(strReverse(tm),buff)==0)
         {
              *tmp=combo[i][2];
              fl=1;
              break;
         }
    }
    return fl;
}
 
int search_opps(char inp[])
{
     int k,l,i,j,fl=0;
     char tmp[100],buff[3];
     buff[2]='\0';tmp[0]='\0';
     for(k=0,l=0;k<strlen(inp);k++)
     {
          if(strchr(tmp,inp[k])==NULL)
              if(strchr(base,inp[k])!=NULL)
                   tmp[l++]=inp[k];
          tmp[l]='\0';
     }
     
     if(strlen(tmp)<1) return 0;
     for (i=0;i<strlen(tmp)-1;i++)
     {
          for (j=i+1;j<strlen(tmp);j++)
          {
                buff[0]=tmp[i];buff[1]=tmp[j];
                for(k=0;k<d;k++)
                {
                     if(strcmp(opps[k],buff)==0||strcmp(opps[k],strReverse(buff))==0)
                     {
                          fl=1;
                          break;
                     }
                }
                if(fl==1) break;
          }
          if(fl==1) break;
     }
     return fl;
}
 

It’s slightly big.I think I can reduce that.Your suggestions are highly solicited.

Discussion will be carried out if needed.

Google CodeJam 2011–Bot Trust Solved–C Programming

noreply@blogger.com (Soham) — Sun, 8 May 2011 13:05:00 +0530

Problem is Bot Trust on Google CodeJam 2011.
I have solved the problem in C-language. The algorithm is pretty simple. If anyone want to know in details,please let me know by commenting on this post, I’ll post the details.

Here’s the C-Code:

Bot Trust Problem
#include<stdio.h>
#include<string.h>
int search_pos(char seq[],int rbt,int indx)
//Searches the next position of 'rbt' Robot
//after 'index' in the sequence
{
    int i,val=-1;char robot;
    if(rbt==1) robot='O'; else robot='B';
    for(i=indx;seq[i]!='\0';i++)
        if(robot==seq[i])
        {
             val=i;
             break;
        }
    return val;
}

int main()
{
    int i,t,n,sq,timer,cnt=0,bt[10],inr;
    char r[10];
    int o_frst,b_frst,o_cur,b_cur,o_targt,b_targt;
    
    scanf("%d",&t);
    
    while(t--)
    {
              timer=0,inr=0;
              o_cur=1,b_cur=1,o_targt=1,b_targt=1;    
              scanf("%d",&n);
              for(i=0;i<n;i++)
              {
                   scanf(" %c %d",&r[i],&bt[i]);
              }
              
              r[i]='\0';bt[i]='\0';
              o_frst=search_pos(r,1,0);
              b_frst=search_pos(r,2,0);
              if(o_frst!=-1) o_targt=bt[o_frst];
              if(b_frst!=-1) b_targt=bt[b_frst];
              
              for(sq=0;sq<strlen(r);)
              {
                   //For Orange Robot
                   if(o_targt>o_cur)
                        o_cur++;
                   else if(o_targt<o_cur)
                        o_cur--;
                   else if(o_targt==o_cur)
                   {
                             if(r[sq]!='B')
                             {
                                  o_targt=bt[search_pos(r,1,sq+1)];
                                  inr=1;
                             }
                   }
                   //For Blue Robot
                   if(b_targt>b_cur)
                        b_cur++;
                   else if(b_targt<b_cur)
                        b_cur--;
                   else if(b_targt==b_cur)
                   {
                             if(r[sq]!='O')
                             {
                                  b_targt=bt[search_pos(r,2,sq+1)];
                                  inr=1;
                             }
                   } 
                   timer++; 
                   
                   if(inr) sq++;//checking if the current button is pushed or not
                   inr=0;                          
              }
              printf("Case #%d: %d\n",++cnt,timer);
    }
    getchar();
}

Thank you.

Saddle Point Algorithm Clarification

noreply@blogger.com (Soham) — Sun, 10 Oct 2010 21:57:00 +0530

Now we will broadly discuss the Algorithm and C-code.

What is Saddle Point of a Matrix?
Saddle Point in a Matrix is the point which has the highest value in the respective row and lowest value in the respective column or vice-versa( i.e Lowest in a row and highest in a column).

The code here first takes the Matrix as input.Then shows the matrix to the user.

Then it evaluates the saddle points.

Evaluation:

First we evaluate the maximum and minimum of a row. If they are not equal that means they may be a candidate for a saddle point. But if they are equal that means all the elements in that row are equal. So we don’t consider them as a candidate for a saddle point. “eq” variable is used in this case for checking equality.

Let’s say they are not equal. Then we take maximum of each column and checks with the Minimum element of the row that was evaluated above.If they are the same, then that is shown as a saddle point.

Same case is taken for Maximum in a row and minimum in a column.

“cnt” variable is used to count the number of saddle points in the matrix.If the variable is 0 then there are no saddle points.

Function Definition:

rw(r,dec)

Here “r” stands for corresponding row. The “dec” variable is used to indicate if we are evaluating maximum or minimum. If dec=0,then we are claiming for minimum and if dec=1, then we are claiming for maximum.

col(r,dec)

Here “r” stands for corresponding column.The “dec” variable is used just as rw(r,dec) function.

Further Clarification:

For further detailing,please let me know through your comments.

The actual Code is here.Click here.

Fibonacci Series Time Comparison for Recursive Algorithm

noreply@blogger.com (Soham) — Fri, 1 Oct 2010 23:47:00 +0530

This Program-code finds the time required to find the nth Fibonacci no. using recursive algorithm.

This program takes no input and outputs .xls file in which the nth Fibonacci no. with the time to compute that is written

Fibonacci no. with Recursion
 #include<stdio.h>
#include<time.h>
 
int fibonacci(int i);
 
int main()
{
 time_t t1,t2;
 
 int i,no,fib;
 FILE *fp;
 
 fp=fopen("fibo.xls","w");
 
 if(fp==NULL)
 {
    printf("ERROR IN FILE OPENNING\n");
    exit(1);
 }
 
  
 fprintf(fp,"No\tFibonacci\ttime\n");
 
 for(i=1;i<=40;i++)
 {
    fprintf(fp,"%d\t",i);
    (void) time(&t1);
    fprintf(fp,"%d",fibonacci(i));
     (void) time(&t2);
     fprintf(fp,"\t%ld\n",(long)(t2-t1));
 }
 
 printf("fibo.xls file has been created.\n");
 getch();
 return 0;
}
 
int fibonacci(int i)
{
 int x;
 if(i==1)
 return 0;
 else if(i==2)
 return 1;
 else 
 {
  x=fibonacci(i-1)+fibonacci(i-2);
  return x;
 }
}
 

You can take a look to the xls file I’ve got in my Laptop.

For further details contact me.

Maximum Number Finding By Smallest Comparisons – C Programming

noreply@blogger.com (Soham) — Sat, 18 Sep 2010 05:14:00 +0530

This Programs finds maximum and minimum Numbers from an Input array with the smallest number of Comparisons.It basically compare between successive two numbers and stores maximum(or minimum) among them and creates a sub-array with those maximums(or minimums) and performs a recursive algorithm in sub-array i.e again find maximum among two successive and creates sub-array with those.

The very last element in the last sub-array will be maximum(or minimum).

Maximum &amp; Minimum Number
#include<stdio.h>
 
void func(int max[],int min[],int no);
int cnt=0;//counting the comparison
int main()
{
 int num[100],max[50],min[50];
 int no,nom,i,j=0;
 
 printf("\nHow many numbers you want to enter:-");
 scanf("%d",&no);
 
 printf("\n");
 
 //inputting the number
 for(i=0;i<no;i++)
 {
  printf("Enter number %d:-",i+1);
  scanf("%d",&num[i]);
 }
 
 //checking if n is odd or not
 if(no%2==0)
  {nom=no;}
 else
 {
  nom=no-1;
  max[nom/2]=num[nom];
  min[nom/2]=num[nom];
 }
 
 i=0;
 
 //dividing the max and min array
 while(i<nom-1)
 {
  if(num[i]>num[i+1])
  {
   max[j]=num[i];
   min[j]=num[i+1];
  }
  else
  {
   max[j]=num[i+1];
   min[j]=num[i];
  }
  cnt++;
  i+=2;
  j++;
 }
 
 //calling the function to determine max and min by sending max,min and no. of elements
 if(no%2==0)
  func(max,min,no/2);
 else
  func(max,min,(no/2)+1);
 
 //output
 printf("\nThe total number you have given is %d and the comparisons are %d.",no,cnt);
 if(cnt!=0)
 {
  printf("\nThe maximum number is %d.",max[0]);
  printf("\nThe minimum number is %d.\n",min[0]);
 }
 else
  printf("\nError in evaluating Maximum and minimum numbers.\n");
 printf("\n");
}
 
void func(int max[],int min[],int no)
{
 int i=0,j=0,nom;
 
 if(no%2==0) nom=no;
 else
 {
  nom=no-1;
 }
 
 while(i<nom-1)
 {
  //for maxm
  if(max[i]>max[i+1])
   max[j]=max[i];
  else
   max[j]=max[i+1];
  //for minm
  if(min[i]<min[i+1])
   min[j]=min[i];
  else
   min[j]=min[i+1];
  
  i+=2;
  j++;
  cnt+=2;//for two comparisons
 }
 
 if(no%2!=0)
 {
  max[nom/2]=max[nom];
  min[nom/2]=min[nom];
 }
 
 if(nom/2>=1) 
 {
  if(no%2==0) func(max,min,nom/2);
  else func(max,min,(nom/2)+1);
 }
}

Further Discussion will be carried out later.

Any suggestion is solicited.

Parenthesis Checking – C Programming and Algorithom

noreply@blogger.com (Soham) — Sun, 12 Sep 2010 08:52:00 +0530

This Program check in an expression that if the brackets in the expression are in the proper form or not and also it checks for the same no. of opening and closing parenthesis.
This Program takes input from a file named "bracket.txt". Expressions are given there in each new line.Program takes an expression,checks it and shows the result on the display screen.

Code Snipped
#include<stdio.h>
 
#define STACKSIZE 20
 
struct stack
{
    int top;
    char items[STACKSIZE];
};
 
struct stack stk;
 
 
char pop(struct stack *ps)
{
    char var;
    if(ps->top!=-1)
    {
        var=ps->items[ps->top];
        ps->top--;
        return var;
    }
}
 
void push(struct stack *ps,char a)
{
    if(ps->top==STACKSIZE-1)
    {
        printf("\nOverflow");
        exit(1);
    }
    else
    {
        ps->top++;
        ps->items[ps->top]=a;
    }
}
 
 
int main()
{
    FILE *fp;
    char inp[50],x;
    int i,j,k,dec;
    struct stack *ps;
    ps=&stk;
 
    fp=fopen("bracket.txt","r");
    if(fp==NULL)
    {
        printf("\nFile Reading Error.\n");
        exit(1);
    }
 
    while(!feof(fp))
    {
        i=0;j=0;k=0;dec=1;ps->top=-1;
        printf("Expression=");
        fscanf(fp,"%s\n",inp);
        for(k=0;inp[k]!='\0';k++)      //printing the expression
            printf("%c",inp[k]);
        while(inp[j]!='\0' && inp[i]!='\0')
        {
            if(inp[j]=='(' || inp[j]=='{' || inp[j]=='[')
            {
                push(ps,inp[j]);
            }
            j++;
            if(inp[i]==')' || inp[i]=='}' || inp[i]==']')
            {
                if(ps->top>-1)
                {
                    x=pop(ps);
                    if((inp[i]==')' && x=='(') || (inp[i]=='}' && x=='{') || (inp[i]==']' && x=='[')) //Checking the corresponding bracket
                        dec=1;
                    else
                        dec=0;
                }
                else
                    dec=0;
            }
            i++;
            if(dec==0)
                break;
        }
        if(dec==0||ps->top>-1)
            printf("\n\tBrackets are not matched.");
        else
            printf("\n\tBrackets are matched.");
        printf("\n\n");
    }
    return 0;
}

Further discussion will be carried out later.Any suggestion is solicited.
Thanks.

Infix to Postfix – C Programming And Algorithom

noreply@blogger.com (Soham) — Sat, 11 Sep 2010 08:52:00 +0530

This Proram makes an Infix expression to its Postfix form.

Infix to postfix
#include<stdio.h>
#include<string.h>
 
#define size 10
 
struct stack 
{
  char stkel[size];
  int tos;
};
 
struct stack stk;
int ele;
char infix[50],output[50];
 
void push(struct stack *ps,char ele);
char pop(struct stack *ps);
void show_stack(struct stack *ps);
void show_output(char output[]);
int prec(char);
 
int main()
{
    int i=0,j=0,k=0,length;
    char temp;
    struct stack *ps;
    FILE *fp;
 
    fp=fopen("data1.txt","r");
    if(fp==NULL)
    {
        printf("\nError Openning File\n");
        exit(1);
    }
    else
        printf("Data from the file data1.txt has been taken.\n");
 
    ps=&stk;
    ps->tos=-1;
 
    while(!feof(fp))
    {
        ps->tos=-1;j=0;
        fscanf(fp,"%s\n",infix);
        printf("\nThe infix expresson is %s\n",infix);
        length=strlen(infix);
    
        printf("\nInp\t\tPostfx\t\t\tStk\n");
        
        for(i=0;i<length;i++)
        {
                printf("%c\t\t",infix[i]);//Input string Printed
                                //Numbers are added to the out put string 
                if(infix[i]!='+' && infix[i]!='-' && infix[i]!='*' && infix[i]!='/' && infix[i]!='^' && infix[i]!='$' && infix[i]!=')' && infix[i]!='(' )
                {
                    output[j]=infix[i];
                    j++;
                }
                                //If an operator or a bracket is encountered 
                else
                {
                    if(ps->tos==-1) //If there are no elements in the stack,the operator added to stack
 
                    {
                    push(ps,infix[i]);
                    }
                    else
                    {       //Operators or pushed or poped based on the precedence 
                        if(infix[i]!=')' && infix[i]!='(')
                        {
                            if(prec(infix[i]) <= prec(ps->stkel[(ps->tos)]))
                            {
                            temp=pop(ps);
                            output[j]=temp;
                            j++;
                            push(ps,infix[i]);
                            }
                            else
                            {
                              push(ps,infix[i]);
                            }
                        }
                        else    //if bracket occurs
                        {
                            if(infix[i]=='(')
                            {
                              push(ps,infix[i]);
                            }
                            if(infix[i]==')')
                            {
                              temp=pop(ps);
                              while(temp!='(')
                              { 
                                output[j]=temp;
                                j++;
                                temp=pop(ps);
                              } 
                            }
                        }
                    }
                }
                output[j]='\0';
                show_output(output);
                printf("\t\t\t");
                show_stack(ps);
   
 
        }
 
        //rest of the elemets of stack added to postfix string
        while(ps->tos!=-1)
        {
            output[j++]=pop(ps);
            output[j]='\0';
            printf("\t\t");
            show_output(output);
            printf("\t\t\t");
            show_stack(ps);
        }
 
        printf("\nThe postfix expression is\t");
         for(i=0;i<length;i++)
            printf("%c",output[i]);
        printf("\n");
    }
    return 0;
 
}
//Functions for operations on stack
 
void push(struct stack *ps,char ele)
{
    ps->tos++;
    ps->stkel[ps->tos]=ele;
}
 
char pop(struct stack *ps)
{
    char var;
    var=ps->stkel[ps->tos];
    ps->tos--;
    return var;
}
 
//showing postfix string
void show_output(char output[])
{
    int i;
    for(i=0;output[i]!='\0';i++)
        printf("%c",output[i]);
}
 
//showing the elements of stack
void show_stack(struct stack *ps)
{
    int x=0;   
    if(ps->tos>-1)
        while(x<=ps->tos)
        {
            printf("%c",ps->stkel[x]);
            x++;
        }
    printf("\n");
}
 
//Function to get the precedence of an operator
 
int prec(char symbol)
{
 
if(symbol== '(')
return 0;
if(symbol== ')')
return 0;
if(symbol=='+' || symbol=='-')
return 1;
if(symbol=='*' || symbol=='/')
return 2;
if(symbol=='^')
return 3;
//return 0;
}

Further discussion will be carried out later. Any Suggestion is solicited.

Different Number Seaching Algorithoms & Comparisons – C Programming(Sequential,Binary,Interpollation)

noreply@blogger.com (Soham) — Thu, 9 Sep 2010 01:05:00 +0530

Technorati Tags: Search Algorithoms,2nd Year,3rd Semester,Computer Science

This C Program comapres among different searching algorithoms like

Sequential(Unordered)
Sequential(Ordered)
Binary Search(Only for Ordered List)
Interpollation Seach(Only For Ordered List)

This program doesn’t take any inputs.It takes random inputs and generates random numbers to be searched. And it outputs the time-complexity i.e number of comparisons of the search algorithoms.It also output a file in .xls format containning the data.

Code Snippet
 #include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
int seq_unord(int list[],int serch_el[],int no);
int seq_ord(int ord_list[],int serch_el[],int no);
int binary(int ord_list[],int serch_el[],int no);
int intrpoll(int ord_list[],int serch_el[],int no);
 
int unord_cnt=0,ord_cnt=0,bin_cnt=0,intr_cnt=0;
 
int main()
{
 int list[8192],serch_el[8192],ord_list[8192];
 int i=2,j,k,cnt=0,swap;
 FILE *fp;
 fp=fopen("data.xls","w");
 if(fp==NULL) 
 {
    printf("\nFile cannot be openned.\n");
     exit(1);
 }
 fprintf(fp,"Number\tSeqUnord\tSeqOrd\tBinary\tIntrpoll");
     for(j=0;j<8192;j++)
    {
     list[j]=rand()%10000;
     ord_list[j]=list[j];
    }
    for(j=0;j<8192;j++)
     serch_el[j]=rand()%10000;
 i=2;
 while(i<=8192)    
 {
    srand(time(0));
    for(j=0;j<i-1;j++)
    {
     for(k=j+1;k<i;k++)
     {
         if(ord_list[j]>ord_list[k])
        {
         swap=ord_list[j];
         ord_list[j]=ord_list[k];
         ord_list[k]=swap;
        }
     }
    }
    fprintf(fp,"\n%d\t%d\t%d\t%d\t%d",i,(seq_unord(list,serch_el,i)/i),(seq_ord(ord_list,serch_el,i)/i),(binary(ord_list,serch_el,i)/i),(intrpoll(ord_list,serch_el,i)/i));
    printf("\ni=%d,Total Searches--- Unorder=%d,Order=%d,Binary=%d,Interpollation=%d",i,unord_cnt,ord_cnt,bin_cnt,intr_cnt);
    i=i*2;
 }
 printf("\nYour data file has been processed and named 'data.xls'.\n");
 return 0;
}
 
int seq_unord(int list[],int serch_el[],int no)
{
 int i,j,cnt=0;
 unord_cnt=0;
 for(i=0;i<no;i++)
 {
     for(j=0;j<no;j++)
      {
     cnt++;
     if(serch_el[i]==list[j]) 
     {
        unord_cnt++;
        break;
     }
    }
 }
 return(cnt);
}
 
int seq_ord(int ord_list[],int serch_el[],int no)
{
 int i,j,cnt=0;
 ord_cnt=0;
 for(i=0;i<no;i++)
 {
     for(j=0;j<no;j++)
    {
     cnt++;
     if(serch_el[i]<=ord_list[j]) 
     {
        if(serch_el[i]==ord_list[j]) ord_cnt++;
        break;
     }
     }
 }
 return(cnt);
}
 
int binary(int ord_list[],int serch_el[],int no)
{
 int i,first,last,mid,cnt=0;
 bin_cnt=0;
 for(i=0;i<no;i++)
 {
     first=0;last=no-1;
    while(first<=last)
    {
     mid=(first+last)/2;
     cnt++;
     if(serch_el[i]==ord_list[mid]) 
     {
        bin_cnt++;
        break;
     }
     else if(serch_el[i]<ord_list[mid]) last=mid-1;
          else first=mid+1;
    }
 }
 return (cnt);
}
 
int intrpoll(int ord_list[],int serch_el[],int no)
{
 int i,first,last,mid,cnt=0,dn;
 intr_cnt=0;
 for(i=0;i<no;i++)
 {
    first=0;
    last=no-1;
     while((serch_el[i]>=ord_list[first] && serch_el[i]<=ord_list[last]) && first<=last)
     {
      cnt++;
      dn=ord_list[last]-ord_list[first];
      if(dn==0) 
       mid=first;
      else 
       mid=first+((serch_el[i]-ord_list[first])*(last-first)/dn);
      if (serch_el[i]==ord_list[mid]) 
      {
        intr_cnt++;
        break;
      }
      else if(serch_el[i]<ord_list[mid]) last=mid-1;
           else first=mid+1;
     }
 }
 return (cnt);
}
 

For any Information we can contact me.Further detail discussion on this will be carried out later.

Any Suggestion is highly expected.

Saddle Point of Matrix – C Programming and Algorithm

noreply@blogger.com (Soham) — Sun, 29 Aug 2010 15:20:00 +0530

This Program Finds the saddle points in a Matrix and shows it.

Finding Saddle Point of Matrix
 #include<stdio.h>
 
int row,colm,eq=1;
int rw(int r,int dec);//determinning the max & min of the row
int col(int r,int dec);//determinning the max & min of the coloumn
 
int num[10][10];
 
int main()
{
 int i,j,sadl[50],min_r,max_r,min_c,max_c,cnt=0,dec_r[10],dec_c[10];
 
 printf("\nEnter How many Number of Rows in the matrix:-");
 scanf("%d",&row);
 printf("Enter How many Number of Coloumns in the matrix:-");
 scanf("%d",&colm);
 printf("\n");
 for(i=1;i<=row;i++)
 {
     for(j=1;j<=colm;j++)
     {
         printf("Enter the Element of %d row and %d coloumn:-",i,j);
         scanf("%d",&num[i][j]);    
     }
 }
 printf("\nThe matrix is :-\n");
 for(i=1;i<=row;i++)
 {
      for(j=1;j<=colm;j++)
      {
        
         printf("%d\t",num[i][j]);
     }
     printf("\n");
 }
 for(i=1;i<=row;i++)     
 {
       min_r=rw(i,0);
      max_r=rw(i,1);
     for(j=1;j<=colm;j++)
      {
         max_c=col(j,1);
           if(max_c==min_r && eq!=0)
         {
          printf("\nRow:-%d Coloumn:-%d Saddle Point Number:-%d",i,j,max_c);
          cnt++;
         }
         min_c=col(j,0);
         if(max_r==min_c && eq!=0)
         {
          printf("\nRow:-%d Coloumn:-%d Saddle Point Number:-%d",i,j,min_c);
          cnt++;
         } 
     }     
 }         
 if(cnt==0) printf("\nThere are no saddle points.");
 printf("\n");     
 return 0;
}
 
int rw(int r,int dec)
{
 int i,min,max;
 min=num[r][1];
 max=min;
 
 for(i=2;i<=colm;i++)
 {
  if(min>num[r][i])
   min=num[r][i];
  if(max<num[r][i])
   max=num[r][i]; 
 }
 if(max==min) eq=0;
 else if(dec==0) return min;
      else return max;
}  
 
int col(int r,int dec)
{
 int i,max,min;
 max=num[1][r];
 min=max;
 for(i=2;i<=row;i++)
 {
  if(max<num[i][r])
   max=num[i][r];
  if(min>num[i][r])
   min=num[i][r];
 }
 if(max==min) eq=0;
 else if(dec==0) return min;
      else return max;
}
 

Clarification is given here.