Redg.No.
22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
HGFHGFG
Experiment-5
AIM: Write a program to implement Optimal storage on Tapes
Source Code:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void optimalTapeStorage(int programs[], int n, int m) {
bubbleSort(programs, n);
int tape[m][n];
int tapeIndex[m];
int tapeSum[m];
for (int i = 0; i < m; i++) {
tapeIndex[i] = 0;
tapeSum[i] = 0;
}
int j = 0;
for (int i = 0; i < n; i++) {
tape[j][tapeIndex[j]] = programs[i];
tapeIndex[j]++;
j = (j + 1) % m;
}
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", programs[i]);
}
printf("\n");
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
int totalSum = 0; HGFHGFG
for (int i = 0; i < m; i++) {
printf("Elements in tape %d: ", i);
int cumulativeSum = 0;
for (int k = 0; k < tapeIndex[i]; k++) {
printf("%d ", tape[i][k]);
cumulativeSum += tape[i][k];
tapeSum[i] += cumulativeSum;
}
printf("\n");
totalSum += tapeSum[i];
}
for (int i = 0; i < m; i++) {
printf("Total sum for tape %d: %d\n", i, tapeSum[i]);
}
printf("Total cumulative sum: %d\n", totalSum);
}
int main() {
int n, m;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter number of tapes: ");
scanf("%d", &m);
int programs[n];
printf("Enter elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &programs[i]);
}
optimalTapeStorage(programs, n, m);
return 0;
}
OUTPUT1 :
harshitha@victus:~$ gcc tapes.c
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
harshitha@victus:~$ ./a.out HGFHGFG
Enter number of elements: 12
Enter number of tapes: 3
Enter elements of the array:
2 4 5 6 7 26 12 18 7 8 6 4
Sorted array: 2 4 4 5 6 6 7 7 8 12 18 26
Elements in tape 0: 2 5 7 12
Elements in tape 1: 4 6 7 18
Elements in tape 2: 4 6 8 26
Total sum for tape 0: 49
Total sum for tape 1: 66
Total sum for tape 2: 76
Total cumulative sum: 191
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
HGFHGFG
Experiment -6
AIM: Write a program to implement All Pairs Shortest Path(Floyd’sWarshall)
Algorithm
Source Code:
#include <stdio.h>
#define INF 9999
#define MAX 100
int n;
int a[MAX][MAX];
void FloydWarshall() {
int i, j, k;
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (a[i][k] + a[k][j] < a[i][j]) {
a[i][j] = a[i][k] + a[k][j];
}
}
}
}
}
void printMatrix() {
int i, j;
printf("Shortest distance matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (a[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", a[i][j]);
}
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
printf("\n"); HGFHGFG
}
}
int main() {
int i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix (use %d for infinity):\n", INF);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
FloydWarshall();
printMatrix();
return 0;
}
OUTPUT1:
harshitha@victus:~$ gcc floydwarshall.c
harshitha@victus:~$ ./a.out
Enter the number of vertices: 3
Enter the adjacency matrix (use 9999 for infinity):
0 4 11
602
3 999 0
Shortest distance matrix:
0 4 6
5 0 2
3 7 0
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
HGFHGFG
Experiment-7
AIM: Write a program to implement Single Source Shortest Path (BellmanFord)
Algorithm
Source Code:
#include <stdio.h>
#include <stdlib.h>
#define INF 99
void printDistanceMatrix(int V, int distance[]) {
printf("Shortest distances from source:\n");
for (int i = 0; i < V; i++) {
if (distance[i] == INF)
printf("INF ");
else
printf("%d ", distance[i]);
}
printf("\n");
}
void BellmanFord(int V, int **graph, int src) {
int *distance = (int *)malloc(V * sizeof(int));
for (int i = 0; i < V; i++) {
distance[i] = INF;
}
distance[src] = 0;
for (int i = 1; i <= V - 1; i++) {
int updated = 0;
int *tempDistance = (int *)malloc(V * sizeof(int));
for (int k = 0; k < V; k++) {
tempDistance[k] = distance[k];
}
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
HGFHGFG
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != INF && distance[u] != INF && distance[u] + graph[u][v] <
tempDistance[v]) {
tempDistance[v] = distance[u] + graph[u][v];
updated = 1;
}
}
}
for (int k = 0; k < V; k++) {
distance[k] = tempDistance[k];
}
free(tempDistance);
if (!updated) {
break;
}
}
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != INF && distance[u] != INF && distance[u] + graph[u][v] < distance[v]) {
printf("Negative weight cycle detected\n");
free(distance);
return;
}
}
}
printDistanceMatrix(V, distance);
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
free(distance); HGFHGFG
int main() {
int V;
printf("Enter number of vertices: ");
scanf("%d", &V);
int **graph = (int **)malloc(V * sizeof(int *));
for (int i = 0; i < V; i++) {
graph[i] = (int *)malloc(V * sizeof(int));
}
printf("Enter the adjacency matrix (%d for INF):\n", INF);
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
}
}
int src;
printf("Enter source vertex (1 to %d): ", V);
scanf("%d", &src);
if (src < 1 || src > V) {
printf("Invalid source vertex!\n");
} else {
BellmanFord(V, graph, src - 1);
}
for (int i = 0; i < V; i++) {
free(graph[i]);
}
free(graph);
Design and Analysis of Algorithm Lab
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
HGFHGFG
return 0;
}
OUTPUT:
harshitha@victus:~$ gcc bellmanford2.c
harshitha@victus:~$ ./a.out
Enter number of vertices: 4
Enter the adjacency matrix (99 for INF):
0 4 5 99
99 0 5 99
99 99 0 3
99 -10 99 0
Enter source vertex (1 to 4): 1
Negative weight cycle detected
Design and Analysis of Algorithm Lab
