Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
1. Find square root of a number. Can we use Divide & Conquer approach for this
problem?Can we have a still better algorithm to solve the problem?
#include<stdio.h>
void main()
{
int n,l=1,r,ans; //user will enter d no.
float m;
printf("Enter the no.");
scanf("%d",&n);
while(l!=m)
{
m=(l+r)/2;
if(n>=m*m)
{
l=m;
m=(l+r)/2;
}
else
r=m;
}
printf("the square root of %d is %.2f\n",n,m);
}
1
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
2. Determine smallest divisor of an integer.
#include<stdio.h>
int smallestdivisor(int n)
{
static int i=2;
if(n%i==0)
return i;
else
{
i++;
smallestdivisor(n);
}
}
void main()
{
int n,i;
printf("Enter No : ");
scanf("%d",&n);
/* for(i=2;i<n;i++) // Without Recursion
{
if(n%i==0)
break;
}*/
printf("Number is : %d\n",smallestdivisor(n));
}
2
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
3. For a given value of n, generate prime numbers <= n (more than one algorithms are
possible)
#include<stdio.h>
void main()
{
int n,i,j,flag=0;
printf("Enter No : ");
scanf("%d",&n);
for(j=2;j<=n;j++)
{
flag=0;
for(i=2;i<=j/2;i++)
{
if(j%i==0)
{
flag=1;
break;
}
}
if(flag==0)
printf("Prime No: %d\n",j);
}
}
3
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
4. Find X n . Iterative and recursive algorithms are possible with complexity log 2 n
#include<stdio.h>
float power(float x,int n)
{
if(n==0)
return 1;
else
{
float temp;
temp=power(x,n/2);
if(n%2==0)
return temp*temp;
else
return x*temp*temp;
}
}
void main()
{
int n,p;
printf("Enter No : ");
scanf("%d",&n);
printf("Enter Power : ");
scanf("%d",&p);
printf("\n Power is : %.0f ",power(n,p));
}
4
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
5. Determine product of 2 integers (a * b) as repeated sums. Iterative and recursive
algorithms are possible.
#include<stdio.h>
void main()
{
int n1,n2,sum;
printf("\n Enter NO :" );
scanf("%d",&n1);
printf("\n Enter NO :" );
scanf("%d",&n2);
sum=n1;
for(int i=0;i<n2-1;i++)
{
sum=sum+n1;
}
printf("\n %d",sum);
}
5
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
6. Determine product of 2 large integers using multiplication of their digits. For
simplicity, assume both numbers to have same number of digits. This assumption can be
relaxed subsequently.
#include<stdio.h>
#include<math.h>
int product(int n1, int n2)
{
int a,b,c,d,p1,p2,p3,n=2;
if(n1==0 ||n2==0)
{
return 0;
}
else
{
a=n1/10;
b=n1%10;
c=n2/10;
d=n2%10;
p1=a*c;
p2=b*d;
p3=(a+b)*(c+d);
return p1*pow(10,n)+(p3-p1-p2)*pow(10,n/2)+p2;
}
}
void main()
{
int n1,n2;
printf("\n--------------------------------------------------");
printf("\n Multiplication using Divide and Conquer");
printf("\n--------------------------------------------------");
printf("\n Enter number 1:");
scanf("%d",&n1);
printf("\n Enter number 2:");
scanf("%d",&n2);
printf("\n----------------------------------------------------");
printf("\n Multiplication of %d and %d is :%d",n1,n2,product(n1,n2));
printf("\n------------------------------------------------------\n");
}
6
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
7. Binary Search of an ordered array. Iterative and Recursive algorithms are possible.
#include<stdio.h>
#include<math.h>
void main()
{
int arr[15]={3,6,8,12,14,17,25,29,31,36,42,47,53,55,62};
int high=14,low=0,flag=1,mid;
int x=8;
while(low<=high)
{
mid=floor((low+high)/2);
if(x>=arr[mid])
{
flag=0;
break;
}
if(x<arr[mid])
high=mid-1;
else
low=mid+1;
}
if(flag==1)
printf("\n Element Not Found %d \n",x);
else
printf("\n Element Found %d \n",x);
}
7
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
8. Sort a given sequence of numbers using (a) Bubble Sort, and (b) Merge Sort
#include<stdio.h>
void mergearray(int arr[],int l,int m,int r)
{
int i,j,k;
int n1 = m-l+1;
int n2 = r-m;
int left[n1],right[n2];
for(i=0;i<n1;i++)
left[i]=arr[l+i];
for (j=0;j<n2;j++)
right[j]=arr[m+1+j];
i=0;j=0,k=l;
while(i<n1 && j<n2)
{
if(left[i]<=right[j])
{
arr[k]=left[i];
i++;
}
else
{
arr[k]=right[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = left[i];
i++; k++;
}
while (j<n2)
{
arr[k]=right[j];
j++; k++;
}
}
void mergesort(int arr[],int l,int r)
{
if(l<r)
{
int m=l+(r-l)/2;
mergesort(arr,l,m);
mergesort(arr,m+1,r);
mergearray(arr,l,m,r);
}
}
void main()
8
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
{
int arr[]={38,27,43,3,9,82,10},temp,swap=1;
//mergesort(arr,0,6);
printf("\n Merge Sort \n");
/*for(int i=0;i<=6;i++)
{
printf("%d ",arr[i]);
}*/
for(int i=0;i<=6;i++)
{
swap=1;
for(int j=i+1;j<=6;j++)
{
if(arr[i]>=arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
swap=0;
}
}
if(swap)
{
printf("Test");
break;
}
}
printf("\n Bubble Sort \n");
for(int i=0;i<=6;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
9
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
9. Knapsack problem using Greedy algorithm.
#include<stdio.h>
void main()
{
float weight[20], profit[20];
int items, i, j,capacity;
float ratio[20], temp;
printf("\nEnter the no. of Items ");
scanf("%d",&items);
printf("\nEnter the weight and profit of each item:- ");
for (i = 0; i < items; i++)
{
printf("\n enter the weight of item %d",i+1);
scanf("%f",&weight[i]);
printf("\n enter the value of item %d",i+1);
scanf("%f",&profit[i]);
}
printf("\nEnter the capacityacity of knapsack : ");
scanf("%d", &capacity);
for (i = 0; i < items; i++)
{
ratio[i] = profit[i] /(float)weight[i];
}
for (i = 0; i <items; i++)
{
for (j = i + 1; j < items ; 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;
}
}
}
for(int i=0;i<items;i++)
{
10
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
printf("| %d | %f | %f | %f |\n",i+1,weight[i],profit[i],ratio[i]);
}
int cu=capacity;
float x[10],t=0;
for(i =0;i<items;i++)
{
x[i]=0.0;
}
for(i=0;i<items;i++)
{
if(weight[i]>cu)
{
printf("No Space");
break;
}
else
{
x[i]=1.0;
t=t+profit[i];
cu=cu-weight[i];
}
}
if(i<items)
{
x[i]=cu/weight[i];
}
t = t + (x[i] * profit[i]);
for (i = 0; i < items; i++)
printf("%f\n", x[i]);
printf("Profit is : %f\n", t);
}
11
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
10. Solution of Rod-cutting problem using Dynamic Programming algorithm.
#include<stdio.h>
#include<stdlib.h>
int rodCut(int price[], int n)
{
int t[n + 1];
for (int i = 0; i <= n; i++)
t[i] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
printf("%d %d",t[i], price[j - 1] + t[i - j]);
t[i] = max(t[i], price[j - 1] + t[i - j]);
}
}
return t[n];
}
void main()
{
// int length[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
int price [] = { 1, 5, 8, 9, 10, 17, 17, 20 };
// rod length
int n = 4;
printf("Profit is %d ", rodCut(price, n));
}
12
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
11. Multiplication of n Matrices using Dynamic Programming algorithm.
#include<stdio.h>
void main()
{
int m, n, p, q, c, d, k, sum = 0,matrix1[10][10], matrix11[10][10], multiply[10][10];
printf("Enter number of rows and columns of matrix1 matrix\n");
scanf("%d%d", &m, &n);
printf("Enter elements of matrix1 matrix\n");
for (c = 0; c < m; c++)
{
for (d = 0; d < n; d++)
scanf("%d", &matrix1[c][d]);
}
printf("Enter number of rows and columns of matrix11 matrix\n");
scanf("%d%d", &p, &q);
if (n != p)
printf("The matrices can't be multiplied with each other.\n");
else
printf("Enter elements of matrix11 matrix\n");
for (c = 0; c < p; c++)
{
for (d = 0; d < q; d++)
scanf("%d", &matrix11[c][d]);
}
for (c = 0; c < m; c++)
{
for (d = 0; d < q; d++)
{
for (k = 0; k < p; k++)
{
sum = sum + matrix1[c][k]*matrix11[k][d];
}
multiply[c][d] = sum;
sum = 0;
}
}
printf("Product of the matrices:\n");
for (c = 0; c < m; c++)
{
for (d = 0; d < q; d++)
{
printf("%d\t", multiply[c][d]);
}
printf("\n");
}
}
13
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
12. Breadth First Search (BFS) in a binary tree.
#include<stdio.h>
#define MAX 20
#define TRUE 1
#define FALSE 0
int g[MAX][MAX];
int v[MAX];
int Q[MAX];
int n;
int front,rear;
void create();
void BFS(int);
void main()
{
int i,j;
char ans;
printf("\n****************************************************");
printf("\nBREADTH FIRST SEARCH");
printf("\n****************************************************");
create();
do
{
for(i=0;i < n;i++)
v[i]=FALSE;
printf("\n Enter Vertex from which you Want to traverse:");
scanf("%d",&i);
if(i>=MAX)
printf("\n Invalid Vertex");
else
{
printf("\n The Breadth First Search of the Graph is:");
printf("\n *******************************************\n");
BFS(i);
printf("\n********************************************\n");
}
printf("\n Dou want to Traverse By other node?");
scanf("%c",&ans);
}while(ans=='y' || ans=='Y');
}
void create()
{
int ch,i,j,flag;
char ans='y';
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
g[i][j]=FALSE;
}
printf("\n Enter number of nodes:");
scanf("%d",&n);
14
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
printf("\n Enter the vertices no. starting from 0");
for(int k=0;k<n;k++)
{
printf("\n Enter the vertices v1 & v2:");
scanf("%d %d",&i,&j);
if(i>=n && j>=n)
printf("\n Invali Vertex value.");
else
{
g[i][j]=TRUE;
g[j][i]=TRUE;
}
}
}
void BFS(int i)
{
int j;
v[i]=TRUE;
front=rear=-1;
Q[++rear]=i;
while(front!=rear)
{
i=Q[++front];
printf("%d -> ",i);
for(j=0;j < n;j++)
{
if(g[i][j]==TRUE && v[j]==FALSE)
{
Q[++rear]=j;
v[j]=TRUE;
}
}
}
}
15
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
13. Depth First Search (DFS) in a binary tree.
#include<stdio.h>
#define MAX 20
#define TRUE 1
#define FALSE 0
int g[MAX][MAX];
int v[MAX];
int n;
void create();
void DFS();
void main()
{
int i,j;
char ans;
printf("\n----------------------------------------------------");
printf("\n DEPTH FIRST SEARCH");
printf("\n----------------------------------------------------");
create();
do
{
for(i=0;i < n;i++)
v[i]=FALSE;
printf("\n Enter Vertex from which you Want to traverse:");
scanf("%d",&i);
if(i>=MAX)
printf("\n Invalid Vertex");
else
{
printf("\n The Depth First Search of the Graph is:");
printf("\n----------------------------------------------------\n");
DFS(i);
printf("\n----------------------------------------------------\n");
}
printf("\n Dou want to Traverse By other node?\n");
scanf(" %c",&ans);
}while(ans=='y' || ans=='Y');
}
void create()
{
int ch,i,j,flag,p=1;
char ans='y';
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
g[i][j]=FALSE;
}
printf("\n Enter number of nodes:");
scanf("%d",&n);
printf("\n Enter the vertices no. starting from 0");
16
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
do
{
printf("\n Enter the vertices v1 & v2:");
scanf("%d %d",&i,&j);
if(i>=n && j>=n)
{
printf("\n Invali Vertex value.");
}
else
{
g[i][j]=TRUE;
g[j][i]=TRUE;
}
p++;
}while(p<=n);
}
void DFS(int i)
{
int j;
printf("%d-->",i);
v[i]=TRUE;
for(j=0;j < MAX;j++)
if(g[i][j]==TRUE && v[j]==FALSE)
DFS(j);
}
17
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
15. Solve 8 Queens problem.
#include<stdio.h>
#include<stdlib.h>
int board[20];
int count;
void print_board(int);
void Queen(int,int);
int place(int,int);
void main()
{
int n,i,j;
printf("\n-------------------------------------------------------");
printf("\n n-Queen problem using Backtracking");
printf("\n-------------------------------------------------------");
printf("\n Enter number of Queen:");
scanf("%d",&n);
Queen(1,n);
}
void print_board(int n)
{
int i,j;
printf("\n-------------Solution %d---------------\n ",++count);
for(i=1;i<=n;i++)
{
printf(" %d",i);
}
printf("\n-------------------------------------------------------");
for(i=1;i<=n;i++)
{
printf("\n%2d | ",i);
for(j=1;j<=n;j++)
{
if(board[i]==j)
printf(" Q");
else
printf(" -");
}
}
printf("\n-------------------------------------------------------\n");
}
int place(int row,int column)
{
int i;
for(i=1;i<=row-1;i++)
{
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
18
Enrollment No : 185313693009
Name : Choksi Khushbu B.
Subject : Design Analysis & Algoritham
}
return 1;
}
void Queen(int row,int n)
{
int column;
for(column=1;column<=n;column++)
{
if(place(row,column))
{
board[row]=column;
if(row==n)
print_board(n);
else
Queen(row+1,n);
}
}
}
19