Anna University Syllabus Materials and Question Papers: CS2915 DATA STRUCTURES LABORATORY

CS2915 / DATA STRUCTURES LABORATORY

MIN HEAP

AIM

To write a C++ program to perform implementation of min heap and its operation.

ALGORITHM

Step 1: Start

Step 2: Define a class and declare the data members and member function

Step 3: In main function, display the choice to be selected

Insert, Display and Delete min

Step 4: If the option is insert, then get the element to be inserted and perform the

Necessary operation

Step 5: If the option is Delete min, then delete the minimum (root) element

Step 6: If the option is display, then display the elements in the heap

Step 7: Stop

PROGRAM

#include<iostream.h>

#include<math.h>

#include<stdio.h>

#include<conio.h>

//#include<stdarg.h>

//using namespace std;

template <class T>

class minheap

{

private:

T *heap;

int capacity;

int size;

public:

//constructor

minheap(int cap)

{

heap=new T[cap];

capacity=cap;

size=0;

}

void insert(T& item);

void deletemin();

void display();

};

//function to insert an element in min heap

argument 1 - the item to be inserted

template <class T>

void minheap<T>::insert(T& item)

{

int i;

if(size==capacity)

cout<<"Can't insert. Heap is full\n";

else

{

size=size+1;

i=size;

while((i>1)&&(heap[i/2]>item))

{

if(heap[i/2]>item)

heap[i]=heap[i/2];

i=i/2;

}

heap[i]=item;

}

//function to display the elements in min heap

template <class T>

void minheap<T>::display()

{

int levelNum=1;

int thisLevel=0;

int gap=16;

for( int i=1; i<=size; i++)

{

for(int j=0; j<gap-1; j++)

cout<<" ";

if(thisLevel != 0)

{

for(int j=0; j<gap-2; j++)

cout<<" ";

}

//if(sizeof(heap[i])==1)

if(heap[i]==1)

cout<<" ";

cout<<heap[i];

thisLevel++;

if(thisLevel == levelNum)

{

cout<<"\n\n";

thisLevel = 0;

levelNum *=2;

gap/=2;

}

cout<<"\n\n";

if(thisLevel !=0)

{

cout<<"\n\n";

}

//function to delete the minimum element

template <class T>

void minheap<T>::deletemin()

{

T del;

int temp,min=0,i=1,pos;

del=heap[1];

temp=heap[size];

//structure property

size=size-1;

heap[1]=temp;

//checking for heap order property

while(((2*i)<=size)||(((2*i)+1)<=size))

{

//finding min child of node i

min=heap[2*i];

pos=2*i;

if(((2*i)+1)<=size)

{

if(min>heap[(2*i)+1])

{

min=heap[(2*i)+1];

pos=(2*i)+1;

}

//if both the child are less than element inserted at i

if(min>heap[i])

{

cout<<"Deleted element is "<<del<<endl;

return;

}

else

{

//swapping during perculate down

temp=heap[pos];

heap[pos]=heap[i];

heap[i]=temp;

}

i=pos;

}

cout<<"Deleted element is "<<del<<endl;

}

//application file

int main()

{

minheap<int> mh(15);

int num,opt,i,n;

char ch;

clrscr();

cout<<"Enter the number of elements to be inserted\n";

cin>>n;

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

{

cout<<"Enter the element to be inserted :";

cin>>num;

mh.insert(num);

}

cout<<"Enter 1.Insert\n2.Display\n3.Delete\n";

{

cout<<"Enter option : ";

cin>>opt;

switch(opt)

{

case 1:

cout<<"Enter the element to be inserted :";

cin>>num;

mh.insert(num);

break;

case 2:

mh.display();

break;

case 3:

mh.deletemin();

mh.display();

break;

}

cout<<"Enter y to continue : ";

cin>>ch;

}while(ch=='y');

}

OUTPUT

Enter the number of elements to be inserted

Enter the element to be inserted :3

Enter the element to be inserted :5

Enter the element to be inserted :7

Enter the element to be inserted :9

Enter 1.Insert

2.Display

3.Delete

Enter option : 2

5 7

Enter y to continue : y

Enter option : 3

Deleted element is 3

9 7

Enter y to continue :n

RESULT

Thus the C++ progeam for Min Heap operations has been implemented and executed.

DEAPS

AIM

To write a C++ program for the implementation of deaps and perform its operation

ALGORITHM

Step 1: Start the program

Step 2: Create a class and declare its data members and member function

Step 3: In main function, display the following options

1. Insert

2. Delete min

3. Delete max

4. Height

5. Find parent – child

Step 4: If the option is insert, then get the element to be inserted and perform the

Necessary operation

Step 5: If the option is delete min, then delete the left child of the empty root and

Perform necessary changes

Step 6: If the option is delete max, then delete the right child of the empty root and

Then perform the necessary changes
Step 7: If the option is to find the height of the deap, then calculate the number of edges

Of the last leaf node

Step 8: If the option is 5, then get the node and display the parent and child of that node

Step 9: Terminate the program

PROGRAM

#include<iostream.h>

#include<stdlib.h>

#include<stdio.h>

#include<conio.h>

#define maxSize 1024

class Deap

{

public:

int deap[maxSize];

int n;

Deap();

int MinMaxHeap(int);

int MaxPartner(int);

int MinPartner(int);

void MinInsert(int, int);

void MaxInsert(int, int);

int DeleteMax();

int DeleteMin();

void Insert(int x);

void Print();

void height_deap();

int parent_child(int);

};

Deap::Deap()

{

n=1;

}

int Deap::MinMaxHeap(int i)

{

while(i>3)

{

i/=2;

}

if(i==2)

return 0;

return 1;

}

//Finding MaxPartner

int Deap::MaxPartner(int pos)

{

int offset =1;

int i =pos;

while(i>3)

{

i/=2;

offset*=2;

}

if((pos+offset) >n)

return (pos+offset)/2;

return pos+offset;

}

//Finding minPartner

int Deap::MinPartner(int pos)

{

int offset =1;

int i =pos;

while(i>3)

{

i/=2;

offset*=2;

}

return pos-offset;

}

//Min Insertion

void Deap::MinInsert(int at, int key)

{

for(int parent; (parent=at/2)!=1 &&

key<deap[parent];deap[at]=deap[parent], at=parent);

deap[at]=key;

}

//Max Insertion

void Deap::MaxInsert(int at, int key)

{

for(int parent; (parent=at/2)!=1 && key>deap[parent];

deap[at]=deap[parent], at=parent);

deap[at]=key;

}

//Max Deletion

int Deap::DeleteMax()

{

int i, j, key, x=deap[n--];

if(n>=3)

{

key=deap[3];

}

else

{

n--;

return deap[2];

}

for(i=3; 2*i<=n; deap[i]=deap[j], i=j)

{

j=i*2;

if(j+1<=n)

{

if(deap[j]<deap[j+1])

{

j++;

}

j=MinPartner(i);

int biggest =j;

if(2*j <=n)

{

biggest = 2*j;

if(((2*j+1)<=n) && (deap[2*j]<deap[2*j+1]))

{

biggest++;

}

if(x<deap[biggest])

{

deap[i]=deap[biggest];

MinInsert(biggest, x);

}

else

{

MaxInsert(i, x);

}

return key;

}

//min Deletion

int Deap::DeleteMin()

{

int i, j, key=deap[2], x=deap[n--];

for(i=2; 2*i<=n;deap[i]=deap[j], i=j)

{

j=i*2;

if(j+1<=n && deap[j] > deap[j+1])

{

j++;

}

j=MaxPartner(i);

if(x>deap[j])

{

deap[i]=deap[j];

MaxInsert(j,x);

}

else

{

MinInsert(i,x);

}

return key;

}

//Insertion

void Deap::Insert(int x)

{

n++;

if(n==sizeof(deap))

{

cout<<"Heap Full\n";

exit(1);

}

if(n==2)

{

deap[2]=x;

return;

}

if(MinMaxHeap(n))

{

int i=MinPartner(n);

if(x<deap[i])

{

deap[n]=deap[i];

MinInsert(i,x);

}

else

{

MaxInsert(n,x);

}

else

{

int i=MaxPartner(n);

if(x>deap[i])

{

deap[n]=deap[i];

MaxInsert(i,x);

}

else

{

MinInsert(n,x);

}

//Print

void Deap::Print()

{

int levelNum=2;

int thisLevel=0;

int gap=8;

for(int i=2; i<=n; i++)

{

for(int j=0; j<gap-1; j++)

{

cout<<" ";

}

if(thisLevel != 0)

{

for(int j=0; j<gap-1; j++)

{

cout<<" ";

}

//if(sizeof(deap[i])==1)

if(deap[i]==1)

{

cout<<" ";

}

cout<<deap[i];

thisLevel++;

if(thisLevel == levelNum)

{

cout<<"\n";

thisLevel = 0;

levelNum *=2;

gap/=2;

}

cout<<"\n";

if(thisLevel !=0)

{

cout<<"\n";

}

int Deap::parent_child(int key)

{

int i,j,k;

i=1;

while(i<=n)

{

j=i*2;

k=i*2+1;

if(key==deap[j] || key==deap[k])

{

cout<<"Key found... Parent:\t"<<i<<"\tChild:\t"<<key<<"\n";

return 1;

}

else

i++;

}

cout<<"Key is not found in deap\n";

return 0;

}

void Deap::height_deap()

{

int i,level;

level=0;

i=n;

while(i>=1)

{

level++;

i=i/2;

}

cout<<"\nHeight of the deap:\t"<<level-1<<"\n";

}

int main()

{

Deap a;

int data[20],ch, newElement, numElement,key;

clrscr();

cout<<"Deaps\n";

while(1)

{

cout<<"\n1.Insert";

cout<<"\n2.DeleteMin\n";

cout<<"\n3.DeleteMax\n";

cout<<"\n4.Height\n";

cout<<"\n5.Find Parent - Child\n";

cout<<"\n6.Exit\n";

cout<<"\nEnter your choice:\n";

cin>>ch;

switch(ch)

{

case 1:

cout<<"Enter the new element:\n";

cin>>newElement;

a.Insert(newElement);

a.Print();

break;

case 2:

key=a.DeleteMin();

cout<<"The Minimum Element is Deleted:\t"<<key<<"\n";

a.Print();

break;

case 3:

key=a.DeleteMax();

cout<<"The Maximum Element is Deleted:\t"<<key<<"\n";

a.Print();

break;

case 4:

a.height_deap();

break;

case 5:

cout<<"Enter the key to find its parent:\n";

cin>>key;

a.parent_child(key);

break;

case 6:

exit(0);

}

OUTPUT

DEAPS

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice:1

Enter the new element:

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice: 1

Enter the new element:

2 3

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice: 1

Enter the new element:

2 4

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice: 4

Height of the deap: 2

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice: 2

The Minimum Element is Deleted: 2

3 4

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice: 3

The Maximum Element is Deleted: 3

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice: 5

Enter the key to find its parent:

Key found... Parent: 1 Child: 4

1.Insert

2.DeleteMin

3.DeleteMax

4.Height

5.Find Parent - Child

6.Exit

Enter your choice:6

RESULT

Thus the C++ program for deap operations has been implemented and executed.

IMPLEMENTATION OF LEFTIST TREE

AIM

To write a c++ program for the implementation of leftist trees.

ALGORITHM

Step 1: Create a class and declare the data members and the member fuctions.

Step 2: There are three operations involved insert, merge and delete

Step 3: To insert an element into a minleftist tree, create a min leftist tree that

contains the above element.

Step 4: Merge the two min leftist tree.

Step 5: To delete the min element we combine the right and left subtree of the

root element, then delete the root element.

Step 6: To combine, first compare the two root keys of the leftist trees

Step 7: The node with the smallest key should be root element and merge its right

subtree with the tree which has the larger root key and then merge the new

tree with the leftist tree with the smallest root key.

Step 8: The Right and left subtrees of the nodes are interchanged to convert this

binary tree into a leftist tree.

PROGRAM

#include<iostream.h>

#include<conio.h>

class minleftist_tree;

class leftistnode

{

friend class minleftist_tree;

private:

int data;

leftistnode *lc,*rc;

int shortest;

};

class minleftist_tree

{

public:

minleftist_tree(leftistnode *init=0)

{

root=init;

}

void insert(int x);

void deletemin();

void display();

void dispin(leftistnode * curnode);

private:

leftistnode * minunion(leftistnode *, leftistnode *);

leftistnode *root;

};

leftistnode * minleftist_tree::minunion(leftistnode *a, leftistnode *b)

{

if (b==0) return a;

if (a->data > b->data)

{ // swap

leftistnode *temp;

temp=a;

a=b;

b=temp;

}

if(a->rc == NULL)

a->rc = b;

else

a->rc = minunion(a->rc,b);

if(a->lc == NULL)

{

a->lc = a->rc;

a->rc = NULL;

}

else if(a->lc->shortest < a->rc->shortest)

{

leftistnode *temp;

temp=a->lc;

a->lc=a->rc;

a->rc=temp;

}

//set shortest values

if(a->rc == NULL)

a->shortest = 1;

else

a->shortest = a->rc->shortest + 1;

return a;

};

void minleftist_tree::insert( int x)

{

leftistnode * newnode;

newnode = new leftistnode();

newnode->data = x;

newnode->rc = NULL;

newnode->lc = NULL;

newnode->shortest=1;

if (root == NULL)

{

root = newnode;

}

else

{

root = minunion(root, newnode);

}

newnode = 0;

}

void minleftist_tree::display()

{

if (root==NULL || root==0)

cout << "Empty Tree" << endl;

else

{

cout << "Inorder .." << endl;

dispin(root);

}

};

void minleftist_tree::dispin(leftistnode * curnode)

{

if (curnode !=NULL)

{

dispin(curnode->lc);

cout << curnode->data << " " << " shortest = " << curnode->shortest << endl;

dispin(curnode->rc);

}

};

void minleftist_tree::deletemin( )

{

if (root==NULL)

{ cout << "Empty Tree ... Nothing to delete.." << endl;

return;

}

int minele = root->data;

leftistnode * temp;

temp = root ;

root = minunion(root->lc, root->rc);

cout << "deleted element is " << minele << endl;

delete temp;

}

void main()

{

minleftist_tree t;

int n=1,data;

clrscr();

{

cout<<"\n1 Insert 2. Delete Enter your choice: ";

cin>>n;

switch(n)

{

case 1:

cout<<"Enter nodes";

cin>>data;

t.insert(data);

t.display();

cout << "tree displayed";

break;

case 2:

t.deletemin();

t.display();

break;

default:

return;

}

}while(n<=2);

getch();

}

OUTPUT

1 Insert 2. Delete Enter your choice: 1

Enter nodes3

Inorder ..

3 shortest = 1

tree displayed

1 Insert 2. Delete Enter your choice: 1

Enter nodes6

Inorder ..

6 shortest = 1

3 shortest = 1

tree displayed

1 Insert 2. Delete Enter your choice: 1

Enter nodes1

Inorder ..

6 shortest = 1

3 shortest = 1

1 shortest = 1

tree displayed

1 Insert 2. Delete Enter your choice: 1

Enter nodes88

Inorder ..

6 shortest = 1

3 shortest = 1

1 shortest = 2

88 shortest = 1

tree displayed

1 Insert 2. Delete Enter your choice: 2

deleted element is 1

Inorder ..

6 shortest = 1

3 shortest = 2

88 shortest = 1

RESULT:

Thus the C++ program for leftist tree has been created and executed.

AVL TREE

AIM

To write a C++ program to perform implementation of AVL tree and its operations.

ALGORITHM

STEP 1: Define a class avlnode and declare the data members.

STEP 2: Define another class avltree and declare the member functions.

STEP 3: Declare the class avltree as a friend class of avlnode.

STEP 4: There are two operations performed namely insert and display.

STEP 5: Display the operations in the main function and get choice of operation from the user.

STEP 6: In the insert operation, first check whether the tree is null or not.

STEP 7: If the tree is null, create a new node and insert the value of the node.

STEP 8: Else, check whether the element to be inserted is lesser than or greater than the value of the node pointed.

STEP 9: If the element is lesser, insert into the left of the node pointed. Else insert into the right of the node pointed.

STEP 10: After insertion, check whether the height of the tree is balanced. If not, perform rotate operations. There are four rotate operations namely rotate with left, rotate with right, double rotate with left and double rotate with right.

STEP 11: In the display operation, display the elements in the AVL tree.

STEP 12: In the exit operation, terminate the execution of the program.

PROGRAM

//**** AVL Tree ****

#include<iostream.h>

#include<stdlib.h>

#include<conio.h>

#include<math.h>

class node

{

int data;

int balance;

public:

node *left,*right;

void create();

node* insert(int x,node* avl);

void findmin(node *);

void findmax(node *);

void ascend(node *);

int height(node *current);

void bal(node *current);

node* rotatewithleftchild(node* avl);

node* rotatewithrightchild(node* avl);

node* doublewithleftchild(node* avl);

node* doublewithrightchild(node* avl);

void search(int p,node *);

}*list,*root,*temp,*l,*ord,*parent;

int h,or=0;

void node::create()

{

list=NULL;

list->balance=NULL;

list->left=NULL;

list->right=NULL;

l=list;

root=list;

}

int node::height(node* current)

{

int hleft=0,hright=0;

if(current==NULL)

return(0);

hleft=height(current->left)+1;

hright=height(current->right)+1;

if(hleft>hright)

h=hleft;

else

h=hright;

return(h);

}

node* node::insert(int num,node* avl)

{

if(avl==NULL)

{

avl=new(node);

avl->data=num;

avl->balance=0;

avl->left=NULL;

avl->right=NULL;

return(avl);

}

else if(num<avl->data)

{

avl->left=insert(num,avl->left);

if(height(avl->left)-height(avl->right)==2)

if(num<avl->left->data)

{

cout<<"\nL ROTATION\n";

avl=rotatewithleftchild(avl);

return(avl);

}

else

{

cout<<"\nRL ROTATION\n";

avl=doublewithleftchild(avl);

}

else if(avl->data<num)

{

avl->right=insert(num,avl->right);

if(height(avl->right)-height(avl->left)==2)

if(avl->right->data<num)

{

cout<<"\nR ROTATION\n";

avl=rotatewithrightchild(avl);

}

else

{

cout<<"\nLR ROTATION\n";

avl=doublewithrightchild(avl);

}

else

cout<<"\n\n\tThe entered element is already exist..........";

return(avl);

}

node* node::rotatewithleftchild(node* k2)

{

node* k1;

k1=k2->left;

k2->left=k1->right;

k1->right=k2;

return k1;

}

node* node::rotatewithrightchild(node* k2)

{

node*k1;

k1=k2->right;

k2->right=k1->left;

k1->left=k2;

return k1;

}

node* node::doublewithleftchild(node* k1)

{ k1->left=rotatewithrightchild(k1->left);

k1=rotatewithleftchild(k1);

return k1;

}

node* node::doublewithrightchild(node *k1)

{

k1->right=rotatewithleftchild(k1->right);

k1=rotatewithrightchild(k1);

return k1;

}

void node::bal(node* current)

{

if(current->left!=NULL)

bal(current->left);

current->balance=height(current->left)-height(current->right);

if(current->right!=NULL)

bal(current->right);

}

void node::ascend(node *r)

{

if(r==NULL)

return;

else

{

ascend(r->left);

if(r->data)

{

cout<<r->data;

if(r->left==NULL)

cout<<"\t0";

else

cout<<"\t"<<r->left->data;

if(r->right==NULL)

cout<<"\t0\n";

else

cout<<"\t"<<r->right->data<<"\n";

}

ascend(r->right);

}

void node::findmin(node *traverse)

{

if(traverse->left!=NULL)

findmin(traverse->left);

else

cout<<"\n\n\tThe minimum element is "<<traverse->data;

}

void node::findmax(node *traverse)

{

if(traverse->right!=NULL)

findmax(traverse->right);

else

cout<<"\n\n\tThe maximum element is "<<traverse->data;

}

void node::search(int x,node *traverse)

{

if(traverse==NULL)

{

cout<<"\n\n\tThe element "<<x<<" is not in the tree....";

return;

}

else if(traverse->data==x)

{

cout<<"\n\n\tThe element "<<x<<" is in the tree.....";

return;

}

else if(traverse->data>x)

search(x,traverse->left);

else

search(x,traverse->right);

}

int main()

{

int n,e=1;

node list1;

list1.create();

clrscr();

while(e)

{

cout<<"\n ************";

cout<<"\n * AVL TREE *";

cout<<"\n ************\n";

cout<<" 1.INSERT\n 2.SEARCH\n 3.FIND MINIMUM\n";

cout<<" 4.FIND MAXIMUM\n 5.DISPLAY\n 6.EXIT";

cout<<"\n Enter Your Choice : ";

cin>>n;

int b,c;

switch(n)

{

case 1:

cout<<"\n Enter the element to be inserted....: ";

cin>>b;

root=list1.insert(b,root);

list1.bal(root);

break;

case 2:

if(root==NULL)

cout<<"\n Empty tree.......:";

else

{

cout<<"\n Enter the element to be searched...: ";

cin>>b;

list1.search(b,root);

}

break;

case 3:

if(root==NULL)

cout<<"\n Empty tree.......:";

else

list1.findmin(root);

break;

case 4:

if(root==NULL)

cout<<"\n Empty tree.......: ";

else

list1.findmax(root);

break;

case 5:

clrscr();

cout<<"ROOT\t LEFT\t RIGHT\n";

list1.ascend(root);

getch();

break;

case 6:

e=0;

break;

}

return 0;

}

OUTPUT

AVL TREE

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 1

Enter the element to be inserted....: 2

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

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 1

Enter the element to be inserted....: 3

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

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 1

Enter the element to be inserted....: 4

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 2

Enter the element to be searched...: 3

The element 3 is in the tree.....

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

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 3

The minimum element is 2

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

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 4

The maximum element is 4

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

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice :5

ROOT LEFT RIGHT

2 0 0

3 2 4

4 0 0

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

* AVL TREE *

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

1.INSERT

2.SEARCH

3.FIND MINIMUM

4.FIND MAXIMUM

5.DISPLAY

6.EXIT

Enter Your Choice : 6

RESULT

Hence the program to implement AVL tree operations are executed successfully and the output is verified.

B TREE

AIM

To write a C++ program to implement B tree and its operation.

ALGORITHM

Step 1: Start

Step 2: Declare the class btree and define the data members and member functions

Step 3: In main program, display the choices of operation done by this program

Step 4: All insertions start at a leaf node. To insert a new element

Search the tree to find the leaf node where the new element should be added.

Step 5:Search for the value to delete.If the value's in a leaf node, simply delete it from the node.

Step 5:Rebalance the after deletion.

PROGRAM

#include <iostream.h>

#include <stdlib.h>

const int MAX = 4 ;

const int MIN = 2 ;

struct btnode

{

int count ;

int value[MAX + 1] ;

btnode *child[MAX + 1] ;

} ;

class btree

{

private :

btnode *root ;

public :

btree( ) ;

void insert ( int val ) ;

int setval ( int val, btnode *n, int *p, btnode **c ) ;

static btnode * search ( int val, btnode *root, int *pos ) ;

static int searchnode ( int val, btnode *n, int *pos ) ;

void fillnode ( int val, btnode *c, btnode *n, int k ) ;

void split ( int val, btnode *c, btnode *n, int k, int *y, btnode **newnode ) ;

void del ( int val ) ;

int delhelp ( int val, btnode *root ) ;

void clear ( btnode *root, int k ) ;

void copysucc ( btnode *root, int i ) ;

void restore ( btnode *root, int i ) ;

void rightshift ( int k ) ;

void leftshift ( int k ) ;

void merge ( int k ) ;

void show( ) ;

static void display ( btnode *root ) ;

static void deltree ( btnode *root ) ;

~btree( ) ;

} ;

btree :: btree( )

{

root = NULL ;

}

void btree :: insert ( int val )

{

int i ;

btnode *c, *n ;

int flag ;

flag = setval ( val, root, &i, &c ) ;

if ( flag )

{

n = new btnode ;

n -> count = 1 ;

n -> value[1] = i ;

n -> child[0] = root ;

n -> child[1] = c ;

root = n ;

}

int btree :: setval ( int val, btnode *n, int *p, btnode **c )

{

int k ;

if ( n == NULL )

{

*p = val ;

*c = NULL ;

return 1 ;

}

else

{

if ( searchnode ( val, n, &k ) )

cout << endl << "Key value already exists." << endl ;

if ( setval ( val, n -> child[k], p, c ) )

{

if ( n -> count < MAX )

{

fillnode ( *p, *c, n, k ) ;

return 0 ;

}

else

{

split ( *p, *c, n, k, p, c ) ;

return 1 ;

}

return 0 ;

}

btnode * btree :: search ( int val, btnode *root, int *pos )

{

if ( root == NULL )

return NULL ;

else

{

if ( searchnode ( val, root, pos ) )

return root ;

else

return search ( val, root -> child[*pos], pos ) ;

}

int btree :: searchnode ( int val, btnode *n, int *pos )

{

if ( val < n -> value[1] )

{

*pos = 0 ;

return 0 ;

}

else

{

*pos = n -> count ;

while ( ( val < n -> value[*pos] ) && *pos > 1 )

( *pos )-- ;

if ( val == n -> value[*pos] )

return 1 ;

else

return 0 ;

}

void btree :: fillnode ( int val, btnode *c, btnode *n, int k )

{

int i ;

for ( i = n -> count ; i > k ; i-- )

{

n -> value[i + 1] = n -> value[i] ;

n -> child[i + 1] = n -> child[i] ;

}

n -> value[k + 1] = val ;

n -> child[k + 1] = c ;

n -> count++ ;

}

void btree :: split ( int val, btnode *c, btnode *n,

int k, int *y, btnode **newnode )

{

int i, mid ;

if ( k <= MIN )

mid = MIN ;

else

mid = MIN + 1 ;

*newnode = new btnode ;

for ( i = mid + 1 ; i <= MAX ; i++ )

{

( *newnode ) -> value[i - mid] = n -> value[i] ;

( *newnode ) -> child[i - mid] = n -> child[i] ;

}

( *newnode ) -> count = MAX - mid ;

n -> count = mid ;

if ( k <= MIN )

fillnode ( val, c, n, k ) ;

else

fillnode ( val, c, *newnode, k - mid ) ;

*y = n -> value[n -> count] ;

( *newnode ) -> child[0] = n -> child[n -> count] ;

n -> count-- ;

}

void btree :: del ( int val )

{

btnode * temp ;

if ( ! delhelp ( val, root ) )

cout << endl << "Value " << val << " not found." ;

else

{

if ( root -> count == 0 )

{

temp = root ;

root = root -> child[0] ;

delete temp ;

}

int btree :: delhelp ( int val, btnode *root )

{

int i ;

int flag ;

if ( root == NULL )

return 0 ;

else

{

flag = searchnode ( val, root, &i ) ;

if ( flag )

{

if ( root -> child[i - 1] )

{

copysucc ( root, i ) ;

flag = delhelp ( root -> value[i], root -> child[i] ) ;

if ( !flag )

cout << endl << "Value " << val << " not found." ;

}

else

clear ( root, i ) ;

}

else

flag = delhelp ( val, root -> child[i] ) ;

if ( root -> child[i] != NULL )

{

if ( root -> child[i] -> count < MIN )

restore ( root, i ) ;

}

return flag ;

}

void btree :: clear ( btnode *root, int k )

{

int i ;

for ( i = k + 1 ; i <= root -> count ; i++ )

{

root -> value[i - 1] = root -> value[i] ;

root -> child[i - 1] = root -> child[i] ;

}

root -> count-- ;

}

void btree :: copysucc ( btnode *root, int i )

{

btnode *temp = root -> child[i] ;

while ( temp -> child[0] )

temp = temp -> child[0] ;

root -> value[i] = temp -> value[1] ;

}

void btree :: restore ( btnode *root, int i )

{

if ( i == 0 )

{

if ( root -> child [1] -> count > MIN )

leftshift ( 1 ) ;

else

merge ( 1 ) ;

}

else

{

if ( i == root -> count )

{

if ( root -> child[i - 1] -> count > MIN )

rightshift ( i ) ;

else

merge ( i ) ;

}

else

{

if ( root -> child[i - 1] -> count > MIN )

rightshift ( i ) ;

else

{

if ( root -> child[i + 1] -> count > MIN )

leftshift ( i + 1 ) ;

else

merge ( i ) ;

}

void btree :: rightshift ( int k )

{

int i ;

btnode *temp ;

temp = root -> child[k] ;

for ( i = temp -> count ; i > 0 ; i-- )

{

temp -> value[i + 1] = temp -> value[i] ;

temp -> child[i + 1] = temp -> child[i] ;

}

temp -> child[1] = temp -> child[0] ;

temp -> count++ ;

temp -> value[1] = root -> value[k] ;

temp = root -> child[k - 1] ;

root -> value[k] = temp -> value[temp -> count] ;

root -> child[k] -> child [0] = temp -> child[temp -> count] ;

temp -> count-- ;

}

void btree :: leftshift ( int k )

{

btnode *temp ;

temp = root -> child[k - 1] ;

temp -> count++ ;

temp -> value[temp -> count] = root -> value[k] ;

temp -> child[temp -> count] = root -> child[k] -> child[0] ;

temp = root -> child[k] ;

root -> value[k] = temp -> value[1] ;

temp -> child[0] = temp -> child[1] ;

temp -> count-- ;

for ( int i = 1 ; i <= temp -> count ; i++ )

{

temp -> value[i] = temp -> value[i + 1] ;

temp -> child[i] = temp -> child[i + 1] ;

}

void btree :: merge ( int k )

{

btnode *temp1, *temp2 ;

temp1 = root -> child[k] ;

temp2 = root -> child[k - 1] ;

temp2 -> count++ ;

temp2 -> value[temp2 -> count] = root -> value[k] ;

temp2 -> child[temp2 -> count] = root -> child[0] ;

for ( int i = 1 ; i <= temp1 -> count ; i++ )

{

temp2 -> count++ ;

temp2 -> value[temp2 -> count] = temp1 -> value[i] ;

temp2 -> child[temp2 -> count] = temp1 -> child[i] ;

}

for ( i = k ; i < root -> count ; i++ )

{

root -> value[i] = root -> value[i + 1] ;

root -> child[i] = root -> child[i + 1] ;

}

root -> count-- ;

delete temp1 ;

}

void btree :: show( )

{

display ( root ) ;

}

void btree :: display ( btnode *root )

{

if ( root != NULL )

{

for ( int i = 0 ; i < root -> count ; i++ )

{

display ( root -> child[i] ) ;

cout << root -> value[i + 1] << "\t" ;

}

display ( root -> child[i] ) ;

}

void btree :: deltree ( btnode *root )

{

if ( root != NULL )

{

for ( int i = 0 ; i < root -> count ; i++ )

{

deltree ( root -> child[i] ) ;

delete ( root -> child[i] ) ;

}

deltree ( root -> child[i] ) ;

delete ( root -> child[i] ) ;

}

btree :: ~btree( )

{

deltree ( root ) ;

}

void main( )

{

btree b ;

int no;

char ch;

cout<<"Enter the no. of elements:";

cin>>no;

int arr[50];

int d;

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

{

cout<<"Enter the element : ";

cin>>arr[i];

}

cout<<"INSERTION OF ELEMENTS INTO THE B-TREE OF ORDER 5"<<endl;

for ( int k = 0 ; k < no ; k++ )

b.insert ( arr[k] ) ;

b.show( ) ;

cout<<endl ;

cout<<"DELETION OF THE SPECIFIED ELEMENT FROM THE B-TREE"<<endl;

cout<<"Enter the element to be deleted:";

cin>>d;

b.del (d) ;

cout << "\n\nB-tree after deletion of values:" << endl ;

b.show( ) ;

}

SAMPLE OUTPUT:

Enter the no. of elements: 7

Enter the element : 7

Enter the element : 3

Enter the element : 5

Enter the element : 2

Enter the element : 1

Enter the element : 6

Enter the element : 4

INSERTION OF ELEMENTS INTO THE B-TREE OF ORDER 5

1 2 3 4 5 6 7

DELETION OF THE SPECIFIED ELEMENT FROM THE B-TREE

Enter the element to be deleted: 5

B-tree after deletion of values:

1 2 3 4 6 7

Press any key to continue

<exiting…>

IMPLEMENTATION OF TRIES

AIM

To write a C++ program to obtain the words from the dictionary using Tries.

ALGORITHM

Step 1: Declare the variables and the member functions.

Step 2: In CountLetters function, count the number of number of times a letter occurs in

the word

Step 3: Returns the vector of all words containing the letters which is given and move

through the tree to obtain the vector of words.

Step 4: Adding the words to the tries, wherever necessary and create an copy.

Step 5: From the dictionary, obtain the all possible words of the given letters.

Step 6: Get a word and print out all possible words.

Step 7: Terminate the program.

PROGRAM

#include "trie.h"

#include <iostream>

#include <fstream>

using namespace std;

void main()

{

cout << "Setting up..." << endl;

fstream Dictionary("format.txt", fstream::in);

if (!Dictionary.is_open())

{

cout << "Error opening dictionary" << endl;

}

CTrie* List = new CTrie();

char word[64];

while (!Dictionary.eof())

{

Dictionary >> word;

List->AddWord(word);

}

Dictionary.close();

cout << "System Ready, press q to quit" << endl;

while (1)

{

cin >> word;

if (strlen(word) <= 1 && *word == 'q')

break;

vector<char*>* all = List->GiveWords(word);

if (all && !all->empty())

{

vector<char*>::const_iterator vai;

int cnt = 0;

for (vai = all->begin(); vai != all->end(); vai++, cnt++)

cout << cnt + 1 << " " << *vai << endl;

}

else

cout << "none" << endl;

}

cout << "Quiting..." << endl;

delete List;

}

Trie.cpp

#include "trie.h"

#include <assert.h>

void CountLetters(const char* word, int count[g_NumLetters])

{

assert(word);

int cnt;

int length = strlen(word);

memset(count, 0, g_NumLetters * sizeof(int));

for (cnt = 0; cnt < length; cnt++)

{

if (word[cnt] >= 'a' && word[cnt] <= 'z')

count[word[cnt] - 'a']++;

}

CTrie::CTrie() : m_Root(NULL)

{

}

CTrie::~CTrie()

{

if (m_Root)

RecDelete(m_Root);

}

vector<char*>* CTrie::GiveWords(const char* word)

{

assert(word);

CNode* current = m_Root;

int cnt;

int cnt2;

CountLetters(word, m_Count);

for (cnt = 0; cnt < g_NumLetters; cnt++)

{

for (cnt2 = 0; cnt2 < m_Count[cnt]; cnt2++)

{

if (!MoveRight(current, false))

return NULL;

}

if (!MoveLeft(current, false))

return NULL;

}

return &current->m_List;

}

void CTrie::AddWord(const char* word)

{

assert(word);

char* copy = new char[strlen(word) + 1];

CNode* current = m_Root;

int cnt;

int cnt2;

strcpy(copy, word);

strlwr(copy);

CountLetters(copy, m_Count);

for (cnt = 0; cnt < g_NumLetters; cnt++)

{

for (cnt2 = 0; cnt2 < m_Count[cnt]; cnt2++)

{

if (!MoveRight(current, true))

break;

}

if (!MoveLeft(current, true))

break;

}

current->m_List.push_back(copy);

}

bool CTrie::MoveRight(CNode* &current, const bool addnew)

{

if (!m_Root)

{

if (addnew)

{

m_Root = new CNode();

current = m_Root;

}

else

return false;

}

if (!current->m_Right)

{

if (addnew)

current->m_Right = new CNode();

else

return false;

}

current = current->m_Right;

return true;

}

bool CTrie::MoveLeft(CNode* &current, const bool addnew)

{

if (!m_Root)

{

if (addnew)

{

m_Root = new CNode();

current = m_Root;

}

else

return false;

}

if (!current->m_Left)

{

if (addnew)

current->m_Left = new CNode();

else

return false;

}

current = current->m_Left;

return true;

}

void CTrie::RecDelete(CNode* &current)

{

if (current->m_Left)

RecDelete(current->m_Left);

if (current->m_Right)

RecDelete(current->m_Right);

vector<char*>::const_iterator vai;

for (vai = current->m_List.begin(); vai != current->m_List.end(); vai++)

delete *vai;

delete current;

current = NULL;

}

Trie.h

#include "trie.h"

#include <assert.h>

void CountLetters(const char* word, int count[g_NumLetters])

{

assert(word);

int cnt;

int length = strlen(word);

//a little faster then using a for loop to set all of count to zero

memset(count, 0, g_NumLetters * sizeof(int));

for (cnt = 0; cnt < length; cnt++)

{

if (word[cnt] >= 'a' && word[cnt] <= 'z')

count[word[cnt] - 'a']++;

}

CTrie::CTrie() : m_Root(NULL)

{

}

CTrie::~CTrie()

{

if (m_Root)

RecDelete(m_Root);

}

vector<char*>* CTrie::GiveWords(const char* word)

{

assert(word);

CNode* current = m_Root;

int cnt;

int cnt2;

CountLetters(word, m_Count);

for (cnt = 0; cnt < g_NumLetters; cnt++)

{

for (cnt2 = 0; cnt2 < m_Count[cnt]; cnt2++)

{

if (!MoveRight(current, false))

return NULL;

}

if (!MoveLeft(current, false))

return NULL;

}

return &current->m_List;

}

void CTrie::AddWord(const char* word)

{

assert(word);

char* copy = new char[strlen(word) + 1];

CNode* current = m_Root;

int cnt;

int cnt2;

strcpy(copy, word);

strlwr(copy);

CountLetters(copy, m_Count);

for (cnt = 0; cnt < g_NumLetters; cnt++)

{

for (cnt2 = 0; cnt2 < m_Count[cnt]; cnt2++)

{

if (!MoveRight(current, true))

break;

}

if (!MoveLeft(current, true))

break;

}

current->m_List.push_back(copy);

}

bool CTrie::MoveRight(CNode* &current, const bool addnew)

{

if (!m_Root)

{

if (addnew)

{

m_Root = new CNode();

current = m_Root;

}

else

return false;

}

if (!current->m_Right)

{

if (addnew)

current->m_Right = new CNode();

else

return false;

}

current = current->m_Right;

return true;

}

bool CTrie::MoveLeft(CNode* &current, const bool addnew)

{

if (!m_Root)

{

if (addnew)

{

m_Root = new CNode();

current = m_Root;

}

else

return false;

}

if (!current->m_Left)

{

if (addnew)

current->m_Left = new CNode();

else

return false;

}

current = current->m_Left;

return true;

}

void CTrie::RecDelete(CNode* &current)

{

if (current->m_Left)

RecDelete(current->m_Left);

if (current->m_Right)

RecDelete(current->m_Right);

vector<char*>::const_iterator vai;

for (vai = current->m_List.begin(); vai != current->m_List.end(); vai++)

delete *vai;

delete current;

current = NULL;

}

OUTPUT

Setting up...

System Ready, press q to quit

check

1 check

hen

1 hen

calen

1 clean

2 lance

splay

1 palsy

2 plays

3 splay

cedf

none

RESULT

Thus the C++ program to implement tries has been implemented and executed.

CONVEXHULL

AIM

To write C++ program for the implementation of convexhull.

ALGORITHM

STEP1: Create the class and declare the data members and member function.

STEP2: It performs Next, Insert ,Swap, Display and Traverse functions.

STEP3: In insert the size of the function is entered the points of the set.

STEP4: Find an extreme point. This point will be the pivot, is guaranteed to be on the

hull, and is chosen to be the point with largest y coordinate.

STEP5: Sort the points in order of increasing angle about the pivot.

STEP6: We end up with a star-shaped polygon (one in which one special point, in this

case the pivot, can "see" the whole polygon).

STEP7: Build the hull, by marching around the star-shaped poly, adding edges when we

make a left turn, and back-tracking when we make a right turn.

PROGRAM

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

#include <graphics.h>

#include <stdarg.h>

#include <stdlib.h>

#include <dos.h>

#define BGI_PATH ""

#define LEFT_CLICK 1

#define RIGHT_CLICK 2

#define NO_CLICK 0

int Max_X, Max_Y;

void InitGraphSystem(const char *bgi_path);

void gprintf(int x_pos, int y_pos, char *fmt, ...);

void StatusLine(char *msg);

int InitMouse(void);

int ShowMouse(void);

int HideMouse(void);

int GetMouseStatus(int *x_pos,int *y_pos,int *btn);

void SetMousePos(int x_pos, int y_pos);

int RestrictMouse(int x1, int y1, int x2, int y2);

inline int IsBetween(int a, int low, int high)

{

return (a >=low && a <=high);

}

class POINT

{

int x_pos, y_pos;

public:

POINT()

{

x_pos = y_pos = 0;

}

POINT(int x, int y)

{

x_pos = x, y_pos = y;

}

void Set(int x, int y)

{

x_pos = x, y_pos = y;

}

void Mark(void);

void DrawLine(POINT p);

int IsOnScreen()

{

return(IsBetween(x_pos, 0, Max_X) && IsBetween(y_pos, 0,

Max_Y));

}

int Get_x()

{

return x_pos;

}

int Get_y()

{

return y_pos;

}

int operator!=(POINT p)

{

return (x_pos != p.x_pos) || (y_pos != p.y_pos);

}

int operator==(POINT p)

{

return (x_pos == p.x_pos) && (y_pos == p.y_pos);

}

};

class LINE

{

long int a,b,c;

public:

LINE()

{

a = b = c = 0;

}

LINE(POINT p, POINT q)

{

Make(p,q);

}

void Make(POINT p, POINT q);

int Evaluate(POINT p);

};

void POINT::Mark(void)

{

if(IsOnScreen())

fillellipse(x_pos,y_pos,2,2);

}

void POINT::DrawLine(POINT p)

{

if( IsOnScreen() && p.IsOnScreen())

line(x_pos, y_pos, p.x_pos, p.y_pos);

}

void LINE::Make(POINT p, POINT q)

{

a = q.Get_y() - p.Get_y();

b = - (q.Get_x() - p.Get_x());

c = ((long)p.Get_x() * (q.Get_y()- p.Get_y())) -

(long)p.Get_y()*(q.Get_x()-p.Get_x());

}

int LINE::Evaluate(POINT p)

{

long int val = a*p.Get_x() + b*p.Get_y();

if(val > c)

return 1;

else if(val == c)

return 0;

else

return -1;

}

void InitGraphSystem(const char *bgi_path)

{

int graphDriver = DETECT, graphMode, result;

initgraph(&graphDriver, &graphMode,bgi_path);

result = graphresult();

if(result != grOk)

{

cout<<"Failed to initialize graphics system.\nError: "

<<grapherrormsg(result)<<"\nAborting...";

getch();

exit(1);

}

Max_X = getmaxx();

Max_Y = getmaxy();

}

void gprintf(int xloc, int yloc, char *fmt, ...)

{

va_list argptr;

char str[140];

va_start(argptr, fmt);

vsprintf(str, fmt, argptr);

outtextxy(xloc, yloc, str);

va_end(argptr);

}

void StatusLine(char *msg)

{

setfillstyle(SOLID_FILL, LIGHTGRAY);

setcolor(BLACK);

bar(0, Max_Y - 10, Max_X, Max_Y);

gprintf(10, Max_Y - 7, msg);

setfillstyle(SOLID_FILL, WHITE);

setcolor(BLACK);

}

int main()

{

int x,y,btn = 0, n = 0, i, prev = 0, min_y = -1, j, side, prev_side;

POINT points[50], p, init_point, q;

LINE l;

InitGraphSystem(BGI_PATH);

if(!InitMouse())

{

cout<<"\nFatal Error: Cannot init mouse.\nAborting...";

getch();

closegraph();

return 1;

}

ShowMouse();

RestrictMouse(2, 2, Max_Y - 10, Max_X - 2);

StatusLine("Left-click to add points. Right-click when done.");

while(btn != RIGHT_CLICK)

{

GetMouseStatus(&x, &y, &btn);

if(btn == LEFT_CLICK)

{

if(prev == 1)

continue;

points[n].Set(x, y);

if(min_y == -1)

{

min_y = y;

init_point = points[n];

}

else

{

if(y < min_y)

{

min_y = y;

init_point = points[n];

}

HideMouse();

points[n].Mark();

n++;

ShowMouse();

prev = btn;

}

else

prev = btn;

}

p = q = init_point;

setcolor(CYAN);

setfillstyle(SOLID_FILL, CYAN);

{

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

{

if(points[i] == p || points[i] == q)

continue;

l.Make(p, points[i]);

prev_side = 0;

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

{

if(points[j] == points[i] || points[j] == p)

continue;

side = l.Evaluate(points[j]);

if(prev_side == 0)

prev_side = side;

else if((prev_side == 1 && side == -1)

|| (prev_side == -1 && side == 1))

break;

}

if(j == n && side == prev_side)

{

p.DrawLine(points[i]);

p.Mark();

points[i].Mark();

q = p;

p = points[i];

break;

}

}while(p != init_point);

StatusLine("Done... press any key to exit");

getch();

closegraph();

return 0;

}

int InitMouse(void)

{

union REGS in, out;

in.x.ax = 0;

int86(0x33, &in, &out);

return out.x.ax;

}

int ShowMouse(void)

{

union REGS in, out;

in.x.ax = 1;

int86(0x33, &in, &out);

return out.x.ax;

}

int HideMouse(void)

{

union REGS in, out;

in.x.ax = 2;

int86(0x33, &in, &out);

return out.x.ax;

}

int GetMouseStatus(int *x_pos, int *y_pos, int *btn)

{

union REGS in, out;

in.x.ax = 3;

int86(0x33, &in, &out);

*x_pos = out.x.cx;

*y_pos = out.x.dx;

*btn = out.x.bx;

return out.x.ax;

}

int RestrictMouse(int x1, int y1, int x2, int y2)

{

union REGS in, out;

in.x.ax = 7;

in.x.cx = x1;

in.x.dx = x2;

int86(0x33, &in, &out);

in.x.ax = 8;

in.x.cx = y1;

in.x.dx = y2;

int86(0x33, &in, &out);

return out.x.ax;

}

OUTPUT

RESULT

Hence the program to create convex hull has been implemented successfully

KNAPSACK 0/1 USING DYNAMIC PROGRAMMING

AIM

To write a C++ program to implement 0/1 Knapsack using Dynamic Programming.

ALGORITHM

Step 1: Declare the variables and the member functions.

Step 2: Declare the number of objects, the cost of the ith object to pay and the value of

the objects.

Step 3: Declare an array size for holding the maximum value that can be obtained for

almost weight of i

Step 3: In fill_sack function, add the number of objects into the collection upto the

maximum weight.

Step 4: Calculate the benefits for adding the each object into the sack and its remaining

space to be filled.

Step 5: Display the number of objects added and its benefit calculation for the maximum

weight.

PROGRAM

#include<stdio.h>

#include<conio.h>

#define MAXWEIGHT 110

int n=8;

int c[10]={1,11,21,23,33,43,45,55};

int v[10]={11,21,31,33,43,53,55,65};

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;object %d(%d$ %dKg) is added 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("\n 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("\n\nTotal value added:%d$\n",a[W]);

}

void main()

{

clrscr();

printf("\n\n\t\t IMPLEMENTATION OF 0/1 KNAPSACK USING DYNAMIC PROGRAMMING\n\n\n");

fill_sack();

getch();

}

OUTPUT

IMPLEMENTATION OF 0/1 KNAPSACK USING DYNAMIC PROGRAMMING

Weight 0;benefit:0; can't reach this exact weight

weight 1;Benefit:11;object 1(11$ 1Kg) is added to weight 0.

weight 2;Benefit:22;object 1(11$ 1Kg) is added to weight 1.

weight 3;Benefit:33;object 1(11$ 1Kg) is added to weight 2.

weight 4;Benefit:44;object 1(11$ 1Kg) is added to weight 3.

weight 5;Benefit:55;object 1(11$ 1Kg) is added to weight 4.

weight 6;Benefit:66;object 1(11$ 1Kg) is added to weight 5.

weight 7;Benefit:77;object 1(11$ 1Kg) is added to weight 6.

weight 8;Benefit:88;object 1(11$ 1Kg) is added to weight 7.

weight 9;Benefit:99;object 1(11$ 1Kg) is added to weight 8.

weight 10;Benefit:110;object 1(11$ 1Kg) is added to weight 9.

----------------------

Added object 1(11$ 1Kg).Space left:9

Added object 1(11$ 1Kg).Space left:8

Added object 1(11$ 1Kg).Space left:7

Added object 1(11$ 1Kg).Space left:6

Added object 1(11$ 1Kg).Space left:5

Added object 1(11$ 1Kg).Space left:4

Added object 1(11$ 1Kg).Space left:3

Added object 1(11$ 1Kg).Space left:2

Added object 1(11$ 1Kg).Space left:1

Added object 1(11$ 1Kg).Space left:0

Total value added:110$

RESULT

Hence the program to implement 0/1 Knapsack using dynamic programming has been executed and the output is obtained successfully.

GRAPH COLORING USING BACKTRACKING

AIM

To write the Java program for the implementation of graph coloring

ALGORITHM

Step 1: Start the program and define the function

Step 2:Create a class coloring

Step 3:Get the number of vertices in the graph

Step 4:Enter one if there is an edge in the graph

Step 5:And enter zero if there is no edge in the graph.

Step 5:Get the adjacency matrix of the given values

Step 6:Perform all possible combinations that are given

Step 7:Display all the combination

Step 8:End of the program

Program:

#include<iostream.h>

#include<conio.h>

class gcoloring

{

public:

int a[10][10];

int x[10];

int m, n;

void nextvalue(int k)

{

int j;

{

x[k]=(x[k]+1)%(m+1);

if(x[k]==0) return;

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

{

if((a[k][j]==1)&&(x[k]==x[j]))

break;

}

if(j==n+1) return;

}while(1);

}

void mcoloring(int k)

{

nextvalue(k);

if(x[k]==0) break;

if(k==n)

{

for(int i=1;i<=n;i++)

{

cout<<x[i]<<"\t";

}

cout<<"\n";

}

else

mcoloring(k+1);

}while(1);

}

void read()

{

cout<<"Enter number of vertices in the graph";

cin>>n;

cout<<"Enter 1 if there is an edge Otherwise 0";

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

cout<<"between "<<i<<" and "<<j;

cin>>a[i][j];

}

cout<<"Given adjacency matrix is";

for(int i1=1;i1<=n;i1++)

{

for(int j1=1;j1<=n;j1++)

cout<<a[i1][j1]<<"\t";

cout<<"\n";

}

for(int i2=1;i2<=n;i2++)

x[i2]=0;

for(int i3=2;i3<n;i3++)

{

m=i3;

cout<<"All possible combinations for m = "<<i3<<" are ";

mcoloring(1);

}

};

void main()

{

gcoloring g;

clrscr();

g.read();

getch();

}

OUTPUT:

number of vertices in the graph

Enter 1 if there is an edge Otherwise 0

between 1 and 1

between 1 and 2

between 1 and 3

between 1 and 4

between 2 and 1

between 2 and 2

between 2 and 3

between 2 and 4

between 3 and 1

between 3 and 2

between 3 and 3

between 3 and 4

between 4 and 1

between 4 and 2

between 4 and 3

between 4 and 4

Given adjacency matrix is

0 1 0 1

1 0 1 0

0 1 0 1

1 0 1 0

All possible combinations for m = 2 are

1 2 1 2

2 1 2 1

All possible combinations for m = 3 are

1 2 1 2

1 2 1 3

1 2 3 2

1 3 1 2

Anna University Syllabus Materials and Question Papers

Tuesday 21 May 2013

CS2915 DATA STRUCTURES LABORATORY

No comments:

Post a Comment