BE-SEM1-CL-1 Programs & Writeup

BE SEM-1 CL-1 Programs & Writeup

 

=============================

Assignment No. A-1 Binary search

=============================

 

Using Divide and Conquer Strategies design a function for Binary Search using C++/Java/Python
/Scala.

 

Writeup : 

Binary search 

#include <stdio.h>
 
int main()
{
   int c, first, last, middle, n, search, array[100];
 
   printf("Enter number of elements\n");
   scanf("%d",&n);
 
   printf("Enter %d integers\n", n);
 
   for (c = 0; c < n; c++)
      scanf("%d",&array[c]);
 
   printf("Enter value to find\n");
   scanf("%d", &search);
 
   first = 0;
   last = n - 1;
   middle = (first+last)/2;
 
   while (first <= last) {
      if (array[middle] < search)
         first = middle + 1;    
      else if (array[middle] == search) {
         printf("%d found at location %d.\n", search, middle+1);
         break;
      }
      else
         last = middle - 1;
 
      middle = (first + last)/2;
   }
   if (first > last)
      printf("Not found! %d is not present in the list.\n", search);
 
   return 0;   
}

=============================

Assignment No. A-2 Quick Sort using openMP

=============================

 

Using Divide and Conquer Strategies design a class for Concurrent Quick Sort using C++.

 

Writeup:

Quick sort 

 #include <iostream>
#include <stdlib.h>
#include <omp.h>
using namespace std;


int partition(int * a, int p, int r)
{
    int lt[r-p];
    int gt[r-p];
    int i;
    int j;
    int key = a[r];
    int lt_n = 0;
    int gt_n = 0;

#pragma omp parallel for
    for(i = p; i < r; i++){
        if(a[i] < a[r]){
            lt[lt_n++] = a[i];
        }else{
            gt[gt_n++] = a[i];
        } 
    } 

    for(i = 0; i < lt_n; i++){
        a[p + i] = lt[i];
    } 

    a[p + lt_n] = key;

    for(j = 0; j < gt_n; j++){
        a[p + lt_n + j + 1] = gt[j];
    } 

    return p + lt_n;
}

void quicksort(int * a, int p, int r)
{
    int div;

    if(p < r)
   {
        div = partition(a, p, r);
        #pragma omp parallel sections
        { 
            #pragma omp section
            quicksort(a, p, div - 1);
             #pragma omp section
            quicksort(a, div + 1, r);

        }
    }
}

int main(void)
{
   int i, n, a[10];
   cout<<"Enter the count to sort the numbers:- ";
   cin>>n;
   cout<<endl;
   cout<<"Enter the elements to sort the numbers:- ";
    for(i = 0;i < n; i++)
        {
            cin>>a[i];
    }

    quicksort(a, 0, n-1);
    cout<<"The Sorted elements are:- "<<endl;
    for(i = 0;i < n; i++){
        cout<<"\t"<<a[i];
    }
   cout<<endl;
    return 0;
}

/*
gescoe@computerdept:~$ g++ quick_openmp.cpp -o quick_openmp -fopenmp
gescoe@computerdept:~$ ./quick_openmp

*/

=============================

Assignment No. A-3 LEX TOKEN

=============================

 

Lexical analyzer for sample language using LEX.

 

Writeup:

LEX 

 lex.l

 -------------------

%{
FILE *fp;
#include<stdio.h>
#include<string.h>
%}
headerfile "#include<"[a-z]+".h>"[\t]+[\n]+
datatype [\t\n]*"int"|"float"|"char"
keyword "if"|"else"|"then"|"do"|"while"|"return"|"void"|"for"
inbuilt "printf(".*");"[\n]+|"scanf(".*");"[\n]+|"getch"|"clrscr"
operator "+"|"-"|"*"|"/"
comment "/*"[\t\n]*.*[\n]*.*[\t\n]*.*"*/"
digit[0-9]+
identifier [a-zA-Z0-9]+
mainfun "main()"[\t\n]+
relation "<"|">"|"="|"<="|">="|"!="
smallbracket "("|")"
curlybracket "{"|"}"
squarebracket "["|"]"
punctuation ";"|"!"|"@"|"~"|"#"|"$"|"&"|"'"
%%
{headerfile} {
        fprintf(yyout,"\n Header file declaration: %s",yytext);
        //printf("\n Header file declaration: %s",yytext);
          }
{datatype} {
        fprintf(yyout,"\n Datatype: %s",yytext);
        //printf("\n Datatype: %s",yytext);
          }
{keyword} {
        fprintf(yyout,"\n Keyword: %s",yytext);
        //printf("\n keyword: %s",yytext);
          }
{inbuilt} {
        fprintf(yyout,"\n inbulit: %s",yytext);
        //printf("\n Inbuilt: %s",yytext);
          }
{operator} {
        fprintf(yyout,"\n Operator: %s",yytext);
        //printf("\n Operator: %s",yytext);
          }
{comment} {
        fprintf(yyout,"\n comment: %s",yytext);
        //printf("\n comment: %s",yytext);
          }
{digit} {
        fprintf(yyout,"\n Digit: %s",yytext);
        //printf("\n Digit: %s",yytext);
          }
{identifier} {
        fprintf(yyout,"\n identifier: %s",yytext);
        //printf("\n identifier: %s",yytext);
          }
{mainfun} {
        fprintf(yyout,"\n mainfun: %s",yytext);
        //printf("\n mainfun: %s",yytext);
          }
{relation} {
        fprintf(yyout,"\n relation: %s",yytext);
        //printf("\n relation: %s",yytext);
          }
{smallbracket} {
        fprintf(yyout,"\n smallbracket: %s",yytext);
        //printf("\n smallbracket: %s",yytext);
          }
{curlybracket} {
        fprintf(yyout,"\n curlybracket: %s",yytext);
        //printf("\n curlybracket: %s",yytext);
          }
{squarebracket} {
        fprintf(yyout,"\n squarebracket: %s",yytext);
        //printf("\n squarebracket: %s",yytext);
          }
{punctuation} {
        fprintf(yyout,"\n punctuation: %s",yytext);
        //printf("\n punctuation: %s",yytext);
          }
%%
main(int argc, char *argv[])
{
extern FILE *yyout;
FILE *fp;
if(argc>1)
{
fp=fopen(argv[1],"r");
if(!fp)
{
fprintf(stderr,"error in opening file",argv[1]);
exit(1);
}
yyin=fp;
yyout=fopen(argv[2],"w");
yylex();
fclose(fp);
}
}

input.c

-------------------

#include<stdio.h>
void main()
{
int a,b;
printf("\n Enter value of a & b:");
scanf("%d %d",&a,&b);
if(a>b)
{
    printf("a is greater no.");
}
else
{
    printf("b is greater no.");
}
}




     

 

=============================

Assignment No. A-4 YACC PARSER

=============================

 

Parser for sample language using YACC.

 

Writeup:

 YACC

 lex.l

 ----------------

%{
#include "y.tab.h"
%}

%%
[ \t\n] ;
"void"|"int"|"float"|"char"|"long"|"double"  {return DATATYPE;}
\# {return HASH;}
"include" {return INCLUDE;}
"define" {return DEFINE;}
printf\(.*\)";" {return STATEMENT;}
\< {return LT;}
\> {return GT;}
\( {return LB;}
\) {return RB;}
\, {return COMMA;}
\{ {return OCB;}
\} {return CCB;}
\; {return EOL;}
[a-zA-Z_]+[a-zA-Z0-9_]*\.h {return HEADER_FILE;}
[a-zA-Z_]+[a-zA-Z0-9_]* {return IDENTIFIER;}
[0-9]+ {return NUMBER;}
[0-9]+\.[0-9]+ {return RNUMBER;}
%%

yacc.y

-----------------

%{
    #include<stdio.h>
%}
%token DATATYPE IDENTIFIER NUMBER RNUMBER EOL LB  RB COMMA HASH LT GT INCLUDE HEADER_FILE DEFINE OCB CCB STATEMENT

%%
    pgm: header other { printf("\n Valid C Program\n"); }
    header: HASH INCLUDE LT HEADER_FILE GT header
            | HASH DEFINE IDENTIFIER NUMBER header
        | HASH DEFINE IDENTIFIER RNUMBER header
        | ;
    other: fun_name block other
        | ;
    fun_name: declaration LB  parameters RB
        |;
   
    block: OCB stmt CCB
        | ;
    stmt: STATEMENT stmt
      
        | ;
    parameters: declaration t
        | ;
    t: COMMA declaration t
        | ;
    declaration: DATATYPE IDENTIFIER
        | ;
%%

extern FILE *yyin;
extern char *yytext;

main()
{
    char fname[25];
    printf("\nEnter file name: ");
    scanf("%s",fname);
    yyin=fopen(fname,"r");
    while(!feof(yyin))
        yyparse();
    fclose(yyin);
    printf("\nString parsed successfully\n");
}

yyerror(char *s)
{
    printf("Error occured: %s: %s can not parse\n ",s,yytext);
    exit(1);
}

int yywrap()
{
    return 1;
}


ip

-----------

#include<stdio.h>

void main()
{
    int a;
    printf("\n This is main function");
   
   
}

void fun()
{
    printf("Inside fun");
}
void fun1(int x)
{
    printf("Inside fun1");
}

=============================

Assignment No. A-5 ICG

=============================

 

Int code generation for sample language using LEX and YACC.

 

Writeup:

LEX and YACC 

th.l

-------------------

%{
   #include "y.tab.h"
   extern char yyval;
%}

NUMBER [0-9]+
LETTER [a-zA-Z]+

%%
{NUMBER} {yylval.sym=(char)yytext[0]; return NUMBER;}
{LETTER} {yylval.sym=(char)yytext[0];return LETTER;}

\n {return 0;}
.  {return yytext[0];}

%%

th.y

--------------------------

%{

  #include<stdio.h>
  #include<string.h>
  #include<stdlib.h>
void ThreeAddressCode();
void triple();
void qudraple();
char AddToTable(char ,char, char);

  int ind=0;
  char temp='A';
  struct incod
  {
    char opd1;
    char opd2;
    char opr;
  };
%}

%union
{
 char sym;
}

%token <sym> LETTER NUMBER
%type <sym> expr
%left '-''+'
%right '*''/'

%%

statement: LETTER '=' expr ';' {AddToTable((char)$1,(char)$3,'=');}
           | expr ';'
       ;

expr: expr '+' expr {$$ = AddToTable((char)$1,(char)$3,'+');}
      | expr '-' expr {$$ = AddToTable((char)$1,(char)$3,'-');}
      | expr '*' expr {$$ = AddToTable((char)$1,(char)$3,'*');}
      | expr '/' expr {$$ = AddToTable((char)$1,(char)$3,'/');}
      | '(' expr ')' {$$ = (char)$2;}
      | NUMBER {$$ = (char)$1;}
      | LETTER {$$ = (char)$1;}
      ;

%%

yyerror(char *s)
{
  printf("%s",s);
  exit(0);
}

struct incod code[20];

int id=0;

char AddToTable(char opd1,char opd2,char opr)
{
code[ind].opd1=opd1;
code[ind].opd2=opd2;
code[ind].opr=opr;
ind++;
temp++;
return temp;
}

void ThreeAddressCode()
{
int cnt=0;
temp++;
printf("\n\n\t THREE ADDRESS CODE\n\n");
while(cnt<ind)
{
    printf("%c : = \t",temp);

   
        if(isalpha(code[cnt].opd1))
        printf("%c\t",code[cnt].opd1);
    else
        {printf("%c\t",temp);}

    printf("%c\t",code[cnt].opr);
   
    if(isalpha(code[cnt].opd2))
        printf("%c\t",code[cnt].opd2);
    else
        {printf("%c\t",temp);}

    printf("\n");
    cnt++;
    temp++;
}
}

void quadraple()
{
    int cnt=0;
temp++;
printf("\n\n\t QUADRAPLE CODE\n\n");
while(cnt<ind)
{
    //printf("%c : = \t",temp);

   
          printf("%d",id);
          printf("\t");       
          printf("%c",code[cnt].opr);
          printf("\t");    
           if(isalpha(code[cnt].opd1))
        printf("%c\t",code[cnt].opd1);
            else
        {printf("%c\t",temp);}

            //printf("%c\t",code[cnt].opr);
   
        if(isalpha(code[cnt].opd2))
            printf("%c\t",code[cnt].opd2);
        else
        {printf("%c\t",temp);}
       
        printf("%c",temp);

    printf("\n");
    cnt++;
    temp++;
    id++;
   
}
}

void triple()
{
    int cnt=0,cnt1,id1=0;
temp++;
printf("\n\n\t TRIPLE CODE\n\n");
while(cnt<ind)
{
    //printf("%c : = \t",temp);

        if(id1==0)
        {
            printf("%d",id1);
          printf("\t");       
          printf("%c",code[cnt].opr);
          printf("\t");    
           if(isalpha(code[cnt].opd1))
        printf("%c\t",code[cnt].opd1);
            else
        {printf("%c\t",temp);}

            //printf("%c\t",code[cnt].opr);
        cnt1=cnt-1;
        if(isalpha(code[cnt].opd2))
            printf("%c",code[cnt].opd2);
        else
        {printf("%c\t",temp);}
        }
        else
        {
          printf("%d",id1);
          printf("\t");       
          printf("%c",code[cnt].opr);
          printf("\t");    
           if(isalpha(code[cnt].opd1))
        printf("%c\t",code[cnt].opd1);
            else
        {printf("%c\t",temp);}

            //printf("%c\t",code[cnt].opr);
        cnt1=cnt-1;
        if(isalpha(code[cnt].opd2))
            printf("%d",id1-1);
        else
        {printf("%c\t",temp);}
        }
       

    printf("\n");
    cnt++;
    temp++;
    id1++;
   
}

}

main()
{
 printf("\nEnter the Expression: ");
 yyparse();
temp='A';
ThreeAddressCode();
quadraple();
triple();
}

yywrap()
{
 return 1;
}

op

-------------------

administrator@ubuntu:~/Desktop$ lex th.l
administrator@ubuntu:~/Desktop$ yacc -d th.y
administrator@ubuntu:~/Desktop$ gcc lex.yy.c y.tab.c -ll -ly
administrator@ubuntu:~/Desktop$ ./a.out

Enter the Expression: a=((b+c)*(d+e))
syntax error

administrator@ubuntu:~/Desktop$ ./a.out

Enter the Expression: a=((b+c)*(d/e));


     THREE ADDRESS CODE

B : =     b    +    c   
C : =     d    /    e   
D : =     B    *    C   
E : =     a    =    D   


     QUADRAPLE CODE

0    +    b    c    G
1    /    d    e    H
2    *    B    C    I
3    =    a    D    J


     TRIPLE CODE

0    +    b    c
1    /    d    0
2    *    B    1
3    =    a    2
administrator@ubuntu:~/Desktop$
 

 

=============================

Assignment No. A-6 K-means

=============================

 

Implement a simple approach for k-means/ k-medoids clustering using C++.

 

Writeup:

K-means 

 #include <iostream>
#include <stdlib.h>
#include<math.h>
#include<vector>
using namespace std;

int min(int arr[], int maxIndex)
{
int min=100;
for(int i=0;i<maxIndex;i++)
{
if(arr[i]<min)
min=arr[i];
}
return min;
}
int indexOf(int number,int arr[], int maxIndex)
{
int index;
for(int i=0;i<maxIndex;i++)
{
if(number==arr[i])
{
index=i;
break;  
}
}
return index;
}
int mean(vector<int> vc )
{
int sum=0;
for(int i=0;i<vc.size();i++)
sum=sum+vc[i];
return sum/vc.size();
}
void show(vector<int> vc )
{
for(int i=0;i<vc.size();i++){
cout<<vc[i]<<",";  
}
}
bool isEqual(int arr1[], int arr2[], int maxIndex){
for(int i=0;i<maxIndex;i++)
{
if(arr1[i]!=arr2[i])
return false;
}
return true;
}

int main()
{
int noOfItems;
int k;  
cout<<"Enter n objects: ";
cin>> noOfItems;
cout<<"Enter K cluster: ";
cin>> k;
int cluster[k];
int oldCluster[k];
int objects[noOfItems];
int row[k];
vector< vector<int> > groups;
for(int i=0;i<noOfItems;i++)
{
cout<<endl;
cout<<"Enter Value"<<"("<<(i+1)<<")"<<": ";

cin>>objects[i];
if(i<k)
cluster[i]=objects[i];
}
for(int i=0;i<k;i++)
{
vector<int> newGroup;
groups.push_back(newGroup);
}
int iter =1;
do
{
for(int i=0;i<noOfItems;i++)
{
for(int j=0;j<k;j++){
row[j] = abs(cluster[j]-objects[i]);
}  
    groups[indexOf(min(row,k),row,k)].push_back(objects[i]);
}
for(int j=0;j<k;j++)
{
     if(!groups[j].empty())
{
oldCluster[j]=cluster[j];
cluster[j] = mean(groups[j]);
}
}
if(!isEqual(oldCluster,cluster,k))
{
for(int i=0;i<k;i++)
groups[i].clear();
}
iter++;  
}while(!isEqual(oldCluster,cluster,k));
cout<<"\n\n";
for(int i=0;i<k;i++)
{
cout<<"C"<<(i+1)<<" : "<<cluster[i]<<endl;
}
for(int i=0;i<k;i++)
{
cout<<"\n\nGroup "<<(i+1)<<" : \n"<<endl;
show(groups[i]);
}
cout<<"\n\nNumber of Iterations:  "<<iter<<endl;

return 0;
}

/*

gescoe@computerdept:~/Documents/CL-1(CRB)/A6_Kmean$ g++ kmeans.cpp
gescoe@computerdept:~/Documents/CL-1(CRB)/A6_Kmean$ ./a.out
Enter n objects: 10
Enter K cluster: 3

Enter Value(1): 2

Enter Value(2): 5

Enter Value(3): 3

Enter Value(4): 1

Enter Value(5): 9

Enter Value(6): 4

Enter Value(7): 3

Enter Value(8): 10

Enter Value(9): 15

Enter Value(10): 6


C1 : 1
C2 : 11
C3 : 4


Group 1 :

2,1,

Group 2 :

9,10,15,

Group 3 :

5,3,4,3,6,

Number of Iterations:  5


*/

=============================

Assignment No. B-1 8-queen

=============================

 

 

8queens.py

--------------------------- 

import json
import sys

BOARD_SIZE = 8

def under_attack(col, queens):
    left = right = col

    for r, c in reversed(queens):
        left, right = left - 1, right + 1

        if c in (left, col, right):
            return True
    return False

def solve(n):
    if n == 0:
        return [[]]

    smaller_solutions = solve(n - 1)

    return [solution+[(n,i+1)]
        for i in xrange(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, solution)]

former, sys.stdout = sys.stdout, open('queen.json', 'w')

for answer in solve(BOARD_SIZE):
    print answer

results, sys.stdout = sys.stdout, former
for answer in solve(BOARD_SIZE):
    print json.dumps(answer)

'''
gescoe@computerdept:~/Documents/CL-1(CRB)/B1_8queen$ python 8queens.py
[[1, 4], [2, 2], [3, 7], [4, 3], [5, 6], [6, 8], [7, 5], [8, 1]]
[[1, 5], [2, 2], [3, 4], [4, 7], [5, 3], [6, 8], [7, 6], [8, 1]]
[[1, 3], [2, 5], [3, 2], [4, 8], [5, 6], [6, 4], [7, 7], [8, 1]]
[[1, 3], [2, 6], [3, 4], [4, 2], [5, 8], [6, 5], [7, 7], [8, 1]]
[[1, 5], [2, 7], [3, 1], [4, 3], [5, 8], [6, 6], [7, 4], [8, 2]]
[[1, 4], [2, 6], [3, 8], [4, 3], [5, 1], [6, 7], [7, 5], [8, 2]]
[[1, 3], [2, 6], [3, 8], [4, 1], [5, 4], [6, 7], [7, 5], [8, 2]]
[[1, 5], [2, 3], [3, 8], [4, 4], [5, 7], [6, 1], [7, 6], [8, 2]]
[[1, 5], [2, 7], [3, 4], [4, 1], [5, 3], [6, 8], [7, 6], [8, 2]]
[[1, 4], [2, 1], [3, 5], [4, 8], [5, 6], [6, 3], [7, 7], [8, 2]]
[[1, 3], [2, 6], [3, 4], [4, 1], [5, 8], [6, 5], [7, 7], [8, 2]]
[[1, 4], [2, 7], [3, 5], [4, 3], [5, 1], [6, 6], [7, 8], [8, 2]]
[[1, 6], [2, 4], [3, 2], [4, 8], [5, 5], [6, 7], [7, 1], [8, 3]]
[[1, 6], [2, 4], [3, 7], [4, 1], [5, 8], [6, 2], [7, 5], [8, 3]]
[[1, 1], [2, 7], [3, 4], [4, 6], [5, 8], [6, 2], [7, 5], [8, 3]]
[[1, 6], [2, 8], [3, 2], [4, 4], [5, 1], [6, 7], [7, 5], [8, 3]]
[[1, 6], [2, 2], [3, 7], [4, 1], [5, 4], [6, 8], [7, 5], [8, 3]]
[[1, 4], [2, 7], [3, 1], [4, 8], [5, 5], [6, 2], [7, 6], [8, 3]]
[[1, 5], [2, 8], [3, 4], [4, 1], [5, 7], [6, 2], [7, 6], [8, 3]]
[[1, 4], [2, 8], [3, 1], [4, 5], [5, 7], [6, 2], [7, 6], [8, 3]]
[[1, 2], [2, 7], [3, 5], [4, 8], [5, 1], [6, 4], [7, 6], [8, 3]]
[[1, 1], [2, 7], [3, 5], [4, 8], [5, 2], [6, 4], [7, 6], [8, 3]]
[[1, 2], [2, 5], [3, 7], [4, 4], [5, 1], [6, 8], [7, 6], [8, 3]]
[[1, 4], [2, 2], [3, 7], [4, 5], [5, 1], [6, 8], [7, 6], [8, 3]]
[[1, 5], [2, 7], [3, 1], [4, 4], [5, 2], [6, 8], [7, 6], [8, 3]]
[[1, 6], [2, 4], [3, 1], [4, 5], [5, 8], [6, 2], [7, 7], [8, 3]]
[[1, 5], [2, 1], [3, 4], [4, 6], [5, 8], [6, 2], [7, 7], [8, 3]]
[[1, 5], [2, 2], [3, 6], [4, 1], [5, 7], [6, 4], [7, 8], [8, 3]]
[[1, 6], [2, 3], [3, 7], [4, 2], [5, 8], [6, 5], [7, 1], [8, 4]]
[[1, 2], [2, 7], [3, 3], [4, 6], [5, 8], [6, 5], [7, 1], [8, 4]]
[[1, 7], [2, 3], [3, 1], [4, 6], [5, 8], [6, 5], [7, 2], [8, 4]]
[[1, 5], [2, 1], [3, 8], [4, 6], [5, 3], [6, 7], [7, 2], [8, 4]]
[[1, 1], [2, 5], [3, 8], [4, 6], [5, 3], [6, 7], [7, 2], [8, 4]]
[[1, 3], [2, 6], [3, 8], [4, 1], [5, 5], [6, 7], [7, 2], [8, 4]]
[[1, 6], [2, 3], [3, 1], [4, 7], [5, 5], [6, 8], [7, 2], [8, 4]]
[[1, 7], [2, 5], [3, 3], [4, 1], [5, 6], [6, 8], [7, 2], [8, 4]]
[[1, 7], [2, 3], [3, 8], [4, 2], [5, 5], [6, 1], [7, 6], [8, 4]]
[[1, 5], [2, 3], [3, 1], [4, 7], [5, 2], [6, 8], [7, 6], [8, 4]]
[[1, 2], [2, 5], [3, 7], [4, 1], [5, 3], [6, 8], [7, 6], [8, 4]]
[[1, 3], [2, 6], [3, 2], [4, 5], [5, 8], [6, 1], [7, 7], [8, 4]]
[[1, 6], [2, 1], [3, 5], [4, 2], [5, 8], [6, 3], [7, 7], [8, 4]]
[[1, 8], [2, 3], [3, 1], [4, 6], [5, 2], [6, 5], [7, 7], [8, 4]]
[[1, 2], [2, 8], [3, 6], [4, 1], [5, 3], [6, 5], [7, 7], [8, 4]]
[[1, 5], [2, 7], [3, 2], [4, 6], [5, 3], [6, 1], [7, 8], [8, 4]]
[[1, 3], [2, 6], [3, 2], [4, 7], [5, 5], [6, 1], [7, 8], [8, 4]]
[[1, 6], [2, 2], [3, 7], [4, 1], [5, 3], [6, 5], [7, 8], [8, 4]]
[[1, 3], [2, 7], [3, 2], [4, 8], [5, 6], [6, 4], [7, 1], [8, 5]]
[[1, 6], [2, 3], [3, 7], [4, 2], [5, 4], [6, 8], [7, 1], [8, 5]]
[[1, 4], [2, 2], [3, 7], [4, 3], [5, 6], [6, 8], [7, 1], [8, 5]]
[[1, 7], [2, 1], [3, 3], [4, 8], [5, 6], [6, 4], [7, 2], [8, 5]]
[[1, 1], [2, 6], [3, 8], [4, 3], [5, 7], [6, 4], [7, 2], [8, 5]]
[[1, 3], [2, 8], [3, 4], [4, 7], [5, 1], [6, 6], [7, 2], [8, 5]]
[[1, 6], [2, 3], [3, 7], [4, 4], [5, 1], [6, 8], [7, 2], [8, 5]]
[[1, 7], [2, 4], [3, 2], [4, 8], [5, 6], [6, 1], [7, 3], [8, 5]]
[[1, 4], [2, 6], [3, 8], [4, 2], [5, 7], [6, 1], [7, 3], [8, 5]]
[[1, 2], [2, 6], [3, 1], [4, 7], [5, 4], [6, 8], [7, 3], [8, 5]]
[[1, 2], [2, 4], [3, 6], [4, 8], [5, 3], [6, 1], [7, 7], [8, 5]]
[[1, 3], [2, 6], [3, 8], [4, 2], [5, 4], [6, 1], [7, 7], [8, 5]]
[[1, 6], [2, 3], [3, 1], [4, 8], [5, 4], [6, 2], [7, 7], [8, 5]]
[[1, 8], [2, 4], [3, 1], [4, 3], [5, 6], [6, 2], [7, 7], [8, 5]]
[[1, 4], [2, 8], [3, 1], [4, 3], [5, 6], [6, 2], [7, 7], [8, 5]]
[[1, 2], [2, 6], [3, 8], [4, 3], [5, 1], [6, 4], [7, 7], [8, 5]]
[[1, 7], [2, 2], [3, 6], [4, 3], [5, 1], [6, 4], [7, 8], [8, 5]]
[[1, 3], [2, 6], [3, 2], [4, 7], [5, 1], [6, 4], [7, 8], [8, 5]]
[[1, 4], [2, 7], [3, 3], [4, 8], [5, 2], [6, 5], [7, 1], [8, 6]]
[[1, 4], [2, 8], [3, 5], [4, 3], [5, 1], [6, 7], [7, 2], [8, 6]]
[[1, 3], [2, 5], [3, 8], [4, 4], [5, 1], [6, 7], [7, 2], [8, 6]]
[[1, 4], [2, 2], [3, 8], [4, 5], [5, 7], [6, 1], [7, 3], [8, 6]]
[[1, 5], [2, 7], [3, 2], [4, 4], [5, 8], [6, 1], [7, 3], [8, 6]]
[[1, 7], [2, 4], [3, 2], [4, 5], [5, 8], [6, 1], [7, 3], [8, 6]]
[[1, 8], [2, 2], [3, 4], [4, 1], [5, 7], [6, 5], [7, 3], [8, 6]]
[[1, 7], [2, 2], [3, 4], [4, 1], [5, 8], [6, 5], [7, 3], [8, 6]]
[[1, 5], [2, 1], [3, 8], [4, 4], [5, 2], [6, 7], [7, 3], [8, 6]]
[[1, 4], [2, 1], [3, 5], [4, 8], [5, 2], [6, 7], [7, 3], [8, 6]]
[[1, 5], [2, 2], [3, 8], [4, 1], [5, 4], [6, 7], [7, 3], [8, 6]]
[[1, 3], [2, 7], [3, 2], [4, 8], [5, 5], [6, 1], [7, 4], [8, 6]]
[[1, 3], [2, 1], [3, 7], [4, 5], [5, 8], [6, 2], [7, 4], [8, 6]]
[[1, 8], [2, 2], [3, 5], [4, 3], [5, 1], [6, 7], [7, 4], [8, 6]]
[[1, 3], [2, 5], [3, 2], [4, 8], [5, 1], [6, 7], [7, 4], [8, 6]]
[[1, 3], [2, 5], [3, 7], [4, 1], [5, 4], [6, 2], [7, 8], [8, 6]]
[[1, 5], [2, 2], [3, 4], [4, 6], [5, 8], [6, 3], [7, 1], [8, 7]]
[[1, 6], [2, 3], [3, 5], [4, 8], [5, 1], [6, 4], [7, 2], [8, 7]]
[[1, 5], [2, 8], [3, 4], [4, 1], [5, 3], [6, 6], [7, 2], [8, 7]]
[[1, 4], [2, 2], [3, 5], [4, 8], [5, 6], [6, 1], [7, 3], [8, 7]]
[[1, 4], [2, 6], [3, 1], [4, 5], [5, 2], [6, 8], [7, 3], [8, 7]]
[[1, 6], [2, 3], [3, 1], [4, 8], [5, 5], [6, 2], [7, 4], [8, 7]]
[[1, 5], [2, 3], [3, 1], [4, 6], [5, 8], [6, 2], [7, 4], [8, 7]]
[[1, 4], [2, 2], [3, 8], [4, 6], [5, 1], [6, 3], [7, 5], [8, 7]]
[[1, 6], [2, 3], [3, 5], [4, 7], [5, 1], [6, 4], [7, 2], [8, 8]]
[[1, 6], [2, 4], [3, 7], [4, 1], [5, 3], [6, 5], [7, 2], [8, 8]]
[[1, 4], [2, 7], [3, 5], [4, 2], [5, 6], [6, 1], [7, 3], [8, 8]]
[[1, 5], [2, 7], [3, 2], [4, 6], [5, 3], [6, 1], [7, 4], [8, 8]]
gescoe@computerdept:~/Documents/CL-1(CRB)/B1_8queen$ python 8queens.py
[[1, 3], [2, 1], [3, 4], [4, 2]]
[[1, 2], [2, 4], [3, 1], [4, 3]]
gescoe@computerdept:~/Documents/CL-1(CRB)/B1_8queen$ '''

queen.json

-----------------------------

[(1, 4), (2, 2), (3, 7), (4, 3), (5, 6), (6, 8), (7, 5), (8, 1)]
[(1, 5), (2, 2), (3, 4), (4, 7), (5, 3), (6, 8), (7, 6), (8, 1)]
[(1, 3), (2, 5), (3, 2), (4, 8), (5, 6), (6, 4), (7, 7), (8, 1)]
[(1, 3), (2, 6), (3, 4), (4, 2), (5, 8), (6, 5), (7, 7), (8, 1)]
[(1, 5), (2, 7), (3, 1), (4, 3), (5, 8), (6, 6), (7, 4), (8, 2)]
[(1, 4), (2, 6), (3, 8), (4, 3), (5, 1), (6, 7), (7, 5), (8, 2)]
[(1, 3), (2, 6), (3, 8), (4, 1), (5, 4), (6, 7), (7, 5), (8, 2)]
[(1, 5), (2, 3), (3, 8), (4, 4), (5, 7), (6, 1), (7, 6), (8, 2)]
[(1, 5), (2, 7), (3, 4), (4, 1), (5, 3), (6, 8), (7, 6), (8, 2)]
[(1, 4), (2, 1), (3, 5), (4, 8), (5, 6), (6, 3), (7, 7), (8, 2)]
[(1, 3), (2, 6), (3, 4), (4, 1), (5, 8), (6, 5), (7, 7), (8, 2)]
[(1, 4), (2, 7), (3, 5), (4, 3), (5, 1), (6, 6), (7, 8), (8, 2)]
[(1, 6), (2, 4), (3, 2), (4, 8), (5, 5), (6, 7), (7, 1), (8, 3)]
[(1, 6), (2, 4), (3, 7), (4, 1), (5, 8), (6, 2), (7, 5), (8, 3)]
[(1, 1), (2, 7), (3, 4), (4, 6), (5, 8), (6, 2), (7, 5), (8, 3)]
[(1, 6), (2, 8), (3, 2), (4, 4), (5, 1), (6, 7), (7, 5), (8, 3)]
[(1, 6), (2, 2), (3, 7), (4, 1), (5, 4), (6, 8), (7, 5), (8, 3)]
[(1, 4), (2, 7), (3, 1), (4, 8), (5, 5), (6, 2), (7, 6), (8, 3)]
[(1, 5), (2, 8), (3, 4), (4, 1), (5, 7), (6, 2), (7, 6), (8, 3)]
[(1, 4), (2, 8), (3, 1), (4, 5), (5, 7), (6, 2), (7, 6), (8, 3)]
[(1, 2), (2, 7), (3, 5), (4, 8), (5, 1), (6, 4), (7, 6), (8, 3)]
[(1, 1), (2, 7), (3, 5), (4, 8), (5, 2), (6, 4), (7, 6), (8, 3)]
[(1, 2), (2, 5), (3, 7), (4, 4), (5, 1), (6, 8), (7, 6), (8, 3)]
[(1, 4), (2, 2), (3, 7), (4, 5), (5, 1), (6, 8), (7, 6), (8, 3)]
[(1, 5), (2, 7), (3, 1), (4, 4), (5, 2), (6, 8), (7, 6), (8, 3)]
[(1, 6), (2, 4), (3, 1), (4, 5), (5, 8), (6, 2), (7, 7), (8, 3)]
[(1, 5), (2, 1), (3, 4), (4, 6), (5, 8), (6, 2), (7, 7), (8, 3)]
[(1, 5), (2, 2), (3, 6), (4, 1), (5, 7), (6, 4), (7, 8), (8, 3)]
[(1, 6), (2, 3), (3, 7), (4, 2), (5, 8), (6, 5), (7, 1), (8, 4)]
[(1, 2), (2, 7), (3, 3), (4, 6), (5, 8), (6, 5), (7, 1), (8, 4)]
[(1, 7), (2, 3), (3, 1), (4, 6), (5, 8), (6, 5), (7, 2), (8, 4)]
[(1, 5), (2, 1), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)]
[(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)]
[(1, 3), (2, 6), (3, 8), (4, 1), (5, 5), (6, 7), (7, 2), (8, 4)]
[(1, 6), (2, 3), (3, 1), (4, 7), (5, 5), (6, 8), (7, 2), (8, 4)]
[(1, 7), (2, 5), (3, 3), (4, 1), (5, 6), (6, 8), (7, 2), (8, 4)]
[(1, 7), (2, 3), (3, 8), (4, 2), (5, 5), (6, 1), (7, 6), (8, 4)]
[(1, 5), (2, 3), (3, 1), (4, 7), (5, 2), (6, 8), (7, 6), (8, 4)]
[(1, 2), (2, 5), (3, 7), (4, 1), (5, 3), (6, 8), (7, 6), (8, 4)]
[(1, 3), (2, 6), (3, 2), (4, 5), (5, 8), (6, 1), (7, 7), (8, 4)]
[(1, 6), (2, 1), (3, 5), (4, 2), (5, 8), (6, 3), (7, 7), (8, 4)]
[(1, 8), (2, 3), (3, 1), (4, 6), (5, 2), (6, 5), (7, 7), (8, 4)]
[(1, 2), (2, 8), (3, 6), (4, 1), (5, 3), (6, 5), (7, 7), (8, 4)]
[(1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 8), (8, 4)]
[(1, 3), (2, 6), (3, 2), (4, 7), (5, 5), (6, 1), (7, 8), (8, 4)]
[(1, 6), (2, 2), (3, 7), (4, 1), (5, 3), (6, 5), (7, 8), (8, 4)]
[(1, 3), (2, 7), (3, 2), (4, 8), (5, 6), (6, 4), (7, 1), (8, 5)]
[(1, 6), (2, 3), (3, 7), (4, 2), (5, 4), (6, 8), (7, 1), (8, 5)]
[(1, 4), (2, 2), (3, 7), (4, 3), (5, 6), (6, 8), (7, 1), (8, 5)]
[(1, 7), (2, 1), (3, 3), (4, 8), (5, 6), (6, 4), (7, 2), (8, 5)]
[(1, 1), (2, 6), (3, 8), (4, 3), (5, 7), (6, 4), (7, 2), (8, 5)]
[(1, 3), (2, 8), (3, 4), (4, 7), (5, 1), (6, 6), (7, 2), (8, 5)]
[(1, 6), (2, 3), (3, 7), (4, 4), (5, 1), (6, 8), (7, 2), (8, 5)]
[(1, 7), (2, 4), (3, 2), (4, 8), (5, 6), (6, 1), (7, 3), (8, 5)]
[(1, 4), (2, 6), (3, 8), (4, 2), (5, 7), (6, 1), (7, 3), (8, 5)]
[(1, 2), (2, 6), (3, 1), (4, 7), (5, 4), (6, 8), (7, 3), (8, 5)]
[(1, 2), (2, 4), (3, 6), (4, 8), (5, 3), (6, 1), (7, 7), (8, 5)]
[(1, 3), (2, 6), (3, 8), (4, 2), (5, 4), (6, 1), (7, 7), (8, 5)]
[(1, 6), (2, 3), (3, 1), (4, 8), (5, 4), (6, 2), (7, 7), (8, 5)]
[(1, 8), (2, 4), (3, 1), (4, 3), (5, 6), (6, 2), (7, 7), (8, 5)]
[(1, 4), (2, 8), (3, 1), (4, 3), (5, 6), (6, 2), (7, 7), (8, 5)]
[(1, 2), (2, 6), (3, 8), (4, 3), (5, 1), (6, 4), (7, 7), (8, 5)]
[(1, 7), (2, 2), (3, 6), (4, 3), (5, 1), (6, 4), (7, 8), (8, 5)]
[(1, 3), (2, 6), (3, 2), (4, 7), (5, 1), (6, 4), (7, 8), (8, 5)]
[(1, 4), (2, 7), (3, 3), (4, 8), (5, 2), (6, 5), (7, 1), (8, 6)]
[(1, 4), (2, 8), (3, 5), (4, 3), (5, 1), (6, 7), (7, 2), (8, 6)]
[(1, 3), (2, 5), (3, 8), (4, 4), (5, 1), (6, 7), (7, 2), (8, 6)]
[(1, 4), (2, 2), (3, 8), (4, 5), (5, 7), (6, 1), (7, 3), (8, 6)]
[(1, 5), (2, 7), (3, 2), (4, 4), (5, 8), (6, 1), (7, 3), (8, 6)]
[(1, 7), (2, 4), (3, 2), (4, 5), (5, 8), (6, 1), (7, 3), (8, 6)]
[(1, 8), (2, 2), (3, 4), (4, 1), (5, 7), (6, 5), (7, 3), (8, 6)]
[(1, 7), (2, 2), (3, 4), (4, 1), (5, 8), (6, 5), (7, 3), (8, 6)]
[(1, 5), (2, 1), (3, 8), (4, 4), (5, 2), (6, 7), (7, 3), (8, 6)]
[(1, 4), (2, 1), (3, 5), (4, 8), (5, 2), (6, 7), (7, 3), (8, 6)]
[(1, 5), (2, 2), (3, 8), (4, 1), (5, 4), (6, 7), (7, 3), (8, 6)]
[(1, 3), (2, 7), (3, 2), (4, 8), (5, 5), (6, 1), (7, 4), (8, 6)]
[(1, 3), (2, 1), (3, 7), (4, 5), (5, 8), (6, 2), (7, 4), (8, 6)]
[(1, 8), (2, 2), (3, 5), (4, 3), (5, 1), (6, 7), (7, 4), (8, 6)]
[(1, 3), (2, 5), (3, 2), (4, 8), (5, 1), (6, 7), (7, 4), (8, 6)]
[(1, 3), (2, 5), (3, 7), (4, 1), (5, 4), (6, 2), (7, 8), (8, 6)]
[(1, 5), (2, 2), (3, 4), (4, 6), (5, 8), (6, 3), (7, 1), (8, 7)]
[(1, 6), (2, 3), (3, 5), (4, 8), (5, 1), (6, 4), (7, 2), (8, 7)]
[(1, 5), (2, 8), (3, 4), (4, 1), (5, 3), (6, 6), (7, 2), (8, 7)]
[(1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 1), (7, 3), (8, 7)]
[(1, 4), (2, 6), (3, 1), (4, 5), (5, 2), (6, 8), (7, 3), (8, 7)]
[(1, 6), (2, 3), (3, 1), (4, 8), (5, 5), (6, 2), (7, 4), (8, 7)]
[(1, 5), (2, 3), (3, 1), (4, 6), (5, 8), (6, 2), (7, 4), (8, 7)]
[(1, 4), (2, 2), (3, 8), (4, 6), (5, 1), (6, 3), (7, 5), (8, 7)]
[(1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7, 2), (8, 8)]
[(1, 6), (2, 4), (3, 7), (4, 1), (5, 3), (6, 5), (7, 2), (8, 8)]
[(1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3), (8, 8)]
[(1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4), (8, 8)] 

=============================

Assignment No. B-2 TSP

=============================

 

Concurrent Implementation of travelling salesman problem.

 

Writeup:

TSP 

#include<stdio.h>
#include<iostream>
#include<omp.h>
using namespace std;
int graph[5][5],cost = 999;

void swap (int *x, int *y)

{

    int temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

void copy_array(int *a, int n)

{

    int i, sum = 0;
#pragma omp parallel for
    for(i = 0; i <= n; i++)

    {

        sum += graph[a[i % 5]][a[(i + 1) % 5]];

    }

    if (cost > sum)

    {

        cost = sum;

    }

} 

void permute(int *a, int i, int n)

{

   int j, k;

   if (i == n)

   {
 #pragma omp parallel sections
    {
        copy_array(a, n);
    }
   }

   else

   {
   
    #pragma omp parallel for
        for (j = i; j <= n; j++)

        {
   
   
        
   
                swap((a + i), (a + j));
       
   
            permute(a, i + 1, n);

            swap((a + i), (a + j));
   
        }

    }

}

int main()

{
   

  
     cout<<"Enter the elements for 5*5 array";
    for(int i=0;i<5;i++)
    {
        cout<<"\n Enter the elements of "<<i+1<< "th row :\t";
        for(int j=0;j<5;j++)
        {
            cin>>graph[i][j];
            cout<<"\t";
        }
        cout<<"\t";
    }


    int i, j;

       int a[] = {0, 1, 2, 3,4}; 

    int c = 0;
   

   permute(a, 0, 4);

   cout<<"\n\n\t\tminimum cost:"<<cost<<endl;



}

/*
gescoe@computerdept:~/Documents/CL-1(CRB)/B2_tsp$ g++ tspconcurrent.cpp -o tspconcurrent -fopenmp
gescoe@computerdept:~/Documents/CL-1(CRB)/B2_tsp$ ./tspconcurrent

Enter the elements for 5*5 array
 Enter the elements of 1th row :    -999 10 8 9 7
                       
 Enter the elements of 2th row :    10 -999 10 5 6
                       
 Enter the elements of 3th row :    8 10 -999 8 9
                       
 Enter the elements of 4th row :    9 5 8 -999 6
                       
 Enter the elements of 5th row :    7 6 9 6 -999
                       

        minimum cost:34

gescoe@gescoe-OptiPlex-3020:~/Desktop/BE37$
*/

=============================

Assignment No. B-3 Knapsack

=============================

/*---- 0/1 Knapsack using Branch and bound-----*/

#include <queue>
#include <iostream>
 #include <cstdlib>
using namespace std;

struct node
{
    int level;
    int profit;
    int weight;
    int bound;
};

int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa)
{
    int j = 0, k = 0;
    int totweight = 0;
    int result = 0;

    if (u.weight >= W)
    {
        return 0;
    }
    else
    {
        result = u.profit;
        j = u.level + 1;
        totweight = u.weight;

        while ((j < n) && (totweight + wVa[j] <= W))
        {
            totweight = totweight + wVa[j];
            result = result + pVa[j];
            j++;
        }

        k = j;

        if (k < n)
        {
            result = result + (W - totweight) * pVa[k]/wVa[k];
        }
        return result;
    }
}

int knapsack(int n, int p[], int w[], int W)
{
    queue<node> Q;
    node u, v;
    vector<int> pV;
    vector<int> wV;
    Q.empty();

    for (int i = 0; i < n; i++)
    {
        pV.push_back(p[i]);
        wV.push_back(w[i]);
    }

    v.level = -1; 
    v.profit = 0;
    v.weight = 0;

    int maxProfit = 0;

    //v.bound = bound(v, n, W, pV, wV);
    Q.push(v);

    while (!Q.empty())
    {
        v = Q.front();
        Q.pop();

        if (v.level == -1)
        {
            u.level = 0;
        }
        else if (v.level != (n - 1))
        {
            u.level = v.level + 1;
        }

        u.weight = v.weight + w[u.level];
        u.profit = v.profit + p[u.level];

        u.bound = bound(u, n, W, pV, wV);

        if (u.weight <= W && u.profit > maxProfit)
        {
            maxProfit = u.profit;
        }

        if (u.bound > maxProfit)
        {
            Q.push(u);
        }

        u.weight = v.weight;
        u.profit = v.profit;

        u.bound = bound(u, n, W, pV, wV);

        if (u.bound > maxProfit)
        {
            Q.push(u);
        }
    }
    return maxProfit;
}

int main()
{
    int maxProfit,n,p[10],w[10],W;

    cout << "Enter the number of items in a Knapsack:";
    cin >> n;

    for (int i = 0; i < n; i++)
    {

        cout << "Enter value and weight for item " << i << ": ";

        cin >> p[i];

        cin >> w[i];

    }

    cout << "Enter the capacity of knapsack : ";
    cin >> W;
   


    cout << "Output: "<< knapsack(n, p, w, W) << endl;
cout<<"\n";
    system("PAUSE");
}


/*-------------------------Output--------------------
gescoe@gescoe-OptiPlex-3020:~/Desktop/BE47$ g++ SIMPLE.cpp
gescoe@gescoe-OptiPlex-3020:~/Desktop/BE47$ ./a.out
Enter the number of items in a Knapsack:5
Enter value and weight for item 0:1 20
Enter value and weight for item 1:2 30
Enter value and weight for item 2:4 06
Enter value and weight for item 3:9 92
Enter value and weight for item 4:7 10
Enter the capacity of knapsack50
Output: 13
*/

 

=============================

Assignment No. B-4 Code Optimization

=============================

 

Code optimization using DAG.

 

Writeup:

Code optimization 

 

codeopt.l

-------------------

/*------------------------------- .l FILE ----------------------------*/

%{
#include<stdio.h>
#include<math.h>
#include "y.tab.h"
%}
%%
[a-zA-Z0-9] {yylval.dval=yytext[0];return NUM;}
[\t];
\n return NL;
. {return yytext[0];}
%%

/*
gescoe@computerdept:~$ cd Documents/CL-1\(CRB\)/B4_codeopt/
gescoe@computerdept:~/Documents/CL-1(CRB)/B4_codeopt$ ./a.out

 Optimized Code is =>
 A=1*2
 C=A+A
 D=3*4
 E=C+D
 G=E+A
 J=G+Dgescoe@computerdept:~/Documents/CL-1(CRB)/B4_codeopt$

*/

codeopt.y

-----------------------------

/* A. NO : 14
   TITLE : Write a program to given any intermediate code form implement
                 code optimization technique.
   ROLL NO :              BATCH :                          */

/*-------------------------------------- .y FILE ---------------------------------*/

%{
#include<stdio.h>
int yylex(void);
char r1[20],r2[20],r3[20],l[20],rr1[20],rr2[20],rr3[20],ll[20];
char w,x,y,z;
int k=0,i,j,p=0,flag[20],pk[20];
%}

%union
{
    char dval;
}
%token <dval> NUM
%token <dval> NL
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS
%type <dval> S
%type <dval> E
%%
S : N '=' E LINE {}
  | {
    for(i=0;i<20;i++)     
        pk[i]=flag[i]=0;

    /*    r1[],r2[],r3[] are the arrays used to store character
                          on RHS of '=' of 3 address generated code.
          l[] array used for storing LHS character of expression 
                         of 3 address generated code.               

          rr1[],rr2[],rr3[] are the arrays used to store character
                         on RHS of '=' of optimized code.
          ll[] array used for storing LHS character of expression
                         of optimized code.                

          pk[] is array for replacement in optimization.
           flag[] is array used to check whether RHS of expression
                         is repeated or not.
       
          w,x,y,z are the characters used for elliminating Dead
                         code generation in optimized code.

    */
for(i=0;i<k;i++)
{
    for(j=i+1;j<k;j++)
    {
      if(r1[i]==r1[j] && r2[i]==r2[j] && r3[i]==r3[j] && flag[j]!=1)
         {
            flag[j]=1;
            pk[j]=i;
         }
      }
}
for(i=0;i<k;i++)
{
   if(flag[i]!=1)
    {
        x=rr1[p]=r1[i];
        y=rr2[p]=r2[i];
        z=rr3[p]=r3[i];
        ll[p]=l[i];
        p++;
    }
    else
    {
        rr1[p]='\0';
        rr2[p]='\0';
        rr3[p]='\0';
        ll[p]='\0';
        p++;
      }
}

for(i=0;i<p;i++)
{
  if(flag[i]==1)
   {
     for(j=0;j<p;j++)
    {
      if(rr1[j]==l[i])
      rr1[j]=l[pk[i]];
      if(rr3[j]==l[i])
      z=rr3[j]=l[pk[i]];
     }
   }
}
   
printf("\n Optimized Code is => ");
for(i=0;i<p-1;i++)
{
   if(ll[i]!='\0' || rr1[i]!='\0' || rr2[i]!='\0' || rr3[i]!='\0')
    {
      printf("\n %C=%C%C%C",ll[i],rr1[i],rr2[i],rr3[i]);
    }
}
 printf("\n %C=%C%C%C",w,x,y,z);
}
  ;
N : NUM {w=l[k]=$1;}
  ;
LINE : NL S {}
     | {}
     ;
E : NUM {$$=$1;}
  | E '+' E {r1[k]=$1;r2[k]='+';r3[k]=$3;k++;}
  | E '-' E {r1[k]=$1;r2[k]='-';r3[k]=$3;k++;}
  | E '*' E {r1[k]=$1;r2[k]='*';r3[k]=$3;k++;}
  | E '/' E {r1[k]=$1;r2[k]='/';r3[k]=$3;k++;}
  ;
%%
FILE *yyin;


main()
{
FILE *fpInput;
FILE *fpOut;

fpInput=fopen("ip.txt","r");
if(fpInput=='\0')   
{
    printf("file read error");
}

fpOut=fopen("a14op.txt","w");
if(fpOut=='\0')
{
printf("file creation error");
//exit(0);
}
yyin=fpInput;
yyparse();
fcloseall();
}

yyerror(char *msg)

{
    printf("%s\n",msg);
}

yywrap()
{
return 1;
}

ip.txt

-------------------

A=1*2
B=1*2
C=A+B
D=3*4
E=C+D
F=1*2
G=E+F
H=3*4
I=G+H
J=I

 

 

=============================

Assignment No. B-5 Code Generation

=============================

/*
Assignment no.    :
Problem Statement : Generate the target code for optimized three
                    address code
class:BE(B) 09


//--------------------target.l------------------------------------*/

%{
#include"stdio.h"
#include"y.tab.h"
%}

%%

[a-z][a-zA-Z0-9]* |
[0-9]+                  {
                                strcpy(yylval.vname,yytext);
                                return NAME;
                        }

[ |\t]                  ;

.|\n                    { return yytext[0]; }

%%

yacctarget.y

-----------------------------

%{

#include"stdio.h"
FILE *fpOut;

%}

%union
{
        char vname[10];
        int val;
}

%left '+' '-'
%left '*' '/'

%token <vname> NAME
%type <vname> expression

%%

input   : line '\n' input
          | '\n' input
          | ;


line    : NAME '=' expression  {
                                  fprintf(fpOut,"MOV %s, AX\n",$1);
                                         }
        ;


expression: NAME '+' NAME      {
                                  fprintf(fpOut,"MOV AX, %s\n",$1);
                                  fprintf(fpOut,"ADD AX, %s\n",$3);
                                         }

          | NAME '-' NAME        {
                                  fprintf(fpOut,"MOV AX, %s\n",$1);
                                  fprintf(fpOut,"SUB AX, %s\n",$3);
                                         }

          | NAME '*' NAME        {
                                  fprintf(fpOut,"MOV AX, %s\n",$1);
                                  fprintf(fpOut,"MUL AX, %s\n",$3);
                                         }

          | NAME '/' NAME        {
                                  fprintf(fpOut,"MOV AX, %s\n",$1);
                                  fprintf(fpOut,"DIV AX, %s\n",$3);
                                         }
          | NAME                 {
                                  fprintf(fpOut,"MOV AX, %s\n",$1);
                                  strcpy($$, $1);
                                         }
          ;

%%

FILE *yyin;
main()
{
        FILE *fpInput;

        fpInput = fopen("ip.txt","r");
        if(fpInput=='\0')
        {
                printf("file read error");
                exit(0);
        }
        fpOut = fopen("op.txt","w");
        if(fpOut=='\0')
        {
                printf("file creation error");
                exit(0);
        }
        yyin = fpInput;
        yyparse();
        fcloseall();
}


yyerror(char *msg)
{
        printf("%s",msg);
}

ip.tx

-------------------

t1 = b * c
t2 = t1 / d
t3 = a + t2
t4 = t3 - e
f = t4

op.txt

----------------------

 

MOV AX, b
MUL AX, c
MOV t1, AX
MOV AX, t1
DIV AX, d
MOV t2, AX
MOV AX, a
ADD AX, t2
MOV t3, AX
MOV AX, t3
SUB AX, e
MOV t4, AX
MOV AX, t4
MOV f, AX

 

 

=============================

Assignment No. B-6 

=============================

 

Generating abstract syntax tree using LEX and YACC.

Writeup:

Lex and Yacc

 

=============================

Assignment No. B-7 AST

=============================

 ast.l

-------------------------

%{
#include "y.tab.h"
%}


%%

[0-9]+                {yylval = (int)yytext; return NUMBER;}
                       /* cast pointer to int for compiler warning */
[ \t\n]               ;
"+"      return(PLUS);
"-"      return(MINUS);
"*"      return(TIMES);
"/"      return(DIVIDE);
"^"      return(POWER);
"("      return(LEFT_PARENTHESIS);
")"      return(RIGHT_PARENTHESIS);
";"      return(END);


%%

int yywrap (void) {return 1;}


/*
gescoe@computerdept:~/Documents/CL-1(CRB)/B6$ lex ast.l
gescoe@computerdept:~/Documents/CL-1(CRB)/B6$ yacc -d ast.y
ast.y:49 parser name defined to default :"parse"
gescoe@computerdept:~/Documents/CL-1(CRB)/B6$ gcc lex.yy.c y.tab.c -ll -ly
gescoe@computerdept:~/Documents/CL-1(CRB)/B6$ ./a.out
(9+8*7+9-2);
( - ( + ( +  9 ( *  8  7 )) 9 ) 2 )

*/

ast.y

------------------------

%{

#include <stdio.h>

  typedef struct node
  {
    struct node *left;
    struct node *right;
    char *token;
  } node;
  node *mknode(node *left, node *right, char *token);
  void printtree(node *tree);

#define YYSTYPE struct node *

%}

%start lines

%token    NUMBER
%token    PLUS    MINUS    TIMES    DIVIDE    POWER
%token    LEFT_PARENTHESIS    RIGHT_PARENTHESIS
%token    END

%left    PLUS    MINUS
%left    TIMES    DIVIDE
%right    POWER

%%

lines:  /* empty */
        | lines line /* do nothing */

line:   exp END        { printtree($1); printf("\n");}
    ;

exp    : term             {$$ = $1;}
        | exp PLUS term     {$$ = mknode($1, $3, "+");}
        | exp MINUS term    {$$ = mknode($1, $3, "-");}
        ;

term   : factor           {$$ = $1;}
        | term TIMES factor  {$$ = mknode($1, $3, "*");}
        ;

factor : NUMBER           {$$ = mknode(0,0,(char *)yylval);}
        | LEFT_PARENTHESIS exp RIGHT_PARENTHESIS {$$ = $2;}
        ;
%%

int main (void) {return yyparse ( );}

node *mknode(node *left, node *right, char *token)
{
  /* malloc the node */
  node *newnode = (node *)malloc(sizeof(node));
  char *newstr = (char *)malloc(strlen(token)+1);
  strcpy(newstr, token);
  newnode->left = left;
  newnode->right = right;
  newnode->token = newstr;
  return(newnode);
}

void printtree(node *tree)
{
  int i;


  if (tree->left || tree->right)
    printf("(");

  printf(" %s ", tree->token);

  if (tree->left)
    printtree(tree->left);
  if (tree->right)
    printtree(tree->right);

  if (tree->left || tree->right)
    printf(")");
}

int yyerror (char *s) {fprintf (stderr, "%s\n", s);}

 

=============================

Assignment No. B-7 Recursive descent parser

=============================

 

 

/* The grammar on which recursive descent parser is impelemented

E->E+T|T
T->T*F|F
F->(E)|id

First to eliminate left recursion

E->TE'
E'->+TE'|epsilon
T->FT'
T'->*FT'|epsilon
F->(E) | id

*/

#include<iostream>
#include<string.h>
#include<ctype.h>

using namespace std;

char input[10];
int i,error;
void E();
void T();
void Edash();
void Tdash();
void F();

int main()
{
    i=0;
    error=0;
    cout<<"Enter the arithmatic expression: ";   //eg. a+a*a;
    cin>>input;
    E();
    if(strlen(input)==i &&(error==0))
        cout<<input<<"\tString is Accepted !!!\n";
    else
        cout<<input<<"\tString is not Accepted !!!!\n";   
    return 0;
}

void E()
{
    T();
    Edash();
}


void Edash()
{
    if(input[i]=='+')
    {
        i++;
        T();
        Edash();
    }

}

void T()
{
    F();
    Tdash();
}


void Tdash()
{
    if(input[i]=='*')
    {
        i++;
        F();
        Tdash();
    }

}

void F()
{
    if(isalnum(input[i]))i++;
    else if(input[i]=='(')
    {
        i++;
        E();
        if(input[i]==')')
        i++;
        else
            error=1;
    }
    else
        error=1;
}

=============================

Assignment No. B-8 Simple LR

=============================

 

Write a program to implement SLR Parsing algorithm using Python for the ordered input Set
in XML.
{P->E,E->E+T,E->T,T->T*F,T->F,F->(E),F->i,END}

 

Writeup:

Simple LR 

 slr.c

---------------------------

/* C program to implement Simple LR Parser. */

#include<stdio.h>
#include<string.h>

int i,j,k,m,n=0,o,p,ns=0,tn=0,rr=0,ch=0;
char read[15][10],gl[15],gr[15][10],temp,templ[15],tempr[15][10],*ptr,temp2[5],dfa[15][15];

struct states
{
    char lhs[15],rhs[15][10];
    int n;
}I[15];

int compstruct(struct states s1,struct states s2)
{
    int t;
    if(s1.n!=s2.n)
        return 0;
    if( strcmp(s1.lhs,s2.lhs)!=0 )
        return 0;
    for(t=0;t<s1.n;t++)
        if( strcmp(s1.rhs[t],s2.rhs[t])!=0 )
            return 0;
    return 1;
}

void moreprod()
{
    int r,s,t,l1=0,rr1=0;
    char *ptr1,read1[15][10];

    for(r=0;r<I[ns].n;r++)
    {
        ptr1=strchr(I[ns].rhs[l1],'.');
        t=ptr1-I[ns].rhs[l1];
        if( t+1==strlen(I[ns].rhs[l1]) )
        {
            l1++;
            continue;
        }
        temp=I[ns].rhs[l1][t+1];
        l1++;
        for(s=0;s<rr1;s++)
            if( temp==read1[s][0] )
                break;
        if(s==rr1)
        {
            read1[rr1][0]=temp;
            rr1++;
        }
        else
            continue;

        for(s=0;s<n;s++)
        {
            if(gl[s]==temp)
            {
                I[ns].rhs[I[ns].n][0]='.';
                I[ns].rhs[I[ns].n][1]=NULL;
                strcat(I[ns].rhs[I[ns].n],gr[s]);
                I[ns].lhs[I[ns].n]=gl[s];
                I[ns].lhs[I[ns].n+1]=NULL;
                I[ns].n++;
            }
        }
    }
}

void canonical(int l)
{
    int t1;
    char read1[15][10],rr1=0,*ptr1;
    for(i=0;i<I[l].n;i++)
    {
        temp2[0]='.';
        ptr1=strchr(I[l].rhs[i],'.');
        t1=ptr1-I[l].rhs[i];
        if( t1+1==strlen(I[l].rhs[i]) )
            continue;

        temp2[1]=I[l].rhs[i][t1+1];
        temp2[2]=NULL;

        for(j=0;j<rr1;j++)
            if( strcmp(temp2,read1[j])==0 )
                break;
        if(j==rr1)
        {
            strcpy(read1[rr1],temp2);
            read1[rr1][2]=NULL;
            rr1++;
        }
        else
            continue;

        for(j=0;j<I[0].n;j++)
        {
            ptr=strstr(I[l].rhs[j],temp2);
            if( ptr )
            {
                templ[tn]=I[l].lhs[j];
                templ[tn+1]=NULL;
                strcpy(tempr[tn],I[l].rhs[j]);
                tn++;
            }
        }

        for(j=0;j<tn;j++)
        {
            ptr=strchr(tempr[j],'.');
            p=ptr-tempr[j];
            tempr[j][p]=tempr[j][p+1];
            tempr[j][p+1]='.';
            I[ns].lhs[I[ns].n]=templ[j];
            I[ns].lhs[I[ns].n+1]=NULL;
            strcpy(I[ns].rhs[I[ns].n],tempr[j]);
            I[ns].n++;
        }

        moreprod();
        for(j=0;j<ns;j++)
        {
            //if ( memcmp(&I[ns],&I[j],sizeof(struct states))==1 )
            if( compstruct(I[ns],I[j])==1 )
            {
                I[ns].lhs[0]=NULL;
                for(k=0;k<I[ns].n;k++)
                    I[ns].rhs[k][0]=NULL;
                I[ns].n=0;
                dfa[l][j]=temp2[1];
                break;
            }
        }
        if(j<ns)
        {
            tn=0;
            for(j=0;j<15;j++)
            {
                templ[j]=NULL;
                tempr[j][0]=NULL;
            }
            continue;
        }

        dfa[l][j]=temp2[1];
        printf("\n\nI%d :",ns);
        for(j=0;j<I[ns].n;j++)
            printf("\n\t%c -> %s",I[ns].lhs[j],I[ns].rhs[j]);
       
        ns++;
        tn=0;
        for(j=0;j<15;j++)
        {
            templ[j]=NULL;
            tempr[j][0]=NULL;
        }
    }
}

void main()
{
    FILE *f;
    int l;
   

    for(i=0;i<15;i++)
    {
        I[i].n=0;
        I[i].lhs[0]=NULL;
        I[i].rhs[0][0]=NULL;
        dfa[i][0]=NULL;
    }

    f=fopen("ip.txt","r");
    while(!feof(f))
    {
        fscanf(f,"%c",&gl[n]);
        fscanf(f,"%s\n",gr[n]);
        n++;
    }

    printf("THE GRAMMAR IS AS FOLLOWS\n");
    for(i=0;i<n;i++)
        printf("\t\t\t\t%c -> %s\n",gl[i],gr[i]);

    I[0].lhs[0]='Z';
    strcpy(I[0].rhs[0],".S");
    I[0].n++;
    l=0;
    for(i=0;i<n;i++)
    {
        temp=I[0].rhs[l][1];
        l++;
        for(j=0;j<rr;j++)
            if( temp==read[j][0] )
                break;
        if(j==rr)
        {
            read[rr][0]=temp;
            rr++;
        }
        else
            continue;
        for(j=0;j<n;j++)
        {
            if(gl[j]==temp)
            {
                I[0].rhs[I[0].n][0]='.';
                strcat(I[0].rhs[I[0].n],gr[j]);
                I[0].lhs[I[0].n]=gl[j];
                I[0].n++;
            }
        }
    }
    ns++;

    printf("\nI%d :\n",ns-1);
    for(i=0;i<I[0].n;i++)
        printf("\t%c -> %s\n",I[0].lhs[i],I[0].rhs[i]);

    for(l=0;l<ns;l++)
        canonical(l);

    printf("\n\n\t\tPRESS ANY KEY FOR DFA TABLE");
  

    printf("\t\t\tDFA TABLE IS AS FOLLOWS\n\n\n");
    for(i=0;i<ns;i++)
    {
        printf("I%d : ",i);
        for(j=0;j<ns;j++)
            if(dfa[i][j]!='\0')
                printf("'%c'->I%d | ",dfa[i][j],j);
        printf("\n\n\n");
    }
    printf("\n\n\n\t\tPRESS ANY KEY TO EXIT");
   
}

ip.txt

-------------------

S S+T
S T
T T*F
T F
F (S)
F t

op.txt

-------------------

gescoe@computerdept:~$ cd Documents/CL-1\(CRB\)/B8_SLR/
gescoe@computerdept:~/Documents/CL-1(CRB)/B8_SLR$ ./a.out
THE GRAMMAR IS AS FOLLOWS
                S -> S+T
                S -> T
                T -> T*F
                T -> F
                F -> (S)
                F -> t

I0 :
    Z -> .S
    S -> .S+T
    S -> .T
    T -> .T*F
    T -> .F
    F -> .(S)
    F -> .t


I1 :
    Z -> S.
    S -> S.+T

I2 :
    S -> T.
    T -> T.*F

I3 :
    T -> F.

I4 :
    F -> (.S)
    S -> .S+T
    S -> .T
    T -> .T*F
    T -> .F
    F -> .(S)
    F -> .t

I5 :
    F -> t.

I6 :
    S -> S+.T
    T -> .T*F
    T -> .F
    F -> .(S)
    F -> .t

I7 :
    T -> T*.F
    F -> .(S)
    F -> .t

I8 :
    F -> (S.)
    S -> S.+T

I9 :
    S -> S+T.
    T -> T.*F

I10 :
    T -> T*F.

I11 :
    F -> (S).

        PRESS ANY KEY FOR DFA TABLE            DFA TABLE IS AS FOLLOWS


I0 : 'S'->I1 | 'T'->I2 | 'F'->I3 | '('->I4 | 't'->I5 |


I1 : '+'->I6 |


I2 : '*'->I7 |


I3 :


I4 : 'T'->I2 | 'F'->I3 | '('->I4 | 't'->I5 | 'S'->I8 |


I5 :


I6 : 'F'->I3 | '('->I4 | 't'->I5 | 'T'->I9 |


I7 : '('->I4 | 't'->I5 | 'F'->I10 |


I8 : '+'->I6 | ')'->I11 |


I9 : '*'->I7 |


I10 :


I11 :





        PRESS ANY KEY TO EXIT 

 

=============================

Assignment No. D-2 Apriori

=============================

#include<iostream>
using namespace std;

int main()
{
int i,j,t1,k,l,f1,f2,f3;


//Initial item-purchase
int a[5][6];
for(i=0;i<5;i++)
{
    cout<<"\n Enter items for Transaction T"<<i+1<<": ";
    for(j=0;j<6;j++)
    {
    cin>>a[i][j];
    }
}
//Defining minimum level for acceptence
int min;
cout<<"\n Enter minimum support : ";
cin>>min;
//Printing initial input
cout<<"Initial Input";
cout<<"\n----------------------------------------------------------";
cout<<"\nTrasaction\t\tItems\n";
cout<<"----------------------------------------------------------\n";
for(i=0;i<5;i++)
{
    cout<<"T"<<i+1<<"\t\t";
    for(j=0;j<6;j++)
    {
    cout<<a[i][j]<<"\t";
    }
    cout<<"\n";
}
cout<<"----------------------------------------------------------\n";
cout<<"\nAssume minimum support: "<<min;

//First pass
int l1[11];
for(i=0;i<11;i++)
{
    t1=0;
    for(j=0;j<5;j++)
    {
        for(k=0;k<6;k++)
        {
            if(a[j][k]==i+1)
            {
            t1++;
            }
        }
    }
    l1[i]=t1;
}
//Printing first pass
cout<<"\n\nGenerating Candidate item (CL1)\n";
cout<<"item set\tSupport\n\n";
for(i=0;i<11;i++)
{
cout<<" "<<i+1<<"\t\t"<<l1[i]<<"\n";
}

//Second pass
//Counting number of possibilities for pass2
int p2pcount=0;
int p2items[11];
int p2pos=0;
for(i=0;i<11;i++)
{
if(l1[i]>=min)
{
p2pcount++;
p2items[p2pos]=i;
p2pos++;
}
}
//Printing selected items for second pass
cout<<"\nGenerating Frequent item set (L1)\n";
cout<<"item set\tSupport\n\n";
for(i=0;i<p2pos;i++)
{
cout<<"  "<<p2items[i]+1<<"\t\t"<<l1[p2items[i]]<<"\n";
}

//Joining items
int l2[5][3];
int l2t1; //will hold first item for join
int l2t2; //will hold second item for join
int l2pos1=0; //position pointer in l2 array
int l2ocount=0; //product join occruance counter
int l2jcount=0; //join counter
for(i=0;i<p2pcount;i++)
{
for(j=i+1;j<p2pcount;j++)
{
l2t1=p2items[i]+1;
l2t2=p2items[j]+1;
if(l2t1==l2t2)
{
//it is self join
continue;
}
//join the elements
l2[l2pos1][0]=l2t1;
l2[l2pos1][1]=l2t2;
l2jcount++;
//count occurances
l2ocount=0; //reset counter
for(k=0;k<5;k++)
{
    f1=f2=0; //resetting flag
    //scan a purcahse
    for(l=0;l<6;l++)
    {
        if(l2t1==a[k][l])
        {
        //one of the element found
        f1=1;
        }
        if(l2t2==a[k][l])
        {
        //second elements also found
        f2=1;
        }
    }
    //one purchase scanned
    if(f1==1&&f2==1) //both items are present in purchase
    {
    l2ocount++;
    }
}
//assign count
l2[l2pos1][2]=l2ocount;
l2pos1++;
}
}
//Printing second pass
cout<<"\n\nGenerating Candidate item (CL2)\n";
cout<<"item set\tSupport\n\n";
for(i=0;i<l2jcount;i++)
{
    for(j=0;j<3;j++)
    {
    cout<<l2[i][j]<<"\t";
    }
    cout<<"\n";
}



//Third pass
int p3pcount=0;
int p3items[11];
int p3pos=0;

for(i=0;i<11;i++)
{
    if(l2[i][2]>=min)
    {
    p3pcount++;
    p3items[p3pos]=i;
    p3pos++;
    }
}
//Printing selected items for second pass
cout<<"\nGenerating Frequent item set (L2)\n";
cout<<"item set\tSupport\n\n";
for(i=0;i<p3pos;i++)
{
cout<<l2[p3items[i]][0]<<"\t"<<l2[p3items[i]][1]<<"\t"<<l2[p3items[i]][2]<<"\n";
}


//Joining
int l3[5][4];
int l3ocount=0; //occurance counter
int l3jcount=0; //join counter
for(i=0;i<p3pcount;i++)
{
for(j=i+1;j<p3pcount;j++)
{
    for(k=j+1;k<p3pcount;k++)
    {
        l3[i][0]=l2[p3items[i]][0];
        l3[i][1]=l2[p3items[i]][1];
        if(l2[p3items[i]][1]==l2[p3items[j]][0])
        {
            l3[i][2]=l2[p3items[j]][1];
            l3jcount++;
        }
       
        //count occurances
        l3ocount=0; //reset counter
        for(k=0;k<5;k++)
        {
            f1=f2=f3=0; //resetting flag
            //scan a purcahse
            for(l=0;l<6;l++)
            {
                if(l3[i][0]==a[k][l])
                {
                //one of the element found
                f1=1;
                }
                if(l3[i][1]==a[k][l])
                {
                //second elements also found
                f2=1;
                }
                if(l3[i][2]==a[k][l])
                {
                //second elements also found
                f3=1;
                }

            }
            //one purchase scanned
            if(f1==1&&f2==1&&f3==1) //all items are present in purchase
            {
            l3ocount++;
            }
        }

        //assign count
        l3[i][3]=l3ocount;
        }
}
}
//Printing second pass
cout<<"\n\nGenerating Candidate item (CL3)\n";
cout<<"Item set\t\tSupport\n\n";
for(i=0;i<l3jcount;i++)
{
    for(j=0;j<4;j++)
    {
    cout<<l3[i][j]<<"\t";
    }
cout<<"\n";
}

//Ending
return 0;
}

/*
------------------------------
OUTPUT

[nishi@localhost apriori]$ g++ apriori.cpp
[nishi@localhost apriori]$ ./a.out

 Enter items for Transaction T1: 1
2
3
4
5
6

 Enter items for Transaction T2: 7
2
3
4
5
6

 Enter items for Transaction T3: 1
8
4
5
0
0

 Enter items for Transaction T4: 1
9
10
4
6
0

 Enter items for Transaction T5: 10
2
2
4
11
5

 Enter minimum support : 3
Initial Input
----------------------------------------------------------
Trasaction        Items
----------------------------------------------------------
T1        1    2    3    4    5    6   
T2        7    2    3    4    5    6   
T3        1    8    4    5    0    0   
T4        1    9    10    4    6    0   
T5        10    2    2    4    11    5   
----------------------------------------------------------

Assume minimum support: 3

Generating Candidate item (CL1)
item set    Support

 1          3
 2          4
 3          2
 4          5
 5          4
 6          3
 7          1
 8          1
 9          1
 10          2
 11          1

Generating Frequent item set (L1)
item set    Support

  1        3
  2        4
  4        5
  5        4
  6        3


Generating Candidate item (CL2)
item set    Support

1    2    1       
1    4    3       
1    5    2       
1    6    2       
2    4    3       
2    5    3       
2    6    2       
4    5    4       
4    6    3       
5    6    2       

Generating Frequent item set (L2)
item set    Support

1    4    3
2    4    3
2    5    3
4    5    4
4    6    3


Generating Candidate item (CL3)
Item set        Support

1    4    5    2   
2    4    5    3   
[nishi@localhost apriori]$
*/

=============================

Assignment No. D-3 Decision tree

=============================

Decisiontreeapp.java

-------------------------------------

// DECISION TREE  APPLICATION
// Frans Coenen
// Thursday 15 August 2002
// Department of Computer Science, University of Liverpool

import java.io.*;

class DecisionTreeApp {

    /* ------------------------------- */
    /*                                 */
    /*              FIELDS             */
    /*                                 */
    /* ------------------------------- */

    static BufferedReader keyboardInput = new
                           BufferedReader(new InputStreamReader(System.in));
    static DecisionTree newTree;

    /* --------------------------------- */
    /*                                   */
    /*               METHODS             */
    /*                                   */
    /* --------------------------------- */

    /* MAIN */

    public static void main(String[] args) throws IOException {

        // Create instance of class DecisionTree

        newTree = new DecisionTree();

        // Generate tree

        generateTree();

        // Output tree

        System.out.println("\nOUTPUT DECISION TREE");
        System.out.println("====================");
        newTree.outputBinTree();

        // Query tree

        queryTree();
        }

    /* GENERATE TREE */

    static void generateTree() {
        System.out.println("\nGENERATE DECISION TREE");
        System.out.println("======================");
        newTree.createRoot(1,"Semisterwise Computer Branch Subject");
        newTree.addYesNode(1,2,"Semister-1?");
        newTree.addNoNode(1,3,"Semister-2?");
        newTree.addYesNode(2,4,"Elective");
     newTree.addYesNode(4,8," Subject is DMT");
     newTree.addNoNode(4,9,"Subject is PC");
    newTree.addNoNode(2,5,"Compulsory Subject");
    // newTree.addYesNode(5,10,"Subject is SSDA");

     newTree.addYesNode(5,10,"Subject is PMCD");
    newTree.addNoNode(5,11,"Subject is DAA");

        newTree.addYesNode(3,6,"Elective");
    newTree.addYesNode(6,12,"Elective-1");
    newTree.addNoNode(6,13,"Elective-2");

        newTree.addNoNode(3,7,"Compulsory Subject");
    newTree.addYesNode(7,14,"Subject is SDMT");
    newTree.addNoNode(7,15,"Subject is HPC");
        }

    /* QUERY TREE */
   
    static void queryTree() throws IOException {
        System.out.println("\nQUERY DECISION TREE");
        System.out.println("===================");
        newTree.queryBinTree();

        // Option to exit

        optionToExit();
        }

    /* OPTION TO EXIT PROGRAM */

    static void optionToExit() throws IOException {
        System.out.println("Exit? (enter \"Yes\" or \"No\")");
        String answer = keyboardInput.readLine();
        if (answer.equals("Yes")) return;
        else {
            if (answer.equals("No")) queryTree();
            else {
                System.out.println("ERROR: Must answer \"Yes\" or \"No\"");
                optionToExit();
                }
            }
        }
    }

op.txt

----------------------

http://www.markhneedham.com/blog/2015/02/24/pythonnltk-naive-vs-naive-bayes-vs-decision-tree/
http://webdocs.cs.ualberta.ca/~aixplore/learning/DecisionTrees/InterArticle/4-DecisionTree.html
gescoe@computerdept:~/Downloads$ javac DecisionTreeApp.java
gescoe@computerdept:~/Downloads$ java DecisionTreeApp

GENERATE DECISION TREE
======================
Created root node 1
Added node 2 onto "yes" branch of node 1
Added node 3 onto "no" branch of node 1
Added node 4 onto "yes" branch of node 2
Added node 8 onto "yes" branch of node 4
Added node 9 onto "no" branch of node 4
Added node 5 onto "no" branch of node 2
Added node 10 onto "yes" branch of node 5
Added node 11 onto "no" branch of node 5
Added node 6 onto "yes" branch of node 3
Added node 12 onto "yes" branch of node 6
Added node 13 onto "no" branch of node 6
Added node 7 onto "no" branch of node 3
Added node 14 onto "yes" branch of node 7
Added node 15 onto "no" branch of node 7

OUTPUT DECISION TREE
====================
[1] nodeID = 1, question/answer = Branch Computer
[1.1] nodeID = 2, question/answer = Semister-1?
[1.1.1] nodeID = 4, question/answer = Elective
[1.1.1.1] nodeID = 8, question/answer =  Subject is DMT
[1.1.1.2] nodeID = 9, question/answer = Subject is PC
[1.1.2] nodeID = 5, question/answer = Compulsory Subject
[1.1.2.1] nodeID = 10, question/answer = Subject is PMCD
[1.1.2.2] nodeID = 11, question/answer = Subject is DAA
[1.2] nodeID = 3, question/answer = Semister-2?
[1.2.1] nodeID = 6, question/answer = Elective
[1.2.1.1] nodeID = 12, question/answer = Elective-1
[1.2.1.2] nodeID = 13, question/answer = Elective-2
[1.2.2] nodeID = 7, question/answer = Compulsory Subject
[1.2.2.1] nodeID = 14, question/answer = Subject is SDMT
[1.2.2.2] nodeID = 15, question/answer = Subject is HPC

QUERY DECISION TREE
===================
Branch Computer (enter "Yes" or "No")
No
Semister-2? (enter "Yes" or "No")
Yes
Elective (enter "Yes" or "No")
No
Elective-2
Exit? (enter "Yes" or "No")

 

 

=============================

Assignment No. D-4 Naive Bayes

=============================

 

To implement Naive Bayes for classification.

 

Writeup:

Naive Bayes 

 

data.csv

30,1,9,Consultancy

21,2,1,Service

26,2,2,Research

28,3,10,Service

40,2,14,Consultancy

35,1,10,Research

27,3,6,Research

32,2,9,Service

45,3,17,Consultancy

36,1,7,Research

a.py

import numpy as np

from sklearn.naive_bayes import GaussianNB

data=[]

x=[]

y=[]

raw_data=open('data.csv','r')

for i in raw_data:

splitted=i.split(',')

splitted[3]=splitted[3].replace('\n','')

data.append(splitted)

for i in data:

temp=[]

for j in i[:3]:

temp.append(int(j))

x.append(temp)

for i in data:

y.append(i[3])

input=np.array(x)

output=np.array(y)

c=GaussianNB()

c.fit(input,output)

print c.predict([30,2,8])

output:-

administrator@siftworkstation:~/Desktop/BE11$sudo apt-get install python-sklearn

administrator@siftworkstation:~/Desktop/BE11$ python a.py

['Research']

 

=============================

Assignment No. D-5 KNN

=============================

 

Implementation of K-NN approach take suitable example.

 

Writeup:

KNN 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;

/**
 *
 * An implementation of knn.
 * Uses Euclidean distance weighted by 1/distance
 *
 * Main method to classify if entry is male or female based on:
 * Height, weight
 */
public class NearestNeighbour{
    public static void main(String[] args) throws IOException
    {
        System.out.println("\nData Set is:\n");
        System.out.println("\tHeight\tWeight\tGender");       
        System.out.println("\t175\t80\tMale");
          System.out.println("\t193.5\t110\tMale");
            System.out.println("\t183\t92.8\tMale");
        System.out.println("\t160\t60\tMale");
        System.out.println("\t177\t73.1\tMale");
        System.out.println("\t170\t80\tFemale");       
        System.out.println("\t150\t55\tFemale");
        System.out.println("\t159\t63.2\tFemale");
        System.out.println("\t180\t70\tFemale");
        System.out.println("\t163\t110\tFemale");

        BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("\nEnter Height of Person in cms:");
        int ht=Integer.parseInt(b.readLine());
         System.out.println("\nEnter Weight of Person in kgs:");
                int wt=Integer.parseInt(b.readLine());
        ArrayList<NearestNeighbour.DataEntry> data = new ArrayList<NearestNeighbour.DataEntry>();
        data.add(new DataEntry(new double[]{175,80}, "Male"));
        data.add(new DataEntry(new double[]{193.5,110}, "Male"));
        data.add(new DataEntry(new double[]{183,92.8}, "Male"));
        data.add(new DataEntry(new double[]{160,60}, "Male"));
        data.add(new DataEntry(new double[]{177,73.1}, "Male"));
        data.add(new DataEntry(new double[]{170,80}, "Female"));
        data.add(new DataEntry(new double[]{150,55}, "Female"));
        data.add(new DataEntry(new double[]{159,63.2}, "Female"));
        data.add(new DataEntry(new double[]{180,70}, "Female"));
        data.add(new DataEntry(new double[]{163,110}, "Female"));
        NearestNeighbour nn = new NearestNeighbour(data, 3); //3 neighbours
        System.out.println("\nClassified as: "+nn.classify(new DataEntry(new double[]{ht, wt},"Ignore")));
       
       
    }

   
   
    private int k;
    private ArrayList<Object> classes;
    private ArrayList<DataEntry> dataSet;
    /**
     *
     * @param dataSet The set
     * @param k The number of neighbours to use
     */
    public NearestNeighbour(ArrayList<DataEntry> dataSet, int k){
        this.classes = new ArrayList<Object>();
        this.k = k;
        this.dataSet = dataSet;
       
        //Load different classes
        for(DataEntry entry : dataSet){
            if(!classes.contains(entry.getY())) classes.add(entry.getY());
        }
    }
   
    private DataEntry[] getNearestNeighbourType(DataEntry x){
        DataEntry[] retur = new DataEntry[this.k];
        double fjernest = Double.MIN_VALUE;
        int index = 0;
        for(DataEntry tse : this.dataSet){
            double distance = distance(x,tse);
            if(retur[retur.length-1] == null){ //Hvis ikke fyldt
                int j = 0;
                while(j < retur.length){
                    if(retur[j] == null){
                        retur[j] = tse; break;
                    }
                    j++;
                }
                if(distance > fjernest){
                    index = j;
                    fjernest = distance;
                }
            }
            else{
                if(distance < fjernest){
                    retur[index] = tse;
                    double f = 0.0;
                    int ind = 0;
                    for(int j = 0; j < retur.length; j++){
                        double dt = distance(retur[j],x);
                        if(dt > f){
                            f = dt;
                            ind = j;
                        }
                    }
                    fjernest = f;
                    index = ind;
                }
            }
        }
        return retur;
    }
   
    private static double convertDistance(double d){
        return 1.0/d;
    }

    /**
     * Computes Euclidean distance
     * @param a From
     * @param b To
     * @return Distance
     */
    public static double distance(DataEntry a, DataEntry b){
        double distance = 0.0;
        int length = a.getX().length;
        for(int i = 0; i < length; i++){
            double t = a.getX()[i]-b.getX()[i];
            distance = distance+t*t;
        }
        return Math.sqrt(distance);
    }
    /**
     *
     * @param e Entry to be classifies
     * @return The class of the most probable class
     */
    public Object classify(DataEntry e){
        HashMap<Object,Double> classcount = new HashMap<Object,Double>();
        DataEntry[] de = this.getNearestNeighbourType(e);
        for(int i = 0; i < de.length; i++){
            double distance = NearestNeighbour.convertDistance(NearestNeighbour.distance(de[i], e));
            if(!classcount.containsKey(de[i].getY())){
                classcount.put(de[i].getY(), distance);
            }
            else{
                classcount.put(de[i].getY(), classcount.get(de[i].getY())+distance);
            }
        }
        //Find right choice
        Object o = null;
        double max = 0;
        for(Object ob : classcount.keySet()){
            if(classcount.get(ob) > max){
                max = classcount.get(ob);
                o = ob;
            }
        }
       
        return o;
    }

public static class DataEntry{
    private double[] x;
    private Object y;
   
    public DataEntry(double[] x, Object y){
        this.x = x;
        this.y = y;
    }
   
        public double[] getX(){
            return this.x;
        }
   
        public Object getY(){
            return this.y;
        }
    }
}

/*

gescoe@computerdept:~$ cd Documents/CL-1\(CRB\)/D5_KNN/
gescoe@computerdept:~/Documents/CL-1(CRB)/D5_KNN$ javac NearestNeighbour.java
gescoe@computerdept:~/Documents/CL-1(CRB)/D5_KNN$ java NearestNeighbour

Data Set is:

    Height    Weight    Gender
    175    80    Male
    193.5    110    Male
    183    92.8    Male
    160    60    Male
    177    73.1    Male
    170    80    Female
    150    55    Female
    159    63.2    Female
    180    70    Female
    163    110    Female

Enter Height of Person in cms:
180

Enter Weight of Person in kgs:
100

Classified as: Male
gescoe@computerdept:~/Documents/CL-1(CRB)/D5_KNN$ java NearestNeighbour

Data Set is:

    Height    Weight    Gender
    175    80    Male
    193.5    110    Male
    183    92.8    Male
    160    60    Male
    177    73.1    Male
    170    80    Female
    150    55    Female
    159    63.2    Female
    180    70    Female
    163    110    Female

Enter Height of Person in cms:
155

Enter Weight of Person in kgs:
20

Classified as: Female


*/

==============================
Assignment No. C-1
==============================

Code Generation using iburg tool.

Writeup:

iburg

==============================
Assignment No. C-2
==============================

Cross compilation using XMLVM.

Writeup:

XMLVM