/*Prog2 CSE5311
Name: Anan Tongprasith
compile: cc prog2.c
inputfile: randomnumber
random number generator: random.c
usage: a.out
limitation: 8750 input max please

Make sure "randomnumber" file exists when running the program
*/

#include 
#include 

void myread();
int bruteforce(int x[],int y[],int xsize,int ysize,int result[],int resultsize);
int strictlyinc(int x[],int size);
int comp(int *a,int *b);
int LCSLength(int x[],int y[],int maxsize,int bsize,int *result);
int memoizing(int x[],int y[],int maxsize,int bsize,int *result);
int LookupArray(int x[],int y[], int **c,int i,int j);

void main()
{  int *a,*b;		// original and sorted array
   int maxsize,i,bsize,choice;
   int *result,resultsize;
   struct timespec tp1,tp2;
   double timeuse;

///////////// Reading input
   printf("\nHow many input do you want to read ?:");
   scanf("%d",&maxsize);
   if(maxsize>8750)
   {maxsize=8750;printf("\nLimit maximum to 8750.\n");
   }
   printf("\nReading from randomnumber file...\n\n");

   a=(int *)malloc(sizeof(int)*maxsize);
   myread(a,maxsize); 

//////////// Select calculation technique
   printf("Available algorithm:\n");
   printf("1) BruteForce\n");
   printf("2) Bottom-up Dynamic Programming\n");
   printf("3) Memoizing Dynamic Programming\n");
   printf("Select you choice(1,2,3):");
   scanf("%d",&choice);

   getclock(TIMEOFDAY,&tp1);               /* start timing */
   if(choice==1)
   {
//////////// Calling Bruteforce
   	resultsize=0;
   	result=(int *)malloc(sizeof(int)*maxsize);
   	resultsize=bruteforce(a,b,maxsize,0,result,resultsize);
   	printf("Bruteforce found longest sequence size to be %d.\n",resultsize);
   	printf("The sequence is:\n");
   	for(i=0;i=0;i--)
           printf("%d ",result[i]);
   	printf("\n");
   	free(b);
   	free(result);
   }
   if(choice==3)
   {
//////////// Memoizing
	resultsize=0;
       	//// Create a second array (sorted and no redundant value)
   	b=(int *)malloc(sizeof(int)*maxsize);
   	for(i=0;i=0;i--)
           printf("%d ",result[i]);
   	printf("\n");
   	free(b);
   	free(result);
   }
   getclock(TIMEOFDAY,&tp2);               /* stop timing */
///////////////////////
   free(a);
   timeuse=(tp2.tv_sec - tp1.tv_sec)*1000000000 + (tp2.tv_nsec - tp1.tv_nsec);
   printf("Time used is %2.4f milliseconds.\n",timeuse/1000000);
}

void myread(int *a,int maxsize)
{ int i,buf;FILE *fp;

   fp=fopen("randomnumber","r");

   for(i=0;iresultsize)	// check if it is longer than current result
	{
 	   if(strictlyinc(y,ysize))	// check if it is strictly increasing 
	   {
		resultsize=ysize;
		for(i=0;i=c[i][j-1])
                   c[i][j]=c[i-1][j];
                else
                   c[i][j]=c[i][j-1];
           }
        }
   }

/*
// show c array
   for(i=0;i0)
   {    if(x[i-1]==y[j-1])      // don't forget! we shifted the arrays 1 block
        {
           result[k]=x[i-1];
           k=k+1;
           i=i-1;
           j=j-1;
        }
        else
        {  if(c[i-1][j]>=c[i][j-1])
                i=i-1;
           else
                j=j-1;
        }
   }
   for(i=0;i0)
   {    if(x[i-1]==y[j-1])      // don't forget! we shifted the arrays 1 block
        {
           result[k]=x[i-1];
           k=k+1;
           i=i-1;
           j=j-1;
        }
        else
        {  if(c[i-1][j]>=c[i][j-1])
                i=i-1;
           else
                j=j-1;
        }
   }
   return k;
}
///////// lookup recursive
int LookupArray(int x[],int y[], int **c,int i,int j)
{
   if(c[i][j]>=0)
	return c[i][j];
   else
   {
	if(x[i-1]==y[j-1])
	   c[i][j]=1+LookupArray(x,y,c,i-1,j-1);
	else
	{  if(LookupArray(x,y,c,i-1,j)>=LookupArray(x,y,c,i,j-1))
		c[i][j]=c[i-1][j];
	   else
		c[i][j]=c[i][j-1];
	}
   }
   return c[i][j];
}

    Source: geocities.com/Vienna/7079/src/LCS

               ( geocities.com/Vienna/7079/src)                   ( geocities.com/Vienna/7079)                   ( geocities.com/Vienna)