Implementation of banker's algorithm in c++

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define s(x) printf("\n%s\n",x);
#define p(x) printf("%d\n",x);
#define ss(a) scanf("%d",&a);
#define f(a,b) for(int i=0;<a;i++) \
                   for(int j=0;j<b;j++)
#define ff(a) for(int i=0;i<a;i++)
int main()
{
int _max[5][5]={0};
int a_lc[5][5]={0};
int _ned[5][5]={0};
int res[5]={0};
int re_v[5]={0};
s("enter max table")
//f(0,5)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
ss(_max[i][j])
s("enter allocation table")
//f(0,5)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
ss(a_lc[i][j])
//f(0,5)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
_ned[i][j]=_max[i][j]-a_lc[i][j];
s("enter available resource vector")
ff(5)
ss(res[i])
s("enter request vector");
ff(5)
ss(re_v[i])
ff(5)
{
if(re_v[i]>res[i])
{
puts("error");
return 0;
}
}
// now check for saftey algo
ff(5)
{
res[i]=res[i]-re_v[i];
}
int counter=10;
bool finish[5]={false};
while(counter--)
{
    for(int i=0;i<4;i++)
     {
     int flag=false;
       if(finish[i])
        continue;
        for(int j=0;j<4;j++)
        {
              flag=true;
              if(res[j]<_ned[i][j])
              {
              flag=false;
              break;
              }
        }
          finish[i]=true;
          if(finish[i]==true)
          {
          for(int l=0;l<4;l++)
          res[l]+=a_lc[i][l];
          }
     }
}
for(int i=0;i<4;i++)
if(finish[i]==false)
{
printf("unsafe state\n");
return 0;
}
printf("safe state\n");
return 0;
}

LEET CODE PROBLEM :-Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

 class Solution {
public:
    bool isPalindrome(string s) {
        int l=s.length();
        char a1[l],c1=0;
        for(int i=0;i<l;i++)
    if((s.at(i)>=97&&s.at(i)<=122)||(s.at(i)>=65&&s.at(i)<=90)||(s.at(i)>=48&&s.at(i)<=57))
        {
                   a1[c1++]=s.at(i);
                   if(s.at(i)>=97)
                   a1[c1-1]-=32;
        }
                   a1[c1]='\0';
        int l1=0,h=c1-1;
        char a2[c1];
    for(int i=0,j=c1-1;i<c1;i++,j--)
         a2[i]=a1[j];
         a2[c1]=0;
    if(!strcmp(a1,a2))
    return true;
    return false;
}
};                                                                                                                                               

MATRIX MULTIPLICATION USING PIPES

CODE SNIPPET IS HERE PLEASE WRITE COMMENT 'S FOR ANY MODIFICATION
        #include<unistd.h>
#include<stdio.h>
#include<sys/stat.h>
#define P(X) for(l=0;l<2;l++){\
                 for(m=0;m<2;m++)\
                        printf("%d ",X[l][m]); printf("\n");}\

#define S(X) for(l=0;l<2;l++){\
                 for(m=0;m<2;m++)\
                        scanf("%d",&X[l][m]);}\

int main()
{
    int l,m,n;
    int pid;
    int p1[2],p2[2];
    pipe(p1);
    pipe(p2);

            if((pid=fork())==0)
                   {
              
                           int mat1[2][2]={1,2,3,4};
                           int mat2[2][2]={{1,2},{2,3}};
                            P(mat1);
                         P(mat2);
                 
                           int ans[2][2];
    
                           write(p1[1],mat1,2*2*sizeof(int));
                           write(p2[1],mat2,2*2*sizeof(int));
       
       
                           read(p1[0],ans,2*2*sizeof(int));
                           P(ans);
            
                   }
                else
                   {
                           int mul[2][2]={0},m1[2][2],m2[2][2],i,j,k;
 
                           read(p1[0],m1,2*2*sizeof(int));
                           read(p2[0],m2,2*2*sizeof(int));
                           P(m1);
                           P(m2);
                           for(i=0;i<2;i++)
                                 for(j=0;j<2;j++)
                                          for(k=0;k<2;k++)
                                              mul[i][j]+=m1[i][k]*m2[k][j];
           
                           P(mul);
                           write(p1[1],mul,2*2*sizeof(int));
             
            
                    }
return 0;
}

CHECK WHEN YOU HAVE NO EFFICIENT MEMORY TO ALLOCATE

There is a header new in c++ which have a function set_new_handler()
it run when " new " doesn't allocate memory
you can check it with the help of following program
#include<iostream>
#include<new>
#include<cstdlib>
using namespace std;
int count=0;
void out_of_memory()
{
    cerr<<"memory exhausted after"<<count<<"allocations!"<<endl;
    exit(1);
}
int main()
{
set_new_handler(out_of_memory);
while(1)
{
    count++;
    new int[10000];
}
return 0;
}

output:---

kruskal algorithm code snippet of MST

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;
vector< pair< pair < int,int > ,int > > edge,ans;   //edge x,y,weight
map< int, vector<int> > group;    //groupno --> groupelement
vector<int> node(1001,0);   //number of nodes maximum 1000;
bool comp(pair< pair <int,int > ,int > A,pair< pair <int ,int > ,int > B)
{
    if(A.second< B.second)
        return true;
    else
        return false;
}
int main()
{
    int cgroup=1,m;
    int n,x,y,w,e=0;
    cin>>n>>m;  //m - no of nodes
    for(int i=0;i<n;i++)
    {

        cin>>x>>y>>w;
        edge.push_back(make_pair(make_pair(x,y),w));

    }

    sort(edge.begin(),edge.end(),comp);
    int k=0;
    while(e<n-1)
    {
        x=edge[k].first.first,y=edge[k].first.second,w=edge[k].second;
        if(node[x]==0&&node[y]==0)
        {
              ans.push_back(make_pair(make_pair(x,y),w));
                      group[cgroup].push_back(x);
              group[cgroup].push_back(y);
              node[x]=cgroup;
              node[y]=cgroup;
              cgroup++;
              e++;
        }
        else if(node[x]!=0&&node[y]!=0)
        {
                    if(node[x]>node[y])
                          {
                  ans.push_back(make_pair(make_pair(x,y),w));

                  e++;
                  int tempgrp=node[y];
                  node[y]=node[x];
                        for(int i=0;i<group[tempgrp].size();i++)
                  {
                      int elem=group[tempgrp][i];
                      node[elem]=node[x];
                      group[node[x]].push_back(elem);
                  }
               
                }
            else if(node[x]<node[y])
            {
                ans.push_back(make_pair(make_pair(x,y),w));

                e++;
                int tempgrp=node[x];
                node[x]=node[y];
                for(int i=0;i<group[tempgrp].size();i++)
                {
                    int elem=group[tempgrp][i];
                    node[elem]=node[y];
                    group[node[y]].push_back(elem);
                }
           
            }
        }
        else if(node[x]!=0&&node[y]==0)
        {
            ans.push_back(make_pair(make_pair(x,y),w));

            e++;
            int tempgrp=node[x];
            group[tempgrp].push_back(y);
            node[y]=node[x];
        }
        else if(node[x]==0&&node[y]!=0)
        {
            ans.push_back(make_pair(make_pair(x,y),w));

            e++;
            int tempgrp=node[y];
            node[x]=node[y];
            group[tempgrp].push_back(x);
        }

             k++;
    }
    int grp=node[1];
    for(int i=0;i<ans.size();i++)
        cout<<ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second<<endl;
       


}

KMP - algorithm for string matching
complexity of compute prefix function O(m) ,where m is length of the pattern
complexity of KMP is O(n)
Reference-Coreman 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int pie[500];
char *pattern;
char *text;
int m;  //length is pattern
int n;  //length of text
void compute_prefix()
{
    cin>>pattern+1;
    cin>>text+1;
     m=strlen(pattern+1);
    int k=0;
    pie[1]=0;
    for(int q=2;q<=m;q++)
    {
        while(k>0&&pattern[k+1]!=pattern[q])
        {
            k=pie[k];
          
        }
        if(pattern[k+1]==pattern[q])
            k=k+1;
        pie[q]=k;

    }
}
void kmp_matching()
{

     compute_prefix();
     n=strlen(text+1);
     int q=0;
     for(int i=1;i<=n;i++)
     {
         while(q>0&&pattern[q+1]!=text[i])
         {
             q=pie[q];
         }
         if(pattern[q+1]==text[i])
             q=q+1;
         if(q==m)
         {
             printf("pattern occurs with shift %d\n",i-m);
             q=pie[q];
         }
     }

}

int main()
{

    pattern=new char[500];
    text=new char[1000];
        kmp_matching();
    return 0;
}

Matrix_exponential Template use for solving recurrence relation

/* Template of matrix exponential written by Rahul Kumar Singh (selfcompiler) date :19-oct-2012 time --8:41 P.M. */
/* ~~~~~~~~**@#*#@**~~~~~~~~~*/
#include<cstdio>
#include<iostream>
#include<math.h>
#include<vector>
#include<utility>
#include<map>
using namespace std;
#define K 3 
//size of matrix using 1 based index not 0'!!!!! ........
#define LIMIT 10000000000000
//maximum value of n
#define MODULO 1000000007
// modulo value
#define ll long long int
/*matrix structure */
struct MATRIX{
        ll mat[K+1][K+1];
    MATRIX()  //constructor
    {
        for(int i=0;i<=K;i++)
            for(int j=0;j<=K;j++)
                mat[i][j]=0;
    }//end constructor
    void print_matrix() //print matrix
    {
        for(int i=1;i<=K;i++)
        {
            for(int j=1;j<=K;j++)
                cout<<mat[i][j]<<" ";
            cout<<std::endl;
        }
    } //end print matrix

};//end of matrix structre
/* main program start here */
int main()
{
    struct MATRIX A;  
    ll column[K+1]={0,1,1,1};  //column vector to find the answer
    A.mat[1][1]=1,A.mat[1][2]=1,A.mat[1][3]=1;  //transformation matrix of 3 X 3 (1 based index)
    A.mat[2][1]=1,A.mat[2][2]=0;A.mat[2][3]=0;
    A.mat[3][1]=0,A.mat[3][2]=1,A.mat[3][3]=0;
    map<int,struct MATRIX> I;
    I[1]=A;  //transformation matrix
        ll next=2,p=1,p1,p2;
while(next<=LIMIT)    //precomputation of matrix of power 1,2,4,8,16,.......
{
             MATRIX object;
         p1=p2=p;
         for(int i=1;i<=K;i++)    //matrix multiplication start
         for(int j=1;j<=K;j++)
             for(int k=1;k<=K;k++)
             {
                  object.mat[i][j]+=(I[p1].mat[i][k]*I[p2].mat[k][j])%MODULO;
                  if(object.mat[i][j]>=MODULO)
                           object.mat[i][j]%=MODULO;

             }//matrix multipliaction end
         I[next]=object;
         p=next;
         next=next*2;
               
}//end of precomputation
    ll tc,n,count=0,pw2;
    cin>>tc;
    ll term[K+1]={0,1,1,1};     //r=q+w+e;   //term[1]>term[2]>term[3];
while(tc--)
{
    cin>>n;
    MATRIX obj;
        count=1;
                if(n>=4)
        {
        n=n-3;
        while(n)  //compute matrix of power n
        {


                     ll x=n&-n;  //farthest set bit of n
                          if(count)  
              {      //first encounter for initialization
                                 count=0;  
                 obj=I[x];

              }
              else
              {
                    MATRIX temp;  //make a temp object
                 for(int i=1;i<=K;i++)// matrix multipliaction
                 for(int j=1;j<=K;j++)
                     for(int k=1;k<=K;k++)
                         {
                           temp.mat[i][j]+=(I[x].mat[i][k]*obj.mat[k][j])%MODULO;
                           if(temp.mat[i][j]>=MODULO)
                           temp.mat[i][j]%=MODULO;
                         }//matrix multipliaction end
                obj=temp;
              }
              n=n-x;
        ll ans=0;
        for(int i=1;i<=K;i++)  //compute answer
        {
            ans+=(column[i]*obj.mat[1][i])%MODULO;
            if(ans>=MODULO)
                ans%=MODULO;
        }// finally computed
             cout<<ans<<std::endl;
        }
        else
        {
            cout<<term[n]<<std::endl;
        }

}

         return 0;
}

   
 // complexity O(logN)