Newton's Backward Interpolation

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
void differenceTable(double **A,double **L,int ROW);
double result(double **A,double **L,double x,int ROW);
double factorial(int n);
FILE *fp;
int main(int argc, char *argv[])
{
double **A,*b,*xn,*xnplus1,*p,temp,x,**L,**U,lambda,error,t1=0.0;
int ROW,i,j,k,t=1,m=1,bo=1;
char ch;
if(argc==1)
{
printf("\n Enter the number of values:");
scanf("%d",&ROW);
printf("\n Enter the value at which value has to be aprroximated:");
scanf("%lf",&x);
A=(double **)malloc((ROW+1)*sizeof(double*));
L=(double **)malloc((ROW+1)*sizeof(double*));
U=(double **)malloc((ROW+1)*sizeof(double*));
for(i=0;i<=ROW;i++)
{
A[i]=(double *)malloc((ROW+1)*sizeof(double));
L[i]=(double *)malloc((ROW+1)*sizeof(double));
U[i]=(double *)malloc((ROW+1)*sizeof(double));
}
b=(double *)malloc((ROW+1)*sizeof(double));
p=(double *)malloc((ROW+1)*sizeof(double));
xn=(double *)malloc((ROW+1)*sizeof(double));
xnplus1=(double *)malloc((ROW+1)*sizeof(double));
for(i=1;i<=ROW;i++)
{
printf("\n Enter the value of X[%d]:",i);
scanf("%lf",&A[i][1]);
}
for(i=1;i<=ROW;i++)
{
printf("\n Enter the value of Y[%d]:",i);
scanf("%lf",&A[i][2]);
}

}
else if (argc==2)
{
fp=fopen(argv[1],"r");
if(fp==NULL)
{
printf("\n File not found, program will terminate:");
exit(0);
}
fscanf(fp,"%d",&ROW);
fscanf(fp,"%lf",&x);
A=(double **)malloc((ROW+1)*sizeof(double*));
L=(double **)malloc((ROW+1)*sizeof(double*));
U=(double **)malloc((ROW+1)*sizeof(double*));
for(i=0;i<=ROW;i++)
{
A[i]=(double *)malloc((ROW+1)*sizeof(double));
L[i]=(double *)malloc((ROW+1)*sizeof(double));
U[i]=(double *)malloc((ROW+1)*sizeof(double));
}
b=(double *)malloc((ROW+1)*sizeof(double));
p=(double *)malloc((ROW+1)*sizeof(double));
xn=(double *)malloc((ROW+1)*sizeof(double));
xnplus1=(double *)malloc((ROW+1)*sizeof(double));

while(!feof(fp))
{
for(i=1;i<=ROW;i++)
{
for(j=1;j<=2;j++)
{
fscanf(fp,"%lf ",&A[i][j]);
}

}
}
fclose(fp);
}
else
{
printf("\n Invalid Arguments,program will terminate:\n");
exit(0);
}
printf("\n         X          Y");
printf("\n------------------------------------------------------------------\n");
for(i=1;i<=ROW;i++)
{
for(j=1;j<=2;j++)
{

U[i][j]=A[i][j];
printf("   %+lf",U[i][j]);
}
printf("\n");
}
for(i=1;i<=ROW-1;i++)
{
for(j=ROW-i,t=1;j>=1;j--,t++)
{
L[t][i]=U[t+1][2]-U[t][2];
}
for(t=1;t<=ROW-i;t++)
U[t][2]=L[t][i];
}
differenceTable(A,L,ROW);
printf("\n Value at %+lf by Newton's Backward Interpolation formula is %+lf\n",x,result(A,L,x,ROW));
return 0;
}
double result(double **A,double **L,double x,int ROW)
{
int i,j,flag=1,t;

double h,value=0,p,tmp=1.0;
h=A[2][1]-A[1][1];
p=(A[ROW][1]-x)/h;
for(i=0,t=ROW+1;i<=ROW;i++,t--)
{
if(i==0)
value +=A[ROW][2];
else
{
for(j=1;j<=i;j++)
tmp=tmp*(p-j+1)*(-1);
tmp = tmp/factorial(i);
tmp = tmp*L[t-1][i];
value +=tmp;
}
tmp=1.0;
}
return value;
}
double factorial(int n)
{
 if(n<=1)
  return 1;
 else
  return n*factorial(n-1);
}
void differenceTable(double **A,double **L,int ROW)
{
int **position,*ap,j,m,i;
position=(int **)malloc((ROW+1)*sizeof(int*));
ap=(int *)malloc((ROW+1)*sizeof(int));
for(i=0;i<=ROW;i++)
position[i]=(int *)malloc((ROW+1)*sizeof(int));
int an,tmp;
tmp=ROW;
for(i=1;i<=ROW;i++)
{
an=1+(i-1)*2;
ap[i]=an;
for(j=1;j<=tmp;j++)
{
position[i][j]=an+(j-1)*4;
}
tmp--;
}
tmp=ROW;
tmp=ROW+(ROW-1)*3;
int *match,tmp1,l,*pos,flag,z,k;
match=(int *)malloc((ROW+1)*sizeof(int));
pos=(int *)malloc((ROW+1)*sizeof(int));
for(i=0;i<=ROW;i++)
{
match[i]=0;
pos[i]=0;
}

printf("\n-----------------------------Difference Table-----------------------------\n");
printf("\n X       Y");
for(i=1;i<=ROW-1;i++)
printf("      D_%d",i);
printf("\n--------------------------------------------------------------------------\n");
for(i=1;i<=tmp;i++)
{
tmp1=ROW;

for(l=1;l<=ROW;l++)
{
flag=0;
for(m=1;m<=tmp1;m++)
{
if(i==position[l][m])
{
flag=1;
match[l]=1;
pos[m]=position[l][m];
break;
}
} //inner for
if(flag==1)
{
for(k=1;k<=ROW;k++)
{
if(match[k]==0)
{
printf("");
}
else
{
if(k==1)
//printf("(%d,%d)+(%d,%d)|%d",(position[l][m]/4)+1,k,(position[l][m]/4)+1,k+1,i);
printf("%+2.2lf\t%+2.2lf",A[(position[l][m]/4)+1][k],A[(position[l][m]/4)+1][k+1]);
else
{
z=(position[l][m]-ap[k])/4+1;
//printf("\t\t(%d,%d)|%d",z,k-1,i);
printf("\t\t%+2.2lf",L[z][k-1]);
}

}
} //end of k-loop

} //end of flag==1

else
{printf(" ");}
tmp1--;
for(k=0;k<=ROW;k++)
{
pos[k]=0;
match[k]=0;
}
}

printf("\n");
}
printf("\n--------------------------------------------------------------------------\n");
}

Newton's Forward Interpolation : Numerical Analysis C Program

Newton's Forward Interpolation : Numerical Analysis C Program

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

void differenceTable(double **A,double **L,int ROW);

double result(double **A,double **L,double x,int ROW);

double factorial(int n);

FILE *fp;

int main(int argc, char *argv[]) {

double **A,*b,*xn,*xnplus1,*p,temp,x,**L,**U,lambda,error,t1=0.0;

int ROW,i,j,k,t=1,m=1,bo=1;

char ch;

if(argc==1) { 

    printf("\n Enter the number of values:");

    scanf("%d",&ROW);

    printf("\n Enter the value at which value has to be aprroximated:");

    scanf("%lf",&x);

    A=(double **)malloc((ROW+1)*sizeof(double*));

    L=(double **)malloc((ROW+1)*sizeof(double*));

    U=(double **)malloc((ROW+1)*sizeof(double*));

    for(i=0;i<=ROW;i++) {

        A[i]=(double *)malloc((ROW+1)*sizeof(double));

        L[i]=(double *)malloc((ROW+1)*sizeof(double));

        U[i]=(double *)malloc((ROW+1)*sizeof(double));

    }

 b=(double *)malloc((ROW+1)*sizeof(double));

 p=(double *)malloc((ROW+1)*sizeof(double));

 xn=(double *)malloc((ROW+1)*sizeof(double));

 xnplus1=(double *)malloc((ROW+1)*sizeof(double));

 for(i=1;i<=ROW;i++)  {

    printf("\n Enter the value of X[%d]:",i);

    scanf("%lf",&A[i][1]);

 }

 for(i=1;i<=ROW;i++) {

    printf("\n Enter the value of Y[%d]:",i);

    scanf("%lf",&A[i][2]);

 }

  

}

else if (argc==2) {

    fp=fopen(argv[1],"r");

    if(fp==NULL) {

        printf("\n File not found, program will terminate:");

        exit(0);

    }

    fscanf(fp,"%d",&ROW);

    fscanf(fp,"%lf",&x);

    A=(double **)malloc((ROW+1)*sizeof(double*));

    L=(double **)malloc((ROW+1)*sizeof(double*));

    U=(double **)malloc((ROW+1)*sizeof(double*));

    for(i=0;i<=ROW;i++) {

        A[i]=(double *)malloc((ROW+1)*sizeof(double));

        L[i]=(double *)malloc((ROW+1)*sizeof(double));

        U[i]=(double *)malloc((ROW+1)*sizeof(double));

    }

    b=(double *)malloc((ROW+1)*sizeof(double));

    p=(double *)malloc((ROW+1)*sizeof(double));

    xn=(double *)malloc((ROW+1)*sizeof(double));

    xnplus1=(double *)malloc((ROW+1)*sizeof(double));

    while(!feof(fp)) {

    for(i=1;i<=ROW;i++) {

        for(j=1;j<=2;j++) {

            fscanf(fp,"%lf ",&A[i][j]);

            }

        }

    }  

 fclose(fp);

 }

 else {

    printf("\n Invalid Arguments,program will terminate:\n");

    exit(0);

}

printf("\n         X          Y");

printf("\n------------------------------------------------------------------\n");

for(i=1;i<=ROW;i++) {

    for(j=1;j<=2;j++) {

        U[i][j]=A[i][j];

        printf("   %+lf",U[i][j]);

        }

    printf("\n");

}

for(i=1;i<=ROW-1;i++) {

    for(j=ROW-i,t=1;j>=1;j--,t++)  {

        L[t][i]=U[t+1][2]-U[t][2];

        }

 for(t=1;t<=ROW-i;t++)

    U[t][2]=L[t][i];

} 

differenceTable(A,L,ROW);

printf("\n Value at %+lf by Newton's Forward Interpolation formula is %+lf\n",x,result(A,L,x,ROW));

return 0;

}

double result(double **A,double **L,double x,int ROW) {

int i,j;

double h,value=0,p,tmp=1.0;

h=A[2][1]-A[1][1];

p=(x-A[1][1])/h;

for(i=0;i<ROW;i++){

    if(i==0)

    value +=A[1][2];

    else {

        for(j=1;j<=i;j++)

        tmp=tmp*(p-j+1);

        tmp = tmp/factorial(i);

        tmp = tmp*L[1][i];

        value +=tmp;

    }

    if(i==0)

        printf("%2.2lf ",A[1][2]);

    else

        printf("%2.2lf ",L[1][i]);

    tmp=1.0;

    }

    return value;

}

double factorial(int n) {

    if(n<=1)

        return 1;

    else

        return n*factorial(n-1);

}

void differenceTable(double **A,double **L,int ROW) {

    int **position,*ap,j,m,i;

    position=(int **)malloc((ROW+1)*sizeof(int*));

    ap=(int *)malloc((ROW+1)*sizeof(int));

    for(i=0;i<=ROW;i++)

        position[i]=(int *)malloc((ROW+1)*sizeof(int));

    int an,tmp; 

    tmp=ROW;

    for(i=1;i<=ROW;i++) {

        an=1+(i-1)*2;

        ap[i]=an;

        for(j=1;j<=tmp;j++)  {

            position[i][j]=an+(j-1)*4;

            }

        tmp--;

    }

    tmp=ROW;

    tmp=ROW+(ROW-1)*3;

    int *match,tmp1,l,*pos,flag,z,k;

    match=(int *)malloc((ROW+1)*sizeof(int));

    pos=(int *)malloc((ROW+1)*sizeof(int));

    for(i=0;i<=ROW;i++) {

        match[i]=0;

        pos[i]=0;

        }

printf("\n-----------------------------Difference Table-----------------------------\n");

printf("\n X       Y");

for(i=1;i<=ROW-1;i++)

    printf("      D^%d",i);

printf("\n--------------------------------------------------------------------------\n");

for(i=1;i<=tmp;i++) {

    tmp1=ROW;

     for(l=1;l<=ROW;l++) {

        flag=0;

        for(m=1;m<=tmp1;m++)  {

            if(i==position[l][m])   {

                flag=1;

                match[l]=1;

                pos[m]=position[l][m];

                break;

                }

            } //inner for

        if(flag==1)        {

            for(k=1;k<=ROW;k++)  {

                if(match[k]==0) {

                    printf("");

                }

        else  {

            if(k==1)

            //printf("(%d,%d)+(%d,%d)|%d",(position[l][m]/4)+1,k,(position[l][m]/4)+1,k+1,i);

                printf("%+2.2lf\t%+2.2lf",A[(position[l][m]/4)+1][k],A[(position[l][m]/4)+1][k+1]);

            else   {

                z=(position[l][m]-ap[k])/4+1;

                //printf("\t\t(%d,%d)|%d",z,k-1,i);

                printf("\t\t%+2.2lf",L[z][k-1]);

                }

            }

        } //end of k-loop     

    } //end of flag==1

    else

        {printf(" ");}

    tmp1--;

   for(k=0;k<=ROW;k++) {

        pos[k]=0;

        match[k]=0;

        }

    }

    printf("\n");

    }

printf("\n--------------------------------------------------------------------------\n");

}

Random Quotes

This is a command line utility that prints a "Maths Quote of the Day" on the user's terminal when run.
User's types "java MathQuoteOFDay" on the command line
System prints out a quote.

import java.util.*;
public class MathsQuoteOFDay
    {
    public static void main(String[] args)
        {
        Quotes qts = new Quotes();
            int n = (int)(Math.random()*10);
            System.out.println("");
            System.out.println(qts.getQuote(n));   
            System.out.println("");        
        }
    }
class Quotes
    {
    Quotes()
        {
        }
    public String getQuote(int n)
        {
        return (quotes[n]);
        }
    private static String quotes[]={"I like mathematics because it is not human and has nothing particular to do with this planet or with the whole accidental universe                         - because like Spinoza's God, it won't love us in return.  ~Bertrand Russell",
                    "If there is a God, he's a great mathematician.  ~Paul Dirac",
                    "Do not worry about your problems with mathematics, I assure you mine are far greater. ~Albert Einstein",
                    "There are things which seem incredible to most men who have not studied mathematics. ~ Aristotle",
                    "Mathematics is a game played according to certain simple rules with meaningless marks on paper. ~ David Hilbert",
                    "Go down deep enough into anything and you will find mathematics~ Dean Schlicter",
                    " Life is good for only two things, discovering mathematics and teaching mathematics. ~ Simeon Poisson",
                    "In mathematics you don't understand things. You just get used to them. ~ Johann von Neumann",
                    " Medicine makes people ill, mathematics make them sad and theology makes them sinful. ~ Martin Luther",
                    "A man whose mind has gone astray should study mathematics. ~ Francis Bacon"};
    }

Parentheses Checking

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[","]” are correct in exp. For example, the program should print true for exp = “[a+{b-(c-(d-e)*d)+w)}+q]” and false for exp = “[(])”

 import java.util.*;

public class Parentheses
   {
   public static void main(String[] args)
{
int n,i,pos,posm,t;
boolean flag=true;
char[] symb={'(','{','[',']','}',')'};
char tmp;
Scanner in = new Scanner(System.in);
String expression;
System.out.println(" Enter the expression:");
expression=in.nextLine();
System.out.println(" Entered expression is:"+expression);
n=expression.length();
Stack s = new Stack(n);
System.out.println("");
for(i=0;i<n;i++)
{
pos=0;
posm=0;
if(expression.charAt(i)==symb[0] || expression.charAt(i)==symb[1] || expression.charAt(i)==symb[2] )
{
s.push(expression.charAt(i));

}
if(expression.charAt(i)==symb[3] || expression.charAt(i)==symb[4] || expression.charAt(i)==symb[5] )
{
if(s.isempty()==true)
{
flag=false;
break;
}
else
{
tmp=s.pop();
for(t=0;t<3;t++)
if(symb[t]==tmp)
pos=t;
for(t=3;t<6;t++)
if(symb[t]==expression.charAt(i))
posm=t;
if(pos+posm!=5)
{
flag=false;
break;
}
}
}
 

}
if(s.isempty()==false)
flag=false;
if(flag==true)
System.out.println(" Valid Expression:");
else
System.out.println(" Invalid Expression:");
in.close();
}

  }
class Stack
{
public Stack(int a)
{
top=-1;
n=a;
stack = new char[n];
}
public void push(char x)
{
stack[++top]=x;
}
public char pop()
{
return (stack[top--]);
}
public char stacktop()
{
return (stack[top]);
}
public boolean isempty()
{
return ( top==-1 ? true: false);
}
private int top;
private int n;
private char[] stack;

}

Data Structure GATE Questions

GATE questions on Data Structure from 1987 to 2012. Here is the link for download
http://sdrv.ms/1cX5ofa

n-Queen

n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 and n=3.


#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0

int BOARDSIZE;
int DIAGONAL;
int OFFSET;
void dispal(void);
void add_queen(void);
int *queencol;
int *colfree;
int *upfree;
int *downfree;
int Queenc=-1;
int main()
{
int i;
printf("\n Enter the boardsize: ");
scanf("%d",&BOARDSIZE);
DIAGONAL=2*BOARDSIZE-1;
OFFSET=BOARDSIZE-1;
queencol=(int *)malloc(BOARDSIZE*sizeof(int));
colfree=(int *)malloc(BOARDSIZE*sizeof(int));
upfree=(int *)malloc(DIAGONAL*sizeof(int));
downfree=(int *)malloc(DIAGONAL*sizeof(int));
for(i=0;i<BOARDSIZE;i++)
    colfree[i]=TRUE;
    //queencol[i]=-1;
for(i=0;i<DIAGONAL;i++)
    {
    upfree[i]=TRUE;
    downfree[i]=TRUE;
    }
add_queen();
return 0;
}
void add_queen(void)
    {
    int col;
    Queenc++;
    for(col=0;col<BOARDSIZE;col++)
        if(colfree[col] && upfree[Queenc+col] && downfree[Queenc-col+OFFSET])
            {
            queencol[Queenc]=col;
            colfree[col]=FALSE;
            upfree[Queenc+col]=FALSE;
            downfree[Queenc-col+OFFSET]=FALSE;
            if(Queenc==BOARDSIZE-1)
                display();
            else
                add_queen();
            colfree[col]=TRUE;
            upfree[Queenc+col]=TRUE;
            downfree[Queenc-col+OFFSET]=TRUE;
            }
        Queenc--;
    }
void display(void)
    {
    printf("\n");
    int i,j,tmp;
    for(i=0;i<BOARDSIZE;i++)
        {
        tmp=queencol[i];
        for(j=0;j<BOARDSIZE;j++)
            {
            if(j==tmp)
            printf(" Q ");
            else
            printf(" 0 ");
            }
        printf("\n");
        }
    printf("\n");
    return;
    }