Banker Algorithm

                              Banker Algorithm

The resource-allocation graph algorithm is suitable to a resource allocation system with single instances of each resource type. It is not suitable for multiple instance of each resource type. Banker’s algorithm is suitable to a resource allocation system with multiple instances of each resource type. The banker’s algorithm makes decisions on granting a resource based on whether or not granting the request will put the system into an unsafe state. Several data structures must be maintained to implement the banker’s algorithm. Let n be the number processes in the system and m be the number of resource types. We need the following data structures:
(1) Available (2) Max (3) Allocation (4) Need
1) Available: A vector of length m indicates the number of available resources of each type. If available [j] = k, there are k instances of resource type R available.
2)    Max: An n x m matrix defines the maximum demand of each process. If Max [i, j] = k, then process P. may request at most k instances of resource type R_r3)   Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. If allocation [i, j] = k, then P. is currently allocated k instances of resource type R
4)  Need: An n x m matrix indicates the remaining resource need of each process. If Need |i, j] = k, then process P. may need k more instances of resource type R, to complete its task. Need [i, j] – Allocation [i, j].
Safety algorithm: Safety algorithm is used to find the state of the system: That is, system may be safe state or unsafe state. Method for this is as follows:
1)   Let work and finish be vector of length m and n respectively. Initialize work = Available and Finish [i] = False for i = 1, 2, 3, 4, … n.
2)   Find an i such that both
a) Finish [i] = False b) Need fj] < work
If no such i exist, go to step 4.
3)    Work : = Work + Allocation i
Finish [i] = true to step 2
4)    If Finish [i] = true for all i, then the system is in a safe state. Resource-request algorithm: Let request, be the request vector for process P. If Request, fj] = k, then process P. wants k instances of resource type R.. When a request for resources is made by process P, the following actions are taken.
1)     If Request. < Need₍, then go to step 2. Otherwise, raise an eitor condition since the process has exceeded its maximum claim.
2)    If Request < Available, then go to step 3. Otherwise, P. must wait since the resources are not available.
3)        Available : = Available – Request.; Allocation : = Allocation + Request.; Need_; : = Need_t – Request.;
If the resulting resource allocation stale is safe, the transaction is completed and process P. is allocated its resources. If the new state is unsafe, then P. must wait to the Request, and the old resource allocation state is restored.

Coding

#include<stdio.h>
#include<stdlib.h>
struct bank
{
 int alloc[10];
 int max[10];
 int need[10];
 int c;
 }p[10];

 int av[10];
 int m,n;
 char res[5]={'D','E','B','A','S'};
 int safe[20];
 int grant[10];
 int g=0;


void read()
{
 printf("\nEnter the number of processes--");
 scanf("%d",&n);
 int i,j;
 printf("\nEnter the number of resorces--");
 scanf("%d",&m);
 for(i=0;i<n;i++)
 {
   p[i].c=0;
   printf("\n\nEnter the details of the process %d--\n",i+1);
   for(j=0;j<m;j++)
    {
      printf("\nEnter the instances of %c allocated--",res[j]);
      scanf("%d",&p[i].alloc[j]);
    }
   for(j=0;j<m;j++)
    {
      printf("\nEnter the instances of %c maximum",res[j]);
      scanf("%d",&p[i].max[j]);
      p[i].need[j]=p[i].max[j]-p[i].alloc[j];
    }

 }


 printf("\nEnter the total instances of available resources--\n");
 for(i=0;i<m;i++)
 {
 printf("%c\t",res[i]);
 scanf("%d",&av[i]);
 }
}


void display()
{
 int i,j;
 printf(" \t Alloc \t Max \t Need \t Avail \n");
 printf(" \t ");
 for(j=0;j<4;j++,printf("\t "))
 for(i=0;i<m;i++)
 printf("%c",res[j]);
 printf("\n");
 for(i=0;i<n;i++)
 {
   printf("P%d\t",i);
   for(j=0;j<m;j++)
   printf("%d",p[i].alloc[j]);
   printf("\t");
   for(j=0;j<m;j++)
   printf("%d",p[i].max[j]);
   printf("\t");
   //printf("dev test 1");
   for(j=0;j<m;j++)
   printf("%d",p[i].need[j]);
   printf("\t");
   if(i==0)
   {
   for(j=0;j<m;j++)
   printf("%d\t",av[j]);
   }
   printf("\n");
   }
   }


int over()
{
  int i,j;
  for(i=0;i<n;i++)
  for(j=0;j<m;j++)
  if(p[i].need[j]!=0)
  return 1;
  return 0;
  }
void banker()
{
  int i,j,k,l;
  for(i=0,l=0;;i++,l++,i=i%n)
  {
   if(over()==0)
    {
     printf("\nAll processes complete\n\nNo Deadlock");
     printf("\n\nSafe state<");
     for(i=0;i<g;i++)
     printf("P%d",safe[i]);
     printf(">");
     break;
  }
  //printf("debasis");
  else
  {
    if(p[i].c==0)
    {
      for(j=0;j<m;j++)
      if(p[i].need[j]>av[j])
      break;
      if(j==m)
      {
        safe[g]=i;
        g++;
        p[i].c=1;
        for(j=0;j<m;j++)
         {
           av[j]=av[j]-p[i].need[j];
           p[i].need[j]=0;
           p[i].alloc[j]=p[i].max[j];
         }
        printf("\n\nProcess P%d is executing---\n\n",i);
        display();
        for(j=0;j<m;j++)
        {
         av[j]=av[j]+p[i].alloc[j];
         p[i].alloc[j]=0;
         p[i].max[j]=0;
        }
        printf("\n\nProcess P%d is completed---\n\n",i);
        display();
        }
 }
 }
 if(l==25)
 {
  printf("---Deadlock---");
  break;
  }
  }
  }


void req()
{
  int i,j,k=0;
  printf("\nEnter the process number--");
  scanf("%d",&i);
  for(j=0;j<m;j++)
  {
   printf("\nEnter the number of instances of resource %c--",res[j]);
   scanf("%d",&grant[j]);
  }
 for(j=0;j<m;j++)
 if(p[i].need[j]<grant[j])
 k=1;
 for(j=0;j<m;j++)
 if(av[j]<grant[j])
 k=2;
 if(k==1)
 {
  printf("Need is less than request cannt be allocated--");
  }
 if(k==2)
 {
  printf("Available is less than reuest cannot be allocated");
 }
 if(k==0)
 {
  for(j=0;j<m;j++)
  {
   p[i].alloc[j]+=grant[j];
   p[i].need[j]-=grant[j];
   av[j]-=grant[j];
   }
   }
   banker();
 }

  main()
  {
   int ch;
   do
   {
    printf("\n\nDEVS TEST BANKERS ALGORITHM");
    printf("\n1.Read devs input data file \n2.Display devs Input data file\n3.Generate devs Safe sequence\n4.Request for resource\n5.Exit\nEnter you choice dev :-)");
    scanf("%d",&ch);
    switch(ch)
    {
     case 1:read();break;
     case 2:display();break;
     case 3:banker();break;
     case 4:req();break;
     case 5:break;
    }
  }while(ch!=5);
 }

What Actually is “Higgs Boson” Or “The God Particle”.

Higgs Boson

The Higgs Boson and the Higgs Mechanism became a cornerstone of the Standard Model of particle physics. The Higgs boson is the particle associated with the Higgs field, an energy field that transmits mass to the things that travel through it.This theory may be a little hard to digest if you’re totally unfamiliar with particle physics,so lets get familiar with some of the basic fundamentals about this particle:-

·         To know this we must examine one of the most prominent theories describing how the "cosmos works" which is given by the standard model.

·         we know that there are 4 fundamental forces –gravitational, electromagnetic, strong and weak nuclear forces out of these four the weak force and the electromagnetic forces can be described within the same theory, which forms the basis of the standard model which implies that electricity, magnetism, light and some types of radioactivity are all manifestations of a single underlying force known as the electroweak force.

·         There are also 12 fundamental particles of matter  these 12 fundamental particles of matter describes the 12 fermions that make up the basic set of particles. These 12 fermions are further divided into two sets of six quarks and six leptons. Hence Lepton and Quarks are called as the basic building block.

·         The Quarks make up protons and neutrons while members of the Lepton family include the electron and the electron neutrino, its neutrally charged counterpart.

·         The six Quarks are called up, down, strange, charm, top and bottom.

·         The Six Leptons are called the electron, electron neutrino, muon, muon neutrino, tau and tau neutrino.

·         There are also the force carrying particles called bosons. They are photons which responsible for the electromagnetic force, W and Z bosons that cause the weak force and gluons that result in the strong force. There may also be a boson caused the Higgs boson that would help to explain gravity.

·         In particle physics, the Higgs mechanism is a kind of mass generation mechanism, a process that gives mass to elementary particles. According to this theory, particles gain mass by interacting with the Higgs field that permeates all space

The four fundamental forces has a corresponding carrier particle, or boson, that acts upon matter .Now think each of the four fundamental ones has its own specific bosons. Electromagnetic fields, for instance, depend on the photon to transit electromagnetic force to matter. Physicists think the Higgs boson might have a similar function -- but transferring mass itself.

Think for a moment of time if all particles have no inherent mass, but instead gain mass by passing through a field? This field, known as a Higgs field, could affect different particles in different ways. Photons could slide through unaffected, while W and Z bosons would get bogged down with mass. In fact, assuming the Higgs boson exists, everything that has mass gets it by interacting with the all-powerful Higgs field, which occupies the entire universe. Like the other fields covered by the standard model, the Higgs one would need a carrier particle to affect other particles, and that particle is known as the Higgs boson.To test the existence of Higgs particle and Higgs Field the particle accelerators came into picture which are known as the Large Hadron collider which shoots beams of protons into each other. When they collide, they create super-high-energy mash-ups that spew out subatomic particles. From time to time, a Higgs boson might be one of those particles.

 Just after the big bang the Higgs field was zero, but as the universe cooled and the temperature fell below a critical value, the field grew spontaneously so that any particle interacting with it acquired a mass. The more a particle interacts with this field, the heavier it is. Particles like the photon that do not interact with it are left with no mass at all. Like all fundamental fields, the Higgs field has an associated particle – the Higgs boson. The Higgs boson is the visible manifestation of the Higgs field, rather like a wave at the surface of the sea.

According to Einstein Theory Of General Relativity mass is connected to gravitation. The Higgs Boson Mechanism solves the mass enigma but totally ignores gravitation and General Relativity.From this we can say that Higgs Field is nothing but a "Newtonian Field in Spacetime.

Graph Coloring Technique

   GRAPH COLORING TECHNIQUE

DEFINATION:-

A coloring of a graph means assigning of a color to each vertex of the graph so that no two adjacent vertices are given the same color.In order to accomplish this we need the minimum number of colors to color the adjacent vertices which is called as the Chromatic Number of the graph.

PROCEDURE:-

Lets consider a un-directed graph G having V number of vertices and E number of  edges.

--> Enter the number of vertices of the graph.

--> Create an adjacency matrix of the above un-directed graph representing the             connected adjacent vertices.

  

--> Assign  Color 1 the nth vertices.

--> Check whether nth vertex is connected to any of previous (n-1) vertices 
      using  backtracking.

-->If connected then assign a color x[i]+1 where x[i] is the color of i th vertex          that is connected with nth vertex.

 SOURCE CODE USING C :-

#include<stdio.h>
#include<stdlib.h>

int col[100];
int adj[100][100];

void chkcolour(int v)
{
        int i;
        col[v]=1;
        for(i=0;i<v;i++)
        {
                if(adj[v][i]!=0 && col[v]==col[i])
                {
                        col[v]=col[i]+1;
                }
        }
}
void print_color(int v)
{
        int i;
        printf(" Printing the vertex colours:\n");
        for(i=0;i<v;i++)
        {
                 printf("Nodevertex-->[%d] has color --> :%d\n",i+1,col[i]);
        }

}

int main()
{
        int i,j,v;
        printf("enter the no of vertices:\n");
        scanf("%d",&v);
       printf("Start entering the values for adjacency matrix:\n");
        printf("________________________________________________\n");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        scanf("%d",&adj[i][j]);
                }
        }

        printf("_______________________________\n");

        printf("The entered adjacency matrix is:\n ");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        printf("%d",adj[i][j]);
                }
                printf("\n");
        }
        for(i=0;i<v;i++)
        {
                chkcolour(i);
        }
        chkcolour(v);
        printf("_______________________________\n");
        print_color(v);
        printf("_______________________________\n");


        return 0;
}



OUTPUT:

enter the no of vertices:
7
Start entering the values for adjacency matrix:
________________________________________________
0 1 1 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 1 0 1 1 0
1 0 1 1 0 1 0 
1 0 0 1 1 0 1
1 0 0 0 0 1 0
_______________________________
The entered adjacency matrix is:
 0110111
1010000
1101100
0010110
1011010
1001101
1000010
_______________________________
 Printing the vertex colours:
Nodevertex-->[1] has color --> :1
Nodevertex-->[2] has color --> :2
Nodevertex-->[3] has color --> :3
Nodevertex-->[4] has color --> :1
Nodevertex-->[5] has color --> :2
Nodevertex-->[6] has color --> :3
Nodevertex-->[7] has color --> :2

_______________________________

**********************************************************************************

Computational Geometry Problem To Find Out The Closest Set Of Points.

Closest Set Of Points Promblem

The closest pair of points problem is a problem of computational geometry promblem: given n points in metric space, find a pair of points with the smallest distance between them. 

suppose we are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. Recall the following formula for distance between two points p and q.

This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision so we need to track out the closest pair between them.

we know that the closest pair of points can be computed in O (n²) time by performing a brute-force approach. To do that, one could compute the distances between all the n(n − 1) / 2 pairs of points, then pick the pair with the smallest distance, as illustrated below.

minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

Although we can design it in various number of ways here is one of the possible ways where time complexity is O(n x (Logn)^2)

process:-

Input: An array of n points P[]
Output: The smallest distance between two points in the given array.

1) Find the middle point in the sorted array.

2) Divide the given array in two halves. The first subarray contains points from arr[0] to arr[n/2]. The second subarray contains points from arr[n/2+1] to arr[n-1].

3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.

4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in pair is from left half and other is from right half. Consider the vertical line passing through passing through arr[n/2] and find all points whose x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such points.

5) Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by recursively sorting and merging.

6) Find the smallest distance in S. 

c code to implement the closest set of points:-

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

typedef struct

{

int x,y;

}point;

int main()

{

point *p;

int i,j,**d,n,min,s,t;

printf("\n Enter the no of points::\n");

scanf("%d",&n);

d=(int **)malloc(n*sizeof(int *));

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

        {

                d[i]=(int*)malloc(n*sizeof(int));

        }

p=(point*)malloc(n*sizeof(point));

printf("\n enter %d no of (x,y) co-ordinate points \n ",n);

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

{

scanf("%d %d",&p[i].x,&p[i].y);

}

printf("the distance matrix is:\n");

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

{

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

{

d[i][j]=sqrt(pow((p[i].x-p[j].x),2)+pow((p[i].y-p[j].y),2));

printf(" \t %d",d[i][j]);

 

}

printf("\n");

}

min=9999;

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

        {

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

                {

                        if(i!=j)

{

if(min>d[i][j])

{

min=d[i][j];

s=i;

t=j;

}

}

                }

        }

 

printf("\n FROM  %d   to  %d  is the minimum distance =  %d ",s+1,t+1,min);

}

*********************************************************************************************************************