DAAC

Implementation of Merge Sort using C

#include <stdio.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) {
// Same as (l+r)/2, but avoids overflow for large l and r
int m = l + (r - l) / 2;

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

    // Merge the sorted halves
    merge(arr, l, m, r);
}

}

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

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

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

mergeSort(arr, 0, arr_size - 1);

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

}

Implement Quick Sort Using C
#include <stdio.h>

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

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
        i++;
        swap(&arr[i], &arr[j]);
    }
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);

}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

}

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

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: \n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Implementation of Bubble, Insertion and selection sort algoritms.

#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 insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
    arr[j + 1] = key;
}

}

void selectionSort(int arr[], int n) {
int i, j, min_idx;

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;


    int temp = arr[min_idx];
    arr[min_idx] = arr[i];
    arr[i] = temp;
}

}

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

int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
printf("Unsorted array for Bubble Sort: \n");
printArray(arr1, n1);
bubbleSort(arr1, n1);
printf("Sorted array using Bubble Sort: \n");
printArray(arr1, n1);

int arr2[] = {12, 11, 13, 5, 6};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
printf("\nUnsorted array for Insertion Sort: \n");
printArray(arr2, n2);
insertionSort(arr2, n2);
printf("Sorted array using Insertion Sort: \n");
printArray(arr2, n2);

int arr3[] = {64, 25, 12, 22, 11};
int n3 = sizeof(arr3) / sizeof(arr3[0]);
printf("\nUnsorted array for Selection Sort: \n");
printArray(arr3, n3);
selectionSort(arr3, n3);
printf("Sorted array using Selection Sort: \n");
printArray(arr3, n3);

return 0;

}

Implement 0/1 knapsack using dynamic programming
#include <stdio.h>

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

// Function to solve the 0/1 knapsack problem
int knapsack(int capacity, int weights[], int values[], int n) {
int dp[n + 1][capacity + 1];

// Initialize dp table
for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= capacity; w++) {
        if (i == 0 || w == 0)
            dp[i][w] = 0;
        else if (weights[i - 1] <= w)
            dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
        else
            dp[i][w] = dp[i - 1][w];
    }
}

return dp[n][capacity];

}

int main() {
int weights[] = {2, 3, 4, 5};
int values[] = {3, 4, 5, 6};
int capacity = 5;
int n = sizeof(values) / sizeof(values[0]);

int max_value = knapsack(capacity, weights, values, n);
printf("Maximum value: %d\n", max_value);

return 0;

}

Implement bellman ford algorithm to find shortest path using dynamic programming approach

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

struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}
void printDistances(int dist[], int V) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void bellmanFord(struct Graph* graph, int src) {
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;

for (int i = 1; i <= V - 1; i++) {
    for (int j = 0; j < E; j++) {
        int u = graph->edge[j].src;
        int v = graph->edge[j].dest;
        int weight = graph->edge[j].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
            dist[v] = dist[u] + weight;
    }
}


for (int i = 0; i < E; i++) {
    int u = graph->edge[i].src;
    int v = graph->edge[i].dest;
    int weight = graph->edge[i].weight;
    if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
        printf("Graph contains negative weight cycle\n");
        return;
    }
}

printDistances(dist, V);

}

int main() {
int V = 5; // Number of vertices
int E = 8; // Number of edges
struct Graph* graph = createGraph(V, E);

// Add the edges of the graph
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;

graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;

graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;

graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;

graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;

graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;

graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;

bellmanFord(graph, 0);

return 0;

}

Implement prims algorithm to find mst in c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define V 5

int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}

void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V]) {
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}

int main() {
int graph[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}
};
primMST(graph);
return 0;
}