Daa 1-10 here
Week 1:
#include<stdio.h>
int max,min;
int a[100];
void maxmin(int i,int j)
{
int max1,min1,mid;
if(i==j)
{
min=max=a[i];
}
else
{
if(i==j-1)
{
if(a[i]<a[j])
{
max=a[i];
min=a[j];
}
else
{
max=a[i];
min=a[j];
}
}
else
{
mid=(i+j)/2;
maxmin(i,mid);
max1=max;
min1=min;
maxmin(mid+1,j);
if(max<max1)
max=max1;
if(min>min1)
min=min1;
}
}
}
int main()
{
int i,n;
printf("Enter no of keys\n");
scanf("%d",&n);
printf("Enter the keys:\n");
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
max=a[1];
min=a[1];
maxmin(1,n);
printf("Minimum element in the array is:%d\n",min);
printf("Maximum element in the array is:%d\n",max);
return 0;
}
Week 2:
#include<stdio.h>
#include<stdlib.h>
void merge(int arr[],int l,int m,int r)
{
int i,j,k;
int n1=m-l+1;
int n2=r-m;
int L[n1],R[n2];
for(i=0;i<n1;i++)
{
L[i]=arr[l+i];
}
for(j=0;j<n2;j++)
{
R[j]=arr[m+1+j];
}
i=0;
j=0;
k=l;
while(i<n1&&j<n2)
{
if(L[i]<=R[j])
{
arr[k]=L[i];
i++;
}
else
{
arr[k]=R[j];
j++;
}
k++;
}
while(i<n1)
{
arr[k]=L[i];
i++;
k++;
}
while(j<n2)
{
arr[k]=R[j];
j++;
k++;
}
}
void mergesort(int a[],int l,int r)
{
if(l<r)
{
int m=l+(r-l)/2;
mergesort(a,l,m);
mergesort(a,m+1,r);
merge(a,l,m,r);
}
}
void printarray(int a[],int size)
{ int i;
for(i=1;i<=size;i++)
{
printf("%d\n",a[i]);
}
}
int main()
{
int k,i;
int a[100];
int size;
printf("enter size");
scanf("%d",&size);
for(i=1;i<=size;i++)
{
scanf("%d",&a[i]);
}
printarray(a,size);
mergesort(a,1,size);
printf("\n sorted array is\n");
printarray(a,size);
printf("enter smallest element");
scanf("%d",&k);
if(k<=size)
{
for(i=0;i<size;i++)
{
if(i!=k)
continue;
else {
printf("%d",a[i]);
break;
}
}
}
}
Week 3:
#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);
}
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;
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();
return(0);
}
Week 4:
#include<limits.h>
#include<stdbool.h>
#include<stdio.h>
#define V 9
int minDistance(int dist[],bool sptset[])
{
int min=INT_MAX,min_index;
for(int v=0;v<V;v++)
if(sptset[v]==false&&dist[v]<=min)
min=dist[v],min_index=v;
return min_index;
}
void printSolution(int dist[])
{
printf("vertex\t\t distance from source\n");
for(int i=0;i<V;i++)
printf("%d\t\t\t%d\n",i,dist[i]);
}
void dijkstra(int graph[V][V],int src)
{
int dist[V];
bool sptset[V];
for(int i=0;i<V;i++)
dist[i]=INT_MAX,sptset[i]=false;
dist[src]=0;
for(int count=0;count<V-1;count++)
{
int u=minDistance(dist,sptset);
sptset[u]=true;
for(int v=0;v<V;v++)
if(!sptset[v]&&graph[u][v]&&dist[u]!=INT_MAX&&dist[u]+graph[u][v]<dist[v])
dist[v]=dist[u]+graph[u][v];
}
printSolution(dist);
}
int main()
{
int graph[V][V]={{0,4,0,0,0,0,8,0},
{4,0,8,0,0,0,0,11,0},
{0,8,0,7,0,4,0,0,2},
{0,0,7,0,9,14,0,0,0},
{0,0,0,9,0,10,0,0,0},
{0,0,4,14,10,0,2,0,0},
{0,0,0,0,0,2,0,1,6},
{8,11,0,0,0,0,1,0,7},
{0,0,2,0,0,0,6,7,0}};
dijkstra(graph,0);
return 0;
}
Week 5:
#include <stdio.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 uni(int, int);
void main()
{
printf("Kruskal's algorithm in C\n");
printf("========================\n");
printf("Enter the no. of vertices:\n");
scanf("%d", &n);
printf("\nEnter the cost adjacency matrix:\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = 999;
}
}
printf("The edges of Minimum Cost Spanning Tree are\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("%d edge (%d,%d) =%d\n", ne++, a, b, min);
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("\nMinimum cost = %d\n", mincost);
}
int find(int i)
{
while (parent[i])
i = parent[i];
return i;
}
int uni(int i, int j)
{
if (i != j)
{
parent[j] = i;
return 1;
}
}
Week 6:
#include<stdio.h>
#include<conio.h>
void main()
{
int stages=4,min;
int n=8;
int cost[9],path[9],d[9];
int c[9][9]={
{0,0,0,0,0,0,0,0,0},
{0,0,2,1,3,0,0,0,0},
{0,0,0,0,0,2,3,0,0},
{0,0,0,0,0,6,7,0,0},
{0,0,0,0,0,6,8,9,0},
{0,0,0,0,0,0,0,0,6},
{0,0,0,0,0,0,0,0,4},
{0,0,0,0,0,0,0,0,5},
{0,0,0,0,0,0,0,0,0},
};
cost[n]=0;
clrscr();
for(int i=n-1;i>=1;i--)
{
min=32767;
for(int k=i+1;k<=n;k++)
{ if(c[i][k]!=0 && c[i][k]+cost[k]<min)
{ min= c[i][k]+cost[k];
d[i]=k;
}
}
cost[i]=min;
}
printf("shortest path value is: %d",cost[1]);
getch();
}
Week 7:
#include <stdio.h>
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshall(int dist[][V])
{
int i, j, k;
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V])
{
printf(
"The following matrix shows the shortest distances"
" between every pair of vertices \n");
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
int main()
{
int graph[V][V] = { { 0, 11, 1, 6 },
{ 11, 0, 7, 3 },
{ 1, 7, 0, 2 },
{ 6, 3, 2, 0 } };
floydWarshall(graph);
return 0;
}
Week 8:
#include<stdio.h>
#include<math.h>
int board[20],count;
int main()
{
int n,i,j;
void queen(int row,int n);
printf(" - N Queens Problem Using Backtracking -");
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
queen(1,n);
return 0;
}
void print(int n)
{
int i,j;
printf("\n\nSolution %d:\n\n",++count);
for(i=1;i<=n;++i)
printf("\t%d",i);
for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j)
{
if(board[i]==j)
printf("\tQ");
else
printf("\t-");
}
}
}
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;
}
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(n);
else
queen(row+1,n);
}
}
}
Week 9:
#include<stdio.h>
#include<conio.h>
#define n 4
void printSolution(int color[]);
int isSafe(int graph[n][n], int color[])
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (graph[i][j] && color[j] == color[i])
return 0;
return 1;
}
int graphColoring(int graph[n][n], int m, int i,int color[n])
{
if (i == n)
{
if (isSafe(graph, color))
{
printSolution(color);
return 1;
}
return 0;
}
for (int j = 1; j <= m; j++)
{
color[i] = j;
if (graphColoring(graph, m, i + 1, color))
return 1;
color[i] = 0;
}
for (int j = 1; j <= m; j++)
{
color[i] = j;
if (graphColoring(graph, m, i + 1, color))
return 1;
color[i] = 0;
}
return 0;
}
void printSolution(int color[])
{
printf("Solution Exists:"
" Following are the assigned colors \n");
for (int i = 0; i < n; i++)
printf(" %d ", color[i]);
printf("\n");
}
int main()
{
int graph[n][n] = {
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};
int m = 3;
clrscr();
int color[n];
for (int i = 0; i < n; i++)
color[i] = 0;
if (!graphColoring(graph, m, 0, color))
printf("Solution does not exist");
getch();
return 0;
}
Week 10:
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { NO, YES } BOOL;
int N;
int vals[100];
int wts[100];
int cap = 0;
int mval = 0;
void getWeightAndValue (BOOL incl[N], int *weight, int *value) {
int i, w = 0, v = 0;
for (i = 0; i < N; ++i) {
if (incl[i]) {
w += wts[i];
v += vals[i];
}
}
*weight = w;
*value = v;
}
void printSubset (BOOL incl[N]) {
int i;
int val = 0;
printf("Included = { ");
for (i = 0; i < N; ++i) {
if (incl[i]) {
printf("%d ", wts[i]);
val += vals[i];
}
}
printf("}; Total value = %d\n", val);
}
void findKnapsack (BOOL incl[N], int i) {
int cwt, cval;
getWeightAndValue(incl, &cwt, &cval);
if (cwt <= cap) {
if (cval > mval) {
printSubset(incl);
mval = cval;
}
}
if (i == N || cwt >= cap) {
return;
}
int x = wts[i];
BOOL use[N], nouse[N];
memcpy(use, incl, sizeof(use));
memcpy(nouse, incl, sizeof(nouse));
use[i] = YES;
nouse[i] = NO;
findKnapsack(use, i+1);
findKnapsack(nouse, i+1);
}
int main() {
printf("Enter the number of elements: ");
scanf(" %d", &N);
BOOL incl[N];
int i;
for (i = 0; i < N; ++i) {
printf("Enter weight and value for element %d: ", i+1);
scanf(" %d %d", &wts[i], &vals[i]);
incl[i] = NO;
}
printf("Enter knapsack capacity: ");
scanf(" %d", &cap);
findKnapsack(incl, 0);
return 0;
}
Comments
Post a Comment