Some more programs on the DAA



DESIGN AND ANALYSIS OF ALGORITHMS











1

EXPERIMENT NO:- 1(A)


AIM:- WRITE A PROGRAM TO IMPLEMENT BINARY SEARCH USING DIVIDE


AND CONCUR STRATEGY.





ALGORITHM


BINARYSEARCH(K,N)


  1. [ INITIALIZE ]

LOW🡨 1

HIGH🡨 N


  1. [ PERFORM SEARCH ]


Repeat through step 4 while LOW<=HIGH


3. [ OBTAIN MID POINT ] MIDDLE🡨 [ (LOW+HIH)/2 ]

4. [ COMPARE ]


IF X < K[MIDDLE]

Then HIGH 🡨 MIDDLE-1

Then  LOW 🡨 MIDDLE-1

ELSE


WRITE(“SEARCH SUCCESSFUL”)


5. [ UNSUCCESSFUL SEARCH ]


WRITE(“UNSUCCESSFUL SEARCH”)


RETURN(0)











2




PROGRAM





#include <stdio.h> int main()


{


int c, first, last, middle, n, search, array[100]; printf("Enter number of elements\n"); scanf("%d",&n);


printf("Enter %d integers\n", n); for (c = 0; c < n; c++) scanf("%d",&array[c]); printf("Enter value to find\n"); scanf("%d", &search);


first = 0; last = n - 1;


middle = (first+last)/2; while (first <= last) {


if (array[middle] < search) first = middle + 1;


else if (array[middle] == search) {


3

printf("%d found at location %d.\n", search, middle+1);


break;


}


else


last = middle - 1;


middle = (first + last)/2;


}


if (first > last)


printf("Not found! %d is not present in the list.\n", search);


return 0;




















RESULT:- THUS A PROGRAM TO IMPLEMENT BINARY SEARCH USING DIVIDE


AND CONCUR STRATEGY IS WRITTEN AND EXECUTED SUCCESSFULLY.













4




EXPERIMEN NO:- 1(B)


AIM:- WRITE A PROGRAM TO IMPLEMENT QUICK SORT.





ALGORITHM





QUICKSORT(S, P, r)



1 If p < r


  1. then q <- PARTITION(S, p, r)


  1. QUICKSORT(S, p, q-1)


  1. QUICKSORT(S, q+1, r)



PARTITION(S, p, r)


  1. x <- S[r]


  1. i <- p-1


  1. for j <- p to r-1


  1. do if S[j] <= x


  1. then i <- i+1


6 swap S[i] <-> S[j]


  1. swap S[i+1] <-> S[r]


  1. return i+1












5

PROGRAM







#include<stdio.h>



void quicksort(int [10],int,int); int main()


{


int x[20],size,i;


printf("Enter size of the array: ");


scanf("%d",&size);


printf("Enter %d elements: ",size);


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




scanf("%d",&x[i]); quicksort(x,0,size-1); printf("Sorted elements: ");


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


printf(" %d",x[i]);



return 0;


}


void quicksort(int x[10],int first,int last){


int pivot,j,temp,i;





6

if(first<last)


{


pivot=first;


i=first;


j=last;



while(i<j)


{


while(x[i]<=x[pivot]&&i<last)


i++;


while(x[j]>x[pivot]) j--;



if(i<j){


temp=x[i];


x[i]=x[j];


x[j]=temp;


}


}



temp=x[pivot];


x[pivot]=x[j];


x[j]=temp; quicksort(x,first,j-1); quicksort(x,j+1,last);


}


}




RESULT:- THUS A PROGRAM TO IMPLEMENT QUICJK SORT IS WRITTEN AND


EXECUTED SUCCESSFULLY.


7

EXPERIMENT NO:-1(C)


AIM:- WRITE A PROGRAM TO IMPLEMENT MERGE SORT.


ALGORITHM


mergesort(m)


var list left, right, result if length(m) ≤ 1


return m else

var middle = length(m) / 2


for each x in m up to middle - 1 add x to left


for each x in m at and after middle add x to right


left = mergesort(left) right = mergesort(right) if last(left) ≤ first(right)


append right to left return left


result = merge(left, right) return result


function merge(left,right) var list result


while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right)


append first(left) to result left = rest(left)


else


append first(right) to result right = rest(right)

if length(left) > 0


append rest(left) to result if length(right) > 0


append rest(right) to result return result


8

PROGRAM



#include<stdio.h>


#include<conio.h>


void merge(int [],int ,int ,int ); void part(int [],int ,int );


int main()


{


int arr[30]; int i,size;


printf("\n\t------- Merge sorting method -------\n\n"); printf("Enter total no. of elements : "); scanf("%d",&size);


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


{


printf("Enter %d element : ",i+1); scanf("%d",&arr[i]);


}


part(arr,0,size-1);


printf("\n\t------- Merge sorted elements -------\n\n"); for(i=0; i<size; i++)


printf("%d ",arr[i]); getch();


return 0;


}


void part(int arr[],int min,int max)


{


int mid; if(min<max)



9

{


mid=(min+max)/2;


part(arr,min,mid);


part(arr,mid+1,max);


merge(arr,min,mid,max);


}


}


void merge(int arr[],int min,int mid,int max)


{


int tmp[30]; int i,j,k,m; j=min; m=mid+1;


for(i=min; j<=mid && m<=max ; i++)


{


if(arr[j]<=arr[m])


{


tmp[i]=arr[j];


j++;


}


else


{


tmp[i]=arr[m];


m++;


}


}


if(j>mid)


{


for(k=m; k<=max; k++)


{


10

tmp[i]=arr[k];


i++;


}


}


else


{


for(k=j; k<=mid; k++)


{


tmp[i]=arr[k];


i++;


}


}


for(k=min; k<=max; k++) arr[k]=tmp[k];


}

























RESULT:- THUS A PROGRAM TO IMPLEMENT MERGE SORT IS WRITTEN AND


EXECUTED SUCCESSFULLY.





11

EXPERIMENT NO:- 02





AIM:- WRITE A PROGRAM TO IMPLEMENT HUFFMAN’S ALGORITHM BY


GREEDY APPROACH.





ALGORITHM





Huffman(c)


n <-- |c| Q <-- c


for i <-- 1 to n - 1


do z <-- ALLOCATE_NODE()


x <-- left [ z ] <-- EXTRACT_MIN(Q) y <-- right[ z ] <-- EXTRACT_MIN(Q) F(z) <-- F[x] + F[y]


INSERT[Q , Z]


Return EXTRACT_MIN(Q)













12

PROGRAM







#include <stdio.h> #include <stdlib.h> #define MAX_TREE_HT 100 struct MinHeapNode


{


char data; unsigned freq;


struct MinHeapNode *left, *right;


};


struct MinHeap


{


unsigned size; unsigned capacity;


struct MinHeapNode **array;


};


struct MinHeapNode* newNode(char data, unsigned freq)


{


struct MinHeapNode* temp =


(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode)); temp->left = temp->right = NULL;


temp->data = data; temp->freq = freq; return temp;


}


struct MinHeap* createMinHeap(unsigned capacity)


{


struct MinHeap* minHeap =


13


(struct MinHeap*) malloc(sizeof(struct MinHeap)); minHeap->size = 0; // current size is 0 minHeap->capacity = capacity;


minHeap->array =


(struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));


return minHeap;


}


void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)


{


struct MinHeapNode* t = *a; *a = *b;


*b = t;


}


void minHeapify(struct MinHeap* minHeap, int idx)


{


int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2;


if (left < minHeap->size &&


minHeap->array[left]->freq < minHeap->array[smallest]->freq) smallest = left;


if (right < minHeap->size &&


minHeap->array[right]->freq < minHeap->array[smallest]->freq) smallest = right;


if (smallest != idx)


{


swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);


minHeapify(minHeap, smallest);


14

}


}


int isSizeOne(struct MinHeap* minHeap)


{


return (minHeap->size == 1);


}


struct MinHeapNode* extractMin(struct MinHeap* minHeap)


{


struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size;


minHeapify(minHeap, 0); return temp;


}


void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode)


{ int i; ++minHeap->size;


i = minHeap->size - 1;


while (i && minHeapNode->freq < minHeap->array[(i - 1)/2]->freq)


{


minHeap->array[i] = minHeap->array[(i - 1)/2]; i = (i - 1)/2;


}


minHeap->array[i] = minHeapNode;


}


void buildMinHeap(struct MinHeap* minHeap)


{


int n = minHeap->size - 1; int i;


for (i = (n - 1) / 2; i >= 0; --i)


15

minHeapify(minHeap, i);


}


void printArr(int arr[], int n)


{


int i;


for (i = 0; i < n; ++i) printf("%d", arr[i]);


printf("\n");


}


int isLeaf(struct MinHeapNode* root)


{


return !(root->left) && !(root->right) ;


}


struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size)


{   int i;


struct MinHeap* minHeap = createMinHeap(size); for ( i = 0; i < size; ++i)


minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size;


buildMinHeap(minHeap); return minHeap;


}


struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)


{


struct MinHeapNode *left, *right, *top;


struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);


while (!isSizeOne(minHeap))


{


16


left = extractMin(minHeap); right = extractMin(minHeap);


top = newNode('$', left->freq + right->freq); top->left = left;


top->right = right; insertMinHeap(minHeap, top);


}


return extractMin(minHeap);


}


void printCodes(struct MinHeapNode* root, int arr[], int top)


{



if (root->left)


{


arr[top] = 0; printCodes(root->left, arr, top + 1);


}


if (root->right)


{


arr[top] = 1; printCodes(root->right, arr, top + 1);


}


if (isLeaf(root))


{


printf("%c: ", root->data); printArr(arr, top);


}


}


void HuffmanCodes(char data[], int freq[], int size)


{


struct MinHeapNode* root = buildHuffmanTree(data, freq, size);


17


int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top);


}


int main()


{


char arr[] = {'a', 'b', 'c', 'd', 'e','f'}; int freq[6];


int ct,size; for(ct=0;ct<6;ct++)


{


printf("\n ENTER THE FREQUENCY OF %c:",arr[ct]); getch();


scanf("%d",&freq[ct]);


}


printf("SOLUTION:\n");


size = sizeof(arr)/sizeof(arr[0]); HuffmanCodes(arr, freq, size); getch();


return 0;


}















RESULT:- THUS A PROGRAM TO IMPLEMENT HUFFMAN’S ALGORITHM BY


GREEDY APPROACH IS WRITTEN AND EXECUTED SUCCESSFULLY.





18

EXPERIMENT NO:- 03


AIM :- WRITE A PROGRAM TO IMPLEMENT KNAPSACK ALGORITHM BY


GREEDY APPROACH.





ALGORITHM


  1. i <-- 1 TO n


  1. do x[i] <-- 0


  1. W <-- value


  1. V<-- 0


5.i <-- n


6. if I[i]>W 7.Goto step 15 8.otherwise x[i]<--1 9.w <--(W - w[i])


10. V <-- V + v[i] * x[i] 11.if i < n


12.x[i] <--W/w[i]


  1. V <-- V +v[ i ] * x[i]


  1. return V


  1. Exit.





19

PROGRAM





# include<stdio.h>


void knapsack(int n, float weight[], float profit[], float capacity) { float x[20], tp = 0;


int i, j, u;


u = capacity;



for (i = 0; i < n; i++) x[i] = 0.0;



for (i = 0; i < n; i++) { if (weight[i] > u)


break; else {


x[i] = 1.0;


tp = tp + profit[i]; u = u - weight[i];


}


}



if (i < n)


x[i] = u / weight[i];



tp = tp + (x[i] * profit[i]);



printf("\nThe result vector is:- "); for (i = 0; i < n; i++)


printf("%f\t", x[i]);



20

printf("\nMaximum profit is:- %f", tp);



}



int main() {


float weight[20], profit[20], capacity; int num, i, j;


float ratio[20], temp;



printf("\nEnter the no. of objects:- "); scanf("%d", &num);



printf("\nEnter the wts and profits of each object:- "); for (i = 0; i < num; i++) {


scanf("%f %f", &weight[i], &profit[i]);


}



printf("\nEnter the capacityacity of knapsack:- "); scanf("%f", &capacity);



for (i = 0; i < num; i++) { ratio[i] = profit[i] / weight[i];


}



for (i = 0; i < num; i++) {


for (j = i + 1; j < num; j++) { if (ratio[i] < ratio[j]) {


temp = ratio[j]; ratio[j] = ratio[i]; ratio[i] = temp;



21


temp = weight[j]; weight[j] = weight[i]; weight[i] = temp;



temp = profit[j]; profit[j] = profit[i]; profit[i] = temp;


}


}


}



knapsack(num, weight, profit, capacity); return(0);


}




























RESULT:- THUS A PROGRAM TO IMPLEMENT KNAPSACK PROBLEM BY


GREEDY APPROACH IS WRITTEN AND EXECUTED SUCCESSFULLY






22

EXPERIMENT NO:- 04


AIM :- WRITE A PROGRAM TO IMPLEMENT KRUSKALS ALGORITHM TO


FIND MINIMAL SPANNING TREE.





ALGORITHM


KRUSKAL(G,W)


  1. A <-- phi


  1. for each vertex v belongs to v[G] 3.do MAKE_SET (V)


4.sort the edges E into no decreasing order by weight W


5.for each edge(u,v) belongs to E take in nondecreasing order by weight. 6.do if FIND_SET(u) != FIND_SET(v)


7.then A <-- A U {(u,v)} 8.UNION(u,v) 9.return A



















23

PROGRAM





#include<stdio.h>


#include<conio.h>


#include<stdlib.h>


int i,j,k,a,b,u,v,n,ne=1,edge,x,y;


int min,mincost=0,cost[20][20],parent[20]; int find(int);


int uni(int,int); void main()


{


printf("\n\n\tImplementation of Kruskal's algorithm\n\n"); printf("\nEnter the no. of vertices\n");


scanf("%d",&n); printf("ENTER THE edges"); scanf("%d",&edge); for(i=1;i<=n;i++) for(j=1;j<=n;j++)


{


cost[i][j]=999;


}


for(k=1;k<=edge;k++)


{


printf("\nENTER EDGE AND WEIGHT OF EDGE(X,Y)"); scanf("%d",&x);


scanf("%d",&y);


scanf("%d",&cost[x][y]);


printf("\nEDGE(%d,%d)=%d'",x,y,cost[x][y]);


}



24


printf("\nThe edges of Minimum Cost Spanning Tree are\n\n"); while(ne<n)


{


for(i=1,min=999;i<=n;i++)


{


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


{


if(cost[i][j]<min)


{


min=cost[i][j];


a=u=i;


b=v=j;


}


}


}


u=find(u);


v=find(v);


if(uni(u,v))


{


printf("\n%d edge (%d,%d) =%d\n",ne++,a,b,min); mincost +=min;


}


cost[a][b]=cost[b][a]=999;


}


printf("\n\tMinimum cost = %d\n",mincost); getch();


}


int find(int i)


{


while(parent[i])


i=parent[i];


25

return i;


}


int uni(int i,int j)


{


if(i!=j)


{


parent[j]=i; return 1;


}


return 0;


}
































RESULT:- THUS A PROGRAM TO IMPLEMENT KRUSKALS ALGORITHM TO


FIND MINIMAL SPANNING TREE IS WRITTEN AND EXECUTED SUCCESSFULLY .








26

EXPERIMENT NO:- 05





AIM:- WRITE A PROGRAM TO SOLVE JOB SEQUENCING PROBLEM WITH


DEADLINE.


ALGORITHM






1)Sort all jobs in decreasing order of profit



  1. Initialize the result sequence as first job in sorted jobs.


  1. Do following for remaining n-1 jobs ......


If


the current job can fit in the current result sequence without missing the deadline, add current job to the result.


Else


ignore the current job.




























27

PROGRAM





#include<conio.h>


#include<stdio.h> int n,i,j,k,t;


int check(int s[],int p)


{ int ptr=0,i; for(i=0;i<n;i++) {if(s[i]==p)


ptr++;


}


if(ptr==0) return 1; else return 0;


}





int main()


{


int slot[20],profit,p[20],d[20]; clrscr();


28

printf("enter the no of jobs : \t");


scanf("%d",&n);





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


{printf("\n enter the profit of job #%d :",i+1);


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


printf("\n enter the deadline of job #%d :",i+1);


scanf("%d",&d[i]);


}


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


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


if(p[i]<p[j])


{ t=p[i];


p[i]=p[j];


p[j]=t;


t=d[i];


d[i]=d[j];


d[j]=t;


}


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


slot[i]=0;


29

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


for(j=d[i];j>0;j--)


{if(check(slot,j)==1)


{slot[i]=j;


break;}


}


printf("\n\n INDEX  PROFIT DEADLINE SLOT ALLOTTED ");


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


{if(slot[i]>0)


printf("\n\n  %d %d %d [%d - %d]", i+1,p[i],d[i],(slot[i]-


1),slot[i]);


else


printf("\n\n  %d %d %d REJECTED", i+1,p[i],d[i]);


}


getch();


}








RESULT:- THUS A PROGRAM TO SOLVE JOB SEQUENCING PROBLEM WITH


DEADLINE IS WRITTEN AND EXECUTED SUCCESSFULLY .







30

EXPERIMENT NO:-06





AIM: - WRITE A PROGRAM TO SOLVE TRAVELLING SALESMAN PROBLEM


USING DYNAMIC PROGRAMMING.






ALGORITHM





STEP1:-


Let function c{1,v-1} is a total length of the tour terminating at 1.the objective of TSP is that the cost of this tour should be minimum Let d[i,j] be the shortest path between two cities I and j.





STEP2:-


Let v1,v2,……,vn be the sequence of vertices follows the optimal tour then (v1,v2,……,vn ) must be the shortest path from v1 to vn which passes through each vertex exactly once.

















31

PROGRAM





#include<stdio.h>


#include<conio.h>


int a[10][10],visited[10],n,cost=0;





void get()


{


int i,j;


printf("Enter No. of Cities: "); scanf("%d",&n); printf("\nEnter Cost Matrix\n"); for(i=0;i < n;i++)


{


printf("\nEnter Elements of Row # : %d\n",i+1); for( j=0;j < n;j++)


scanf("%d",&a[i][j]);


visited[i]=0;


}


printf("\n\nThe cost list is:\n\n"); for( i=0;i < n;i++)


32

{


printf("\n\n"); for(j=0;j < n;j++)


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


}


}





void mincost(int city)


{


int i,ncity; visited[city]=1; printf("%d -->",city+1); ncity=least(city); if(ncity==999)

{


ncity=0;


printf("%d",ncity+1);


cost+=a[city][ncity];


return;


}


mincost(ncity);


33

}





int least(int c)


{


int i,nc=999;


int min=999,kmin; for(i=0;i < n;i++)


{


if((a[c][i]!=0)&&(visited[i]==0)) if(a[c][i] < min)


{


min=a[i][0]+a[c][i];


kmin=a[c][i];


nc=i;


}


}


if(min!=999)


cost+=kmin; return nc;


}





34

void put()


{


printf("\n\nMinimum cost:");


printf("%d",cost);


}





void main()


{





get();


printf("\n\nThe Path is:\n\n");


mincost(0);


put();


getch();


}









RESULT:- THUS A PROGRAM TO SOLVE TRAVELLING SALESMAN PROBLEM


USING DYNAMIC PROGRAMMING IS WRITTEN AND EXECUTED


SUCCESSFULLY .






35








EXPERIMENT NO:-07


AIM : - WRITE A PROGRAM TO FIND LCS OF GIVEN SUBSTRING.






ALGORITHM


Lcs_length(x,y)


  1. m 🡨 length[x]


  1. n 🡨 length[y]


  1. FOR i =1 to m


  1. do c[i,0] 🡨 0

  2. FOR j =1 to n


  1. do c[0,j] 🡨 0

  2. FOR i =1 to m


  1. FOR j =1 to n


  1. do IF x[i]==y[j]


  1. Then c[i,j] 🡨 c[i-1,j-1]+1

  2. B[i,j]🡨 “↖”


  1. Else IF c[i-1,j] > = c[I,j-1]


  1. Then c[i,j] 🡨 c[i-1,j]

  2. b[i,j] 🡨 “↑”


  1. else


  1. c[i,j] 🡨 c[I,j-1]

  2. b[I,j]🡨🡨


  1. Return c and b.



36

PROGRAM





#include<stdio.h>


#include<conio.h>


#include<string.h>



int i,j,m,n,a,c[20][20],leng=0; char x[15],y[15],b[20][20];



void print_lcs(int i,int j)


{


if(i==0 || j==0) return;


if(b[i][j]=='c')


{


print_lcs(i-1,j-1); printf(" %c",x[i-1]); leng++;


}


else if(b[i][j]=='u') print_lcs(i-1,j);


else


print_lcs(i,j-1);


}



void lcs_length(void)


{


m=strlen(x);


n=strlen(y);


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


37

c[i][0]=0;


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


c[0][i]=0;


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


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


{


if(x[i-1]==y[j-1])


{


c[i][j]=c[i-1][j-1]+1; b[i][j]='c';


}


else if(c[i-1][j]>=c[i][j-1])


{


c[i][j]=c[i-1][j]; b[i][j]='u';


}


else


{


c[i][j]=c[i][j-1]; b[i][j]='l';


}


}


print_lcs(m,n);


}
















38

void main()


{


clrscr();


printf("Enter 1st sequence : "); gets(x);


printf("Enter 2nd sequence : "); gets(y);


printf("\nlongest common subsequence is : "); lcs_length();printf("\nLENGTH OF LCS IS :%d",leng);



getch();


}































RESULT:- THUS A PROGRAM TO FIND LCS OF GIVEN STRINGS IS WRITTEN


AND EXECUTED SUCCESSFULLY







39

EXPERIMENT NO:-08


AIM:- WRITE A PROGRAM TO IMPLEMENT N-QUEEN PROBLEM USING


BACKTRACKING.





ALGORITHM





N_queen(k,n)


{


for ( i = 1 to n )


{


if ( place (k, i ) )


{


x[ k ] =i; if ( k == n )


print("x [ 1. . . . . n ]"); else


N_queen( k + 1 , n )


} } }


place( k , i )


{




40

for ( j=1 to k-1 )


if ( x[j] == 1 ) || ( abs x[ j ] - i ) ) == abs ( j - k ) ) return( false );


else


return( true );


}

















































41

PROGRAM


#include<stdio.h>


#include<conio.h>


#include<math.h> int a[30],count=0; int place(int pos)


{


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


{


if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos)))) return 0;


}


return 1;


}


void print_sol(int n)


{


int i,j; count++;


printf("\n\nSolution #%d:\n",count); for(i=1;i<=n;i++)


42

{


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


{


if(a[i]==j)


printf("Q\t");


else


printf("*\t");


}


printf("\n");


}  }


void queen(int n)


{


int k=1; a[k]=0; while(k!=0)


{


a[k]=a[k]+1;


while((a[k]<=n)&&!place(k))


a[k]++;


if(a[k]<=n)


{


43

if(k==n)


print_sol(n);


else


{


k++;


a[k]=0;


} }


else


k--;


} }


void main()


{


int i,n;


clrscr();


printf("Enter the number of Queens:");


scanf("%d",&n);


queen(n);


printf("\nTotal solutions=%d",count); }





RESULT:- THUS A PROGRAM TO IMPLEMENT N-QUEEN PROBLEM


USING BACKTRACKING IS WRITTEN AND EXECUTED SUCCESSFULLY.



44

EXPERIMENT NO:-09


AIM: - WRITE A PROGRAM TO FIND OPTIMAL BINARY SEARCH TREE.





ALGORITHM




OPTIMAL-BST(p, q, n)



1 for i = 1 to n + 1


  1. do e[i, i - 1] = qi-1


  1. w[i, i - 1] = qi-1


  1. for l =1 to n


  1. do for i = 1 to n - l + 1


  1. do j = i + l - 1


  1. e[i, j] = ∞


  1. w[i, j] = w[i, j - 1] + pj + qj


  1. for r = i to j


  1. do t = e[i, r - 1] + e[r + 1, j] + w[i, j]


  1. if t < e[i, j]


  1. then e[i, j] = t


  1. root[i, j] = r


  1. return e and root















45

PROGRAM


#include<conio.h>


#include<stdio.h> int main()


{


float e[100][100],w[100][100],p[100],q[100],t; int i,n,j,k,l,m,r,root[100][100];


printf("this is optimal binary search tree\n"); printf("enter the value of n\n"); scanf("%d",&n);


printf("enter the values of the probability\n"); for(i=1;i<=n;i++)


{


scanf("%f",&p[i]);


}


printf("enter the values of the probability of dummy\n"); for(i=0;i<=n;i++)


{


scanf("%f",&q[i]);


}


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


46

{


e[i][i-1]=q[i-1]; w[i][i-1]=q[i-1];


}


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


{


for(i=1;i<=n-l+1;i++)


{


j=i+l-1; e[i][j]=100.0;


w[i][j]=w[i][j-1]+p[j]+q[j]; for(r=i;r<=j;r++)


{


t=e[i][r-1]+e[r+1][j]+w[i][j]; if(t<e[i][j])


{


e[i][j]=t;


root[i][j]=r;


} } }  }


printf("the result is\n"); printf("values of e are:\n");


47

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


{


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


{


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


}


printf("\n");


}


printf("\nvalues of root are:\n"); for(i=1;i<=n;i++)


{


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


{


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


}


printf("\n");


}


getch(); return 0; }



RESULT:- THUS A PROGRAM TO FIND OPTIMAL BINARY SEARCH TREE


IS WRITTEN AND EXECUTED SUCCESSFULLY


48

EXPERIMENT NO:-10


AIM: - WRITE A PROGRAM TO SOLVE SUM OF SUBSET PROBLEM.


ALGORITHM





Let S be set of elements and D is the expected sum of subset then


  1. Start with an empty set.


  1. Add to the subset the next element from the list.


  1. If the subset is having sum D then stop with that subset as a solution.


  1. If the subset is not fesible or if we have reached the end of the set then backtrack to the subset until we find more suitable value.


  1. If the subset is fesible then repeat step 2.


  1. If we have visited all the elements without finding a suitable subset and if no backtrack


is possible then


stop without solution.

















49

PROGRAM








void sumOfSub(int,int,int); static int m=0;


int*w;


int*x;


void main()


{ int i=0,sum=0,n=0; clrscr();


printf("Enter size of array: "); scanf("%d",&n); w=(int*)malloc(sizeof(int)*n+1); x=(int*)malloc(sizeof(int)*n+1); printf("Enter %d elements: ",n); for(i=1;i<=n;i++)


{


scanf("%d",&w[i]);


sum+=w[i];


x[i]=0;


}


50


printf("Enter the sum to be obtained: "); scanf("%d",&m);


if(sum < m)


{


printf("Not possible to obtain any subset !!! "); exit(1);


}


printf("Possible Subsets are( 0 indicates exclusion and 1 indicates inclusion) :\n ");


sumOfSub(0,1,sum);


getch();


}





void sumOfSub(int s,int k,int r) { int i=0;


x[k]=1;


if(s+w[k]==m) { printf("\n"); for(i=1;i<=k;i++)


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


}



51

else if((s+w[k]+w[k+1])<=m)


{


sumOfSub(s+w[k],k+1,r-w[k]);


}


if((s+r-w[k])>=m&&(s+w[k+1])<=m)


{


x[k]=0;


sumOfSub(s,k+1,r-w[k]);


}


}






















RESULT:- THUS A PROGRAM TO SOLVE SUM OF SUBSET PROBLEM IS


WRITTEN AND EXECUTED SUCCESSFULLY











52

 

Comments