C Greedy Algorithms 🚀

Welcome to our deep dive into Greedy Algorithms in C Programming! 🎯

Greedy algorithms are a type of algorithm that makes the locally optimal choice at each stage with the hope of finding a global optimum. In this lesson, we'll learn the basics, understand real-world applications, and dive into two practical examples. Let's get started!

What are Greedy Algorithms? 📝

Greedy algorithms work by making the locally optimal choice at each stage with the hope that such local decisions will lead to a global optimum. They are called "greedy" because at each step, they select the choice that seems best at the moment without considering future steps.

Key Points

Focus on making the best choice at the current step, without looking ahead
Not always guaranteed to find the optimal solution, but often provide near-optimal solutions quickly

Why use Greedy Algorithms? 💡

Fast solution for NP-hard problems
Easy to understand and implement
Good for problems where locally optimal solutions are also globally optimal

Coding Greedy Algorithms ✅

Now that we understand the concept, let's dive into coding two popular greedy algorithm examples in C: Huffman Coding and Activity Selection.

Huffman Coding 📝

Huffman Coding is a lossless data compression algorithm used for encoding characters based on their frequency.

Example: Compress the string "HELLO WORLD"

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

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

Node* createNode(char ch, int freq) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->ch = ch;
    newNode->freq = freq;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void insert(Node **root, Node *node) {
    if (*root == NULL) {
        *root = node;
    } else {
        if (node->freq < (*root)->freq) {
            if ((*root)->left == NULL)
                (*root)->left = node;
            else
                insert(&(*root)->left, node);
        } else {
            if ((*root)->right == NULL)
                (*root)->right = node;
            else
                insert(&(*root)->right, node);
        }
    }
}

void printCodes(Node *root, char code[], int n) {
    if (root == NULL)
        return;

    if (root->left == NULL && root->right == NULL && root->freq > 0) {
        printf("%c: %s\n", root->ch, code);
        root->freq--;
    }

    printCodes(root->left, code, n + 1);
    printCodes(root->right, code, n + 1);
}

void huffmanCodes(char data[]) {
    int n = strlen(data);
    Node **heap, i;
    for (i = 0; i <= n; i++) {
        heap = (Node**)realloc(heap, ++i * sizeof(Node*));
        heap[i] = createNode(data[i - 1], 1);
    }

    for (i = 1; i < n; i++) {
        insert(heap, heap[i], heap[i + 1]);
    }

    while (n > 1) {
        insert(heap, createNode('/', heap[n]->freq), heap[n--]);
    }

    printCodes(heap[1], "", 0);
}

int main() {
    char data[] = "HELLO WORLD";
    huffmanCodes(data);
    return 0;
}

📝 Note: The code above computes Huffman Codes for the given string "HELLO WORLD".

Activity Selection 📝

Activity Selection is a problem where we have a set of activities, each with a start and end time, and we want to select the maximum number of activities without overlapping.

Example: Given activities:

| Start Time | End Time | |------------|----------| | 1 | 3 | | 2 | 4 | | 3 | 5 | | 4 | 6 | | 7 | 9 | | 8 | 10 | | 1 | 2 |

The optimal solution would be to choose activities 1-4, 7, and 8.

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

typedef struct Activity {
    int start;
    int end;
    int index;
} Activity;

int compare(const void *a, const void *b) {
    return (*(Activity*)a).end - (*(Activity*)b).end;
}

void printActivities(Activity activities[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("Activity %d: %d - %d\n", activities[i].index, activities[i].start, activities[i].end);
}

void selection(Activity activities[], int n) {
    qsort(activities, n, sizeof(Activity), compare);

    int selected[n], count = 0;

    for (int i = 0, j = 0; i < n;) {
        if (selected[j] == -1 || activities[i].start >= selected[j][1]) {
            selected[++j] = i;
            selected[j][0] = i;
            selected[j][1] = activities[i].end;
            count++;
            i++;
        } else
            i++;
    }

    printf("Selected Activities:\n");
    printActivities(selected, j);
}

int main() {
    Activity activities[] = {
        {1, 3, 0}, {2, 4, 1}, {3, 5, 2}, {4, 6, 3},
        {7, 9, 4}, {8, 10, 5}, {1, 2, -1}
    };

    int n = sizeof(activities) / sizeof(Activity);
    selection(activities, n);

    return 0;
}

📝 Note: The code above selects the maximum number of activities without overlapping, given the activities in the example table.

Quiz 🎯

Enjoy learning and practicing C Greedy Algorithms! If you have any questions or need further explanations, don't hesitate to ask 😊. Happy coding!