Codes
Experiment 1 exp1
Aim: compute the time and space complexity of basic recursive and iterative functions using Big-O notation.
#include <stdio.h>
#include <time.h>
// Recursive
long long factR(int n){
return (n<=1)?1:n*factR(n-1);
}
int main(){
int n,i;
long long f;
clock_t s,e;
double t;
printf("Enter a number to find factorial: ");
scanf("%d",&n);
// Iterative
f=1;
s=clock();
for(i=1;i<=n;i++) f*=i;
e=clock();
t=(double)(e-s)/CLOCKS_PER_SEC;
printf("\n[Iterative] Factorial of %d = %lld",n,f);
printf("\n[Iterative] Time taken: %f seconds",t);
printf("\n[Iterative] Space Complexity ≈ O(1)\n");
// Recursive
s=clock();
f=factR(n);
e=clock();
t=(double)(e-s)/CLOCKS_PER_SEC;
printf("\n[Recursive] Factorial of %d = %lld",n,f);
printf("\n[Recursive] Time taken: %f seconds",t);
printf("\n[Recursive] Space Complexity ≈ O(n) (due to recursion stack)\n");
return 0;
}
OUTPUT:
Enter a number to find factorial: 10
.....
Experiment 2 exp2
#include <stdio.h>
#include <time.h>
// Recursive Binary Search
int bs(int a[], int l, int r, int key){
if(l>r) return -1;
int m=(l+r)/2;
if(a[m]==key) return m;
return (key<a[m]) ? bs(a,l,m-1,key) : bs(a,m+1,r,key);
}
int main(){
int a[100000], n, key, res, i;
clock_t s,e;
double t;
printf("Enter number of elements: ");
scanf("%d",&n);
printf("Enter %d elements in sorted order:\n",n);
for(i=0;i<n;i++) scanf("%d",&a[i]);
printf("Enter the element to search: ");
scanf("%d",&key);
// Timing
s=clock();
res=bs(a,0,n-1,key);
e=clock();
t=(double)(e-s)/CLOCKS_PER_SEC;
if(res!=-1)
printf("\nElement %d found at position %d.\n",key,res+1);
else
printf("\nElement %d not found in the array.\n",key);
printf("\nTime taken by recursive binary search: %.10f seconds",t);
printf("\nTheoretical Time Complexity: O(log n)");
printf("\nSpace Complexity (due to recursion stack): O(log n)\n");
return 0;
}
OUTPUT:
Enter number of elements: 6
Enter 6 elements in sorted order:
3 7 12 18 25 31
Enter the element to search: 18
Experiment 3 exp3
#include <stdio.h>
int main(){
int a[100], n, i, j, t;
printf("Enter number of elements: ");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++) scanf("%d",&a[i]);
// Bubble Sort
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
printf("\nSorted array in ascending order:\n");
for(i=0;i<n;i++) printf("%d ",a[i]);
return 0;
}
OUTPUT:
Enter number of elements: 5
Enter 5 elements:
34 12 9 56 23
Experiment 4 exp4
Aim: implement Huffman Encoding algorithm...
#include <stdio.h>
#include <stdlib.h>
struct node{
char d;
int f;
struct node *l,*r;
};
struct node* newNode(char d,int f){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->d=d;
n->f=f;
n->l=n->r=NULL;
return n;
}
// Sort nodes (ascending freq)
void sort(struct node* a[],int n){
int i,j;
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(a[j]->f > a[j+1]->f){
struct node* t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
struct node* build(char d[],int f[],int n){
struct node* a[100];
int i;
for(i=0;i<n;i++)
a[i]=newNode(d[i],f[i]);
while(n>1){
sort(a,n);
struct node* l=a[0];
struct node* r=a[1];
struct node* top=newNode('$',l->f+r->f);
top->l=l;
top->r=r;
a[0]=top;
a[1]=a[n-1];
n--;
}
return a[0];
}
void print(struct node* r,int a[],int t){
int i;
if(r->l){
a[t]=0;
print(r->l,a,t+1);
}
if(r->r){
a[t]=1;
print(r->r,a,t+1);
}
if(!r->l && !r->r){
printf("%c: ",r->d);
for(i=0;i<t;i++) printf("%d",a[i]);
printf("\n");
}
}
int main(){
char d[]={'A','B','C','D','E','F'};
int f[]={5,9,12,13,16,45};
int n=6;
struct node* root=build(d,f,n);
int a[100];
printf("Huffman Codes are:\n");
print(root,a,0);
return 0;
}
Experiment 5: exp5
Aim: Implement and compare Prim’s and Kruskal’s algorithms for MST.
#include <stdio.h> #include <time.h> #define INF 9999 #define MAX 100 void prim(int c[MAX][MAX], int n){ int sel[MAX] = {0}; int i, j, min, x = 0, y = 0; int edges = 0, cost = 0; sel[0] = 1; printf("\nPrim's Algorithm Edges:\n"); while(edges < n - 1){ min = INF; for(i = 0; i < n; i++){ if(sel[i]){ for(j = 0; j < n; j++){ if(!sel[j] && c[i][j] < min){ min = c[i][j]; x = i; y = j; } } } } printf("Edge %d: (%d - %d) cost: %d\n", edges + 1, x, y, c[x][y]); cost += c[x][y]; sel[y] = 1; edges++; } printf("Total cost using Prim's Algorithm = %d\n", cost); } int find(int p[], int i){ while(p[i] != i) i = p[i]; return i; } void kruskal(int c[MAX][MAX], int n){ int p[MAX]; int i, j, u = 0, v = 0, min; int edges = 0, cost = 0; int used[MAX][MAX] = {0}; for(i = 0; i < n; i++) p[i] = i; printf("\nKruskal's Algorithm Edges:\n"); while(edges < n - 1){ min = INF; for(i = 0; i < n; i++){ for(j = 0; j < n; j++){ if(c[i][j] < min && !used[i][j]){ min = c[i][j]; u = i; v = j; } } } used[u][v] = used[v][u] = 1; if(find(p, u) != find(p, v)){ printf("Edge %d: (%d - %d) cost: %d\n", edges + 1, u, v, c[u][v]); cost += c[u][v]; p[find(p, u)] = find(p, v); edges++; } } printf("Total cost using Kruskal's Algorithm = %d\n", cost); } int main(){ int n, c[MAX][MAX], i, j; clock_t s, e; double t1, t2; printf("Enter number of vertices: "); scanf("%d", &n); printf("Enter the cost adjacency matrix:\n"); for(i = 0; i < n; i++){ for(j = 0; j < n; j++){ scanf("%d", &c[i][j]); if(c[i][j] == 0 && i != j) c[i][j] = INF; } } s = clock(); prim(c, n); e = clock(); t1 = (double)(e - s) / CLOCKS_PER_SEC; s = clock(); kruskal(c, n); e = clock(); t2 = (double)(e - s) / CLOCKS_PER_SEC; printf("\nExecution Time Comparison:"); printf("\nPrim's Algorithm Time: %.10f seconds", t1); printf("\nKruskal's Algorithm Time: %.10f seconds\n", t2); return 0; }
OUTPUT:
Enter number of vertices: 5
Enter the cost adjacency matrix:
0 4 0 7 0
4 0 6 0 3
0 6 0 5 8
7 0 5 0 2
0 3 8 2 0
Experimnet - 6 exp6
Aim: To solve 0/1 Knapsack problem using dynamic programming
/ To find the maximum profit for a knapsack of given capacity using the greedy approach (Fractional Knapsack).
#include <stdio.h>
int max(int a,int b){ return a>b?a:b; }
int main(){
int val[20],wt[20],K[50][50];
int n,W,i,w;
printf("Enter number of items: ");
scanf("%d",&n);
printf("Enter values (profits) of %d items:\n",n);
for(i=0;i<n;i++) scanf("%d",&val[i]);
printf("Enter weights of %d items:\n",n);
for(i=0;i<n;i++) scanf("%d",&wt[i]);
printf("Enter capacity of Knapsack: ");
scanf("%d",&W);
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];
}
}
printf("\nDynamic Programming Table:\n");
for(i=0;i<=n;i++){
for(w=0;w<=W;w++)
printf("%3d ",K[i][w]);
printf("\n");
}
printf("Maximum value that can be put in the knapsack = %d\n",K[n][W]);
return 0;
}
OUTPUT:
Enter number of items: 4
Enter values (profits) of 4 items:
3 4 5 6
Enter weights of 4 items:
2 3 4 5
Enter capacity of Knapsack: 5
Experiment - 7 exp7
Aim: To find the Longest Common Subsequence (LCS) between two strings using dynamic programming.
#include <stdio.h>
#include <string.h>
int max(int a,int b){ return a>b?a:b; }
int main(){
char X[]="AGGTAB", Y[]="GXTXAYB";
int m=strlen(X), n=strlen(Y);
int dp[50][50];
int i,j;
printf("Input:\n");
printf("X = '%s'\n",X);
printf("Y = '%s'\n",Y);
for(i=0;i<=m;i++){
for(j=0;j<=n;j++){
if(i==0 || j==0) dp[i][j]=0;
else if(X[i-1]==Y[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
printf("Output:\n");
printf("Length of LCS is %d\n",dp[m][n]);
return 0;
}
Experiment - 8 exp8
Aim:To implement Breadth First Search (BFS) and Depth First Search (DFS) algorithms (Implement Floyd-Warshall algorithm for shortest paths)
#include <stdio.h>
#define MAX 10
int a[MAX][MAX], v[MAX], n;
void bfs(int s){
int q[MAX], f=0, r=0, i;
v[s]=1;
q[r++]=s;
printf("BFS Traversal: ");
while(f<r){
int x=q[f++];
printf("%d ",x);
for(i=0;i<n;i++)
if(a[x][i] && !v[i]){
q[r++]=i;
v[i]=1;
}
}
printf("\n");
}
void dfs(int s){
int i;
printf("%d ",s);
v[s]=1;
for(i=0;i<n;i++)
if(a[s][i] && !v[i])
dfs(i);
}
int main(){
int i,j,s;
printf("Enter number of vertices: ");
scanf("%d",&n);
printf("Enter adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("Enter starting vertex: ");
scanf("%d",&s);
for(i=0;i<n;i++) v[i]=0;
bfs(s);
for(i=0;i<n;i++) v[i]=0;
printf("DFS Traversal: ");
dfs(s);
printf("\n");
return 0;
}
OUTPUT:
Enter number of vertices: 4
Enter adjacency matrix:
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
Enter starting vertex: 0
Experiment - 9 exp9
Aim: ....all pairs of vertices in a weighted graph using the Floyd-Warshall Algorithm.
#include <stdio.h>
#define V 4
#define INF 99999
int main(){
int g[V][V]={
{0,5,INF,10},
{INF,0,3,INF},
{INF,INF,0,1},
{INF,INF,INF,0}
};
int d[V][V], i,j,k;
printf("Floyd–Warshall Algorithm Implementation\n");
printf("--------------------------------------\n");
for(i=0;i<V;i++)
for(j=0;j<V;j++)
d[i][j]=g[i][j];
for(k=0;k<V;k++)
for(i=0;i<V;i++)
for(j=0;j<V;j++)
if(d[i][k]+d[k][j] < d[i][j])
d[i][j]=d[i][k]+d[k][j];
printf("\nShortest distances between every pair of vertices:\n");
for(i=0;i<V;i++){
for(j=0;j<V;j++){
if(d[i][j]==INF)
printf("%5s","INF");
else
printf("%5d",d[i][j]);
}
printf("\n");
}
return 0;
}
Experiment - 10 exp10
Aim: To solve the Traveling Salesperson Problem (TSP).....
#include <stdio.h>
#define N 4
#define INF 9999
int c[N][N]={
{0,10,15,20},
{10,0,35,25},
{15,35,0,30},
{20,25,30,0}
};
int dp[20][20], all=(1<<N)-1;
int tsp(int m,int p){
if(m==all) return c[p][0];
if(dp[m][p]!=-1) return dp[m][p];
int i,ans=INF;
for(i=0;i<N;i++)
if(!(m&(1<<i))){
int t=c[p][i]+tsp(m|(1<<i),i);
if(t<ans) ans=t;
}
return dp[m][p]=ans;
}
int approx(){
int vis[N]={0},i,cur=0,cost=0,min,j,next;
vis[0]=1;
printf("\nNearest Neighbor Path: 0");
for(i=1;i<N;i++){
min=INF; next=-1;
for(j=0;j<N;j++)
if(!vis[j] && c[cur][j]<min && c[cur][j]!=0){
min=c[cur][j];
next=j;
}
vis[next]=1;
cost+=min;
cur=next;
printf(" -> %d",cur);
}
cost+=c[cur][0];
printf(" -> 0\n");
return cost;
}
int main(){
int i,j;
for(i=0;i<20;i++)
for(j=0;j<20;j++)
dp[i][j]=-1;
printf("Traveling Salesperson Problem (TSP) Comparison\n");
printf("----------------------------------------------\n");
int exact=tsp(1,0);
int approxCost=approx();
double err=((double)(approxCost-exact)/exact)*100;
printf("\nOptimal (Exact) TSP Cost = %d",exact);
printf("\nApproximate (Nearest Neighbor) TSP Cost = %d",approxCost);
printf("\nApproximation Error = %.2f%%\n",err);
return 0;
}
Comments
Post a Comment