1. Write a program to sort a list of N elements using Selection Sort Technique.

#include <stdio.h>
int main()
{
int a[20],i,j,n,temp,s;
{
printf(“Enter the size of an array\n”);
scanf(“%d”,&n);
printf(“Enter %d array elements\n”,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
for(i=0;i<n;i++)
{
s=i;
for(j=i+1;j<n;j++)
{
if (a[j]<a[s])
s=j;
}
temp=a[s];
a[s] = a[i];
a[i] = temp;
}
printf(“The sorted elements are….\n”);
for(i=0;i<n;i++)
printf(“%3d”,a[i]);
}
return 0;
}
2. Write a program to perform Travelling Sales Man Problem.

#include<stdio.h>
#include<conio.h>
int visited[10]={0},n,cost=0,tsp[10][10];
void travellingsalesman(int c)
{
int k,adj_vertex=999;
int min=999;
visited[c]=1;
printf("%d ",c);
for(k=1;k<=n;k++)
{
if((tsp[c][k]!=0) && (visited[k] == 0))
{
if(tsp[c][k]<min)
{
min=tsp[c][k];
adj_vertex=k;
}
}
}
if(min!=999)
{
cost=cost+min;
}
if(adj_vertex==999)
{
adj_vertex=1;
printf("%d",adj_vertex);
cost=cost+tsp[c][adj_vertex];
return;
}
 travellingsalesman(adj_vertex);
}
void main()
{
int i,j;
clrscr();
printf("Enter the number of nodes on a graph\n");
scanf("%d",&n);
printf("Enter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&tsp[i][j]);
printf("Shortest Path: ");
travellingsalesman(1);
printf("\nMinimum Cost:");
printf("%d\n",cost);
getch();
}

3. Write a program to implement Dynamic Programming algorithm for the 0/1

Knapsack Problems.
#include<stdio.h>

int Knapsack(int W,int wt[],int val[],int n);

int max(int a,int b)

return (a>b)? a:b;

int Knapsack(int W,int wt[],int val[],int n)

int i,w;

int K[10][10];
 for(i=0;i<=n;i++)

for(w=0;w<=W;w++)

if(i==0 || w==0)

K[i][w]=0;

else if(wt[i-1] <= w)

K[i][w] =max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);

else

K[i][w] = K[i-1][w];

return K[n][W];

void main()

int n;

int val[10];

int wt[10];

int i;

int W;

printf("enter the number of items : ");

scanf("%d",&n);

printf("\n Enter the items weight and its value\n");

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

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

printf("\nEnter the capacity of the Knapsack : ");

scanf("%d",&W);

printf("\nValue=%d",Knapsack(W,wt,val,n));
 getch();

4. Write a program to perform Knapsack problem using Greedy Solution.

#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]);

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

}
void main()

float weight[20],profit[20],capacity;

int num,i,j;

float ratio[20],temp;

clrscr();

printf("\nEnter the number 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 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();

5. (a) Write a program to implement the DFS algorithm for a graph.

#include<stdio.h>
#include<stdlib.h>
int adj[100][100],n,visited[10]={0};
void dfs(int v,int n)
{
int i;
visited[v]=1;
for(i=1;i<=n;i++)
{
if(adj[v][i]==1 && visited[i] == 0)
{
printf("%d->%d\n",v,i);
dfs(i,n);
}
}
}
int main()
{
int i,j;
 clrscr();
printf("Enter the number of nodes on a graph\n");
scanf("%d",&n);
printf("Enter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&adj[i][j]);
dfs(1,n);
getch();
return 0;
}

(b) Write a program to implement the BFS algorithm for a graph.

#include<stdio.h>
#include<conio.h>
int a[10][10],q[10]={0},visited[10]={0},n,i,j,f=0,r=0;
void bfs(int v)
{
visited[v]=1;
printf("%d\t", v);
while(f<=r)
{
for(i=1;i<=n;i++)
{
if((a[v][i]==1)&&(visited[i]==0))
{
q[r++]=i;
visited[i]=1;
printf("%d\t",i);
}
}
v=q[f++];
 }
}
int main()
{
int v;
clrscr();
printf("Enter the number of vertices:\n");
scanf("%d", &n);
printf("Enter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d", &a[i][j]);
bfs(1);
getch();
return 0;
}

6. Write a program to find Minimum and Maximum value in an array using divide
and conquer.
#include<stdio.h>
#include<conio.h>
int max,min;
int a[100];
void minmax(int i,int j)
{
int max1,min1,mid;
if(i==j)
{
max=min=a[i];
}
else
 {
if(i==j-1)
{
if(a[i]<a[j])
{
max=a[j];
min=a[i];
}
else
{
max=a[i];
min=a[j];
}
}
else
{
mid=(i+j)/2;
minmax(i,mid);
max1=max;
min1=min;
minmax(mid+1,j);
if(max<max1)
max=max1;
if(min>min1)
min=min1;
}
}
}
void main()
{
int i,num;
clrscr();
 printf("\nEnter the total number of numbers : ");
scanf("%d",&num);
printf("Enter the numbers :\n");
for(i=1;i<=num;i++)
scanf("%d",&a[i]);
max=max=a[0];
minmax(1,num);
printf("Minimum element in an array : %d\n",min);
printf("Maximum element in an array : %d\n",max);
getch();
}

7. Write a test program to implement Divide and Conquer Strategy eg:-QuickSort

Algorithm for sorting list of integers in ascending order
#include<stdio.h>
#include<conio.h>
int a[100],i,j,n;
int partition(int low,int high)
{
int pivot=low;
int i=low,j=high,temp;
while(i<j)
{
while(a[i]<=a[pivot])
i++;
while(a[j]>a[pivot])
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
 }
temp=a[j];
a[j]=a[pivot];
a[pivot]=temp;
return j;
}
void quickSort(int low,int high)
{
int j;
if(low<high)
{
j=partition(low,high);
quickSort(low, j-1);
quickSort(j+1,high);
}
}
void main()
{
clrscr();
printf("Enter the size of the array \n");
scanf("%d",&n);
printf("Enter the aray elements \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quickSort(0,n-1);
printf("Order of Sorted elements: \n");
for(i=0;i<n;++i)
printf("%d\t",a[i]);
printf("\n");
getch();
}
8. Write a program to implement Merge Sort Algorithm for sorting a list of integers
in ascending order.

#include<stdio.h>
#include<conio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int low,int mid,int high);
int main()
{
int a[30],n,i;
clrscr();
printf("Enter number of elements:");
scanf("%d",&n);
printf("Enter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
return 0;
}
void mergesort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
 }
}
void merge(int a[],int low,int mid,int high)
{
int c[50];
int i,j,k;
i=low;
j=mid+1;
k=low;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
{
c[k++]=a[i++];
}
else
{
c[k++]=a[j++];
}
}
while(i<=mid)
c[k++]=a[i++];
while(j<=high)
c[k++]=a[j++];
for(i=0;i<k;i++)
a[i]=c[i];
}
9. Sort a given set of n integer elements using Merge sort method and compute its
time [Link] the program for varied values of n>5000 and record the time
take to sort.

#include <time.h>
#include <stdlib.h>

void mergesort(int, int);

void merge(int, int, int);

int a[20000], temp[20000], n, i, j, k; // n>5000

int main()
{
clock_t start, end;
double t;
printf("Enter the size\n");
scanf("%d", &n);
/*printf("Enter the array of elements\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
*/
for (i = 0; i < n; i++)
a[i] = rand();
start = clock();
mergesort(0, n - 1);
end = clock();
t = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("After sorting\n"); for (i = 0; i < n; i++)
printf("%d\t", temp[i]);
printf("time------>%f",t);
}
void mergesort(int low, int high)
{
int mid;
if (low != high)
{
mid = ((low + high) / 2);
 mergesort(low, mid);
mergesort(mid + 1, high);
merge(low, mid, high);
}
}
void merge(int low, int mid, int high)
{
i = low;
j = mid + 1;
k = low;
while ((i <= mid) && j <= high)
{
if (a[i] >= a[j])
temp[k++] = a[j++];
else
temp[k++] = a[i++];
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= high)
temp[k++] = a[j++];
for (i = low; i <= high; i++)
a[i] = temp[i];
}

10. Sort a given set of n integer elements using Quick sort method and compute its
time [Link] the program for varied values of n>5000 and record the time
take to sort.
#include <stdio.h>
#include <time.h>
int partition(int arr[], int low, int high);
void swap(int *a, int *b);
void quickSort(int arr[], int low, int high)
{
 int pivot;
if (low < high)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1); int j;
for (j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
printf("%d\t", arr[i]);
 }
printf("\n");
}
int main()
{
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d integers, (Let no be > 5000): \n", n);
for (i = 0; i < n;i++)
{
scanf("%d", &arr[i]);
}
for (i = 0; i < n; i++)

arr[i] = rand();

clock_t start, end;

start = clock();

quickSort(arr, 0, n - 1);

end = clock();

double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Sorted array: \n");
printArray(arr, n);
printf("Time taken to sort: %f second\n", time_taken);
return 0;
}

11. Write a C program that accepts the vertices and edges for a graph and stores it
as an adjacency matrix.

#include<stdio.h>
#include<conio.h>
 void main()
{
int a[10][10],i,j,n;
clrscr();
printf("Enter the number of vertices in a graph\n");
scanf("%d",&n);
printf("Enter the edges in the graph\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
Printf("The adjacency matrix of the graph is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",a[i][j]);
}
printf("\n");
}
getch();
}

12. Implement function to print In-Degree ,Out-degree and to display the adjacency
matrix.

#include<stdio.h>
int main()
{
int graph[50][50]={0};
int i,j,e,v,p,x,y,indegree[10]={0},outdegree[10]={0},a,q,w;
 clrscr();
printf("Enter the Number of Vertex:\n");
scanf("%d",&v);
printf("Enter the Number of Edge:\n");
scanf("%d",&e);
printf("Enter the edges in the graph\n");
for(i=1;i<=e;i++)
{
scanf("%d%d",&x,&y);
graph[x][y]=1;
}
for(i=1;i<=v;i++)
{
for(j=1;j<=v;j++)
{
if(graph[i][j]==1)
{
outdegree[i]++;
indegree[j]++;
}
}
}
printf("Indegree\n");
for(i=1;i<=v;i++)
{
printf("%d:%d\n",i,indegree[i]);
}
printf("Outdegree\n");
for(i=1;i<=v;i++)
{
printf("%d:%d\n",i,outdegree[i]);
}
 printf("The adjacency matrix is\n");
for(i=1;i<=v;i++)
{
for(j=1;j<=v;j++)
{
printf("%d\t",graph[i][j]);
}
printf("\n");
}
getch();
return 0;
}

13. Write a program to implement backtracking algorithm for solving problems like
N Queens.

#include<stdio.h>
#include<conio.h>
#include<math.h>
int x[30],count=0;
int place(int k,int pos)
{
int j;
for(j=1;j<k;j++)
{
if((x[j]==pos)||(abs(x[j]-pos)==abs(j-k)))
return 0;
}
return 1;
}
 void printsol(int n)
{
int i,j;
count++;
printf("______________\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
(x[i]==j)?printf("Q"):printf("*");
printf("\n");
}
}
void queen(int k,int n)
{
int i;
for(i=1;i<=n;i++)
if(place(k,i))
{
x[k]=i;
(k==n)?printsol(n):queen(k+1,n);
}
}
void main()
{
int n;
clrscr();
printf("Enter the number of queens\n");
scanf("%d",&n);
queen(1,n);
getch();
}
14. Write a program to implement the backtracking algorithm for sum of subsets
problem.

#include<stdio.h>
#include<conio.h>
void subset(int,int,int);
int x[10],w[10],d,count=0;
void main()
{
int i,n,sum=0;
clrscr();
printf("\nEnter the number of elements:");
scanf("%d",&n);
printf("\nEnter the elements in ascending order:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("\nEnter the sum: ");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum < d)
{
printf("No solution\n");
getch();
return;
}
subset(0,0,sum);
if(count == 0)
{
printf("No solution\n");
getch();
 return;
}
getch();
}
void subset(int cs,int k,int r)
{
int i;
x[k]=1;
if(cs + w[k] == d)
{
printf("\n\nSubset %d\n", ++count);
for(i=0;i<=k;i++)
{
if(x[i] ==1)
printf("%d\t",w[i]);
}
}
else if(cs + w[k] + w[k+1] <=d)
subset(cs + w[k],k + 1,r - w[k]);
if(cs+ r-w[k] >=d && cs+ w[k] <=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}

15. Write a program to implement greedy algorithm for job sequencing with
deadlines

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int id;
int deadline;
 int profit;
} Job;
int compareJobs(const void* a, const void* b)
{
Job* job1 = (Job*)a;
Job* job2 = (Job*)b;
return job2->profit - job1->profit;
}
void jobSequencing(Job jobs[], int n)
{
qsort(jobs, n, sizeof(Job), compareJobs);
int maxDeadline = 0;
for (int i = 0; i < n; i++)
{
if (jobs[i].deadline > maxDeadline)
maxDeadline = jobs[i].deadline;
}
int slots[maxDeadline];
for (int i = 0; i < maxDeadline; i++)
{
slots[i] = -1;
}
int totalProfit = 0;
int jobCount = 0;

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

{
for (int j = jobs[i].deadline - 1;
j >= 0; j--)
{
if (slots[j] == -1)
{
slots[j] = jobs[i].id;
totalProfit += jobs[i].profit;
jobCount++;
break;
}
}
}

printf("Selected Jobs (by ID): ");

for (int i = 0; i < maxDeadline; i++)
{
if (slots[i] != -1) {
 printf("%d ", slots[i]);
}
}
printf("\nTotal Profit: %d\n", totalProfit);
}

int main()
{
Job jobs[] = {
{1, 2, 100},
{2, 1, 19},
{3, 2, 27},
{4, 1, 25},
{5, 3, 15}
};
int n = sizeof(jobs) / sizeof(jobs[0]);
printf("Job Sequencing with Deadlines\n");
jobSequencing(jobs, n);

return 0;
}

16. Write a program to implement Dynamic programming algorithm for optimal

binary search tree problem.

#include <stdio.h>
#include <limits.h>
#define MAX 100
void optimalBST(int keys[], int freq[], int n)
{
int cost[MAX][MAX] = {0};
int root[MAX][MAX] = {0};
int sum[MAX][MAX] = {0};

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

{
sum[i][i] = freq[i];
for (int j = i + 1; j < n; j++)
{
sum[i][j] = sum[i][j - 1] + freq[j];
}
}

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

cost[i][i] = freq[i];
root[i][i] = i;
 }

for (int L = 2; L <= n; L++) {

for (int i = 0; i <= n - L; i++) {
int j = i + L - 1;
cost[i][j] = INT_MAX;

for (int r = i; r <= j; r++)

{
int leftCost = (r > i) ? cost[i][r - 1] : 0;
int rightCost = (r < j) ? cost[r + 1][j] : 0;
int totalCost = leftCost + rightCost + sum[i][j];

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

{
cost[i][j] = totalCost;
root[i][j] = r;
}
}
}
}
printf("Optimal Cost: %d\n", cost[0][n - 1]);
printf("Root Table:\n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i <= j)
printf("%d ", root[i][j]);
else
printf(" ");
}
printf("\n");
}
}

int main()
{
int keys[] = {10, 20, 30, 40};
int freq[] = {3, 6, 8, 10};
int n = sizeof(keys) / sizeof(keys[0]);
printf("Optimal Binary Search Tree Problem\n");
optimalBST(keys, freq, n);
return 0;
}
17. Write a program that implements Prim's algorithm to generate minimum cost
spanning tree.

#include<stdio.h>
#include<conio.h>
void main()
{
int ne=1,n,min,vis[10]={0},cost[10][10],i,j,u,v,mincost=0;
clrscr();
printf("Enter the number of edges in the graph\n");
scanf("%d",&n);
printf("Enter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
}
vis[1]=1;
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((vis[i]==1) &&(cost[i][j]<min))
{
min=cost[i][j];
v=i;
u=j;
}
if(vis[u]==0)
{
 printf("%d-->%d=%d\n",v,u,min);
ne++;
mincost=mincost+min;
vis[u]=1;
}
cost[u][v]=cost[v][u]=999;
}
printf("Minimum Cost=%d\n",mincost);
getch();
}

18. Write a program that implements Kruskal's algorithm to generate minimum cost
spanning tree.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0;cost[9][9],parent[9];
int find(int);
int check(int,int);
void main()
{
clrscr();
printf("Enter the number of vertices:\n");
scanf("%d",&n);
printf("\Enter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne<n)
{
min=999;
for(i=1;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(check(u,v))
{
printf("%d edge (%d, %d)=%d\n",ne++,a,b,min);
mincost=mincost+min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\nMinimum cost=%d\n",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int check(int i,int j)
{
if(i!=j)
 {
parent[j]=i;
return 1;
}
return 0;
}