Untitled

//Huffman Coding - 

#include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

Node* createHuffmanTree(string text) {
    map<char, int> freq;
    for (char ch : text) {
        freq[ch]++;
    }

    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto& it : freq) {
        pq.push(new Node{it.first, it.second, nullptr, nullptr});
    }

    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node{'\0', left->freq + right->freq, left, right};
        pq.push(parent);
    }

    return pq.top();
}

void generateCodes(Node* root, string code, map<char, string>& codes) {
    if (root == nullptr) {
        return;
    }

    if (root->ch != '\0') {
        codes[root->ch] = code;
    }

    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

int calculateTotalBits(string text, map<char, string>& codes) {
    int totalBits = 0;
    for (char ch : text) {
        totalBits += codes[ch].size();
    }
    return totalBits;
}

int main() {
    string text;
    cout << "Enter the text: ";
    getline(cin, text);

    Node* root = createHuffmanTree(text);
    map<char, string> codes;
    generateCodes(root, "", codes);

    int totalBits = calculateTotalBits(text, codes);
    cout << "Total bits using Huffman coding is " << totalBits << endl;

    return 0;
}

----------------------------------------------------------------------------------------------------------------------

// Insertion Sort

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

void insertionSort(int arr[], int size){
    int key;
    for(int i =0; i < size; i++){
        key = arr[i];
        int j = i-1;
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}

int main(){
    int s;
    scanf("%d", &s);
    int *arr = (int *)malloc(s * sizeof(int));
    
    for(int i = 0; i < s; i++){
        scanf("%d", &arr[i]);
    }
    insertionSort(arr, s);
    
    for(int i = 0; i < s-1; i++){
        printf("%d ", arr[i]);
    }
    printf("%d", arr[s-1]);
}

----------------------------------------------------------------------------------------------------------------------

//Longest Common Sequence  - 

#include <stdio.h>
#include <string.h>

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

int longest_common_subsequence(char *text1, char *text2) {
    int m = strlen(text1);
    int n = strlen(text2);

    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    char text1[5];
    scanf("%s", text1);
    
    char text2[5];
    scanf("%s", text2);

    int lcs = longest_common_subsequence(text1, text2);
    printf("%d", lcs);

    return 0;
}

----------------------------------------------------------------------------------------------------------------------
//Matrix Chain Multiplication - 

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



int min_multiplications(int arr[], int n) {
    int dp[n + 1][n + 1];
    int i, j, k, l;

    for (i = 1; i <= n; ++i) {
        dp[i][i] = 0;
    }

    for (l = 2; l <= n; ++l) {
        for (i = 1; i <= n - l + 1; ++i) {
            j = i + l - 1;
            dp[i][j] = INT_MAX;

            for (k = i; k < j; ++k) {
                int temp = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j];
                dp[i][j] = (dp[i][j] > temp) ? temp : dp[i][j];
            }
        }
    }

    return dp[1][n];
}

int main() {
    int s;
    scanf("%d", &s);
    
    int arr2[s];
    for(int i = 0; i < s; i++){
        scanf("%d", &arr2[i]);
    }
    
    int n2 = sizeof(arr2) / sizeof(arr2[0]) - 1;
    
    printf("%d\n", min_multiplications(arr2, n2));

    return 0;
}

----------------------------------------------------------------------------------------------------------------------
Sum of Subarray - 

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

int max_subarray_sum(int nums[], int n, int *start_index, int *end_index) {
    int max_sum = INT_MIN;
    int current_sum = 0;
    int current_start = 0;

    for (int i = 0; i < n; ++i) {
        current_sum += nums[i];

        if (current_sum > max_sum) {
            max_sum = current_sum;
            *start_index = current_start;
            *end_index = i;
        }

        if (current_sum < 0) {
            current_sum = 0;
            current_start = i + 1;
        }
    }

    if (max_sum == INT_MIN) {
        max_sum = nums[0];
        *start_index = 0;
        *end_index = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > max_sum) {
                max_sum = nums[i];
                *start_index = i;
                *end_index = i;
            }
        }
    }

    return max_sum;
}

int main() {
    int s;
    scanf("%d", &s);

    int *arr = (int *)malloc(s * sizeof(int));

    for (int i = 0; i < s; ++i) {
        scanf("%d", &arr[i]);
    }

    int start_index, end_index;
    int max_sum = max_subarray_sum(arr, s, &start_index, &end_index);
    
    printf("[");
    for (int i = start_index; i <= end_index - 1 ; ++i) {
        printf("%d, ", arr[i]);
    }
    printf("%d", arr[end_index]);
    printf("]");

    free(arr);
    return 0;
}
----------------------------------------------------------------------------------------------------------------------

//Knapsack

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

struct Item {
    int weight;
    int profit;
};

int compare(const void* a, const void* b) {
    const struct Item* item1 = (const struct Item*)a;
    const struct Item* item2 = (const struct Item*)b;
    return (double)(item2->profit / item2->weight) - (double)(item1->profit / item1->weight);
}

int knapsack(struct Item items[], int n, int capacity) {
    qsort(items, n, sizeof(struct Item), compare); // Sort items by profit/weight ratio

    int currentWeight = 0;
    int maxProfit = 0;

    for (int i = 0; i < n; i++) {
        if (currentWeight + items[i].weight <= capacity) {
            currentWeight += items[i].weight;
            maxProfit += items[i].profit;
        } else {
            // Calculate fraction of item to be included
            int fraction = (capacity - currentWeight) / items[i].weight;
            maxProfit += fraction * items[i].profit;
            break;
        }
    }

    return maxProfit;
}

int main() {
    int n;
    int capacity;

    scanf("%d", &n);
    scanf("%d", &capacity);

    struct Item items[n];

    printf("Enter the weights and profits of the items:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].weight, &items[i].profit);
    }

    int maxProfit = knapsack(items, n, capacity);

    printf("Total Weight is: %d\n", maxProfit);
    printf("Maximum Profit is: %d\n", maxProfit);

    return 0;
}


KMP

#include <iostream>
#include <vector>
using namespace std;

vector<string> naiveStringMatching(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<string> matches;

    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }

        if (j == m) {
            matches.push_back(pattern);
        }
    }

    return matches;
}

int main() {
    string text, pattern;

    cout << "";
    getline(cin, text);

    cout << "";
    getline(cin, pattern);

    vector<string> result = naiveStringMatching(text, pattern);

    if (result.empty()) {
        cout << "None" << endl;
    } else {
        cout << result[0] << endl;
    }

    return 0;
}