SmartCoders

Synchronization(using Semaphores)-Producer Consumer

2013-10-20T09:00:00.002-07:00

/*......
Before moving to the algorithm...I am writing the structutre of the program
we have created two threads p and c

pthread_create(&c,NULL,&consume,NULL);
pthread_create(&p,NULL,&produce,NULL);
first argument is the address of the variable holding the address of the thread
second argument is priority of the thread which we have set to 0
third argument is the function name from where thread starts its execution
fourth argument is the parameter passed to the function...here we have no parameter hence we have written as NULL

NOW thread c will take handling consumer process and thread p will handle producer process

Consumer-Producer Problem
Here we have taken the bounded buffer of size 5
Three semaphores have been taken-:

mutex-Initial value is taken as 1,this has been used to implement lock ie. while producer is in
making changes to buffer consumer cannot do and vice-versa

empty-Initial value is size of the buffer since in the beginning buffer will be empty hence number of empty slots will also be equal to buffer

full-Initial value is 0 since at the beginning number of the filled slots are 0

...........*/

#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>
pthread_t p;
pthread_t c;
sem_t mutex,full,empty;
int bufferSize=5;
int buffer[5];
int nextProduce,nextConsume;
int in,out;

void *produce(void *p)
{

int i=0;
while(i<=10)
{
sem_wait(&empty);//if buffer is full number of empty slots will be 0 hence empty=0 and thread has to wait here untill consumer consumes some of the product
sem_wait(&mutex);//it locks the consumer function so that while p is in its critical section c cannot move to its critical section
nextProduce=(int)rand();
buffer[in]=nextProduce;
printf("\nProduced %d at %d",nextProduce,in);
in=((in+1)%bufferSize);
sem_post(&mutex);//releasing the lock
sem_post(&full);//increasing the value of the full since number of filled slots will increase
i++;
}//end of while
}//end of produce

void *consume(void *p)
{int i=0;
while(i<=10)
{

sem_wait(&full);
sem_wait(&mutex);
nextConsume=buffer[out];
printf("\nConsume %d at %d",nextConsume,out);
out=((out+1)%bufferSize);
sem_post(&mutex);
sem_post(&empty);
i++;
}//end of while
}//end of consume

int main()
{
sem_init(&mutex,0,1);
sem_init(&full,0,0);
sem_init(&empty,0,bufferSize);
pthread_create(&c,NULL,&consume,NULL);
pthread_create(&p,NULL,&produce,NULL);
pthread_join(p,NULL);
pthread_join(c,NULL);
}

For compilation gcc -pthread xyz.c

Bankers Algorithm(Deadlock Avoidance)

2013-10-14T14:16:00.002-07:00

Bankers algorithm is Deadlock avoidance algorithm which capable of dealing with more than two or n process resource allocation.Everytime there is demand by the process for allocation algorithm is invoked by OS.
DATA STRUCTURES USED-:
Available-Vector to store resources available with the system
Max[i][j]-Max demand made by the ith process for jth resource
Allocated[i][j]-Number of instances of jth resources has been allocated to ith process
Need[][]-Max-Allocated

ALGO-:

The process works on lines of bank management.Whenever there is the demand of resources allocation which cannot be completed by OS, process is asked to wait until some finished process release its resources.
Released resources are added to Available list
This Available list is compared with Need list of next process
If Need is greater than Available, process is put on hold and same condition is checked for next process
If Need is less than or Equal to Available then the Allocated resources are added to Available(since if condition is true process can successfully finish itself and can release its resources)
All above process are repeated until all process have been completed or there is no process left for which Need <=Available. In the latter case system is not in SAFE state and in former safe sequence can be generated

#include<stdio.h>

#include<conio.h>
#include<stdlib.h>

int available[1][5];
int max[5][5];
int allocated[5][5];
int need[5][5];
int p[5]={0};
int n=5;//number of process
int m=3;
void input()
{
int i,j;
puts("Enter the Allocation Matrix");
for(i=0;i<n;i++)
{
printf("P%d ",i);
for(j=0;j<m;j++)
{
scanf("%d",&allocated[i][j]);
}//inner for
printf("\n");
}//outer for

puts("Enter the MAX Matrix");
for(i=0;i<n;i++)
{
printf("P%d ",i);
for(j=0;j<m;j++)
{
scanf("%d",&max[i][j]);
}//inner for
printf("\n");
}//outer for

puts("Enter the Available Matrix");
for(i=0;i<m;i++)
{
scanf("%d",&available[0][i]);
}

}//function end
void calc_need()
{
int i,j;
puts("NEED matrix");
for(i=0;i<n;i++)
{

for(j=0;j<m;j++)
{
need[i][j]=max[i][j]-allocated[i][j];
printf("%d ",need[i][j]);
}//inner for
printf("\n");
}//outer for

}//end of calc_need
int less_than_or_equal(int i)//to check if for process i need <=Available
{
int j;
for(j=0;j<m;j++)
{
if(need[i][j]<=available[0][j])
continue;
else
return 0;
}//end of for
return 1;

}
void increase_available(i)
{

int j;
for(j=0;j<m;j++)
{
available[0][j]=available[0][j]+allocated[i][j];
}
}

void check()
{
int j;
for(j=0;j<n;j++)
{
printf("%d",p[j]);
}
}
main()
{

int i;
int f=0;
input();//to take inputs for Allocated Max and Available
calc_need();
while(1)
{
if(f==n)
break;
f=0;
for(i=0;i<n;i++)
{

if((p[i]==0)&&(less_than_or_equal(i)))
{
increase_available(i);
p[i]=1;
printf("P%d ",i);
continue;
}
else
{
f=f+1;
continue;
}

}//end of for

}//end of while
getch();
check();
getch();
}//end of main

OUTPUT
Safe Sequence
<P1,P3,P4,P0,P2>

Optimal Page Replacement

2013-09-30T13:34:00.000-07:00

Since optimal page replacement is not used practically and is implement for comparing algos hence it doesn't need a dynamic queue or link list and hence here it has been implemented using arrays

let 70120304230321201701 be the sequence string
number of pages are 20
if frame size taken 3 number of page faults will be 9

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

int frame[100];//frame
int a[100];//to store pages
int Frame_size;//to store frame size;
int n;//to store number of pages to be input by user
int j=0;
int nulp()//function to return the index number of the page which will not be used for longest period ie..which is to removed from the frame
{
int i=0;
int jj=j+1;
int max=-1;
int pos;
while(1)
{
while(1)
{
if(frame[i]==a[jj])
{
if(max<(jj-j))
{
max=jj-j;
pos=i;
}
jj=j+1;
i++;
break;
}
else
{

jj++;
if(jj==n)
{
max=jj-n;
pos=i;
return i;
jj=j+1;
i++;
break;
}
}

}
if(i==Frame_size)
break;
}
return pos;
}

int ifexist(int i)
{
int j1;
for(j1=0;j1<Frame_size;j1++)
{
if(frame[j1]==i)
return 1;
}
return 0;
}
main()
{
puts("Enter the number of pages");
scanf("%d",&n);
puts("Enter pages");
int i=0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
puts("Eneter the Frame size");
scanf("%d",&Frame_size);

int Fault=0;//counting the number of page faults occur
int counter=0;//to make sure size of frame is equal to the Frame_size as entered

frame[counter]=a[j];
counter++;
j++;
Fault++;//we can be sure when first element will be entered it will be a fault
while(j<n)
{
if((counter<Frame_size)&&(!ifexist(a[j])))
{
frame[counter]=a[j];
j++;
counter++;
Fault++;
}
if(ifexist(a[j]))
j++;
if((counter==Frame_size)&&(!ifexist(a[j])))
{

int i=nulp();//returns the index number of element which will not be utilized for longest period of time or page which has to be removed
frame[i]=a[j];
j++;
Fault++;

}
}
printf("%d",Fault);
getch();
}

Producing a mirror tree of given tree

2013-09-30T13:33:00.002-07:00

Given Tree
a
/ \
b c
/ \
d e
Mirror Tree

a
/ \
c b
/ \
e d

ALGO

Here we have simply traversed the tree in postfix manner and instead of printing the node we have switched it right child with left and vice versa
Per-order is used because root's child will be switched at last

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<time.h>//for producing random tree

struct node
{int n;
struct node *left;
struct node *right;
};
int c=0;
create(int d,struct node**m)
{
struct node *q=*m;
if(*m==NULL)
{
struct node *r=(struct node*)malloc(sizeof(struct node));

r->n=d;
r->left=NULL;
r->right=NULL;
*m=r;

}

else
{
if(q->n>d)
create(d,&(q->left));
if(q->n<d)
create(d,&(q->right));

}

}
display(struct node *root)
{

if(root==NULL)
return;

else
{

display(root->left);
display(root->right);
printf("%d\n",(root->n));
}

}

conversion(struct node *m)//code for creating mirror tree of the given tree
{
struct node *n=m;
if(n==NULL)
return;
conversion(n->left);
conversion(n->right);
struct node *t=n->left;
n->left=n->right;
n->right=t;

}

main()
{
struct node *root=NULL;
srand(time(NULL));
int i;
for(i=0;i<=5;i++)
create((rand()%20),&root);

display(root);//before conversion
conversion(root);
display(root);//after conversion
getch();

}

FIFO Page Replacement

2013-09-29T09:08:00.000-07:00

//ALL there are three possibileties
//first-: All frames are occupied and fault occurs, in such case we need to first deque and then enqueue the required page and variable counting the fault will be incremented
//second-: Some Frame is empty and fault occurs, in such we will enqueue the required page and increment the fault variable
//third-: if fault does not occur,in such case we will move to next page

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct que
{
int data;
struct que *next;
};

void enque(struct que **q,int a)
{
struct que *t,*r;

if(*q==NULL)
{
t=(struct que*)malloc(sizeof(struct que));
t->data=a;
t->next=NULL;
*q=t;

}
else
{
t=*q;
while(t->next!=NULL)
t=t->next;
r=(struct que*)malloc(sizeof(struct que));
r->data=a;
r->next=NULL;
t->next=r;
}

}

int deque(struct que **q)
{
if(*q==NULL)
{
printf("que is underflow");
return -999;
}
struct que *r;
r=*q;
int x;
x=r->data;
*q=r->next;
free(r);
return x;

}
int ifexist(struct que **q,int i)
{
struct que *t,*r;
t=*q;
while(t!=NULL)
{

if(t->data==i)
return 1;
t=t->next;
}
return 0;
}
main()
{
int a[100];//page sequence;
int n;
int Frame_size;
puts("Eneter the number of pages to be entered");//number of pages
scanf("%d",&n);
int i=0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
puts("\nEnter the size of Frame");//number of frames
scanf("%d",&Frame_size);
struct que *p;
p=NULL;
int j=0;
int counter=0;//to count the number of frames
enque(&p,a[j]);//first element is to insert without any condition
j=j+1;
int fault=1;//first element will always produce fault
counter=counter+1;
while(j<n)
{
if((counter==Frame_size)&&(!ifexist(&p,a[j])))//if all frames are filled and fault occurs
{
deque(&p);
enque(&p,a[j]);
j++;
fault=fault+1;

}

if(ifexist(&p,a[j]))//if no fault occurs
j++;

if((counter!=Frame_size)&&(!ifexist(&p,a[j])))//if all frame not filled and fault occurs
{
enque(&p,a[j]);
j++;
fault=fault+1;
counter=counter+1;
}

}
printf("\nNumber of Page fault occurs %d",fault);
getch();

}

DFS Search

2013-09-26T12:48:00.000-07:00

//Here we have used the Adjacnet Matrix method hence time complexity for the DFS is O(V^2)
//Since whole matrix of V^2 has to be searched for the adjacnet nodes
//If Adjacent list would have been used in that case complexiy would have been 0(V+E) since only only V vertices had been passed and E edges would have searched for
//Not an optimal solution...
//But saves lots of space
//if A[u][v]=1 it implies that there exist a path from u to v hence v is adjacent to u

DFS:A>B>D>F>C>G>E

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int V;//Number of vertices

int E;//number of Edges..not used since adjacent matrix representation has been used

int A[10][10];//Adjacent matrix

int visited[10]={0,0,0,0,0,0,0,0,0,0};//visited array...initially all are set to zero since no node has been visited

void dfs(int u)
{
visited[u]=1;//whatever node is passed to node is consider to be visited hence we make it visited
printf("%c\t",(65+u));//printing the node visited..and nodes are in character form A,B,C..
int i;
for( i=0;i<V;i++)
if(!visited[i]&&A[u][i])//if node is not visited and it is adjacent to the node passed as argument to the function then only we will visit it..the first adjacent node will be visited and the remaing adjacent node will be visited recursively
{
dfs(i);
}
}

main()
{

puts("Enter the number of Vertices and Graph");
scanf("%d",&(V));
scanf("%d",&(E));

int i;
int j;
puts("Enter the Adjacent Matrix Row wise");
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
scanf("%d",&(A[i][j]));
}
i=0,j=0;
puts("Adjacent Matrix");
for(i=0;i<V;i++)
{

for(j=0;j<V;j++)
printf("%d\t",(A[i][j]));
printf("\n");

}

dfs(0);//Here since graph is single componet we can take only one vertex and start dfs else in separate component then we have to do dfs for all the nodes

getch();
}

Sjf preemptive...with idle time

2013-09-10T05:38:00.000-07:00

//first all the processes are taken in the array of structure P[]
//THEN a[] contains the burst time of all the process in order of their arival
//min function calculates the minimum value in the array a[], beteen the index number 0 to j where j is number of process which have arived
//maximum valu of j can be equal to number of process
//if the a[i] is 0 means burst time remain is 0 and hence that procee need not be processed hence we will ignore it
// if a[i] is 0 till i to j and j is not equal to the number of process then cpu is idle all the arrived porcess have been finished and waiting for new process
// if a[i] is 0 for all the process and j=number of process then all process have been finished
// Moment burst time of the process becomes 0 at that time of interval value of cl(clock) become completition time of that process

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct process
{
       int at;
       int bt;
       int rt;
       int c;//process completiotion time
       int wt;
       int trt;
       };


       int min(int *a,int j)
       {
           int min;
       int i=0;
       int flag=0;
       int pos;
       for(i=0;i<=j;i++)
       {
       if(a[i]==0)
       continue;
       min=a[i];
       pos=i;
       flag=1;
       break;
       }
       if(flag==0 &&j!=3)
       return -2;
       else if(flag==0)
       return -1;
       else
       for(i=0;i<=j;i++)
       {
       if(a[i]==0)
       continue;
       if(a[i]<min)
       {
       min=a[i];
       pos=i;
       }
       }
       return pos;
       }
void display(struct process *p)
{
    int i=1;
    for(i=0;i<4;i++)
    {
        printf("Arrival time%d ",p[i].at);
        printf("Burst Time%d ",p[i].bt);
        printf("comlete Time%d ",p[i].c);
        printf("waiting Time%d ",(p[i].c-p[i].at-p[i].bt));
        printf("\n\n");
}


}
main()
{
      struct process p[100];
      int b[100];
      int a[4];//since number of process taken are four
      puts("Enetr the process arival time and burst time");
      int i=0;
      int j=0;
      while(1)
      {

      scanf("%d",&(p[i].at));
      scanf("%d",&(p[i].bt));
      a[j]=p[i].bt;
      j++;
      i++;
      if(i==4)
      break;
      }

      //array a[] contains the burst time of the process

      //array p[] contains the proceess

      int x=0;
      int y=0;
      int m;
       j=0;
       i=0;
       int cl=0;
       int pid=2;
       while(cl<p[0].at)
       {
       printf("idle %d---",cl);
       cl++;
       printf("%d\n",cl);
    }
      while(x!=-1)
      {
       a[x]=a[x]-1;
       cl++;
       if(a[x]==0)
       p[x].c=cl;

       if(cl<p[i+1].at)
   {
       x=min(a,j);
       if(x==-2)
       {
                 while(cl<p[i+1].at)
                 {
                 printf("idle %d---",cl);
       cl++;
       printf("%d\n",cl);
                 }

         }

    }
       if(cl==p[i+1].at)
       {j++;
       x=min(a,j);
       i++;
         }
         if(i==4)
         x=min(a,3);


}





      printf("\n\n");
     display(p);
      getch();
      }

SJF-Preemetive---Only gantt chart

2013-09-09T08:07:00.003-07:00

Following code produces Gantt chart for the SJF-preemtive schedulign.....works for 4 process.
In a Array process one is represented by 0 and so on

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct process
{
       int at;
       int bt;
       int rt;
       int c;
       int wt;
       int trt;
       };


       int min(int *a,int j)
       {int min;
        int i=0;
        int flag=0;
        int pos;
        for(i=0;i<=j;i++)
        {
        if(a[i]==0)
        continue;
        min=a[i];
        pos=i;
        flag=1;
        break;
        }
        if(flag==0)
        return -1;
        else
        for(i=0;i<=j;i++)
        {
        if(a[i]==0)
        continue;
        if(a[i]<min)
        {
        min=a[i];
        pos=i;
        }
       }
       return pos;
       }
void display(struct process *p)
{
    int i=1;
    while(1)
    {
        printf("Arrival time%d ",p[i].at);
        printf("Burst Time%d ",p[i].bt);
        printf("Response Time%d ",p[i].rt);
        printf("comlete Time%d ",p[i].c);
        printf("waiting Time%d ",(p[i].rt-p[i].at));
        printf("\n\n");
        i++;
        if(i==5)
        break;
    }
}
main()
{
      struct process p[100];
    int b[100];
    int a[4];//since number of process taken are four
      puts("Enetr the process arival time and burst time");
      int i=0;
    int j=0;
      while(1)
      {
      i++;
      scanf("%d",&(p[i].at));
      scanf("%d",&(p[i].bt));
    a[j]=p[i].bt;
    j++;
      if(i==4)
      break;
      }
    int x=0;
    int y=0;
       j=0;
      while(x!=-1)
    {
        a[x]=a[x]-1;
        b[y]=x;
        y++;
        if(j!=3)
        j++;
        x=min(a,j);

    }
    printf("\n\n");
      for(i=0;i<y;i++)
    printf("%d\n",b[i]);
      getch();
      }

FCFS ALGORITHM

2013-09-08T04:49:00.002-07:00

First we tried to calculate the response time and complete time
for the first process response time is equal to arrival time and complete time is equal to the sum of response time and burst time.
For next process
                            if arrival time is equal to the complete time of the previous process then there will be no idle time and response time is equal to the complete time of the previous process
   if arrival time is greater than the complete time of the previous process then there will be the idle time and the response time will equal to the arival time of the porcess
   if arrival time is less than the complete time of the previous process then there will again no idle time and response time is equal to to the complete time of the previous time

For all the above case
complete time =response+burst time
waiting time=response time-arrival time

#include<stdio.h>
#include<stdlib.h>
struct process
{
       int at; //arival time
       int bt; //burst time
       int rt; //response time
       int c; //completed time
       int wt; //waiting time
       int trt;
       }; //structure to hold all the attributes associated with process

void display(struct process *p)//Function to display all the attributes of the process
{
    int i=1;
    while(1)
    {
        printf("Arrival time%d ",p[i].at);
        printf("Burst Time%d ",p[i].bt);
        printf("Response Time%d ",p[i].rt);
        printf("comlete Time%d ",p[i].c);
        printf("waiting Time%d ",(p[i].rt-p[i].at));
        printf("\n\n");
        i++;
        if(i==4)
        break;
    }
}
void fcfs(struct process *p)//first position of the array is ignored and counting has started from index value one
{
     if((p[1].at)>0)
      printf("Idle   0-%d\n",p[1].at);
      p[1].rt=p[1].at;
      p[1].wt=0;
      p[1].c=(p[1].at+p[1].bt);
      int i=2;
      while(1)
      {

             if(p[i].at==p[i-1].c)
             p[i].rt=p[i-1].c;

             if((p[i].at)>(p[i-1].c))
             {
             printf("Idle   %d-%d\n",p[i-1].c,p[i].at);
             p[i].rt=p[i].at;
             p[i].c=p[i].rt+p[i].bt;
              }

              if(p[i].at<p[i-1].c)
              {
              p[i].rt=p[i-1].c;
              p[i].c=p[i].rt+p[i].bt;
              }

              i++;
              if(i==4)
              break;
        }
}
main()
{
      struct process p[100];
      puts("Enetr the process arival time and burst time");
      int i=0;
      while(1)
      {
      i++;
      scanf("%d",&(p[i].at));
      scanf("%d",&(p[i].bt));
      if(i==3)
      break;
      }
      fcfs(p);
      display(p);
      }

Cookie handling through Javascript

2013-09-04T11:38:00.002-07:00

Following Code will work only in mozilla...for chrome browser need to be handled explicitly

<html>
<head>

</head>
<body>
<button type "button" onclick="z()">A</button>
<button type "button" onclick="x()">B</button>
<p id="m">A 0</p>
<p id="g">B 0</p>

<script>
var b=document.cookie
document.write(b)
if(b=="")
{
var i=0
var j=0;
}
else
{
var a=document.cookie
var i=parseInt(a.charAt(0))
var j=parseInt(a.charAt(2))
}
function z()
{
i=i+1;
document.getElementById("m").innerHTML="A: "+i
document.cookie=i+" "+(j+0)
}
function x()
{
j=j+1;
document.getElementById("g").innerHTML="B: "+j
document.cookie=i+" "+(j+0)
}
</script>

</body>
</html>

2013-08-09T10:58:00.001-07:00

Its just an example of multiplying any number by 2^n-1 or 2^n+1 without using any multiplication symbol.

//multiplication of the number by 2^n+1 2^n-1

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>//will not work in linux

main()

{

int n=3;

int m=n<<3;

printf("%d\n",(m-n));//multiplying 3 by 7

printf("%d",(m+n));//multiplying 3 by 9

getch();

}

Find highest length substring such that there are equal number of 0’s and 1’sin array of 1’s and 0’s only

2013-08-03T09:58:00.000-07:00

I saw this question on some site stating it was asked in some campus placement....so here is the solution..

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

main()
{
char ch[100];
int l;
int num0=0;
int num1=0;
int even=0;

puts("Enetr the string\n");
gets(ch);//need not to put & since ch is itself a pointer
l=strlen(ch);
int t=l;
if(l%2==0)
even=1;
printf("%d\n",l);
for(int i=0;i<l;i++)
{
if(ch[i]=='0')
num0++;
else
num1++;
}
if((num0==num1))
{
puts("Length of max substring having equal number of zeros and one\n");
printf("%d",l);
}
else{
if(even==0)
t=t+1;
int i=0;
num0=0;
num1=0;
int j=0;
while(t!=0)
{ int w=0;
t=t-2;
j=t;
while(j!=(l+1))
{
for( i=w;i<j;i++)
{
if(ch[i]=='0')
num0++;
else
num1++;

}
if(num0==num1)
{
printf("Maximum substring having equal number of 0's and 1's is %d between %d",w,j-1);
getch();
}
else{
num0=0;
num1=0;
w=w+1;
j=j+1;
}
}

}
}

getch();
}

Traversing link-list in Reverse Order(Recursion)

2013-08-01T09:07:00.000-07:00

Here we traversing the singly-link list in reverse order without saving the contents in another strucutre

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct link
{
int data;
struct link *next;

};

void add(struct link **p,int d)
{struct link *r,*q;
q=*p;
if(*p==NULL)
{
r=(struct link *)malloc(sizeof(struct link));
r->data=d;
r->next=NULL;
*p=r;

}
else
{
while(q->next!=NULL)
{q=q->next;
}
r=(struct link *)malloc(sizeof(struct link));
r->data=d;
r->next=NULL;
q->next=r;

}

}
void display(struct link **p)
{
struct link *q=*p;
while(q!=NULL)
{
printf("%d\n",q->data);
q=q->next;
}
}
void reversetraverse(struct link *p)//using recursion we traversing
{
struct link *q=p;
if(q->next==NULL)
{
printf("%d\n",q->data);
return;
}
reversetraverse(q->next);
printf("%d\n",q->data);

}

main()
{
struct link *p;
p=NULL;

add(&p,5);
add(&p,5);
add(&p,6);
display(&p);
reversetraverse(p);
getch();
}

Recursion-Reversing a String(JAVA)

2013-08-01T08:55:00.002-07:00

public class Reverse
{
String s;
static String r="";

public Reverse()
{
}
public void reverse(String s,int i)//earlier we tried using only string as an argument in that case i would be either static or class variable and in both case for all the stack elements value if i would be 5 hence output will "yyyyy"
{

if(i==5)
{
r=r+s.charAt(i);
return;

}
reverse(s,i+1);
r=r+s.charAt(i);//everything that comes after the function call is call in the reverse method we have used that concept
}
public static void main (String args[])
{
Reverse obj=new Reverse();
obj.reverse("Tanmay",0);
System.out.println(obj.r);
}
}

Static Stacks

2013-01-21T09:00:00.003-08:00

Static Implementation of Stack through C

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 10
struct stack
{
int a[max];
int top;
};

void push(struct stack *p,int n)
{
if(p->top==max-1)

{
printf("STACK FULL");
}
else
{
p->a[++p->top]=n;
}

}//end of push

int pop(struct stack *p)
{
if(p->top==-1)
{
printf("\nStack is empty\n");
return -999;
}
else
return p->a[p->top--];
}//end of POP

int peek(struct stack *p)
{
if(p->top!=max-1)
return p->a[p->top];
}//help us to see the top most element of the stack without removing it

int menu(struct stack *s)
{
printf("\n1.PUSH\n2.POP\n3.PEEK\n4.EXIT\n");
int a;
do
{
printf("Enetr the choice\n");
scanf("%d",&a);

switch(a)
{
case 1:

printf("Enter the number\n");
int n;
scanf("%d",&n);
push(s,n);
return 1;
break;
case 2:
printf("%d\n",pop(s));
return 2;
break;
case 3:printf("%d",peek(s));
return 3;
case 4:return 4;
break;
}

}while(a>4||a<1);

}

main()
{
struct stack s;
s.top=-1;
int x;
do{
x=menu(&s);
}while(x!=4);

getch();
}

QUICK SORT

2012-10-21T09:33:00.000-07:00

Quick sort is divide and conquer algorithm .Its one of the most influential algorithm of 20th century.

Its a top down approach every time a element is taken and is fixed to some position and then from that fixed place array is portioned in two sub arrays(fixing the position of the pivot is termed as portioning the data) which a recursively portioned further.
It is in place sorting algorithm or in situ

Generally we make first element as the pivot in an array but this in all ready sorted array does n^2 number of steps thus we prefer to do random shuffling to an array before passing it to quick sort function

Explanation-Here we have taken first element of the array as the pivot we can take any element as the pivot or median for the best performance.If an array was sorted then we would have taken first element as pivot it would have resulted in worst performance.Thus while doing qsort we must put the given array to a shuffling function

Here split function helps in implementing the divide and conquer stuff by dividing the array into sub-arrays and qsort fixes the position of pivot

Time complexity

Best Case nlogn (in best case number of compares are 1.39nlog(n))

Average Case nlogn (Depth of recursion is logarthmic)

Worst Case n^2

Space Complexity O(n)

Stability* -In normal and efficient implementation of Quick sorting it is not stable

Shuffling is needed for performance grantee

Optimizing quick sort

Use of extra array may help in partitioning but its not worth using it because it takes extra memory(and becomes same as merge sorting)
it can be improved by using cut off ie after dividing array into small sub arrays and applying insertion sort, insertion sort handles the nearly sorted array efficiently and moreover it can sort the numbers during runtime
we can make pivot=median of the data and for large data we can get the median by taking sample the data

Comparison

In average case merge sorting do 39% more compares than quick sorting but quick sorting is faster than merge sorting because it has less data movement

Insertion and merge sort are stable while bubble selection and quick(in an efficient implimentation) are not stable

Insertion and merge sort are stable because in their algorithm we never make equal item pass or swap

What are stable sorting algorithms-:

In a stable sorting algorithms relative order of the equal elements are maintained because we never swap the elements having the equal values(use full when we have lot many fields and need to arrange the data according to any field as required)

int split(int *a,int lower,int upper)
{   int temp;
    int p=lower+1;
    int q=upper;
    int pivot=a[lower];
    while(q>=p)//>= is must because if only > is used here then there would one less swapping and that will affect the sorting    {
while(a[p]<pivot)
    p++;
              while(a[q]>pivot)
              q--;
              if(q>p)
              {
               temp=a[p];
              a[p]=a[q];
              a[q]=temp;
                     }
              }
              temp=a[lower];
              a[lower]=a[q];
              a[q]=temp;
              return q;
}
void qsort(int *a,int lower,int upper)
{
     int i;
     if(upper>lower)
     {
     i=split(a,lower,upper);
     qsort(a,lower,i-1);
     qsort(a,i+1,upper);
     }
}
main()
{
     int a[10]={11,2,9,13,57,25,17,1,90,3};
     qsort(a,0,9);
     for(int i=0;i<=9;i++)
     cout<<a[i]<<endl;
     getch();

}

power of 2 in constant time

2012-10-15T11:33:00.000-07:00

Checking if number can be presented in power of 2 in constant time:

Algorithm

Number which can be represented in power of 2 its binary form will have 1 only at msb while
number one less than it will have 0 at msb while all other will have 1.
For examble
64=1000000
63=0111111
Now if we multiply each bit of 64 with corresponding bit of 63 we will get 0

SOURCECODE
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int m=64;
int n=63;
if((m&n)==0)//bitwise operator
cout<<"yes number can be represented in power of two";
else
cout<<"cannot be represented in power of two";
getch();
}

Memory Layout in C

2012-07-24T11:35:00.000-07:00

Types of memory

Memory layout in C

Whenever program is compiled five types of memories are given to the program to carry out its function

· Text Segment

· Initialized data segment

· Uninitialized data segment

· Stack

· Heap

Text Segment-

Also known as the code segment

Contains executable instructions

Text segment is placed below stack and heap to prevent overflow

It is a read only memory so that it cannot be changed by accident

Initialize Data Segment-

Usually called Data Segment

It contains a static variables and global variables that are initialized by the program

It is a not a read only memory since it can be changed

Uninitialized Data segment-

Also known an bss segment (blog started by symbol)

It contains static and global variables which are initialized to zero or which are not explicitly initialized

Stack-

It contains the local or automatic variables

Even every memory required by the recursive functions also some from the stack memory.

Heap-

Heap memory is the segment where Dynamic memory allocation takes place

Heap area is shared by all the libraires and dynamically loaded modules in the process.

It has a disadvantage that it need to be manually freed thus leads to memory leaks or fault segment

Moreover variables allocated in stack memory are much faster to access than heap memory

MEMORY VIOLATIONS

2012-07-18T03:43:00.003-07:00

MEMORY VIOLATIONS

Dangling Pointers and wild pointers are among the few causes of memory safety violations.C and C++ provides with one of the most powerful tool programming world ever came with and this was Pointers but this gave programmer immense control over memory addresses and sometimes we try to acces memory which we are not suppose to access and this is called FAULT SEGMENT

Above we mentioned two types of memory violations-Dangling and Wild.
Dangling Pointers arises when some object is deleted or relocated or when some memory is made free without making pointer variable null. This happens because even after deletion pointer points to the same location in memory even though the reference has been deleted or may be getting used for some other purposes

For example
void func()
{
char *dp=malloc(1000)
free(dp); //here dp becomes dangling pointer
dp=NULL// now pd is null pointer and no longer a dangling pointer
}

Interesting thing about dangling pointers
char ch='a';
char *c=NULL;
c=&ch;
free(c);
printf("%c",*c);
It will still print the a because it still pointing to same memory location

Wild pointers-:
Main cause of it is not initializing the pointer variable to null when it is initially declared thus every pointer which has not been explicitly initializes is considered as a Wild pointers
For example

int f(int i)
{
char *dp//wild pointers
static char *scp//not a wild pointer because static initializes it to 0
}

SMART POINTERS
its a type of abstract data type and provides the additional features to the pointers such as automatic garbage collection and bound checking and is very useful in removing Dangling pointers.They set the pointers automatically to null when ther object is deleted. Java and C# dosent requires any smart pointers because they have there own garbage collection techniques
LISP was the first language having garbage collection