DAA LAB PROGRAMS

Posted by 9 comments:

SUM OF SUBSET PROBLEM

         ||DAA Lab program for  subset sum problem||

 // A recursive solution for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
   // Base Cases
   if (sum == 0)
     return true;
   if (n == 0 && sum != 0)
     return false;

   // If last element is greater than sum, then ignore it
   if (set[n-1] > sum)
     return isSubsetSum(set, n-1, sum);

   /* else, check if sum can be obtained by any of the following
      (a) including the last element
      (b) excluding the last element   */
   return isSubsetSum(set, n-1, sum) ||
                        isSubsetSum(set, n-1, sum-set[n-1]);
}

// Driver program to test above function
int main()
{
  int set[] = {3, 34, 4, 12, 5, 2};
  int sum = 9;
  int n = sizeof(set)/sizeof(set[0]);
  if (isSubsetSum(set, n, sum) == true)
     printf("Found a subset with given sum");
  else
     printf("No subset with given sum");
  return 0;
}

 OUTPUT

  Found a subset with given sum 
Posted by 1 comment:

Design and Analysis of Algorithms Lab Programs for Engineering

Posted by No comments:

DAA Lab program to implement N Queen Problem using Backtracking

DAA LAB Program 11

Write a program to implement N Queen Problem using Backtracking

#include<stdio.h>
#include<conio.h>
#include<math.h>
char a[10][10];
int n;
void printmatrix()
{
int i, j;
printf("\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
printf("%c\t", a[i][j]);
printf("\n\n");
}
}
int getmarkedcol(int row)
{
int i;
for (i = 0; i < n; i++)
if (a[row][i] == 'Q')
{
return (i);
break;
}
}
int feasible(int row, int col)
{
int i, tcol;
for (i = 0; i < n; i++)
{
tcol = getmarkedcol(i);
if (col == tcol || abs(row - i) == abs(col - tcol))
return 0;
}
return 1;
}
void nqueen(int row)
{
int i, j;
if (row < n)
{
for (i = 0; i < n; i++)
{
if (feasible(row, i))
{
a[row][i] = 'Q';
nqueen(row + 1);
a[row][i] = '.';
}
}
}
else
{
printf("\nThe solution is:- ");
printmatrix();
}
}
void main()
{
clrscr();
int i, j;
printf("\nEnter the no. of queens:- ");
scanf("%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = '.';
nqueen(0);
getch();
}


OUTPUT
Posted by No comments:

DAA Lab program to find Minimum Spanning Tree using Kruskal’s Algorithm

DAA LAB Program 10

Write a program to find Minimum Spanning Tree using Kruskal’s Algorithm

#include<stdio.h>
#include<conio.h>
#define INF 0
char vertex[10];  
int wght[10][10];
int span_wght[10][10];
int source;
struct Sort
{
int v1,v2;
int weight;
}que[20];
int n,ed,f,r;
int cycle(int s,int d)
{
int j,k;
if(source==d)
return 1;
for(j=0;j<n;j++)
if(span_wght[d][j]!=INF && s!=j) 
{
if(cycle(d,j))
return 1;
}
return 0;
}
void build_tree()
{
int i,j,w,k,count=0;
for(count=0;count<n;f++)
{
i=que[f].v1;
j=que[f].v2;
w=que[f].weight;
span_wght[i][j]=span_wght[j][i]=w;
source=i;
k=cycle(i,j);
if(k)
span_wght[i][j]=span_wght[j][i]=INF;
else
count++;
}
}
void swap(int *i,int *j)
{
int t;
t=*i;
*i=*j;
*j=t;
}
void main()
{
int i,j,k=0,temp;
int sum=0;
clrscr();
printf("\n\tEnter the No. of Nodes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter %d value : ",i+1);
fflush(stdin);
scanf("%c",&vertex[i]);
for(j=0;j<n;j++)
{
wght[i][j]=INF;
span_wght[i][j]=INF;
}
}
printf("\n\nGetting Weight\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
printf("\nEnter 0 if path Doesn't exist between %c to %c : ",vertex[i],vertex[j]);
scanf("%d",&ed);
if(ed>=1)
{
wght[i][j]=wght[j][i]=ed;
que[r].v1=i;
que[r].v2=j;
que[r].weight=wght[i][j];
if(r)
{
for(k=0;k<r;k++)
if(que[k].weight>que[r].weight)
{
swap(&que[k].weight,&que[r].weight);
swap(&que[k].v1,&que[r].v1);
swap(&que[k].v2,&que[r].v2);
}
}
r++;
}
}
clrscr();
printf("\n\tORIGINAL GRAPH WEIGHT MATRIX\n\n");
printf("\n\tweight matrix\n\n\t");
for(i=0;i<n;i++,printf("\n\t"))
for(j=0;j<n;j++,printf("\t"))
printf("%d",wght[i][j]);
build_tree();
printf("\n\n\t\tMINIMUM SPANNING TREE\n\n");
printf("\n\t\tLIST OF EDGES\n\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(span_wght[i][j]!=INF)
{
printf("\n\t\t%c ------ %c = %d ",vertex[i],vertex[j],span_wght[i][j]);
sum+=span_wght[i][j];
}
printf("\n\n\t\tTotal Weight : %d ",sum);
getch();
}


 OUTPUT




Posted by No comments:

DAA Lab program to perform Travelling Salesman Problem

DAA LAB Program 9

Write a program to perform Travelling Salesman Problem

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int a[10][10],visited[10],n,cost=0;
void get()
{
int i,j;
printf("\n\nEnter Number of Cities: ");
scanf("%d",&n);
printf("\nEnter Cost Matrix: \n");
for( i=0;i<n;i++)
{
printf("\n Enter 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 Matrix is:\n");
for( i=0;i<n;i++)
{
printf("\n\n");
for(j=0;j<n;j++)
printf("\t%d",a[i][j]);
}
}
void mincost(int city)
{
int i,ncity,least(int city);
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);
}
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;
}
void put()
{
printf("\n\nMinimum cost:");
printf("%d",cost);
}
void main()
{
clrscr();
get();
printf("\n\nThe Path is:\n\n");
mincost(0);
put();
getch();

}

OUTPUT

Posted by 1 comment:

DAA Lab program to perform Knapsack Problem using Greedy Solution

DAA LAB  Program 8

Write a program to perform Knapsack Problem using Greedy Solution

#include<stdio.h>
#include<conio.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]);
printf("\nMaximum profit is:- %f", tp);
}
void main()
{
clrscr();
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 weights and profits of each object:- ");
for (i = 0; i < num; i++)
{
scanf("%f %f", &weight[i], &profit[i]);
}
printf("\nEnter the capacity 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;
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);
getch();
}

 OUTPUT



























Posted by No comments:

DAA Lab program to perform radix sort

DAA LAB Program 7

Write a program to perform radix sort.

#include<stdio.h>
#include<conio.h>
radix_sort(int array[], int n);
void main()
{
int array[100],n,i;
clrscr();
printf("\t\t\tRadix Sort\n\n\n\n");
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("\nEnter the elements to be sorted: \n");
for(i = 0 ; i < n ; i++ )
{
printf("\tArray[%d] = ",i);
scanf("%d",&array[i]);
}
printf("\nArray Before Radix Sort:");  //Array Before Radix Sort
for(i = 0; i < n; i++)
{
printf("%8d", array[i]);
}
printf("\n");
radix_sort(array,n);
printf("\nArray After Radix Sort: ");  //Array After Radix Sort
for(i = 0; i < n; i++)
{
printf("%8d", array[i]);
}
printf("\n");
getch();
}
radix_sort(int arr[], int n)
{
int bucket[10][5],buck[10],b[10];
int i,j,k,l,num,div,large,passes;
div=1;
num=0;
large=arr[0];
for(i=0 ; i<n ; i++)
{
if(arr[i] > large)
{
large = arr[i];
}
while(large > 0)
{
num++;
large = large/10;
}

for(passes=0 ; passes<num ; passes++)
{
for(k=0 ; k<10 ; k++)
{
buck[k] = 0;
}
for(i=0 ; i<n  ;i++)
{
l = ((arr[i]/div)%10);
bucket[l][buck[l]++] = arr[i];
}
i=0;
for(k=0 ; k<10 ; k++)
{
for(j=0 ; j<buck[k] ; j++)
{
arr[i++] = bucket[k][j];
}
}
div*=10;
}
}
return 0;
}



OUTPUT 












Posted by No comments:

DAA Lab program to perform merge sort

DAA LAB  Program 6

Write a program to perform merge sort.

#include <stdio.h>
#include<conio.h>
void mergesort(int arr[], int l, int h);
void main(void)
{
int array[100],n,i = 0;
clrscr();
printf("\t\t\tMerge Sort\n\n\n\n");
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("\nEnter the elements to be sorted: \n");
for(i = 0 ; i < n ; i++ )
{
printf("\tArray[%d] = ",i);
scanf("%d",&array[i]);
}
printf("\nBefore Mergesort:");
for(i = 0; i < n; i++)
{
printf("%4d", array[i]);
}
printf("\n");
mergesort(array, 0, n - 1);
printf("\nAfter Mergesort:");
for(i = 0; i < n; i++)
{
printf("%4d", array[i]);
}
printf("\n");
getch();
}
void mergesort(int arr[], int l, int h)
{
int i = 0;
int length = h - l + 1;
int pivot  = 0;
int merge1 = 0;
int merge2 = 0;
int temp[100];
if(l == h)
return;
pivot  = (l + h) / 2;
mergesort(arr, l, pivot);
mergesort(arr, pivot + 1, h);
for(i = 0; i < length; i++)
{
temp[i] = arr[l + i];
}
merge1 = 0;
merge2 = pivot - l + 1;
for(i = 0; i < length; i++)
{
if(merge2 <= h - l)
{
if(merge1 <= pivot - l)
{
if(temp[merge1] > temp[merge2])
{
arr[i + l] = temp[merge2++];
}
else
{
arr[i + l] = temp[merge1++];
}
}
else
{
arr[i + l] = temp[merge2++];
}
}
else
{
arr[i + l] = temp[merge1++];
}
}
}



 OUTPUT












Posted by No comments:
Subscribe to: Posts (Atom)