DAA Practice Programs

Note some of these programs are self-written and not validated by a faculty member. Although these programs are correct and should work in practical exams, please use it at your own RISK!!!!!

-Shelton Coutinho

Index

1. Write a program to sort a list of N elements using Selection Sort Technique.
2. Write a program to perform Traveling Sales man Problem.
3. Write program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem.
4. Write program to implement the DFS and BFS algorithm for a graph.
5. Write a program to find minimum and maximum value in an array using divide and conquer.
6. Write a test program to implement Divide and Conquer Strategy. Eg: Quick sort algorithm for sorting list of integers in ascending order.
7. Write a program to implement Merge sort algorithm for sorting a list of integers in ascending order.
8. Write C program that accepts the vertices and edges for a graph and stores it as an adjacency matrix.
9. Implement function to print In-Degree,Out-Degree and to display that adjacency matrix.
10. Write a program to perform Knapsack Problem using Greedy Solution.
11. Write program to implement backtracking algorithm for solving problems like N queens.
12. Write a program to implement the backtracking algorithm for the sum of subsets problem.
13. Write program to implement greedy algorithm for job sequencing with deadlines.
14. Write program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.
15. Write a program that implements Prim’s algorithm to generate minimum cost spanning Tree.
16. Write a program that implements Kruskal’s algorithm to generate minimum cost spanning tree.

IMPORTANT!!! Add clrscr() (After intializing variables) and getch() (at the last part of the main()) to every program if you are using turbo C(legacy IDE).

Shelton Coutinho

Programs

1. Write a program to sort a list of N elements using Selection Sort Technique.

#include <stdio.h>

void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}
void selectionSort(int arr[], int n)
{
	int min_idx, i, j;
	for (i = 0; i < n-1; i++)
	{
		min_idx = i;
		for (j = i+1; j < n; j++)
		if (arr[j] < arr[min_idx])
			min_idx = j;
		if(min_idx != i)
			swap(&arr[min_idx], &arr[i]);
	}
}
void main()
{
	int arr[] = {64, 25, 12, 22, 11}, i;
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	printf("Sorted array: \n");
	for (i=0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

2. Write a program to perform Traveling Sales man Problem.

#include <stdio.h>

int visited_cities[10], limit, cost = 0;

int tsp(int matrix[4][4], int c)
{
    int count, nearest_city = 999;
    int min=999, temp;
    for(count = 0; count < limit; count++)
    {
        if((matrix[c][count] != 0) && (visited_cities[count] == 0))
        {
            if(matrix[c][count] < min)
            {
                min = matrix[count][0] + matrix[c][count];
                temp = matrix[c][count];
                nearest_city = count;
            }
        }
    }
    if(min != 999)
        cost += temp;
    return nearest_city;
}

void minimum_cost(int matrix[4][4], int city)
{
    int nearest_city;
    visited_cities[city] = 1;
    printf("%d -> ", city+1);
    nearest_city = tsp(matrix, city);
    if(nearest_city == 999)
    {
        nearest_city = 0;
        printf("%d", nearest_city + 1);
        cost += matrix[city][nearest_city];
        return;
    }
    minimum_cost(matrix, nearest_city);
}

int main()
{
    int i, j;
    int mat[4][4] = {
        {0, 4, 1, 3},
        {4, 0, 2, 1},
        {1, 2, 0, 5},
        {3, 1, 5, 0}
    };
    limit = 4;
    for(i=0; i<limit; i++)
        visited_cities[i] = 0;
    printf("Entered Cost Matrix\n");
    for(i = 0; i < limit; i++)
    {
        printf("\n");
        for(j = 0; j < limit; j++)
        {
            printf("%d\t", mat[i][j]);
        }
    }
    printf("\n\nPath: \t");
    minimum_cost(mat, 0);
    printf("\n\nMinimum Cost:\n");
    printf("%d\n", cost);
    return 0;
}

3. Write program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem.

#include<stdio.h>

int max(int a, int b) { return (a > b) ? a : b;}

int knapsack(int W, int wt[], int profit[], int n)
{
	int i, w, 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(profit[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 profit[] = {20, 25, 40};
	int wt[] = {25, 20, 30};
	int W = 50;
	int n = sizeof(profit)/sizeof(profit[0]);
	printf("The solution is : %d", knapsack(W, wt, profit, n));
	return 0;
}

5. Write a program to find minimum and maximum value in an array using divide and conquer.

#include<stdio.h>

int max, min;
int a[] = {8, 5, 6, 2, 9, 3, 10, 1};

void maxmin(int i, int j)
{
    int max1, min1, mid;
    if(i==j)
        max = min = a[i];
    else
    {
        if(i == j)
        {
            if(a[i] < a[j])
                max = a[j], min = a[i];
            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 n = sizeof(a)/sizeof(a[0]) - 1;
    max = min = a[0];
    maxmin(0, n);
    printf ("Minimum element in an array : %d\n", min);
    printf ("Maximum element in an array : %d\n", max);
    return 0;
}

6. Write a test program to implement Divide and Conquer Strategy. Eg: Quick sort algorithm for sorting list of integers in ascending order.

#include<stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quicksort(int a[], int first, int last)
{
    int i, j, pivot;
    if(first < last)
    {
        pivot = first;
        i = first;
        j = last;
        while(i < j)
        {
            while(a[i] <= a[pivot] && i < last)
                i++;
            while(a[j] > a[pivot])
                j--;
            if(i < j)
                swap(&a[i], &a[j]);
            swap(&a[pivot], &a[j]);
            quicksort(a, first, j-1);
            quicksort(a, j+1, last);
        }
    }
}

void main()
{
    int i, a[] = {3, 1, 5, 4, 2};
    int n = sizeof(a)/sizeof(a[0]);
    quicksort(a, 0, n-1);
    printf("The sorted order is: ");
    for(i = 0; i < n; i++)
        printf(" %d ", a[i]);
}

7. Write a program to implement Merge sort algorithm for sorting a list of integers in ascending order.

#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 arr[], int l, int r)
{
	if (l < r) {
		int m = (l + r) / 2;

		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);

		merge(arr, l, m, r);
	}
}

void printArray(int A[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
}

int main()
{
	int arr[] = { 12, 11, 13, 5, 6, 7 };
	int n = sizeof(arr) / sizeof(arr[0]);

	printf("Given array is \n");
	printArray(arr, n);

	mergeSort(arr, 0, n - 1);

	printf("\nSorted array is \n");
	printArray(arr, n);
	return 0;
}

8. Write C program that accepts the vertices and edges for a graph and stores it as an adjacency matrix.

#include<stdio.h>
#define v 5

void adjmatrix(int arr[v][v], int i, int j)
{arr[i-1][j-1] = 1;}

void main()
{
    int arr[v][v], i, j;
    for (i = 0; i<v; i++)
        for (j = 0; j<v; j++)
            arr[i][j] = 0;
    adjmatrix(arr, 1, 3);
    adjmatrix(arr, 3, 5);
    adjmatrix(arr, 2, 4);
    for (i = 0; i<v; i++)
    {
        for (j = 0; j<v; j++)
            printf("%d\t",arr[i][j]);
        printf("\n");
    }
}

9. Implement function to print In-Degree,Out-Degree and to display that adjacency matrix.

//Program credit to Michael.
#include <stdio.h>

#define MAX_VERTICES 10

void displayMatrix(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    int i, j;
    printf("Adjacency Matrix:\n");
    for (i = 0; i < vertices; i++) {
	for (j = 0; j < vertices; j++) {
	    printf("%d ", adjMatrix[i][j]);
	}
	printf("\n");
    }
}

void inOutDegree(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    int i, j;
    printf("\nVertex\tIn-Degree\tOut-Degree\n");
    for (i = 0; i < vertices; i++) {
	int inDegree = 0, outDegree = 0;
	for (j = 0; j < vertices; j++) {
	    inDegree += adjMatrix[j][i];
	    outDegree += adjMatrix[i][j];
	}
	printf("%d\t%d\t\t%d\n", i + 1, inDegree, outDegree);
    }
}

void main() {
    int vertices, i, j;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
    clrscr();
    printf("Enter the number of vertices (maximum %d): ", MAX_VERTICES);
    scanf("%d", &vertices);
    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < vertices; i++) {
	for (j = 0; j < vertices; j++) {
	    scanf("%d", &adjMatrix[i][j]);
	}
    }

    displayMatrix(adjMatrix, vertices);
    inOutDegree(adjMatrix, vertices);
    getch();
}

#include<stdio.h>
#define MAX 10

void accept_graph(int G[][MAX], int n)
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
        {
            printf("Edge (%d, %d) exists?: ", i+1, j+1);
            scanf("%d", &G[i][j]);
        }
}

void disp_adj_mat(int G[][MAX], int n)
{
    int i, j;
    printf("\nAdjacency matrix:\n");
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
            printf("%d", G[i][j]);
        printf("\n");
    }
}

void calc_out_deg(int G[][MAX], int n)
{
    int i, j, sum;
    for(i = 0; i < n; i++)
    {
        sum = 0;
        for(j = 0; j < n; j++)
            sum += G[i][j];
        printf("Out - deg(%d) : %d\n", i+1, sum);
    }
}

void calc_in_deg(int G[][MAX], int n)
{
    int i, j, sum;
    for(i = 0; i < n; i++)
    {
        sum = 0;
        for(j = 0; j < n; j++)
            sum+=G[j][i];
        printf("In - deg(%d) : %d\n", i+1, sum);
    }
}

void main()
{
    int G[MAX][MAX], n;
    printf("Enter the no. of vertices: \n");
    scanf("%d", &n);
    accept_graph(G, n);
    disp_adj_mat(G, n);
    printf("Out Degree: \n");
    calc_out_deg(G, n);
    printf("In Degree: \n");
    calc_in_deg(G, n);
}

10. Write a program to perform Knapsack Problem using Greedy Solution.(The 1st program is quite unstable only works on moder IDE’s (May work in your Turbo C check it once), for turbo C refer the 2nd Program)

//1st Program
#include<stdio.h>

void swap(int *a, int *b) {
    float temp = *a;
    *a = *b;
    *b = temp;
}

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);
}

void main() {
    float profit[20] = {10, 5, 15, 7, 6, 18, 3};
    float weight[20] = {2, 3, 5, 7, 1, 4, 1};
    float capacity = 15;
    float ratio[20];
    int num = 7, i, j;
    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]) {
                swap(&ratio[i], &ratio[j]);
                swap(&weight[i], &weight[j]);
                swap(&profit[i], &profit[j]);
            }
        }
    }
    knapsack(num, weight, profit, capacity);
}

//2nd Program
#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 profit[20] = {10, 5, 15, 7, 6, 18, 3};
    float weight[20] = {2, 3, 5, 7, 1, 4, 1};
    float capacity = 15;
    int num = sizeof(profit)/sizeof(profit[0]), i, j;
    float ratio[20], temp;
    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);
    return(0);
}

11. Write program to implement backtracking algorithm for solving problems like N queens.

#include<stdio.h>
#define N 4

void print_board(int board[N][N])
{
    int i, j;
    for(i = 0; i < N; i++)
    {
        for(j = 0; j < N; j++)
        {
            if(board[i][j])
                printf(" Q ");
            else
                printf(" . ");
        }
        printf("\n");
    }
}

int issafe(int board[N][N], int row, int col)
{
    int i, j;
    for(i = 0; i < col; i++)
        if(board[row][i])
            return 0;
    for(i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if(board[i][j])
            return 0;
    for(i = row, j = col; i < N && j >= 0; i++, j--)
        if(board[i][j])
            return 0;
    return 1;
}

int solve(int board[N][N], int col)
{
    int i;
    if(col >= N)
        return 1;
    for(i = 0; i < N; i++)
        if(issafe(board, i, col))
        {
            board[i][col] = 1;
            if(solve(board, col+1))
                return 1;
            board[i][col] = 0;
        }
    return 0;
}

int main()
{
    int board[N][N];
    int i, j;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            board[i][j] = 0;
    if(solve(board, 0) == 0)
    {
        printf("Soln doesnt exist");
        return 0;
    }
    print_board(board);
}

12. Write a program to implement the backtracking algorithm for the sum of subsets problem.

#include<stdio.h>
int count, w[10] = {5, 10, 12, 13, 15, 18}, x[10], m = 30;

void subset(int wsf, int k, int rmw)
{
    int i;
    x[k] = 1;
    if(wsf + w[k] == m)
    {
        printf("\nSolution %d = ", ++count);
        for(i = 0; i <=k; i++)
            if(x[i] == 1)
                printf("%d\t", w[i]);
        return;
    }
    if(wsf+w[k]+w[k+1] <= m)
        subset(wsf+w[k], k+1, rmw-w[k]);
    if(wsf+rmw+w[k] >= m && wsf+w[k+1] <= m)
    {
        x[k] = 0;
        subset(wsf, k+1, rmw-w[k]);
    }
}

void main()
{
    int sum = 0, i, n = 5;
    for(i = 0; i < n; i++)
        sum += w[i];
    if(sum < m)
        printf("No Soultion exists\n");
    else
    {
        printf("The Solutions are \n");
        count = 0;
        subset(0, 0, sum);
    }
}

13. Write program to implement greedy algorithm for job sequencing with deadlines.

//own code
#include<stdio.h>

void job(int pt[], int dead[], int maxdead, int n)
{
    int result[10], total = 0, i, j;
    for(i = 0; i < n; i++)
        result[i] = 0;
    for(i = 0; i < maxdead; i++)
    {
        if(result[dead[i]-1] == 0)
            result[dead[i]-1] = pt[i], total += pt[i];
        else
            for(j = dead[i]-1; j >= 0; j--)
                if(result[j] == 0)
                    result[j] = pt[i], total += pt[i];
    }
    printf("Total profit = %d\n", total);
    for(i = 0; i < maxdead; i++)
        printf("%d at index %d\n", result[i], i+1);
}

void main()
{
    int pt[] = {25, 20, 17, 16, 10};
    int dead[] = {4, 2, 4, 1, 3};
    int maxdead = 4;
    int n = sizeof(pt)/sizeof(pt[0]);
    job(pt, dead, maxdead, n);
}

14. Write program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.

#include<stdio.h>
#include<limits.h>

int sum(int freq[], int i, int j)
{
    int s = 0, k;
    for(k = i; k <= j; k++)
        s += freq[k];
    return s;
}

int optcost(int freq[], int i, int j)
{
    int fsum, min, r, cost;
    if(j < i)
        return 0;
    if(j == i)
        return freq[i];
    fsum = sum(freq, i, j);
    min = INT_MAX;
    for(r = i; r <= j; ++r)
    {
        cost = optcost(freq, i, r-1) + optcost(freq, r+1, j);
        if(cost < min)
            min = cost;
    }
    return min+fsum;
}

void main()
{
    int keys[] = {10, 12, 20};
    int freq[] = {34, 8, 50};
    int n = sizeof(keys)/sizeof(keys[0]);
    printf("Cost of optimal bst is %d", optcost(freq, 0, n-1));
}

15. Write a program that implements Prim’s algorithm to generate minimum cost spanning Tree.

#include<stdio.h>
#include<limits.h>
#define V 5

int min_key(int mst[V], int k[V])
{
    int minimum = INT_MAX, min, i;
    for(i = 0; i < V; i++)
        if(mst[i] == 0 && k[i] < minimum)
            minimum = k[i], min = i;
    return min;
}

void prim(int g[V][V])
{
    int mst[V], k[V], parent[V], edge, i, j;
    for(i = 0; i < V; i++)
        k[i] = INT_MAX, mst[i] = 0;
    k[0] = 0, parent[0] = -1;
    for(i = 0; i < V-1; i++)
    {
        edge = min_key(mst, k);
        mst[edge] = 1;
        for(j = 0; j < V; j++)
            if(g[edge][j] && mst[j] == 0 && g[edge][j] < k[j])
                parent[j] = edge, k[j] = g[edge][j];
    }
    printf("Edges\tWeights");
    for(i = 1; i < V; i++)
        printf("\n%d<->%d\t%d", parent[i], i, g[i][parent[i]]);
}

void main()
{
    int g[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };
    prim(g);
}

16. Write a program that implements Kruskal’s algorithm to generate minimum cost spanning tree.

#include<stdio.h>
#define V 5

int find(int i, int parent[V])
{
    while(parent[i])
        i = parent[i];
    return i;
}

int uni(int i, int j, int parent[V])
{
    if(i != j)
    {
        parent[j] = i;
        return 1;
    }
    return 0;
}

void main()
{
    int ne = 0, parent[V], min, a, b, u, v, i, j;
    int g[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };
    for(i = 0; i < V; i++)
        parent[i] = 0;
    for(i = 0; i < V; i++)
        for(j = 0; j < V; j++)
            if(g[i][j] == 0)
                g[i][j] = 999;
    while(ne < V-1)
    {
        for(i = 0, min = 999; i < V; i++)
        {
            for(j = 0; j < V; j++)
            {
                if(g[i][j] < min)
                {
                    min = g[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        u = find(u, parent);
        v = find(v, parent);
        if(uni(u, v, parent))
            printf("%d edge (%d, %d) = %d\n", ne++, a, b, min);
        g[a][b] = g[b][a] = 999;
    }
}