ADSA Lab Programs

Department of CSE
G. Pulla Reddy Engineering College
(JNTUA Scheme 2023)
Table of Contents

1. ~All Pairs Shortest Path

2. ~Breadth first Traversal(BFT)
3. ~BoyerMoore String Search
4. ~BruteForce String Search
5. ~Depth First Traversal(DFT)
6. ~Heap Sort
7. ~Job Sequencing with Deadlines
8. ~Knapsack Problem
9. ~Merge Sort
10. ~N-Queens
11. ~Quick Sort
12. ~Single Source Shortest Path
 ~All Pairs Shortest Path~
#include <stdio.h>
#include<conio.h>
#define INF 9999
#define MAX 20
int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int n, i, j, k;
int dist[MAX][MAX];
clrscr();
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (use %d for INF):\n", INF);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &dist[i][j]);
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
printf("All pairs shortest path matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (dist[i][j] == INF)
printf("INF ");
else
printf("%3d ", dist[i][j]);
}
printf("\n");
}
getch();
return 0;
}
 ~Breadth first Traversal(BFT)~
#include <stdio.h>
#include<conio.h>
#define MAX 20
int adj[MAX][MAX];
int visited[MAX];
int queue[MAX], front = -1, rear = -1;
int n;
void bfs(int start) {
int i, v;
for (i = 0; i < n; i++)
visited[i] = 0;
front = rear = 0;
queue[rear] = start;
visited[start] = 1;
printf("BFS Traversal: ");
while (front <= rear) {
v = queue[front++];
printf("%d ", v);
for (i = 0; i < n; i++) {
if (adj[v][i] == 1 && visited[i] == 0) {
queue[++rear] = i;
visited[i] = 1;
}
}
}
printf("\n");
}
int main() {
int i, j, start;
clrscr();
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", &adj[i][j]);
}
}
printf("Enter starting vertex (0 to %d): ", n - 1);
scanf("%d", &start);
bfs(start);
getch();
return 0;
}
 ~BoyerMoore String Search~
#include <stdio.h>
#include <string.h>
#include<conio.h>
#define NO_OF_CHARS 256
int max(int a, int b) {
return (a > b) ? a : b;
}
void badCharHeuristic(char *str, int size, int badchar[NO_OF_CHARS]) {
int i;
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
int boyerMoore(char text[], char pattern[]) {
int m = strlen(pattern);
int n = strlen(text);
int s = 0;
int badchar[NO_OF_CHARS];
badCharHeuristic(pattern, m, badchar);
while (s <= (n - m)) {
int j = m - 1;
while (j >= 0 && pattern[j] == text[s + j])
j--;
if (j < 0) {
return s;
} else {
s += max(1, j - badchar[(int) text[s + j]]);
}
}
return -1;
}
int main() {
char text[100], pattern[50];
int pos;
clrscr();
printf("Enter text: ");
gets(text);
printf("Enter pattern: ");
gets(pattern);
pos = boyerMoore(text, pattern);
if (pos == -1)
 printf("Pattern not found\n");
else
printf("Pattern found at position %d\n", pos);
getch();
return 0;
}
 ~BruteForce String Search~
#include <stdio.h>
#include <string.h>
#include<conio.h>
int bruteForce(char text[], char pattern[]) {
int n = strlen(text);
int m = strlen(pattern);
int i, j, flag;
for (i = 0; i <= n - m; i++) {
flag = 1;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
flag = 0;
break;
}
}
if (flag == 1)
return i;
}
return -1;
}
int main() {
char text[100], pattern[50];
int pos;
clrscr();
printf("Enter the main text: ");
gets(text);
printf("Enter the pattern to search: ");
gets(pattern);
printf("\nText entered: %s\n", text);
printf("Pattern entered: %s\n", pattern);
pos = bruteForce(text, pattern);
if (pos == -1)
 printf("Pattern not found in the text\n");
else
printf("Pattern found at position %d (0-based index)\n", pos);
getch();
return 0;
}
 ~Depth First Traversal(DFT)~
#include <stdio.h>
#include<conio.h>
#define MAX 20
int adj[MAX][MAX];
int visited[MAX];
int n;
void dfs(int v) {
int i;
visited[v] = 1;
printf("%d ", v);
for (i = 0; i < n; i++) {
if (adj[v][i] == 1 && visited[i] == 0) {
dfs(i);
}
}
}
int main() {
int i, j, start;
clrscr();
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", &adj[i][j]);
}
}
for (i = 0; i < n; i++)
visited[i] = 0;
printf("Enter starting vertex (0 to %d): ", n - 1);
 scanf("%d", &start);
printf("DFS Traversal: ");
dfs(start);
printf("\n");
getch();
return 0;
}
 ~Heap Sort~
#include <stdio.h>
#include<conio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int i;
for (i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
 heapify(arr, i, 0);
}
}
int main() {
int n, i;
int arr[50];
clrscr();
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
heapSort(arr, n);
printf("Sorted array:\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
getch();
return 0;
}
 ~Job Sequencing with Deadlines~
#include <stdio.h>
#include<conio.h>
struct Job {
int id, deadline, profit;
};
void sort(struct Job jobs[], int n) {
int i, j;
struct Job temp;
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (jobs[i].profit < jobs[j].profit) {
temp = jobs[i];
jobs[i] = jobs[j];
jobs[j] = temp;
}
}
}
}
int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int n, i, j, maxd = 0, slot[20], result[20], count = 0, totalProfit = 0;
struct Job jobs[20];
clrscr();
printf("Enter number of jobs: ");
scanf("%d", &n);
printf("Enter job id, deadline and profit:\n");
for (i = 0; i < n; i++) {
scanf("%d%d%d", &jobs[i].id, &jobs[i].deadline, &jobs[i].profit);
if (jobs[i].deadline > maxd)
maxd = jobs[i].deadline;
}
sort(jobs, n);
for (i = 1; i <= maxd; i++)
slot[i] = -1;
for (i = 0; i < n; i++) {
for (j = min(maxd, jobs[i].deadline); j >= 1; j--) {
if (slot[j] == -1) {
slot[j] = jobs[i].id;
totalProfit += jobs[i].profit;
count++;
break;
}
}
}
printf("Selected jobs: ");
for (i = 1; i <= maxd; i++) {
if (slot[i] != -1)
printf("%d ", slot[i]);
}
printf("\nTotal profit: %d\n", totalProfit);
getch();
return 0;
}
 ~Knapsack Problem~
#include <stdio.h>
#include<conio.h>
struct Item {
int weight, value;
};
void sort(struct Item items[], int n) {
int i, j;
struct Item temp;
double r1, r2;
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
r1 = (double)items[i].value / items[i].weight;
r2 = (double)items[j].value / items[j].weight;
if (r1 < r2) {
temp = items[i];
items[i] = items[j];
items[j] = temp;
}
}
}
}
int main() {
int n, i, W;
struct Item items[20];
double total = 0.0;
clrscr();
printf("Enter number of items: ");
scanf("%d", &n);
printf("Enter weight and value of each item:\n");
for (i = 0; i < n; i++)
scanf("%d%d", &items[i].weight, &items[i].value);
printf("Enter capacity of knapsack: ");
scanf("%d", &W);
sort(items, n);
for (i = 0; i < n; i++) {
if (items[i].weight <= W) {
W -= items[i].weight;
total += items[i].value;
} else {
total += (double)items[i].value * W / items[i].weight;
break;
}
}
printf("Maximum value in knapsack = %.2f\n", total);
getch();
return 0;
}
 ~Merge Sort~
#include <stdio.h>
#include<stdlib.h>
void merge(int a[], int l, int m, int r) {
int i = l, j = m + 1, k = l, temp[50];
while (i <= m && j <= r) {
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= r)
temp[k++] = a[j++];
for (i = l; i <= r; i++)
a[i] = temp[i];
}
void mergesort(int a[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergesort(a, l, m);
mergesort(a, m + 1, r);
merge(a, l, m, r);
}
}
int main() {
int n, i, a[50];
clrscr();
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
mergesort(a, 0, n - 1);
printf("Sorted array:\n");
for (i = 0; i < n; i++)
printf("%d ", a[i]);
getch();
return 0;
}
 ~N-Queens~
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<conio.h>
int board[20],count;
int main()
{
int n,i,j;
void queen(int row,int n);
clrscr();
printf(" - N Queens Problem Using Backtracking -");
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
queen(1,n);
getch();
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);
}
}
}
 ~Quick Sort~
#include <stdio.h>
#include<conio.h>
void quicksort(int a[], int low, int high) {
int i = low, j = high, pivot = a[(low + high) / 2], temp;
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (low < j)
quicksort(a, low, j);
if (i < high)
quicksort(a, i, high);
}
int main() {
int n, i, a[50];
clrscr();
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
quicksort(a, 0, n - 1);
printf("Sorted array:\n");
for (i = 0; i < n; i++)
printf("%d ", a[i]);
getch();
return 0;
}
 ~Single Source Shortest Path~
#include <stdio.h>
#include<conio.h>
#define INF 9999
#define MAX 20
int n;
int cost[MAX][MAX];
void dijkstra(int start) {
int dist[MAX], visited[MAX], count, mindist, nextnode, i, j;
for (i = 0; i < n; i++) {
dist[i] = cost[start][i];
visited[i] = 0;
}
dist[start] = 0;
visited[start] = 1;
count = 1;
while (count < n - 1) {
mindist = INF;
for (i = 0; i < n; i++)
if (dist[i] < mindist && !visited[i]) {
mindist = dist[i];
nextnode = i;
}
visited[nextnode] = 1;
for (i = 0; i < n; i++)
if (!visited[i])
if (mindist + cost[nextnode][i] < dist[i])
dist[i] = mindist + cost[nextnode][i];
count++;
}
printf("Vertex\tDistance from source\n");
for (i = 0; i < n; i++)
printf("%d\t%d\n", i, dist[i]);
}
int main() {
int i, j, start;
clrscr();
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (use 9999 for no edge):\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &cost[i][j]);
printf("Enter starting vertex: ");
 scanf("%d", &start);
dijkstra(start);
getch();
return 0;
}