Heapsort in Python

def parent(i):
return i/2

def  left(i):
return 2*i

def  right(i):
return 2*i+1


def heapify(A,i,n):
l=left(i)
r=right(i)
largest=i
if l<=n and A[l]>A[largest]:
largest=l
if r<=n and A[r]>A[largest]:
largest=r
if largest!=i:
A[i],A[largest] =A[largest],A[i]
heapify(A,largest,n)


def length(A):return len(A)-1

def buildheap(A):
n=length(A)
for x in xrange(n/2,-1,-1):
print x
heapify(A,x,length(A))

def heapsort(A):
buildheap(A)
heapsize=length(A)
for i in xrange(heapsize,0,-1) :

A[0],A[i]=A[i],A[0]
heapsize=heapsize-1
heapify(A,0,heapsize)

A=[4,8,1,2,11,3,9]
heapsort(A)
print A

insertion sort in Python

def insertion(A):
x=1
while(x<len(A)):

key=A[x]
i=x-1
while (i>=0)and (A[i]>key):
A[i+1]=A[i]
i=i-1
A[i+1]=key
x+=1
a=[3,2,1,4]
insertion(a)

Check if Expression is Balanced or Not using Stack in Python

import re
balance1 ='2+4-5+[(7+8)-[]]'
balance=list(balance1)
stack=[]
flag=1;

for x in balance:
if re.match('[\(\[\{]',x):
stack.append(x)
else:
if re.match('\)\}\]',x) and stack==[]:
flag=0
break
elif stack!=[]:
if x==')'and stack.pop()!='(':
flag=0
break
if x=='}'and stack.pop()!='{':
flag=0
break
if x==']'and stack.pop()!='[':
flag=0
break
if flag:
print("balanced")
else:
print("Not balanced")

Number of paths with exactly k coins-dynamic programming

#include <string>
#include <iostream>
using namespace std;
int countpath(int mat[][3],int m,int n,int k)
{
if(m<0||n<0)return 0;
if(m==0&&n==0)
{
return (k==mat[0][0]);

}
else
{
return countpath(mat,m-1,n,k-mat[m][n])+countpath(mat,m,n-1,k-mat[m][n]);
}
}
int main()
{
int  mat[3][3] = { {1, 2, 3},
                    {4, 6, 5},
                    {3, 2, 1}
                  };
                  int k=12;
     cout<<countpath(mat,2,2,k);
}

Check if two given strings are isomorphic

#include <string>
#include <iostream>
using namespace std;
int MAX_CHARS=256;
int isomer(string a,string b)
{
int n=a.length();
int m=b.length();
if(n!=m)
return 0;
int map2[MAX_CHARS];
bool map1[256]={false};
int i=0;
while(i<n)
{
if(map1[a[i]]&&b[i]!=map2[a[i]])
return 0;
if(!map1[a[i]])
{
map1[a[i]]=true;
map2[a[i]]=b[i];
}
i++;
}
return 1;
}
int main()
{
string s="abca",s1="xxzz";

cout<<isomer(s,s1);
}

Reverse an array without affecting special characters

#include <string>
#include <iostream>
using namespace std;

int isalpha(char c)
{
return ((c>='a'&&c<='z')||c>='A'&&c<='Z');
}
int main()
{
string s="a,bc";
int n=s.length()-1;
int i=0;

while(i<n)
{
if(isalpha(s.at(i))&& isalpha( s.at(n)))
{
char t=s.at(i);
s.at(i)=s.at(n);
s.at(n)=t;i++;n--;
}
else if(!isalpha(s.at(i))&&isalpha(s.at(n)))
i++;
else if(!isalpha(s.at(n))&&isalpha(s.at(i)))
n--;
else
i++,n--;
}
cout<<s;
}

Distance between two vertices in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);g->vec[d].push_back(s);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}
void bfs(graph *g,int k1,int visited[],int dist[])
{
queue <int > s;
s.push(k1);
visited[k1]=1;

for(int i=0;i<100;i++)
dist[i]=-1;
dist[k1]=0;
int k;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";

for(int j=0;j<g->vec[k].size();j++)
{
if(dist[g->vec[k][j]]==-1)
{
s.push(g->vec[k][j]);
visited[g->vec[k][j]]=1;
dist[g->vec[k][j]]=dist[k]+1;
}
}
}
}

 int main()

{
int visited[100];

graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
   
    cout<<endl;
    int dist[100];
    for(int i=0;i<100;i++)
visited[i]=0,dist[i]=-1;
    bfs(g,2,visited,dist);
    cout<<" Shortest distance between 2 and 0 is "<<dist[0];
return 0;
}

Detect Cycle in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}

int  dfs(graph *g,int k,int visited[],int recstack[])
{

if(!visited[k]){
recstack[k]=1;
visited[k]=1;

for(int j=0;j<g->vec[k].size();j++)
{


if(!visited[g->vec[k][j]]&&dfs(g,g->vec[k][j],visited,recstack))
{
return 1;
}
else if(recstack[g->vec[k][j]])
return 1;
}
}
recstack[k]=0;
return 0;
}
 int main()
{
int visited[100],recstack[100];

graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 0);
    addEdge(g, 3, 4);
   
    for(int i=0;i<100;i++)
{
recstack[i]=0;
visited[i]=0;
}
for (int i = 0; i < 5; i++)
{
for(int i1=0;i1<100;i1++)
{
recstack[i1]=0;
visited[i1]=0;
}
   if(dfs(g,i,visited,recstack))
   {
    cout<<" Cycle present ";
    break;
   }
 
}

return 0;
}

DFS and BFS of undirected graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);g->vec[d].push_back(s);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}
void bfs(graph *g,int k,int visited[])
{
queue <int > s;
s.push(k);
visited[k]=1;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[j])
{
s.push(j);
visited[j]=1;
}
}
}
}
void dfs(graph *g,int k,int visited[])
{
stack <int > s;
s.push(k);
visited[k]=1;
while(!s.empty())
{
k=s.top();
s.pop();
cout<<k<<" -> ";
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[j])
{
s.push(j);
visited[j]=1;
}
}
}
}
 int main()
{
int visited[100];
for(int i=0;i<100;i++)
visited[i]=0;
graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
    dfs(g,0,visited);
    cout<<endl;
    for(int i=0;i<100;i++)
visited[i]=0;
    bfs(g,2,visited);
return 0;
}

vertical redundancy check binary example

vertical redundancy check binary example

add 0 at the end of data block if

- no of 1's are even and parity is given 'even'.

add 1 at the end of data block if

-no of 1's are odd and  parity is given 'even'

for 'odd' parity given do opposite of above.

for eg.

data block is      1100101 parity ='even';

no of 1's = 4;

case 1 matched so, add 0 at the end and

output to be sent will be

                                                

                                            11001010.

eg.

if data block =1010100 parity is even

then,

no of 1's = 3

odd no of 1's and even parity

add 1 at the end

output will be

                                             10101001.