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)
[ INITIALIZE ]
LOW🡨 1
HIGH🡨 N
[ 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
then q <- PARTITION(S, p, r)
QUICKSORT(S, p, q-1)
QUICKSORT(S, q+1, r)
PARTITION(S, p, r)
x <- S[r]
i <- p-1
for j <- p to r-1
do if S[j] <= x
then i <- i+1
6 swap S[i] <-> S[j]
swap S[i+1] <-> S[r]
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
i <-- 1 TO n
do x[i] <-- 0
W <-- value
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]
V <-- V +v[ i ] * x[i]
return V
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)
A <-- phi
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
Initialize the result sequence as first job in sorted jobs.
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)
m 🡨 length[x]
n 🡨 length[y]
FOR i =1 to m
do c[i,0] 🡨 0
FOR j =1 to n
do c[0,j] 🡨 0
FOR i =1 to m
FOR j =1 to n
do IF x[i]==y[j]
Then c[i,j] 🡨 c[i-1,j-1]+1
B[i,j]🡨 “↖”
Else IF c[i-1,j] > = c[I,j-1]
Then c[i,j] 🡨 c[i-1,j]
b[i,j] 🡨 “↑”
else
c[i,j] 🡨 c[I,j-1]
b[I,j]🡨 “🡨”
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
do e[i, i - 1] = qi-1
w[i, i - 1] = qi-1
for l =1 to n
do for i = 1 to n - l + 1
do j = i + l - 1
e[i, j] = ∞
w[i, j] = w[i, j - 1] + pj + qj
for r = i to j
do t = e[i, r - 1] + e[r + 1, j] + w[i, j]
if t < e[i, j]
then e[i, j] = t
root[i, j] = r
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
Start with an empty set.
Add to the subset the next element from the list.
If the subset is having sum D then stop with that subset as a solution.
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.
If the subset is fesible then repeat step 2.
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
Post a Comment