DAA LAB

MANUAL

DAA LAB
Aim: To Implement a Quicksort method using C program
Source code:
#include <stdio.h>
void quick_sort(int[],int,int);
int partition(int[],int,int);
int main()
{
int a[50],n,i;
printf("How many elements?");
scanf("%d",&n);
printf("\nEnter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick_sort(a,0,n-1);
printf("\nArray after sorting:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void quick_sort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}

int partition(int a[],int l,int u)

{
int v,i,j,temp;
v=a[l];

DAA LAB
 i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}

Result:
How many elements?5
Enter array elements:9 4 7 2 4
Array after sorting:2 4 4 7 9

DAA LAB
Aim: To Implement a Merge Sort technique using C program
Source Code:
#include <stdio.h>
void merge(int arr[], int left[], int left_size, int right[], int right_size) {
int i = 0, j = 0, k = 0;
while (i < left_size && j < right_size) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left_size) {
arr[k++] = left[i++];
}
while (j < right_size) {
arr[k++] = right[j++];
}
}
void merge_sort(int arr[], int n) {
if (n <= 1) {
return;
}
int mid = n / 2;
int left[mid], right[n - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < n; i++) {
right[i - mid] = arr[i];
}
merge_sort(left, mid);
merge_sort(right, n - mid);
merge(arr, left, mid, right, n - mid);
}
int main() {
int n;

DAA LAB
 printf("Enter the number of elements in the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Array before sorting: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
merge_sort(arr, n);
printf("Array after sorting: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Result:
How many elements? 5
Enter array elements:9 4 7 2 4
Array after sorting:2 4 4 7 9

DAA LAB
Aim: To implement a Prim’s technique using C program
Source Code:
#include<stdio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main() {
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the 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;
}
visited[1]=1;
printf("\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]< min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
}

DAA LAB
Output:
enter the number of nodes:5
enter the adjacency matrix
02060
20385
03007
68009
05790
02060
Edge 1:(1 2) cost:2
Edge 2:(2 3) cost:3
Edge 3:(2 5) cost:5
Edge 4:(1 4) cost:6
Minimum cost=16

DAA LAB
Aim: To implement a kruskal’s algorithm using C program
Program:
#include <stdio.h>
#include <stdlib.h>
int comparator(const void* p1, const void* p2)
{
const int(*x)[3] = p1;
const int(*y)[3] = p2;
return (*x)[2] - (*y)[2];
}
void makeSet(int parent[], int rank[], int n)
{
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int findParent(int parent[], int component)
{
if (parent[component] == component)
return component;
return parent[component]
= findParent(parent, parent[component]);
}

// Function to unite two sets

void unionSet(int u, int v, int parent[], int rank[], int n)
{
// Finding the parents
u = findParent(parent, u);
v = findParent(parent, v);
if (rank[u] < rank[v]) {
parent[u] = v;
}
else if (rank[u] > rank[v]) {
parent[v] = u;
}
else {
parent[v] = u;

DAA LAB
 rank[u]++;
}
}

void kruskalAlgo(int n, int edge[n][3])

{
qsort(edge, n, sizeof(edge[0]), comparator);
int parent[n];
int rank[n];
makeSet(parent, rank, n);
int minCost = 0;
printf(
"Following are the edges in the constructed MST\n");
for (int i = 0; i < n; i++) {
int v1 = findParent(parent, edge[i][0]);
int v2 = findParent(parent, edge[i][1]);
int wt = edge[i][2];
if (v1 != v2) {
unionSet(v1, v2, parent, rank, n);
minCost += wt;
printf("%d -- %d == %d\n", edge[i][0],
edge[i][1], wt);
}
}
printf("Minimum Cost Spanning Tree: %d\n", minCost);
}
int main()
{
int edge[5][3] = { { 0, 1, 10 },
{ 0, 2, 6 },
{ 0, 3, 5 },
{ 1, 3, 15 },
{ 2, 3, 4 } };

kruskalAlgo(5, edge);

return 0;
}

DAA LAB
Output:
Following are the edges in the constructed MST
2 – 3 == 4
0 – 3 == 5
0 – 1 == 10
Minimum Cost Spanning Tree: 19

DAA LAB
Aim: To implement a 0/1 knapsack problem using C Program
Program:
#include<stdio.h>
int max(int a, int b) {
if(a>b){
return a;
} else {
return b;
}
}
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int knap[n+1][W+1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i==0 || w==0)
knap[i][w] = 0;
else if (wt[i-1] <= w)
knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
else
knap[i][w] = knap[i-1][w];
}
}
return knap[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("The solution is : %d", knapsack(W, wt, val, n));
return 0;
}

Output:
The solution is : 220

DAA LAB
Aim: To implement a Dijkstra Algorithm using C program
Program:
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 5
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\t %d\n”, I, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V]; // sptSet[i] will be true if vertex i is
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);
}

DAA LAB
int main()
{
int graph[V][V] = { {0,10,0,0,3 },{0,0,2,0,4},{0,0,0,9,0},{0,0,7,0,0},{0,1,8,2,0}};
dijkstra(graph, 0);
return 0;
}
Output:
Vertex Distance from Source
0 0
1 4
2 6
3 5
4 3

DAA LAB
Aim: To implement a Floyd Warshall Algorithm in Java
Program:
class FloydWarshall
{
final static int INF = 9999, nV = 4;
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][])
{
int matrix[][] = new int[nV][nV];
int i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
// Adding vertices individually
for (k = 0; k < nV; k++)
{
for (i = 0; i < nV; i++)
{
for (j = 0; j < nV; j++)
{
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}
void printMatrix(int matrix[][])
{
for (int i = 0; i < nV; ++i) {
for (int j = 0; j < nV; ++j) {
if (matrix[i][j] == INF)
System.out.print("INF ");
else
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args)

DAA LAB
{
int graph[][] = { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF}
,{ INF, INF, 2, 0 } };
FloydWarshall a = new FloydWarshall();
a.floydWarshall(graph);
}
}

Output:
0 3 7 5
2 0 6 4
3 1 0 5
5 3 2 0

DAA LAB
Aim: To Implement Sum Of Subsets Problem in Java
Program:
public class sumofsubsets
{
static int subset_count = 0;

static void subset_sum(int list[], int sum, int starting_index, int target_sum)
{
if( target_sum == sum )
{
subset_count++;
if(starting_index < list.length)
subset_sum(list, sum - list[starting_index-1], starting_index,
target_sum);
}
else
{
for( int i = starting_index; i < list.length; i++ )
{
subset_sum(list, sum + list[i], i + 1, target_sum);
}
}
}

public static void main(String args[])

{
int list[] = {1, 3, 5, 2};
subset_sum(list, 0, 0, 6);
System.out.println(subset_count);
}
}
Output:
2

DAA LAB
Aim: To Implement the N Queen Problem in Java
Program:
public class NQueenProblem {
final int N = 4;
void printSolution(int board[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 1)
System.out.print("Q ");
else
System.out.print(". ");
}
System.out.println();
}
}
boolean isSafe(int board[][], int row, int col)
{
int i, j;
// Check this row on left side
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
// Check upper diagonal on left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
// Check lower diagonal on left side
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;

return true;
}
boolean solveNQUtil(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col) {

DAA LAB
 board[i][col] = 1;
if (solveNQUtil(board, col + 1) == true)
return true;
board[i][col] = 0;
}
}
return false;
}
boolean solveNQ()
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
System.out.print("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
public static void main(String args[])
{
NQueenProblem Queen = new NQueenProblem();
Queen.solveNQ();
}
}
Output:
. . Q .
Q . . .
. . . Q
. Q . .

DAA LAB
Aim: To implement inorder traversal in C
Program:
#include <stdio.h>
#include <stdlib.h>

// Definition for a binary tree node

struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};

// Function to create a new node

struct TreeNode* createNode(int val) {
struct TreeNode* newNode = (struct
TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Inorder traversal function

void inorderTraversal(struct TreeNode* root) {
if (root == NULL)
return;

inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}

DAA LAB
int main() {
// Create a binary tree
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Inorder Traversal: ");

inorderTraversal(root);

return 0;
}
Output:

Inorder Traversal: 4 2 5 1 3

DAA LAB
Aim: To implement DFS in python.
Program:
class Graph:
def __init__(self):
self.adjacency_list = {}

def add_edge(self, vertex, edge):

if vertex in self.adjacency_list:
self.adjacency_list[vertex].append(edge)
else:
self.adjacency_list[vertex] = [edge]

def dfs(self, start_vertex, visited=None):

if visited is None:
visited = set()
visited.add(start_vertex)
print("Visited vertex:", start_vertex)
if start_vertex in self.adjacency_list:
for neighbor in self.adjacency_list[start_vertex]:
if neighbor not in visited:
self.dfs(neighbor, visited)

# Create a graph
graph = Graph()

# Add edges
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)

# Perform DFS traversal

print("Depth-First Search Traversal:")
graph.dfs(0)

Output:
Depth-First Search Traversal:
Visited vertex: 0

DAA LAB
Visited vertex: 1
Visited vertex: 3
Visited vertex: 4
Visited vertex: 2
Visited vertex: 5

DAA LAB
Aim:To implement BFS In python
Program:
from collections import deque

class Graph:
def __init__(self):
self.adjacency_list = {}

def add_edge(self, vertex, edge):

if vertex in self.adjacency_list:
self.adjacency_list[vertex].append(edge)
else:
self.adjacency_list[vertex] = [edge]

def bfs(self, start_vertex):

visited = set()
queue = deque([start_vertex])
visited.add(start_vertex)

while queue:
vertex = queue.popleft()
print("Visited vertex:", vertex)

if vertex in self.adjacency_list:
for neighbor in self.adjacency_list[vertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)

# Create a graph
graph = Graph()

# Add edges
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)

DAA LAB
# Perform BFS traversal
print("Breadth-First Search Traversal:")
graph.bfs(0)

Output:
Breadth-First Search Traversal:
Visited vertex: 0
Visited vertex: 1
Visited vertex: 2
Visited vertex: 3
Visited vertex: 4
Visited vertex: 5

DAA LAB
Aim: To implement the Naive String Matching Algorithm using Java

Source Code:

public class NaiveSearch {

static void search(String pat, String txt)
{
int l1 = pat.length();
int l2 = txt.length();
int i = 0, j = l2 - 1;
for (i = 0, j = l2 - 1; j < l1;) {
if (txt.equals(pat.substring(i, j + 1))) {
System.out.println("Pattern found at index "+ i);
}
i++;
j++;
}
}
public static void main(String args[])
{
String pat = "AABAACAADAABAAABAA";
String txt = "AABA";
search(pat, txt);
}
}

Output:

Pattern found at index 0

Pattern found at index 9
Pattern found at index 13

DAA LAB
Aim: To implement the Rabin-Karp Algorithm using Java

Source Code:

public class Main {

public final static int d = 256;
static void search(String pat, String txt, int q)
{
int M = pat.length();
int N = txt.length();
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat.charAt(i)) % q;
t = (d * t + txt.charAt(i)) % q;
}
for (i = 0; i <= N - M; i++) {
if (p == t) {
for (j = 0; j < M; j++) {
if (txt.charAt(i + j) != pat.charAt(j))
break;
}
if (j == M)
System.out.println("Pattern found at index "+i);
}
if (i < N - M) {
t = (d * (t - txt.charAt(i) * h)+ txt.charAt(i + M))% q;
if (t < 0)
t = (t + q);
}
}
}
public static void main(String[] args)
{
String txt = "Old is Gold";
String pat = "old";

DAA LAB
 int q = 101;
search(pat, txt, q);
}
}

Output:

Pattern found at index 8

DAA LAB
Aim: To implement the Knuth Morris Pratt (KMP) Algorithm using Java

Source Code:

class KMP_String_Matching {
void KMPSearch(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
int lps[] = new int[M];
int j = 0;
computeLPSArray(pat, M, lps);
int i = 0;
while ((N - i) >= (M - j)) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
}
if (j == M) {
System.out.println("Found pattern "+"at index "+(i-j));
j = lps[j - 1];
}
else if (i < N&& pat.charAt(j) != txt.charAt(i)) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(String pat, int M, int lps[])
{
int len = 0;
int i = 1;
lps[0] = 0;
while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;

DAA LAB
 }
else
{
if (len != 0) {
len = lps[len - 1];
}
else
{
lps[i] = len;
i++;
}
}
}
}
public static void main(String args[])
{
String txt = "ABABDABACDABABCABAB";
String pat = "ABABCABAB";
new KMP_String_Matching().KMPSearch(pat, txt);
}
}

Output:

Found pattern at index 10

DAA LAB
Aim: To implement String Matching with Finite Automata using Java

Source Code:

class GFG {
static int NO_OF_CHARS = 256;
static int getNextState(char[] pat, int M, int state, int x)
{
if(state < M && x == pat[state])
return state + 1;
int ns, i;
for (ns = state; ns > 0; ns--)
{
if (pat[ns-1] == x)
{
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
static void computeTF(char[] pat, int M, int TF[][])
{
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}
static void search(char[] pat, char[] txt)
{
int M = pat.length;
int N = txt.length;
int[][] TF = new int[M+1][NO_OF_CHARS];
computeTF(pat, M, TF);
int i, state = 0;
for (i = 0; i < N; i++)
{

DAA LAB
 state = TF[state][txt[i]];
if (state == M)
System.out.println("Pattern found "+"at index "+ (i-M+1));
}
}
public static void main(String[] args)
{
char[] pat = "AABAACAADAABAAABAA".toCharArray();
char[] txt = "AABA".toCharArray();
search(txt,pat);
}
}

Output:

Pattern found at index 0

Pattern found at index 9
Pattern found at index 13

DAA LAB