Monday, February 7, 2011

Program to restrict keyboard using c++

#include
#include
#include
using namespace std;
int main()
{
char input[250] = {'\0'};
char *i = input;
char c;
cout<<"ENTER ALPHA CHARACTERS : ";
do{
c = getch();
if(isalpha(c)) cout< }while(c!=13);
cout< <<"PHRASE : "< cin.ignore();
cin.get();
return 0;

}

Sunday, February 6, 2011

How can I make my blog load faster? - Blogger Help

Process Synchronization

idealstudent.blogger.com

Dinning Philosopher Problem

OBJECTIVE: Implementation of process synchronization(DINNING PHILOSOPHER PROBLEM)

THEORY: The goal of problem is to create a program that simulate the behavior of 5 philosopher gathered around a table to think and eat.

Each philosopher has one fork, but needs two forks to eat.Thus the pholoshper decide to share their forks. When a philosopher wants to eat, he takes the fork on his left,whwn it is available,then the fork on his right,eats,and then puts forks back.

After the philosopher have thought and eaten several times ,it may happen that all philosophers simultaneously decide to eat.they take their left fork,and find the right forkalready taken by their right neighbor.In this case,if nothing has been foreseen the philosopher will stay in that situation(deadlock)indefinitely.the program should avoid that situation.

PROGRAM:

#include<sim/sim.h>

const double duration=52*7*24.0;

const int number =5;

const int eatingtime=2;

const int thinkingtime=5;

simulation*sim;

generator*g;

resource*chopstic[number];

histogram*thinking;

class eat:public event

{

public:

eat(int i);

virtual int operator()();

private:

int id;

};

Class think:public event

{

Public:

think(int i);

virtual int operator()();

private:

int id;

};

Class await:public event

{

public:

await(int i)

virtual int operator()();

private:

int id;

};

eat::eat(int i):event()

{

Id=I;

}

int eat::operator()()

{

double t=g->exponential(eatingtime);

think*th=new think(id);

sim->schedule(th,t);

sim->terminate(this);

return ok;

}

think::think(int i):event()

{

id=I;

}

Int think::operator()()

{

chopstick[id]->release();

chopstick[id+1]%number->release();

double t=g->exponential(thinkingtime);

thinking->sample(id,t/duration*100);

await*aw=new await(id);

sim->schedule(aw,t);

sim->terminate(this);

return ok;

}

await::await(int i):event()

{

id=I;

}

Int await::operator()()

{

If((chopstick[id]->available()&&(chopstick[(id+1)%number]->available()))

{

chopstick[id]->acquire();

chopstick[id+1]%number->acquire();

eat*e=new eat(id);

sim->passivate(this);

sim->schedule(e,o);

sim->terminate(this);

}

else if(!conditional())

sim->hold(this);

return ok;

}

class application:public session

{

public:

application(int argc,char**argv);

int main();

};

application::application(int argc,char**argv):session(argc,argv,”philosophers”)

{}

int application::main()

{

sim=new simulation();

g=new generator(80,20,19);

thinking=new histogram(“.h”,”-columns 5-title thinkingtime”);

tk->pack(thinkingtime);

tk->update();

for(int i=0;i<number,i++)

{

chopstick[i]=new resource(1);

await*aw=new await(i);

sim->schedule(aw,0);

}

sim->run(duration);

cout<<(*thinking)<<endl;

delete thinking;

delete sim;

return 0;

}

main(int,char**argv)

{

session*s=new application(argc,argv);

return s->run();

}

Critical section Problem Using Dekker's Algorithm

OBJECTIVE: Write a program for synchronizing of critical section problem using Dekker’s Algorithm.

THEORY: In concurrent programming a critical section is a piece of code that asses a shared resource (data structure or device ) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will only have to wait a fixed time to enter it (i.e. bounded waiting .

PROGRAM:

#include<sydio.h>

#include<conio.h>

void main()

{

int choice;

int c1=1,c2=1,turn=1;

clrscr();

{

printf(“\n1.Process 1 Enter”);

printf(“\n2.Process 2 Enter”);

printf(“\n3.Both Process Enter”);

printf(“\n4.Exit”);

scanf(“%d”,&choice);

if(choice==1)

{

c1=0;

while(c2==0)

{
if(turn==2)

c1=1

while(turn==2);

c1=0;

}

printf(“\nProcess P1 Enters the Critical section”);

c1=1;

turn=2;

else

printf(“\nIt is the turn process P2”);

}

if(choice==2)

{

c2=0;

while(c1==0)

{

if(turn==1)

c2=1;

while(turn==1);

c2=0;

}

printf(“\nProcess P2 enters in critical section”);

c2=1;

turn=1;

else

printf(“\nIt is turn of Process P1”);

}

while(choice!=4);

}

OUTPUT:

Enter the choice: 1

Process 1 Enters Critical section

Enter choice 3

Both Process i

Synchronizing POSTFIX thread using MUREX variable

OBJECTIVE: Write a Program for synchronizing POSTFIX thread using Murex variable.

THEORY:

Technically, a thread is defined as an independent stream of instructions that can be scheduled to run as such by operating system. But what does this mean?

To the software developer, the concept of “procedure” that runs independently from its main program may best describes a thread.

PROGRAM:

#include<pthread.h>

#include<stdio.h>

#include<malloc.h>

typedef struct{
double *a;

double *b;

double sum;

int veclen;

}DOTDATA;

#define NUMTHREAD 4

#define VECLEN 100

DOTDATA dotstr;

Pthread_t callThd[NUMTHRDS];

Pthread_mutexsum;

void *dotprod(void *arg)

{
int i,start,end,offset,len;

double mysum, *x,*y;

offset = (int)arg;

len=dotstr.veclen;

start=offset*len;

end=start+len;

x=dotstr.a;

y=dotstr.b;

mysum=0;

for(i=start;i<end;i++)

{

Mysum+=(x[i]*y[i]);

}

pthread_mutex_lock(&mutexsum);

dotstr.sum+=mysum;

pthead_mutex_unlock(&mutexsum);

pthread_exit((void *)0) ;

}

int main(int argc,char *arvg[])

{

int i;

double *a,*b;

int status;

pthread_attr_t attr;

a=(double *)malloc(NUMTHRDS*VECLEN*sizeof(double));

b==(double *)malloc(NUMTHRDS*VECLEN*sizeof(double));

for(i=0;i<VECLEN*NUMTHRDS;i++)

{

a[i]=1.0;

b[i]=a[i];

}
dotstr.vectlen=VECTLEN;

dotstr.a=a;

dotstr.b=b;

dotstr.sum=0;

pthread_mutex_init(&mutex,NULL);

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_JOOINABLE);

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

{
pthread_create(&callTHd[i],&attr,dotprod,void(*)i);

}
pthread_attr_destroy(&attr);

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

{
pthread_join(callThd[i],(void **)&status);

}
printf(“Sum=%f\n”,dotstr.sum);

free(a);

free(b);

pthread_mutex_destroy(&mutexsum);

pthread_exit(NULL);

}

OUTPUT:

a=3i+5j-2k

b=2i-2j-2k

a.b=(3i+5j-2k).( 2i-2j-2k).

a.b=(3X2)+(5X

Banker's Algorithm

OBJECTIVE: Implementation of Banker's Algorithm.

THEORY:
The Banker's algorithm is run by the operating system whenever a process requests resources.The algorithm avoids deadlock by denying or postponing the request if it determines that accepting the request could put the system in an unsafe state (one where deadlock could occur). When a new process enters a system, it must declare the maximum number of instances of each resource type that may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.

PROGRAM:
#include<stdio.h>

//global variables.
int Pcurr[3][3]; //max of 3 processes, 3 resources

int Pmax[3][3];
int avl[]={6,4,7};
int avltemp[]={6,4,7};
int maxres[]={6,4,7};

int running[3]; //Which processes are running (this appears to be used as a boolean)

int i,j, safe=0,count=0;;

main()

{

for(i=0;i<3;i++)
running[i]=1; //set all the processes to "running" = true (1)
int ch;

initresources();

while(1) //loop forever

{

system("clear"); //calls a command prompt command, this looks like unix clear screen to manage the output.

count=0; //extremely excessive logic to determing that you have a process running.
//should be if(!(running[0]+running[1]+running[2])) to replace 8 lines here for(i=0;i<3;i++)
{
if(running[i])
count++;
}
if(count==0)
{
printf("\n\n\n\n\nCongratulations! We have completed execution of all processes successfully without any deadlock!");
getchar();
break;
}

//end excessive logic section, begin menu section.
//The following is just a menu for the user to see what is going one at each iteration.
else
{
printf("\nDeadlock Prevention using Banker's Algorithm:\n");
viewresources();
printf("\n1. Request resource(s) for a process\n");

printf("\n2. View Allocated Resources\n");

printf("\n3. Exit\n");

printf("\nEnter your choice:\n");

scanf("%d",&ch);

if(ch==1)
{
requestresource();
getchar();
}
else if(ch==2)
{
viewresources();
getchar();
}

else if(ch==3)

break;

else
printf("\nInvalid Choice, please try again!\n");

}
}

}

//initialization routine, this defines the current "problem" to be tested.
//I do not really understand what values go where.
initresources()

{

//for each process, get curr. requirement and max. requirement->check if max. req....
Pmax[0][0]=3; Pcurr[0][0]=1; avl[0]=3;
Pmax[0][1]=3; Pcurr[0][1]=2; avl[1]=1;
Pmax[0][2]=2; Pcurr[0][2]=2; avl[2]=1;
Pmax[1][0]=1; Pcurr[1][0]=1;
Pmax[1][1]=2; Pcurr[1][1]=0;
Pmax[1][2]=3; Pcurr[1][2]=3;
Pmax[2][0]=1; Pcurr[2][0]=1;
Pmax[2][1]=1; Pcurr[2][1]=1;
Pmax[2][2]=5; Pcurr[2][2]=1;

}

// this routine mimics an OS resource request which basiclly checks if a resource is busy,
//if not gives it to your process, and then marks it busy. If it is busy to begin with some
//strategy is used to deny the request. Here, he deadlocks if the request cannot be done --
//I think that means that the processes cannot complete because of lack of resources, no matter
//what you do (Besides runnign them one at a time).
requestresource()

{

//check if it is allocated, will it go to deadlock
int proc, res[3];
printf("\nFor which Process, you need resources?(1-3):\n");
scanf("%d",&proc);
proc--;
if(running[proc])
{
printf("\nCurrently this process needs the foll. resources:\n");
printf("R1\tR2\tR3\n");
for(i=0;i<3;i++)
printf("%d\t",Pmax[proc][i]-Pcurr[proc][i]);
for(i=0;i<3;i++)
{
loop_3:
printf("\nEnter no. of Resource %d to Allocate to Process %d:\n",i+1,proc+1);
scanf("%d",&res[i]);
if((res[i]>(Pmax[proc][i]-Pcurr[proc][i]))||(res[i]>avl[i]))
{
printf("\nInvalid Value!, try again!");
goto loop_3;

}
}
getchar();
if(allocate(proc,res))
{
printf("\nResources successfully allocated.\n");
if(checkcompletion(proc))
printf("\nProcess %d has completed its execution and its resources have been released.\n",proc+1);
}
else
printf("\nResouces cannot be allocated as it may lead to Deadlock!\n");
}
else
{
printf("\nInvalid Process no.\n");
getchar();
}
}

///allocate a resource to a process, used in the above routine. T
//his is just management code to mark the appropriate stuff when an allocation is allowed.
int allocate(int proc, int res[3])
{
for(i=0;i<3;i++)
{
Pcurr[proc][i]+=res[i];
avl[i]-=res[i];
}
if(!checksafe())
{
for(i=0;i<3;i++)
{
Pcurr[proc][i]-=res[i];
avl[i]+=res[i];
}
return 0;
}
return 1;
}
int checkcompletion(int proc)
{
if((Pcurr[proc][0]==Pmax[proc][0])&&(Pcurr[proc][1]==Pmax[proc][1])&&(Pcurr[proc][2]==Pmax[proc][2]))
{
for(i=0;i<3;i++)
{
avl[i]+=Pmax[proc][i];
}
running[proc]=0;
return 1;
}
return 0;
}

//print the state of the resources for the user to study.
viewresources()

{

printf("\n----Current Snapshot of the system----\n");
printf("\nMax. resources in the system:\n");
printf("R1\tR2\tR3\n");
for(i=0;i<3;i++)
printf("%d\t",maxres[i]);
printf("\nCurrent resources available in the system:\n");
printf("R1\tR2\tR3\n");
for(i=0;i<3;i++)
printf("%d\t",avl[i]);
printf("\n\nMax. resources required for Completion of each process:\n");
printf("\tR1\tR2\tR3\n");
for(i=0;i<3;i++)
{
if(running[i])
{
printf("P%d\t",i+1);
for(j=0;j<3;j++)
printf("%d\t",Pmax[i][j]);
printf("\n");
}
}

printf("\n\nCurr. resources allocated for each process:\n");
printf("\tR1\tR2\tR3\n");
for(i=0;i<3;i++)
{
if(running[i])
{
printf("P%d\t",i+1);
for(j=0;j<3;j++)
printf("%d\t",Pcurr[i][j]);
printf("\n");
}
}
}

// this is what you want: the bankers algorithm portion of the code! It uses the algorithm to generate a true or false (safe or unsafe) value
//which is used to see if a resource can be allocated to a given process.

int checksafe()
{
//Check if atleast one process can get all resources it needs --> Banker's algorithm
safe=0;
for(i=0;i<3;i++)
{
avltemp[i]=avl[i];
}
for(i=0;i<3;i++)
{
if(running[i])
{
if((Pmax[i][0]-Pcurr[i][0]<=avltemp[0])&&(Pmax[i][1]-Pcurr[i][1]<=avltemp[1])&&(Pmax[i][2]-Pcurr[i][2]<=avltemp[2]))
{
for(j=0;j<3;j++)
avltemp[j]+=Pcurr[i][j];
safe=1;
}
}
}
return safe;
}

CPU scheduling : Round Robin

OBJECTIVE: Write a program in c to implement Round Robin scheduling.

THEORY: Round-robin job scheduling may not be desirable if the sizes of the jobs or tasks are highly variable. A process that produces large jobs would be favoured over other processes. This problem may be solved by time-sharing, i.e. by giving each job a time slot or quantum (its allowance of CPU time), and interrupt the job if it is not completed by then. The job is resumed next time a time slot is assigned to that process.

Example: The time slot could be 100 milliseconds. If job1 takes a total time of 250ms to complete, the round-robin scheduler will suspend the job after 100ms and give other jobs their time on the CPU. Once the other jobs have had their equal share (100ms each), job1 will get another allocation of CPU time and the cycle will repeat. This process continues until the job finishes and needs no more time on the CPU.

PROGRAM:

#include<stdio.h>
#include<conio.h>
main()
{
int st[10],bt[10],wt[10],tat[10],n,tq;
int i,count=0,swt=0,stat=0,temp,sq=0;
float awt=0.0,atat=0.0;
clrscr();
printf("Enter number of processes:");
scanf("%d",&n);
printf("Enter burst time for sequences:");
for(i=0;i<n;i++)
{
scanf("%d",&bt[i]);
st[i]=bt[i];
}
printf("Enter time quantum:");
scanf("%d",&tq);
while(1)
{
for(i=0,count=0;i<n;i++)
{
temp=tq;
if(st[i]==0)
{
count++;
continue;
}
if(st[i]>tq)
st[i]=st[i]-tq;
else
if(st[i]>=0)
{
temp=st[i];
st[i]=0;
}
sq=sq+temp;
tat[i]=sq;
}
if(n==count)
break;
}
for(i=0;i<n;i++)
{
wt[i]=tat[i]-bt[i];
swt=swt+wt[i];
stat=stat+tat[i];
}
awt=(float)swt/n;
atat=(float)stat/n;
printf("Process_no Burst time Wait time Turn around time
");
for(i=0;i<n;i++)
printf("%d %d %d %d
",i+1,bt[i],wt[i],tat[i]);
printf("Avg wait time is %f
Avg turn around time is %f",awt,atat);
getch();
}

0/1 Knapsack Problem

OBJECTIVE: Implementation of 0-1 dynamic knapsack problem.
THEORY: Let i be the highest-numbered item in an optimal solution S for W pounds. Then S` = S - {i} is an optimal solution for W - wi pounds and the value to the solution S is Vi plus the value of the subproblem.

We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, . . . , i and maximum weight w. Then
0 if i = 0 or w = 0
c[i,w] = c[i-1, w] if wi ≥ 0
max [vi + c[i-1, w-wi], c[i-1, w]} if i>0 and w ≥ wi
The algorithm takes as input the maximum weight W, the number of items n, and the two sequences v = <v1, v2, . . . , vn> and w = <w1, w2, . . . , wn>. It stores the c[i, j] values in the table, that is, a two dimensional array, c[0 . . n, 0 . . w] whose entries are computed in a row-major order. That is, the first row of c is filled in from left to right, then the second row, and so on. At the end of the computation, c[n, w] contains the maximum value that can be picked into the knapsack.
PROGRAM:
#include <stdio.h>
#define MAXWEIGHT 100
int n = 3;
int c[10] = {8, 6, 4};
int v[10] = {16, 10, 7};
int W = 10;
void fill_sack() {
int a[MAXWEIGHT];
int last_added[MAXWEIGHT];
int i, j;
int aux;
for (i = 0; i <= W; ++i) {
a[i] = 0;
last_added[i] = -1;
}
a[0] = 0;
for (i = 1; i <= W; ++i)
for (j = 0; j < n; ++j)
if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
a[i] = a[i - c[j]] + v[j];
last_added[i] = j;
}
for (i = 0; i <= W; ++i)
if (last_added[i] != -1)
printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
else
printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);
printf("---\n");
aux = W;
while ((aux > 0) && (last_added[aux] != -1)) {
printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
aux -= c[last_added[aux]];
}
printf("Total value added: %d$\n", a[W]);
}
int main(int argc, char *argv[]) {
fill_sack();
return 0;
}
OUTPUT:
Weight 0; Benefit: 0; Can't reach this exact weight.
Weight 1; Benefit: 0; Can't reach this exact weight.
Weight 2; Benefit: 0; Can't reach this exact weight.
Weight 3; Benefit: 0; Can't reach this exact weight.
Weight 4; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 0
Weight 5; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 1
Weight 6; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 0
Weight 7; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 1
Weight 8; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 0
Weight 9; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 1
Weight 10; Benefit: 17; To reach this weight I added object 2 (10$ 6Kg) to weight 4
---
Added object 2 (10$ 6Kg). Space left: 4
Added object 3 (7$ 4Kg). Space left: 0
Total value added: 17$

kruskal Algorithms

OBJECTIVE: Implementation of kruskal algorithm.

THEORY: Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example of a greedy algorithm.

PROGRAM:
#include<stdio.h>

#include<conio.h>

#define MAX 20

struct edge

{

int u;

int v;

int weight;

struct edge *link;

}*front = NULL;

int father[MAX];

struct edge tree[MAX];

int n;

int wt_tree=0;

int count=0;

void make_tree();

void insert_tree(int i,int j,int wt);

void insert_pque(int i,int j,int wt);

struct edge *del_pque();

void main()

{

int i;

create_graph();

make_tree();

printf("Edges to be included in spanning tree are :\n");

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

{

printf("%d->",tree[i].u);

printf("%d\n",tree[i].v);

}

printf("Weight of this minimum spanning tree is : %d\n", wt_tree);

}

create_graph()

{

int i,wt,max_edges,origin,destin;

printf("Enter number of nodes : ");

scanf("%d",&n);

max_edges=n*(n-1)/2;

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

{

printf("Enter edge %d(0 0 to quit): ",i);

scanf("%d %d",&origin,&destin);

if( (origin==0) && (destin==0) )

break;

printf("Enter weight for this edge : ");

scanf("%d",&wt);

if( origin > n || destin > n || origin<=0 || destin<=0)

{

printf("Invalid edge!\n");

i--;

}

else

insert_pque(origin,destin,wt);

}

if(i<n-1)

{

printf("Spanning tree is not possible\n");

exit(1);

}

void make_tree()

{

struct edge *tmp;

int node1,node2,root_n1,root_n2;

while( count < n-1)

{

tmp=del_pque();

node1=tmp->u;

node2=tmp->v;

printf("n1=%d ",node1);

printf("n2=%d ",node2);

while( node1 > 0)

{

root_n1=node1;

node1=father[node1];

}

while( node2 >0 )

{

root_n2=node2;

node2=father[node2];

}

printf("rootn1=%d ",root_n1);

printf("rootn2=%d\n",root_n2);

if(root_n1!=root_n2)

{

insert_tree(tmp->u,tmp->v,tmp->weight);

wt_tree=wt_tree+tmp->weight;

father[root_n2]=root_n1;

}

void insert_tree(int i,int j,int wt)

{

printf("This edge inserted in the spanning tree\n");

count++;

tree[count].u=i;

tree[count].v=j;

tree[count].weight=wt;

}

void insert_pque(int i,int j,int wt)

{

struct edge *tmp,*q;

tmp = (struct edge *)malloc(sizeof(struct edge));

tmp->u=i;

tmp->v=j;

tmp->weight = wt;

if( front == NULL || tmp->weight < front->weight )

{

tmp->link = front;

front = tmp;

}

else

{

q = front;

while( q->link != NULL && q->link->weight <= tmp->weight )

q=q->link;

tmp->link = q->link;

q->link = tmp;

if(q->link == NULL)

tmp->link = NULL;

}

struct edge *del_pque()

{

struct edge *tmp;

tmp = front;

printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp->weight);

front = front->link;

return tmp;

}

Fractional Knapsack Problem

OBJECTIVE: Implementation of fractional knapsack problem.
THEORY: The Fractional Knapsack Problem usually sounds like this:
Thief has just broken into the Fort Knox! He sees himself in a room with n piles of gold dust. Because the each pile has a different purity, each pile also has a different value (v[i]) and a different weight (c[i]). Ted has a knapsack that can only hold W kilograms.
PROGRAM:
#include <stdio.h>
#include<conio.h>
int n = 5;
int c[10] = {12, 1, 2, 1, 4};
int v[10] = {4, 2, 2, 1, 10};
int W = 15;
void simple_fill() {
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= c[maxi];
tot_v += v[maxi];
if (cur_w >= 0)
printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
else {
printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
tot_v -= v[maxi];
tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
}
}
printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}
int main(int argc, char *argv[]) {
simple_fill();
return 0;
}
OUTPUT:
Added object 5 (10$, 4Kg) completly in the bag. Space left: 11.
Added object 2 (2$, 1Kg) completly in the bag. Space left: 10.
Added object 3 (2$, 2Kg) completly in the bag. Space left: 8.
Added object 4 (1$, 1Kg) completly in the bag. Space left: 7.
Added 58% (4$, 12Kg) of object 1 in the bag.
Filled the bag with objects worth 17.33$.

N Queen Problem

OBJECTIVE: c Implementation of N-Queen problem.
THEORY: The concept of N queens problem is that we need to place N queens in N x N matrix where in which the following conditions should apply.
1. No two queens should be placed in the same row
2. No two queens should be placed in the same column
3. No two queens should be placed in the same diagonal

PROGRAM:
#include <stdio.h>
#include<conio.h>
define TRUE 1
define FALSE 0
int *board;
int main()
{
board=(int*)calloc(8+1,sizeof(int));
board++;
int col;
int queens=2;//example from userinput
for(col=1;col<=8;col++)
   placeQueens(1,col,queens);
}
void placeQueens(int row,int col,int queens)
{
   int i;
   for(i=1;i<row;i++)
   {
   if((board[i] == col) || ((row+col)==(i+board[i]))||((row-col)==(i-board[i])))
   {
   check= FALSE;
   }
   else
   check=TRUE;
   }
   if(check==TRUE)
   {
   board[row]=col;
  if(row==8)
   {
   for(i=1;i<=queens;i++)
   printf("(%d,%d)",i,board[i]);
   printf("\n");
   }
   else
   {
   for(i=1;i<=8;i++)
   placeQueens(row+1,i);
   }
   }
}

Heap Sort

OBJECTIVE: Implementation of heap sort.
THEORY: Heapsort primarily competes with quicksort, another very efficient general purpose nearly-in-place comparison-based sort algorithm. Quicksort is typically somewhat faster, due to better cache behavior and other factors, but the worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a deta
PROGRAM:
#include<stdio.h>
#include<conio.h>
void restoreHup(int*,int);
void restoreHdown(int*,int,int);
void main()
{
   int a[20],n,i,j,k;
   printf("Enter the number of elements to sort : ");
   scanf("%d",&n);
   printf("Enter the elements : ");
   for(i=1;i<=n;i++){
   scanf("%d",&a[i]);
   restoreHup(a,i);
   }
   j=n;
   for(i=1;i<=j;i++)
   {
   int temp;
   temp=a[1];
   a[1]=a[n];
   a[n]=temp;
   n--;
   restoreHdown(a,1,n);
   }
   n=j;
   printf("Here is it...");
   for(i=1;i<=n;i++)
   printf("%4d",a[i]);
getct();
}
void restoreHup(int *a,int i)
{
   int v=a[i];
   while((i>1)&&(a[i/2]<v))
   {
   a[i]=a[i/2];
   i=i/2;
   }
   a[i]=v;
}
void restoreHdown(int *a,int i,int n)
{
   int v=a[i];
   int j=i*2;
   while(j<=n)
   {
   if((j<n)&&(a[j]<a[j+1]))
   j++;
   if(a[j]<a[j/2]) break;

   a[j/2]=a[j];
   j=j*2;
   }
   a[j/2]=v;
}
OUTPUT:
Enter the number of elements to sort : 6
Enter the elements : 4 2 8 5 1 6
Here is it... 1 2 4 5 6 8

Saturday, February 5, 2011

Self

I am cool & loving ......

Programming in c

About Me

Monday, February 7, 2011

Program to restrict keyboard using c++

Sunday, February 6, 2011

How can I make my blog load faster? - Blogger Help

Process Synchronization

Dinning Philosopher Problem

PROGRAM:

Critical section Problem Using Dekker's Algorithm

Synchronizing POSTFIX thread using MUREX variable

Banker's Algorithm

CPU scheduling : Round Robin

0/1 Knapsack Problem

kruskal Algorithms

Fractional Knapsack Problem

N Queen Problem

Heap Sort

Saturday, February 5, 2011

Self