Design and Analysis of Algorithms

#include <stdio.h>
#include <string.h>
 
int main() {
    int arr[10], i, j;
 
    printf("Enter 10 numbers for the array:\n");
    for (j = 0; j < 10; j++) {
        scanf("%d", &arr[j]);
    }
 
    printf("Enter the number you want to search for in the array: ");
    scanf("%d", &i);
 
    int found = 0; // To check if the number was found
    for (j = 0; j < 10; j++) {
        if (arr[j] == i) {
            printf("Number %d found at position: %d\n", arr[j], j + 1);
            found = 1; // Mark as found
        }
    }
 
    if (!found) {
        printf("Number %d not found in the array.\n", i);
    }
 
    return 0;
}

#include <stdio.h>
#include <string.h>
 
int binsearch(int ar[], int j, int left, int right) {
    if (left <= right) {
        int mid = (left + right) / 2;
        
        if (ar[mid] == j) {
            return mid; // Element found
        }
        if (ar[mid] > j) {
            return binsearch(ar, j, left, mid - 1); // Search in the left half
        }
        return binsearch(ar, j, mid + 1, right); // Search in the right half
    }
    return -1; // Element not found
}
 
int main() {
    int ar[10], i, j, search;
 
    printf("Enter 10 sorted elements in the array:\n");
    for (i = 0; i < 10; i++) {
        scanf("%d", &ar[i]);
    }
 
    printf("Entered elements in the array: ");
    for (i = 0; i < 10; i++) {
        printf("%d ", ar[i]);
    }
    printf("\n");
 
    printf("Enter the element you want to find in the array: ");
    scanf("%d", &j);
 
    search = binsearch(ar, j, 0, 9);
    if (search == -1) {
        printf("Element not found.\n");
    } else {
        printf("Element found at position: %d\n", search + 1);
    }
 
    return 0;
}

#include <stdio.h>
 
int main() {
    int array[100], n, c, d, swap;
 
    printf("Enter number of elements: ");
    scanf("%d", &n);
 
    printf("Enter %d integers:\n", n);
    for (c = 0; c < n; c++) {
        scanf("%d", &array[c]);
    }
 
    // Bubble Sort
    for (c = 0; c < n - 1; c++) {
        for (d = 0; d < n - c - 1; d++) {
            if (array[d] > array[d + 1]) { // For decreasing order, use '<' instead of '>'
                swap = array[d];
                array[d] = array[d + 1];
                array[d + 1] = swap;
            }
        }
    }
 
    printf("Sorted list in ascending order:\n");
    for (c = 0; c < n; c++) {
        printf("%d\n", array[c]);
    }
 
    return 0;
}

#include <stdio.h>
 
int main() {
    int a[10], i, j, temp, num;
 
    printf("Enter the number of elements (max 10): ");
    scanf("%d", &num);
 
    if (num > 10) {
        printf("Please enter a number less than or equal to 10.\n");
        return 1;
    }
 
    for (i = 0; i < num; i++) {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
 
    // Selection Sort
    for (i = 0; i < num - 1; i++) {
        for (j = i + 1; j < num; j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
 
    printf("Sorted array:\n");
    for (i = 0; i < num; i++) {
        printf("a[%d] = %d\n", i, a[i]);
    }
 
    return 0;
}

#include <stdio.h>
 
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low;
    int j = high;
 
    while (i < j) {
        while (arr[i] <= pivot && i <= high - 1) {
            i++;
        }
        while (arr[j] > pivot && j >= low + 1) {
            j--;
        }
        if (i < j) {
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[low], &arr[j]);
    return j;
}
 
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}
 
// Driver code
int main() {
    int arr[] = { 19, 17, 15, 12, 16, 18, 4, 11, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
 
    quickSort(arr, 0, n - 1);
 
    printf("\nSorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n"); // Added for better output formatting
 
    return 0;
}

#include <stdio.h>
 
int main() {
    int i, fact = 1, number;
 
    printf("Enter a number: ");
    scanf("%d", &number);
 
    for (i = 1; i <= number; i++) {
        fact = fact * i;
    }
 
    printf("Factorial of %d is: %d\n", number, fact);
    return 0;
}

#include <stdio.h>
 
long int multiplyNumbers(int n);
 
int main() {
    int n;
    printf("Enter a positive integer: ");
    scanf("%d", &n);
 
    if (n < 0) {
        printf("Factorial is not defined for negative numbers.\n");
    } else {
        printf("Factorial of %d = %ld\n", n, multiplyNumbers(n));
    }
    
    return 0;
}
 
long int multiplyNumbers(int n) {
    if (n >= 1) {
        return n * multiplyNumbers(n - 1);
    } else {
        return 1; // Base case: factorial of 0 is 1
    }
}

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
#define INF 9999999
#define V 5
 
int G[V][V] = {
    {0, 9, 75, 0, 0},
    {9, 0, 95, 19, 42},
    {75, 95, 0, 51, 66},
    {0, 19, 51, 0, 31},
    {0, 42, 66, 31, 0}
};
 
int main() {
    int no_edge = 0;
    bool selected[V];
    memset(selected, false, sizeof(selected));
    selected[0] = true; // Start with the first vertex
 
    printf("Edge : Weight\n");
    while (no_edge < V - 1) {
        int min = INF;
        int x = 0;
        int y = 0;
 
        for (int i = 0; i < V; i++) {
            if (selected[i]) {
                for (int j = 0; j < V; j++) {
                    if (!selected[j] && G[i][j]) {
                        if (min > G[i][j]) {
                            min = G[i][j];
                            x = i;
                            y = j;
                        }
                    }
                }
            }
        }
 
        printf("%d - %d : %d\n", x, y, G[x][y]);
        selected[y] = true;
        no_edge++;
    }
 
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
 
// Comparator function to use in sorting
int comparator(const void* p1, const void* p2) {
    const int(*x)[3] = p1;
    const int(*y)[3] = p2;
    return (*x)[2] - (*y)[2]; // Compare the weights (third element)
}
 
void makeSet(int parent[], int rank[], int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i; // Each node is its own parent
        rank[i] = 0;   // Initialize rank to 0
    }
}
 
int findParent(int parent[], int component) {
    if (parent[component] == component) {
        return component; // Node is its own parent
    }
    return parent[component] = findParent(parent, parent[component]); // Path compression
}
 
void unionSet(int u, int v, int parent[], int rank[]) {
    // 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; // Attach v to u
        rank[u]++;      // Increase rank if the ranks were the same
    }
}
 
void kruskalAlgo(int n, int edge[n][3]) {
    // Sort the edge array in ascending order by weight
    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 the parents are different, union them
        if (v1 != v2) {
            unionSet(v1, v2, parent, rank);
            minCost += wt;
            printf("%d -- %d == %d\n", edge[i][0], edge[i][1], wt);
        }
    }
    
    printf("Minimum Cost Spanning Tree: %d\n", minCost);
}
 
// Driver code
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;
}

#include <stdio.h>
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
int knapSack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n + 1][W + 1]; // Create a 2D array for storing the maximum value
 
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                K[i][w] = 0; // Base case: no items or no capacity
            } else if (wt[i - 1] <= w) {
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            } else {
                K[i][w] = K[i - 1][w];
            }
        }
    }
    
    return K[n][W]; // Return the maximum value
}
 
int main() {
    int i, n, val[20], wt[20], W;
 
    printf("Enter number of items: ");
    scanf("%d", &n);
    
    printf("Enter value and weight of items:\n");
    for (i = 0; i < n; ++i) {
        scanf("%d%d", &val[i], &wt[i]);
    }
    
    printf("Enter size of knapsack: ");
    scanf("%d", &W);
 
    printf("Maximum value in Knapsack = %d\n", knapSack(W, wt, val, n));
    
    return 0;
}

#include <stdio.h>
#include <limits.h>
 
int MatrixChainMultiplication(int p[], int n) {
    int m[n][n];
    int i, j, k, L, q;
 
    // Initialize the diagonal of the matrix to 0
    for (i = 1; i < n; i++) {
        m[i][i] = 0;
    }
 
    // L is the chain length
    for (L = 2; L < n; L++) {
        for (i = 1; i < n - L + 1; i++) {
            j = i + L - 1;
            m[i][j] = INT_MAX; // Initialize to a large value
            for (k = i; k <= j - 1; k++) {
                // Calculate cost of multiplying
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q; // Update minimum cost
                }
            }
        }
    }
    return m[1][n - 1]; // Return the minimum cost
}
 
int main() {
    int n, i;
    printf("Enter number of matrices: ");
    scanf("%d", &n);
    
    n++; // Increment to account for the number of dimensions
    int arr[n];
    
    printf("Enter dimensions:\n");
    for (i = 0; i < n; i++) {
        printf("Enter d%d: ", i);
        scanf("%d", &arr[i]);
    }
 
    printf("Minimum number of multiplications is: %d\n", MatrixChainMultiplication(arr, n));
    
    return 0;
}

#include <stdio.h>
 
int count(int S[], int m, int n) {
    // Base case: If n is 0, there is one solution (do not include any coin)
    if (n == 0)
        return 1;
 
    // If n is less than 0, no solution exists
    if (n < 0)
        return 0;
 
    // If there are no coins left and n is greater than 0, no solution exists
    if (m <= 0 && n >= 1)
        return 0;
 
    // Count the solutions including the last coin and excluding the last coin
    return count(S, m - 1, n) + count(S, m, n - S[m - 1]);
}
 
int main() {
    int arr[] = {2, 5, 8}; // Denominations
    int m = sizeof(arr) / sizeof(arr[0]); // Number of denominations
 
    printf("%d\n", count(arr, m, 10)); // Count ways to make change for 10
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
// Structure for a node in the adjacency list
struct Node {
    int data;
    struct Node* next;
};
 
// Structure for the adjacency list
struct List {
    struct Node* head;
};
 
// Structure for the graph
struct Graph {
    int vertices;
    struct List* array;
};
 
// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->array = (struct List*)malloc(vertices * sizeof(struct List));
    for (int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}
 
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
 
    // Uncomment the following code to make the graph undirected
    /*
    newNode = createNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
    */
}
 
// Function to perform Depth First Search (DFS) from a given vertex
void DFS(struct Graph* graph, int vertex, bool visited[]) {
    visited[vertex] = true;
    printf("%d ", vertex);
    
    struct Node* currentNode = graph->array[vertex].head;
    while (currentNode) {
        int adjacentVertex = currentNode->data;
        if (!visited[adjacentVertex]) {
            DFS(graph, adjacentVertex, visited);
        }
        currentNode = currentNode->next;
    }
}
 
// Function to perform DFS traversal from a given vertex in a specified order
void DFSTraversal(struct Graph* graph, int* order, int orderSize) {
    bool* visited = (bool*)malloc(graph->vertices * sizeof(bool));
    for (int i = 0; i < graph->vertices; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < orderSize; i++) {
        if (!visited[order[i]]) {
            DFS(graph, order[i], visited);
        }
    }
    free(visited);
}
 
// Driver code
int main() {
    int vertices = 4;
    struct Graph* graph = createGraph(vertices);
    
    // Add edges to the graph
    addEdge(graph, 2, 0);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 0, 1);
    addEdge(graph, 3, 3);
    addEdge(graph, 1, 3);
    
    int order[] = {2, 0, 1, 3};
    int orderSize = sizeof(order) / sizeof(order[0]);
    
    printf("Following is Depth First Traversal (starting from vertex 2):\n");
    DFSTraversal(graph, order, orderSize);
    
    // Free memory (not shown here)
    // Ideally, you should free the graph structure and its nodes to avoid memory leaks
 
    return 0;
}

#include <stdio.h>
 
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;
 
// Function to perform BFS
void bfs(int v) {
    for (i = 1; i <= n; i++) {
        if (a[v][i] && !visited[i]) {
            q[++r] = i; // Add to queue
        }
    }
    if (f <= r) {
        visited[q[f]] = 1; // Mark as visited
        bfs(q[f++]); // Recursive call for the next vertex
    }
}
 
int main() {
    int v;
    printf("\nEnter the number of vertices: ");
    scanf("%d", &n);
 
    // Initialize queue and visited arrays
    for (i = 1; i <= n; i++) {
        q[i] = 0;
        visited[i] = 0;
    }
 
    printf("\nEnter graph data in matrix form:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]); // Input adjacency matrix
        }
    }
 
    printf("\nEnter the starting vertex: ");
    scanf("%d", &v);
    
    // Start BFS from the specified vertex
    bfs(v);
 
    printf("\nThe nodes which are reachable are:\n");
    for (i = 1; i <= n; i++) {
        if (visited[i]) {
            printf("%d\t", i);
        } else {
            printf("\nBFS is not possible. Not all nodes are reachable.");
            break; // Exit loop if not all nodes are reachable
        }
    }
 
    return 0;
}

#include <stdio.h>
#include <string.h>
 
int i, j, m, n, LCS_table[20][20];
char S1[20] = "ACADB", S2[20] = "CBDA", lcsStr[20];
 
void lcsAlgo() {
    m = strlen(S1);
    n = strlen(S2);
 
    // Filling 0's in the LCS table
    for (i = 0; i <= m; i++)
        LCS_table[i][0] = 0;
    for (j = 0; j <= n; j++)
        LCS_table[0][j] = 0;
 
    // Building the table in bottom-up way
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (S1[i - 1] == S2[j - 1]) {
                LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;
            } else if (LCS_table[i - 1][j] >= LCS_table[i][j - 1]) {
                LCS_table[i][j] = LCS_table[i - 1][j];
            } else {
                LCS_table[i][j] = LCS_table[i][j - 1];
            }
        }
    }
 
    // Constructing the LCS string
    int index = LCS_table[m][n];
    lcsStr[index] = '\0'; // Null-terminate the LCS string
    i = m;
    j = n;
 
    while (i > 0 && j > 0) {
        if (S1[i - 1] == S2[j - 1]) {
            lcsStr[index - 1] = S1[i - 1];
            i--;
            j--;
            index--;
        } else if (LCS_table[i - 1][j] > LCS_table[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
 
    // Printing the subsequences
    printf("S1: %s\nS2: %s\n", S1, S2);
    printf("LCS: %s\n", lcsStr);
}
 
int main() {
    lcsAlgo();
    return 0;
}