Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Assignment 1

    Uploaded by

    Bhaskor Roy
    fdsasa

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Assignment 1

    Uploaded by

    Bhaskor Roy
    13 views2 pages
    fdsasa

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    fdsasa

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    13 views2 pages

    Assignment 1

    Uploaded by

    Bhaskor Roy
    fdsasa

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Problem 01: Graph coloring with fixed

    number of color.

    #include<bits/stdc++.h>
    using namespace std; }
    bool G[100][100]={0};
    int x[100]={0}; int main(){
    int c=0,m=3; cout<<"Enter the number of vertex"<<endl;
    int n=5; int n;
    void nextvalue(int k){ cin>>n;
    x[k]=(x[k]+1)%(m+1); while(n--){
    if(x[k]==0) int x,y;
    return ; cin>>x>>y;
    int j; G[x][y]=G[y][x]=1;
    for(j=1;j<=n;j++){ }

    if(G[k][j]!=0 && x[k]==x[j]) clock_t st,et;


    break; st=clock();
    mColoring(1);
    } et=clock();
    if(j==n+1) double ex=et-st;
    return ; cout<<ex<<endl;
    return 0;
    nextvalue(k); }

    } }
    Problem 02: Sum of subset finding
    void mColoring(int k){ from an Array.
    nextvalue(k); #include<bits/stdc++.h>
    if(x[k]==0)
    using namespace std;
    return ;
    int x[1000]={0};
    if(k==n) void sumofsub(int s,int k,int r,int w[],int m){
    {
    //k=k-1;
    for(int i=1;i<=n;i++){
    x[k]=1;
    cout<<x[i]<<" "; if(s+w[k]==m)
    }
    {
    cout<<endl;
    for(int i=0;i<=k;i++){
    } cout<<x[i]<<" ";
    else
    }
    mColoring(k+1);
    cout<<endl;
    mColoring(k); }
    else if(s+w[k]+w[k+1]<=m)
    sumofsub(s+w[k],k+1,r-w[k],w,m);
    if((s+r-w[k]>=m) && (s+w[k+1]<=m)){
    x[k]=0;
    sumofsub(s,k+1,r-w[k],w,m);
    }
    }

    int main(){
    int n,m;
    cin>>n>>m;
    int w[n];
    int s=0,k=0,r=0;

    for(int i=0;i<n;i++){
    w[i]=rand()%10+1;
    r+=w[i];

    for(int i=0;i<n;i++){
    cout<<w[i]<<" ";

    }
    cout<<endl; Sum of subset Array size vs
    clock_t st,et; Execution Time Graph
    50 45
    st=clock();
    39
    sumofsub(s,k,r,w,m); 40
    Execution time

    et=clock();
    30 25
    double ex=et-st; 21
    cout<<ex<<endl; 20
    return 0;
    10
    } 0.02
    0
    0 10 20 30 40 50
    Array size

    You might also like