Merge Sort in c++

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

void merge(vector<int> &v,int l, int m,int r)
  {
    vector<int> a(v.begin()+l,v.begin()+m+1);
    vector<int> b(v.begin()+m+1,v.begin()+r+1);
    int ptr1=0,ptr2=0,ptr=l;
    while(ptr1<a.size() && ptr2<b.size())
        if(a[ptr1]<b[ptr2])
            v[ptr++]=a[ptr1++];
        else
            v[ptr++]=b[ptr2++];
    while(ptr1<a.size())
        v[ptr++]=a[ptr1++];
    while(ptr2<b.size())
        v[ptr++]=b[ptr2++];
  }

void mergesort(vector<int> &vec,int l,int r )
   {
      if(l<r)
       {
           int m=(l+(r-1))/2;
           mergesort(vec,l,m);
           mergesort(vec,m+1,r);
           merge(vec,l,m,r);
       }
   }

int main()

  {

    int arr[] ={99,8,22,11,44,55,2,1,5,26,98,8,888,36,99,75,48,74,587,4};
    vector<int> vec(arr,arr+sizeof(arr)/sizeof(int));
    mergesort(vec,0,(vec.size())-1);
    for(int i=0;i<vec.size();i++)
        cout<<vec[i]<<" ";
    return 0;

  }

Python code for Quick Sort using original Hoare partition scheme

from random import randint
def quicksort(array, low, high):
    if low < high:
        p = partition(array, low, high)
        quicksort(array, low, p)
        quicksort(array, p + 1, high)

def partition(array, low, high):
    pivot = array[low]
    i=low-1
    j=high+1
    while 1:
    i = i + 1
        while array[i] < pivot:
            i = i + 1
        j=j-1
        while array[j] > pivot:
            j=j-1
       
        if i >= j:
            return j
        array[i],array[j]=array[j],array[i]




array=[]
for p in range(10):
    array.append(randint(1,100))

quicksort(array,0,len(array)-1)
print array

Implementation of iterative deepening A* (Star) Algorithm

#node              current node
#g                 the cost to reach current node
#f                 estimated cost of the cheapest path (root..node..goal)
#h(node)           estimated cost of the cheapest path (node..goal)
#cost(node, succ)  step cost function
#is_goal(node)     goal test
#successors(node)  node expanding function
V={}
E={}
V=({'A':7,'B':9,'C':6,'D':5,'E':6,'F':4.5,'H':4,'I':2,'J':3,'K':3.5,'G':0})
E=({('B','D'):2,('A','B'):4,('A','C'):4,('A','D'):7,('D','E'):6,('E','F'):5,('D','F'):8,('D','H'):5,('H','I'):3,('I','J'):3,('J','K'):3,('K','H'):3,('F','G'):5})
INFINITY=10000000
cameFrom={}
def h(node):
    return V[node]
def cost(node, succ):
    return E[node,succ]

def successors(node):
    neighbours=[]
    for item in E:
        if node==item[0][0]:
            neighbours.append(item[1][0])
    return neighbours

def reconstruct_path(cameFrom, current):
    total_path = [current]
    while current in cameFrom:
        current = cameFrom[current]
        total_path.append(current)
    return total_path
   
def ida_star(root,goal):
    global cameFrom
    def search(node, g, bound):
        min_node=None
        global cameFrom
        f = g + h(node)
        if f > bound:return f
        if node==goal:return "FOUND"
        minn = INFINITY
        for succ in successors(node):
            t = search(succ, g + cost(node, succ), bound)
            if t == "FOUND":return "FOUND"
            if t < minn:
                minn = t
                min_node=succ
        cameFrom[min_node]=node
        return minn
       
    bound= h(root)
    count =1
    while 1:
        print "itertion"+str(count)
        count+=1
        t = search(root, 0, bound)
        if t == "FOUND":
            print reconstruct_path(cameFrom, goal)
            return bound
        if t == INFINITY:return "NOT_FOUND"
        bound = t
  
print ida_star('A','G')
   

Graph implementation using adjacency list

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int key;
    struct node * next;
}node;
typedef struct list
{
    struct node * head;
}list;
typedef struct GRAPH
{
    int V;
    struct list * array;
}GRAPH;
node * newnode(int k)
{
    node *n=(node *)malloc(1*sizeof(node));
    n->key=k;
    return n;
}
GRAPH *newgraph(GRAPH * g,int v)
{   g=(GRAPH *)malloc(sizeof(GRAPH));
    g->V=v;int i;
    g->array=(list *)malloc(v*sizeof(g->array));
    for(i=0;i<v;i++)
         g->array[i].head=NULL;
    return g;
}
void add_edge(GRAPH * g,int s , int t)
{
    node *n=newnode(t);
    n->next=g->array[s].head;
    g->array[s].head=n;
    node *n2=newnode(s);
    n2->next=g->array[t].head;
    g->array[t].head=n2;
}

void delete_edge(GRAPH * g,int s , int t)
{
     if(g->array[s].head==NULL){printf("There is no edge between %d and %d \n", s , t);return;}
    node * ptr1=g->array[s].head;
    if(ptr1->next==NULL)
        {if(ptr1->key==t){free(ptr1);ptr1=NULL;}return;}
    if(ptr1->key==t)
    {  g->array[s].head=ptr1->next;free(ptr1);return;}

    node * ptr2=g->array[s].head->next;

    while(ptr2!=NULL)
    {
        if(ptr2->key!=t)
          {
            ptr1=ptr2;
            ptr2=ptr2->next;
           }
          else break;

    }
   if(ptr2!=NULL)
    {
      if(ptr2->key==t)
        {ptr1->next=ptr2->next;
        free(ptr2);
        }
      else printf("There is no edge between %d and %d \n", s , t);
    }
    else
         printf("There is no edge between %d and %d \n", s , t);

}
void printgraph(GRAPH *g)
{
    int v,i;
    v=g->V;
    for(i=0;i<v;i++)
        {   node * ptr=g->array[i].head;            printf("%d->",i);

            while(ptr!=NULL)
            {
                printf("%d->",ptr->key);
                ptr=ptr->next;
            }
            printf("\n");
        }
}
void remove_edge(GRAPH *graph ,int a , int b)
{   printf("deleting edge %d-%d \n",a,b);
    delete_edge(graph,a,b);delete_edge(graph,b,a);

}
int main()
{   int size=5;
    GRAPH *graph=newgraph(graph,size);
    add_edge(graph,0,1);add_edge(graph,0,2);add_edge(graph,0,4);
    add_edge(graph,1,4);add_edge(graph,1,2);add_edge(graph,1,3);
    add_edge(graph,2,3);add_edge(graph,2,4);
    add_edge(graph,3,4);
    printgraph(graph);
    remove_edge(graph,2,3);
    remove_edge(graph,1,4);
    remove_edge(graph,1,3);


           printgraph(graph);
    printf("success\n");
return 0;
}

Implementation of longest common sub-sequence in c

#include<stdio.h>
#include<stdlib.h>
int max(int a,int b){return (a>b)?a:b;}
char *x, *y;
int lcs(int i,int j)
 {
  if(i==0||j==0)return 0;
  else if(i>0&&j>0&&x[i]==y[j]) return lcs(i-1,j-1)+1;
  else if(i>0&&j>0&&x[i]!=y[j]) return max(lcs(i-1,j),lcs(i,j-1));
}
int main()
{int n=10,m=5;

 x=(char *)malloc(n*sizeof(char ));
 y=(char *)malloc(m*sizeof(char ));
 gets(x);
 gets(y);
 //sizeof longest common subsequence among first n letters of x and first m letters of y
 printf("%d",lcs(n,m));
return 0;
}

Program for String Matching with Finite Automata in C

#include <stdio.h>
#include <stdlib.h>
char * prefix(char * c,int start, int end,int size)
{   int i;
    char *temp=(char *)malloc(size*sizeof(char));
    for(i=0;i<size;i++)
       temp[i]=c[start++];
    return temp;
}
char * suffix(char * c,int start, int end,int size)
{   int i,j;
    char *temp=(char *)malloc(size*sizeof(char));
    for(j=0,i=end-size+1;i<=end;i++,j++)
       temp[j]=c[i];
    return temp;
}
int match(char * a, char *b)
{  int i=0;
    while(a[i]!='\0')
     {
if(a[i]!=b[i])
 return 0;
i++;
     }
    return 1;
}
int sigma(char * t , char * p ,int i)
{
  int j,v=0;
  for(j=0;p[j]!='\0';j++)
     if(match(suffix(t,0,i,j+1),prefix(p,0,j,j+1)))
v=j+1;
  return v;
}
int main()
{  char a[]="dfhghjgfjschhscgchgfbgfsgfjh";
   char b[]="jhgfj";
   printf("%d\n",sigma(a,b,8));
   
 
}

Implmentation of Rabin-Karp Algorithm in c

#include <stdio.h>
#include<stdlib.h>
int hash (char * a,int s,int t)
{ int h=0;
    for(;s<=t;s++)
        h+=a[s];
       return h;
}
int match(char * a,int a1,int a2,char * b, int b1,int b2)
{  
    for(;a1<=a2,b1<=b2;a1++,b1++)
       { if(a[a1]!=b[b1])
           return 0;
       }
       return 1;
}   
   

void rk(char*a,char *b,int as,int bs)
{ 
   int ph=hash(b,0,bs-1),i;
   for(i=0;i<(as-bs+1);i++)
    { if(hash(a,i,i+bs-1)==ph)
        if(match(a,i,i+bs-1,b,0,bs-1))
      { printf("  match for < %s > found at position : %d ",b,i+1);}
    }
        
    
}
void main()
{  
 char t[]="abcdefghijklmnopqrstuvwxyz";
 char p[]="klmnop";
    int st=sizeof(t)-1;
    int  sp=sizeof(p)-1;
    rk(t,p,st,sp);
    
    
}

Implementation of Breadth First search in C using dynamic adjacency list

#include <stdio.h>
#include <stdlib.h>
typedef struct node{int key;struct node * next;}node;
node * init_node(node * n,int b){n=(node *)malloc(sizeof(node));n->key=b;n->next=NULL;return n;}
node **list,*front=NULL,*rear=NULL;
void enqueue(node * n)
{ if(rear==NULL)front=rear=n;
  else{ rear->next=n;rear=n; } }
node * dequeue()
{
if(front==NULL&&rear==NULL){return NULL;}
if(front==rear){ node *temp=front;front=rear=NULL;return temp;}
node * temp=front;front=front->next;return temp;
}
void add_edge(int a,int b)
{  node * ptr=NULL,*n=NULL,*p;
   n=init_node(n,b);
    if(list[a]==NULL){p=init_node(p,a);list[a]=p;}
    ptr=list[a]; while(ptr->next!=NULL)ptr=ptr->next;ptr->next=n;

    ptr=NULL;n=NULL;
   n=init_node(n,a);
    if(list[b]==NULL){p=init_node(p,b);list[b]=p;}
    ptr=list[b]; while(ptr->next!=NULL)ptr=ptr->next;ptr->next=n;
}
void dfs(int s,int n)
{   node * ptr;int visited[n],i,d=6,parent[n],distance[n],parenti;
      for(i=0;i<n;i++){visited[i]=0;parent[i]=0;distance[i]=-1;}
    if(list[s]==NULL)return;
  enqueue(list[s]);
  parenti=s;
  distance[s]=0;
  visited[s]=1;
printf("\nDFS Distance from %d  :\n",s);
  while(front!=NULL)
  {
     ptr=dequeue();
     parenti=ptr->key;
     ptr=list[ptr->key]->next;

    while(ptr!=NULL)
     {   if(!visited[ptr->key])
         {enqueue(ptr);if(parent[ptr->key]==0)parent[ptr->key]=parenti;visited[ptr->key]=1;
          distance[ptr->key] =distance[parent[ptr->key]]+6;
          printf(" node-%d:parent-:%d:distance:%d\n ",ptr->key,parent[ptr->key],distance[ptr->key]);}
         ptr=ptr->next;
     }


  }
}
int main()
{int n=10,i,j;node *ptr=NULL;
 list=(node **)malloc(n*(sizeof(node *)));

for(i=0;i<n;i++)
{  list[i]=(node *)malloc(n*(sizeof(node *)));list[i]=NULL;}

add_edge(2,1);
add_edge(0,1);add_edge(2,0);
add_edge(2,3);
add_edge(9,6);add_edge(9,0);add_edge(9,5);add_edge(9,4);add_edge(9,7);add_edge(9,8);add_edge(9,3);
add_edge(8,7);add_edge(8,6);
add_edge(7,2);add_edge(7,2);
add_edge(6,0);add_edge(6,1);
add_edge(5,4);add_edge(5,2);add_edge(5,3);
add_edge(4,2);
add_edge(3,0);add_edge(3,1);
add_edge(1,0);

for(j=0;j<n;j++)
    if(list[j]!=NULL)
         { ptr=list[j];
           while(ptr!=NULL){printf("%d --> ",ptr->key);ptr=ptr->next;}
          printf("\n");
         }
dfs(3,10);

return 0;
}

Implementation of Binary Search Tree in C using dynamic linked list

//Binary Search Tree
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
  int key;
  struct node *left;
  struct node* right;
}node;

void printIO(node * n)
{ if(!n)return;
  if(n->left)
    printIO(n->left);
  printf("%d.",n->key);
  if(n->right)
    printIO(n->right);
}

node * create(node * n,int k)
{ n=(node *)malloc(sizeof(node));
  n->key=k;
  n->left=NULL;
  n->right=NULL;  
 return n;
 }

node * insert(node * n,int k)
{  
   node * root=n;
   if(n==NULL)
     {n= create(n,k);printf("%d.",k);}
   else if(k>n->key){n->right= insert(n->right,k);}
   else if(k<=n->key){n->left= insert(n->left,k);} 
   return n;
}

int main()
{
node * root=NULL;
printf("\n Inserting Sequence\n");
root=insert(root,202);root=insert(root,125);root=insert(root,255);root=insert(root,313);
root=insert(root,116);root=insert(root,222);root=insert(root,150);

printf("\n In Order of Created Binary Search tree\n");
printIO(root);
printf("\n");
return 0;
}

Implementation of topological sorting in c++

topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge u->v from vertex u to vertex v, u comes before v in the ordering.

The canonical application of topological sorting  is in scheduling a sequence of jobs or tasks based on their dependencies;


#include<iostream.h>
int n,adj[100][100];
int front = -1,rear = -1,queue[100];
void main()
{
 int i,j = 0,k;
 int topsort[100],indeg[100];
 create_graph();
 cout<<"The adjacency matrix is:"<<"/n";
 display();
 for(i=1;i<+n;i++)
 {
  indeg[i]=indegree(i);
  if(indeg[i]==0)
   insert_queue(i);
 }
 while(front<=rear)
 {
  k=delete_queue();
  topsort[j++]=k;
  for(i=1;i<=n;i++)
  {
   if(adj[k][i]==1)
   {
    adj[k][i]=0;
    indeg[i]=indeg[i]-1;
    if(indeg[i]==0)
     insert_queue(i);
   }
  }
 }
 cout<<"Nodes after topological sorting are:\n");
 for(i=0;i<=n;i++)
  cout<<topsort[i];
 cout<<"\n";
}
create_graph()
{
 int i,max_edges,origin,destin;
 cout<<"\n Enter number of vertices:";
 scamf("%d",&n);
 max_edges = n * (n - 1);
 for(i = 1;i <= max_edges;i++)
 {
  cout<<"\n Enter edge "<<i<<" (00 to quit):";
  cin>>origin>>destin;
  if((origin == 0) && (destin == 0))
  {
   cout<<"Invalid edge!!\n";
   i–-;
  }
  else
   adj[origin][destin] = 1;
 }return;
}
display()
{
 int i,j;
 for(i = 0;i <= n;i++)
 {
  for(j = 1;jrear)
  {
   cout<<"Queue Underflow”;
   return;
  }
  else
  {
   del_item = queue[front];
   front = front + 1;
   return del_item;
  }
 }
 int indegree(int node)
 {
  int i,in_deg = 0;
  for(i = 1;i <= n;i++)
   if(adj[i][node] == 1)
    in_deg++;
  returnin_deg;
 }

Liang - Barsky Plygon clipping Algorithm

algorithm for Clipping Polygon Segments
INPUT : HSA=<h1,h2,...hn> (Half-segment Array)
 w = Rectangle
OUTPUT: cHSA = clipped half-segments and the half-segments
 resulting from the evaluation of turning points
cHSA = Ø;
turningPointSets = Ø;
FOR i=1 TO n DO
 IF (hi has left dominating point) THEN
 IF (SutherlandCohenLineClipping(hi, w, clippedhs, intersection-point,
 isIntersectionPoint)) THEN
 IF (isIntersectionPoint) THEN
 EvaluateTurningPoint(w, intersectionPoint, turningPointSets, hi);
 ELSE
 cHSA.Add(clippedhs);

algorithm to  EvaluateTurningPoint 
INPUT : w = a rectangle described by the coordinates (xmin, ymin) and (xmax, ymax)
 p = Point
 turningPointSets = for each window egde there is a set recording the
 turning point of the edge
 h = halfsegment that the point p belongs to
OUTPUT: If the point is evaluated as a turning point it is added to the Turning
 Point Set of the edge
 tp = p;
IF (p.x = w.xmin) THEN //left edge
 IF (h.insideAbove) THEN
 tp.direction = UP;
 ELSE
 Tp. direction = DOWN;
 END-IF;
 turningPointSets[LEFT].add(tp);
ELSE //right edge
 IF (h.insideAbove) THEN
 tp. direction = UP;
 ELSE
 tp. direction = DOWN;
 END-IF;
 turningPointSets[RIGHT].add(tp);
END-IF;
IF (p.y = w.ymin) THEN //bottom edge
 IF (h.leftPoint > w.ymin) THEN
 tp.direction = GetDirection(p, h.leftPoint, xmin, ymin, h.insideAbove);
 ELSE
 tp.direction = GetDirection(p, h.rightPoint, xmin, ymin, h.insideAbove);
 END-IF;
 turningPointSets[BOTTOM].add(tp);
ELSE
 IF (p.y = w.ymax) THEN //top edge
 IF (h.leftPoint > w.ymin) THEN
 tp.direction = GetDirection(p, h.leftPoint, xmin, ymin, h.insideAbove);
 ELSE
 tp.direction = GetDirection(p, h.rightPoint, xmin, ymin, h.insideAbove);
 END-IF;
 turningPointSets[BOTTOM].add(tp);
 END-IF;
END-IF;

algorithm to Get Direction 
INPUT: tp = turning point
 p = point of the same half segment that the turning point tp belongs
 and is above tp
 (x, y) = the left coordinate of the vertex of the window edge
 insideAbove = insideAbove flag’s value
IF (insideAbove) THEN
 IF (tp.x > p.x) THEN
 return RIGHT;
 ELSE
 return LEFT;
 END-IF;
ELSE
 IF (tp.x > p.x) THEN
 return LEFT;
 ELSE
 return RIGHT;
 END-IF;

algorithm to Create NewSegments
INPUT: edge = indicates which edge is been handled(LEFT, RIGHT, TOP or
 BOTTOM)
 bPoint,ePoint = end points of the edge
 turningPointSet = a set of the turning points of the edge
 cHSA = set of half segments in which the new half segments will be added

OUTPUT: cHSA with the new half segments
 IF edge == TOP or edge == LEFT THEN
 InsideAbove = false;
 ELSE /*RIGHT or BOTTOM edges*/
 InsideAbove = true;
 END-IF;
 begin = 0;
 end = turningPointSet.size();
 tp = turningPointSet[begin];
 IF (tp.Direction== LEFT or tp.Direction == DOWN) and not tp.Rejected THEN
 cHSA.addHalfSegments(tp,bPoint,InsideAbove);
 DiscardTurningPoints(turningPointSet, tp, ASCENDIN_GORDER, begin);
 END-IF;
 tp = turningPointSet[end];
 IF (tp.Direction== RIGHT or tp.Direction == UP) and not tp.Rejected
 and there is no rejected turning point equals to tp THEN
 cHSA.addHalfSegments(tp,ePoint,InsideAbove);
 DiscardTurningPoints(turningPointSet, DESCENDING_ORDER, end);
 END-IF;
 WHILE (begin<end) DO
tp1 = GetNotRejectedTurningPoint(turningPointSet, ASCENDING_ORDER, begin);
IF tp1 == NULL THEN
 return;
END-IF;
tp2 = GetNotRejectedTurningPoint(turningPointSet, DESCENDING_ORDER, end);
IF tp2 == NULL THEN
 return;
END-IF;
cHSA.addHalfSegments(tp1,tp2,InsideAbove);
END-WHILE;

algorithm for  Polygon Reconstruction 

INPUT: HSA=<h1,h2,...hn> (Halfsegment Array) 

OUTPUT: HSA = each halfsegment has the face, cycle, and edge numbers set 

VARIABLES: face = array that stores in position i the last cycle number of the 

 face i 

 hsSet = array that stores in the position i if the half segment hi 

 had already the face number, the cycle number and the edge 

 number set. This array is initialized with values false. 

 IF HSA is not sorted in halfsegment order THEN 

 Sort HSA in halfsegment order; 

END-IF; 

IF the halfsegments of HSA do not have the partner number set THEN 

 Set partner number of the halfsegments of HSA; 

END-IF; 

face[0] = 0; /*0 is assigned to the first cycle of the first face */ 

lastFaceNumber = 0; 

isFirstHS = true; 

 FOR i=1 TO n DO 

 IF hi has left dominating point and not hsSet[i] THEN 

 IF isFirstHS THEN 

 isFirstHS = false; 

 hi.faceNumber = 0; 

 hi.cycleNumber = 0; 

 ELSE 

 existingFaceNumber = GetFaceNumber(HSA, hi, hsSet, i); 

 IF existingFaceNumber is equal to -1 THEN 

 lastFaceNumber++; 

 hi.faceNumber = lastFaceNumber; 

 hi.cycleNumber = 0; 

 /*to store the first cycle number of the face lastFace*/ 

 face[faceNumber-1]=0; 

 ELSE 

 hi.faceNumber = existingFaceNumber; 

 face[faceNumber]++; 

 hi.cycleNumber = face[faceNumber]; 

 END-IF; 

 END-IF; 

 hi.edgeNumber = 0; 

 ComputeCycle(HSA, hi, hsSet); 

 END-IF; 

 END-FOR; 

window clipping in 

Signature: (line x rect) -> line, (region x rect) --> region 

Syntax: windowclippingin( _, _ ) 

Meaning: computes the part of the object that is inside the window. 

Example: query Flaechen feed extend[InWindow: windowclippingin( 

 .geoData, bbox(thecenter))] project[InWindow] 

 filter[not(isempty(.InWindow))] consume 

 window clipping out 

Signature: (line x rect) -> line, (region x rect) --> region 

Syntax: windowclippingout( _, _ ) 

Meaning: computes the part of the object that is outside the window. 

Example: query windowclippingout(trajectory(train7), bbox(thecenter)) 

Implementation of Dijkstra's Single Source Shortest Path Algorithm in C++

#include<iostream.h>
#include<limits.h>
#include<assert.h>
#define max_vertex 100
#define  infinite 999999999

typedef struct Node
{
        int vertex,distance;
}Node;

Node heap[1000000];
int visited[max_vertex];
int heapSize;

void Init()
{
        heapSize = 0;
        heap[0].distance = -INT_MAX;
        heap[0].vertex  = -1;
}

void Insert(Node element)
{
        heapSize++;
        heap[heapSize] = element;

        int now = heapSize;
        while(heap[now/2].distance > element.distance) 
        {
                heap[now] = heap[now/2];
                now /= 2;
        }
        heap[now] = element;
}
Node DeleteMin()
{
       
        Node minElement,lastElement;
        int child,now;
        minElement = heap[1];
        lastElement = heap[heapSize--];
  
  
        for(now = 1; now*2 <= heapSize ;now = child)
        {
               
                child = now*2;
               
                if(child != heapSize && heap[child+1].distance < heap[child].distance ) 
                {
                        child++;
                }
              
                if(lastElement.distance > heap[child].distance)
                {
                        heap[now] = heap[child];
                }
                else /* It fits there */
                {
                        break;
                }
        }
        heap[now] = lastElement;
        return minElement;
}
int main()
{
        int graph[max_vertex][max_vertex],size[max_vertex]={0},distance[max_vertex]={0},cost[max_vertex][max_vertex];
        int vertices,edges,weight;
        int iteration;
    
        cin>>vertices>>edges;
        int from,to;
        for(iteration=0;iteration<edges;iteration++)
        {
                cin>>from>>to>>weight;
                assert(from>=0 && from<vertices);
                assert(to>=0 && to<vertices);
                graph[from][size[from]] = to;
                cost[from][size[from]] = weight;
                size[from]++;
        }
        int source;
        cin>>source;
        Node temp;
        for(iteration=0;iteration<vertices;iteration++)
        {
                if(iteration==source)
                {
                        temp.distance = 0;
                        distance[0]=0;
                }
                else
                {
                        temp.distance = infinite;
                        distance[iteration]= infinite;
                }
                temp.vertex = iteration;
                Insert(temp);
        }
        while(heapSize)
        {
                Node min = DeleteMin();
                int presentVertex = min.vertex;
                if(visited[presentVertex])
                {
                        
                        continue;
                }
                visited[presentVertex] = 1;
                for(iteration=0;iteration<size[presentVertex];iteration++)
                {
                        int to = graph[presentVertex][iteration];
                        if(distance[to] > distance[presentVertex] + cost[presentVertex][iteration])
                        {
                                distance[to] = distance[presentVertex] + cost[presentVertex][iteration];
                               
                                temp.vertex = to;
                                temp.distance = distance[to];
                                Insert(temp);
                        }
                }
        }
        for(iteration=0;iteration<vertices;iteration++)
        {
                cout<<"vertex is "<<iteration<<" , its distance is "<<iteration,distance[iteration]<<endl;
        }

        return 0;
}

Implementation of Banker's algorithm in C++

It is a deadlock avoidance strategy utilized to check where whether the given state of the system having certain maximum request and availability of the resources is safe or if it can lead to a deadlock;

For the Banker's algorithm to work, it needs to know three things:

• Maximum no. of instances a process is allowed to hold [MAX]
• Resources each process is currently holding[ALLOCATED]
• Resources currently available in the system [AVAILABLE]

Either MAX is given or REQUEST is given

if  REQUEST are given  then MAX=allocated+request;

From these [NEED] of each process is calculated.

need=max-allocated

Resources are allocated to a process  if :

• need≤ available

#include<iostream.h>

#include<conio.h>

void main()

{

int instance[5],count,sequence[10],safe,s=0,j,completed;

int available[5],allocation[10][5],max[10][5];

int need[10][5],process,P[10],countofr,countofp,running[10];

clrscr();

cout<<"\n Enter the number of resources (<=5): ";

cin>> countofr;

for(int i=0;i<countofr;i++)

{  cout<<"\n enter the max instances of  resource R["<<i<<"] :";

   cin>>instance[i];

   available[i]=instance[i];

}

cout<<"\n Enter the number of processes (<=10): ";

cin>> countofp;

cout<<"\n Enter the allocation matrix \n     ";

 

for(i=0;i<countofp;i++)

   { cout<<"FOR THE PROCESS :P["<<i<<"]"<<endl;

     for(int j=0;j<countofr;j++)

    {  cout<<"allocation of resource R["<<j<<"] is : " ;

  cin>>allocation[i][j];

  available[j]-=allocation[i][j];

}

   }

cout<<"\nEnter the MAX matrix \n\n";

    for(i=0;i<countofp;i++)

       { cout<<"FOR THE PROCESS P["<<i<<"]"<<endl;

for(int j=0;j<countofr;j++)

 {   cout<<"max demand of resource R["<<j<<"] is : ";

     cin>>max[i][j];

 }

       }

clrscr();

cout<<"\n the given data are : \n";

cout<<endl<<"\nTotal resources in system : \n\n  ";

for(i=0;i<countofr;i++)

   cout<<" R["<<i<<"]  ";

   cout<<endl;

for(i=0;i<countofr;i++)

   cout<<"     "<<instance[i];

cout<<"\n\n ALLOCATION matrix \n\n\t";

for(j=0;j<countofr;j++)

   cout<<"R["<<j<<"]  ";

   cout<<endl;

for(i=0;i<countofp;i++)

{  cout<<"P["<<i<<"]  ";

   for(j=0;j<countofr;j++)

      cout<<"    "<<allocation[i][j];

   cout<<endl;

 }

 cout<<"\n\n MAX matrix \n\n\t";

for(j=0;j<countofr;j++)

   cout<<"R["<<j<<"]  ";

   cout<<endl;

for(i=0;i<countofp;i++)

{  cout<<"P["<<i<<"]  ";

   for(j=0;j<countofr;j++)

      cout<<"    "<<max[i][j];

   cout<<endl;

 }

    for(i=0;i<countofp;i++)

       { 

for(j=0;j<countofr;j++)

 {   

     need[i][j]=max[i][j]-allocation[i][j];

 }

}

 cout<<"\n\n NEED matrix \n\n\t";

for(j=0;j<countofr;j++)

   cout<<"R["<<j<<"]  ";

   cout<<endl;

for(i=0;i<countofp;i++)

{  cout<<"P["<<i<<"]  ";

   for(j=0;j<countofr;j++)

      cout<<"    "<<need[i][j];

   cout<<endl;

 }

 cout<<"\n NOW to  check whether above state is safe";

 cout<<"\n sequence in which above requests can be fulfilled";

 cout<<"\n press any key to continue";

 getch();

count=countofp;

for(i=0;i<countofp;i++)

    { running[i]=1;}

while(count)

    {   safe=0;

        for(i=0;i<countofp;i++)

  { if(running[i])

      {  completed=1;

 for(j=0;j<countofr;j++)

    {   if(need[i][j]> available[j])

  { completed=0;

    break;

  }

    }

if(completed)

                {

   running[i]=0;

                    count--;

   safe=1;

                    for(j=0;j<countofr;j++) 

                    {

                        available[j]+=allocation[i][j];

                    }

   sequence[s++]=i;

   cout<<"\n\n Running process P["<<i<<"]";

   cout<<endl<<"\n\nTotal resources now available:\n\n";

   for(i=0;i<countofr;i++)

   cout<<" R["<<i<<"]  ";

   cout<<endl;

   for(i=0;i<countofr;i++)

   cout<<"     "<<available[i];

                    break;

                }

            }

        }    

         if(!safe)

         break;

     }

if(safe)

 {

            cout<<"\nThe System is in safe state";

   cout<<"\nSafe sequence is :";

            for(i=0;i<countofp;i++)

            {

                cout<<"\t"<<"P["<<sequence[i]<<"]";

            }

 }

else

 {

   cout<<"\nThe System is in unsafe state";

 }

       getch();

}

Implementation of Cohen-Sutherland Line clipping Algorithm

#include<graphics.h>
#include<conio.h>
#include<iostream.h>
const int t=1, b=2, r=4, l=8 ;
float xmin,ymin,xmax,ymax;
int calcode (float x,float y)
{ int code =0;
  if(y> ymax) code |=t;
  else if(y<ymin) code |= b;
  else if(x>xmax) code |= r;
  else if(x<xmin) code |= l;
  return(code);
}

void lineclip(float x1,float y1,float x2,float y2)
{ unsigned int code1,code2,codeout;
  int accept = 0, done=0;
  code1 = calcode(x1,y1);
  code2 = calcode(x2,y2);
  do{ if(!(code1 | code2))
    { accept =1 ; done =1; }
    else if(code1 & code2) done = 1;
    else
    { float x,y;
       codeout = code1 ? code1 : code2;
       if(codeout & t)
    { x = x1 + (x2-x1)*(ymax-y1)/(y2-y1);y = ymax;}
       else if(codeout & b)
    {x=x1+(x2-x1)*(ymin-y1)/(y2-y1);y=ymin;}
       else if (codeout & r)
      {y=y1+(y2-y1)*(xmax-x1)/(x2-x1);x=xmax;}
       else
     {y=y1+(y2-y1)*(xmin-x1)/(x2-x1);x=xmin;}
       if(codeout == code1)
      {x1 = x; y1 = y;
      code1=calcode(x1,y1);}
       else
    {x2 = x; y2 = y;
     code2 = calcode(x2,y2);}
   }
  } while( done == 0);
  if(accept)
    line(x1,y1,x2,y2);
    rectangle(xmin,ymin,xmax,ymax);
}

main()
{ float x1,y1,x2,y2;
  int gd=DETECT,gm;
  clrscr();
  initgraph(&gd,&gm,"");
  cout<<"\n\n\t:::Enter the co-ordinates of Line::::\n\tx1 :";cin>>x1;
  cout<<"\n\ty1 :";cin>>y1;
  cout<<"\n\tx2 :";cin>>x2;
  cout<<"\n\ty2 :";cin>>y2;
  cout<<"\n\t:::Enter the co_ordinates of window:::\n ";
  cout<<"\n\txmin :";cin>>xmin;
  cout<<"\n\tymin :";cin>>ymin;
  cout<<"\n\txmax :";cin>>xmax;
  cout<<"\n\tymax :";cin>>ymax;
  clrscr();
  line(x1,y1,x2,y2);
  rectangle(xmin,ymin,xmax,ymax);
  getch();
  clrscr();
  lineclip(x1,y1,x2,y2);
  getch();
  closegraph();
  return 0;
}

Implementation of Sutherland–Hodgman Polygon Clipping Algorithm

#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <math.h>
#include <process.h>
#define TRUE 1
#define FALSE 0
typedef unsigned int outcode;
outcode CompOutCode(float x,float y);
enum  {  TOP = 0x1,
BOTTOM = 0x2,
RIGHT = 0x4,
LEFT = 0x8
};
float xmin,xmax,ymin,ymax;
void clip(float x0,float y0,float x1,float y1)
{
outcode code1,code2,codeout;
int accept = FALSE,done = FALSE;
code1 = CompOutCode(x0,y0);
code2 = CompOutCode(x1,y1);
do
{
if(!(code1|code2))
{
accept = TRUE;
done = TRUE;
}
else
if(code1 & code2)
done = TRUE;
else
{
float x,y;
 
codeout = code1?code1:code2;
if(codeout & TOP)
{
x = x0+(x1-x0)*(ymax-y0)/(y1-y0);
y = ymax;
}
else
if(codeout & BOTTOM)
{
x = x0+(x1-x0)*(ymin-y0)/(y1-y0);
y = ymin;
}
else
if(codeout & RIGHT)
{
y = y0+(y1-y0)*(xmax-x0)/(x1-x0);
x = xmax;
}
else
{
y = y0+(y1-y0)*(xmin-x0)/(x1-x0);
x = xmin;
}
if(codeout==code1)
{
x0 = x;
y0 = y;
code1 = CompOutCode(x0,y0);
}
else
{
x1 = x;
y1 = y;
code2 = CompOutCode(x1,y1);
}
}
}while(done==FALSE);
if(accept)
line(x0,y0,x1,y1);
outtextxy(150,20,"POLYGON AFTER CLIPPING");
 
rectangle(xmin,ymin,xmax,ymax);
}
outcode CompOutCode(float x,float y)
{
outcode code = 0;
if(y>ymax)
code|=TOP;
else
if(y<ymin)
code|=BOTTOM;
if(x>xmax)
code|=RIGHT;
else
if(x<xmin)
code|=LEFT;
return code;
}
void main( )
{float x1,y1,x2,y2;
int gdriver = DETECT, gmode, n,poly[14],i;
clrscr( );
printf("Enter the no of sides of polygon:");
scanf("%d",&n);
printf("\nEnter the coordinates of polygon\n");
for(i=0;i<2*n;i++)
{scanf("%d",&poly[i]);}
poly[2*n]=poly[0];
poly[2*n+1]=poly[1];
printf("Enter the rectangular coordinates of clipping window\n");
scanf("%f%f%f%f",&xmin,&ymin,&xmax,&ymax);
initgraph(&gdriver, &gmode, "");
 
outtextxy(150,20,"POLYGON BEFORE CLIPPING");
drawpoly(n+1,poly);
rectangle(xmin,ymin,xmax,ymax);
getch( );
cleardevice( );
for(i=0;i<n;i++)
clip(poly[2*i],poly[(2*i)+1],poly[(2*i)+2],poly[(2*i)+3]);
getch( );
restorecrtmode( );
}

implementation of concept of rotation in computer graphics

 #include<iostream.h>
#include<conio.h>
#include<graphics.h>
#include<math.h>
double object[3][3],translate[3][3],output[3][3], rotate[3][3],output2[3][3],output3[3][3];
int n;
void input(int n)
{for(int i=0;i<n;i++)
     {cout<<"\nenter x and y for cordinate #"<<i+1<<endl;
      cin>>object[i][0]>>object[i][1];
     }
}
void matmulti(double a[10][3],double b[3][3],double c[10][3])
{for(int i=0;i<3;i++)
  for(int j=0;j<3;j++)
   for(int k=0;k<3;k++)
       c[i][j]+=a[i][k]*b[k][j];
}

void display(double a[10][3],int n)
{ for(int i=0;i<n-1;i++)
      line(a[i][0],a[i][1],a[i+1][0],a[i+1][1]);
       line(a[0][0],a[0][1],a[n-1][0],a[n-1][1]);
}


void main()
{int i,j,ch,gd=DETECT,gm;
double theta;
translate[0][0]=1;
translate[1][1]=1;
translate[2][2]=1;
object[0][2]=1;
object[1][2]=1;
object[2][2]=1;


 cout<<"\n 1.rotate a line";
 cout<<"\n 2.rotate a triangle";
 cout<<"\n enter your choice : ";
 cin>>ch;
 if(ch==1)
   n=2;
 if(ch==2)
   n=3;
 input(n);
 initgraph(&gd,&gm,"");
 display(object,n);
 getch();
 closegraph();
 cout<<"\nenter the fix points tx and ty\n";
 cin>>translate[2][0]>>translate[2][1];
 cout<<"\nenter the angle to rotate";
 cin>>theta;theta=-theta;
 theta=(3.14)*theta/180;
 rotate[0][0]=cos(theta);
 rotate[0][1]=sin(theta);
 rotate[1][0]=-sin(theta);
 rotate[1][1]=cos(theta);
 rotate[2][2]=1;

 translate[2][0]=(-translate[2][0]);
 translate[2][1]=(-translate[2][1]);
 matmulti(translate,rotate,output);
 translate[2][0]=(-translate[2][0]);
 translate[2][1]=(-translate[2][1]);
 matmulti(output,translate,output2);
 matmulti(object,output2,output3);

  initgraph(&gd,&gm,"");
 display(object,n);
 setcolor(12);
 display(output3,n);
 getch();

}

implementation of concept of translation in computer graphics

Program in c for 2-D Translation of line and Triangle

#include<iostream.h>
#include<conio.h>
#include<graphics.h>
int object[3][3],translate[3][3],output[3][3],n;
void input(int n)
{for(int i=0;i<n;i++)
     {cout<<"\nenter x and y for cordinate #"<<i+1<<endl;
      cin>>object[i][0]>>object[i][1];
     }
}    
void matmulti(int a[10][3],int b[3][3],int c[10][3])
{for(int i=0;i<3;i++)
  for(int j=0;j<3;j++)
   for(int k=0;k<3;k++)
       c[i][j]+=a[i][k]*b[k][j];
}

void display(int a[10][3],int n)
{ for(int i=0;i<n-1;i++)
      line(a[i][0],a[i][1],a[i+1][0],a[i+1][1]);
       line(a[0][0],a[0][1],a[n-1][0],a[n-1][1]);
}     
     

void main()
{int i,j,ch,gd=DETECT,gm;
translate[0][0]=1;
translate[1][1]=1;
translate[2][2]=1;
object[0][2]=1;
object[1][2]=1;
object[2][2]=1;


 cout<<"\n 1.translate a line";
 cout<<"\n 2.translate a triangle";
 cout<<"\n enter your choice : ";
 cin>>ch;
 if(ch==1)
   n=2;
 if(ch==2)
   n=3;
 input(n);
 initgraph(&gd,&gm,"");
 display(object,n);
 getch();
 closegraph();
 cout<<"\nenter the translation factors tx and ty\n";
 cin>>translate[2][0]>>translate[2][1];
 matmulti(object,translate,output);
  initgraph(&gd,&gm,"");
 display(object,n);
 setcolor(12);
 display(output,n);
 getch();

}

Implementation of Midpoint Circle Algorithm

 The Algorithm

function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy
 
   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx
     end if
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
     end if
   end loop

 The Program 

 #include<iostream.h>
     #include<conio.h>
     #include<graphics.h>
     #include<math.h>
     #include<dos.h>
     void main()
     { int dx,dy,s1,s2,x1,x2,y1,y2,x,y,temp,e,i,c;
      cout<<"enter the coordinates of the line in the form x1 x2 y1 y2\n";
      cin>>x1>>y1>>x2>>y2;
      int gdriver=DETECT,gmode;
      initgraph(&gdriver,&gmode,"");
      x=x1;y=y1;
      dx=abs(x2-x1);
      dy=abs(y2-y1);
      if(x2>x1)
 s1=1;
 else s1=-1;
      if(y2>y1)
      s2=1;
      else s2=-1;
  if(dy>dx)
  { temp=dx;
  dx=dy;
  dy=temp;
  c=1;
  }
  else c=0;

  e=2*dy-dx;
  for(i=1;i<=dx;i++)
  {  delay(40);
   putpixel(x,y,10);
    while(e>0)
     { if(c==1)
 { x+=s1;}
       else y=y+s2;
 e-=2*dx;
     }
    if(c==1)
     y+=s2;
    else
     x=x+s1;
  e+=2*dy;
  }
  getch();
}

Implementation of Bresenham's Algorithm For Line Drawing

 The Algorithm

function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy
 
   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx
     end if
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
     end if
   end loop

 The Program 

 #include<iostream.h>
     #include<conio.h>
     #include<graphics.h>
     #include<math.h>
     #include<dos.h>
     void main()
     { int dx,dy,s1,s2,x1,x2,y1,y2,x,y,temp,e,i,c;
      cout<<"enter the coordinates of the line in the form x1 x2 y1 y2\n";
      cin>>x1>>y1>>x2>>y2;
      int gdriver=DETECT,gmode;
      initgraph(&gdriver,&gmode,"");
      x=x1;y=y1;
      dx=abs(x2-x1);
      dy=abs(y2-y1);
      if(x2>x1)
 s1=1;
 else s1=-1;
      if(y2>y1)
      s2=1;
      else s2=-1;
  if(dy>dx)
  { temp=dx;
  dx=dy;
  dy=temp;
  c=1;
  }
  else c=0;

  e=2*dy-dx;
  for(i=1;i<=dx;i++)
  {  delay(40);
   putpixel(x,y,10);
    while(e>0)
     { if(c==1)
 { x+=s1;}
       else y=y+s2;
 e-=2*dx;
     }
    if(c==1)
     y+=s2;
    else
     x=x+s1;
  e+=2*dy;
  }
  getch();
}

Algorithm and Program for Strassen's matrix multiplication

Algorithm

If the sizes of A and B are less than the threshold

Compute C = AB using the traditional matrix multiplication algorithm.
Else use Strassen's algorithm
Split matrices A and B
For each of

Mi i = 1 to 7

Create a new thread to compute

Mi = A'i B'i

If the sizes of the matrices are less than the threshold
Compute C using the traditional matrix multiplication algorithm.
Else use Strassen's algorithm
Split matrices A'

i and B'i

For each of M

ij j = 1 to 7

If i=7 and j=7 go to step 1 with A = A'77

and

B = B'77

Get a thread from the thread pool to compute

M= A'ij B'ij

Execute the recursive version of Strassen's algorithm in this thread
Wait for the Mij

threads to complete execution

Compute MiWait for the Mi

threads to complete execution

Compute C

Program

#include<iostream.h>

#include<conio.h>

void main()

{

int a[2][2],b[2][2],c[2][2],i,j;

int p1,p2,p3,p4,p5,p6,p7;

clrscr();

cout<<"enter the first matrix";

for(i=1;i<=2;i++)

for(j=1;j<=2;j++)

cin>>a[i][j];

cout<<"enter the second matrix";

for(i=1;i<=2;i++)

for(j=1;j<=2;j++)

cin>>b[i][j];

p1=a[1][1]*(b[1][2]-b[2][2]);

p2=(a[1][1]+a[1][2])*b[2][2];

p3=(a[2][1]+a[2][2])*b[1][1];

p4=a[2][2]*(b[2][1]-b[1][1]);

p5=(a[1][1]+a[2][2])*(b[1][1]+b[2][2]) ;

p6=(a[1][2]-a[2][2])*(b[2][1]+b[2][2]) ;

p7=(a[1][1]-a[2][1])*(b[1][1]+b[1][2]) ;

c[1][1]=p5+p4-p2+p6;

c[1][2]=p1+p2;

c[2][1]=p3+p4;

c[2][2]=p5+p1-p3-p7;

for(i=1;i<=2;i++)

{

for(j=1;j<=2;j++)

{

cout<<c[i][j]<<" ";

}

cout<<"\n" ;

}

getch();

}