Greedy Algorithms

Greedy Algorithms

A greedy algorithm is a type of algorithmic approach that follows the problem-solving heuristic of making the locally optimal choice at each step, with the hope that these local choices lead to a globally optimal solution. Essentially, a greedy algorithm makes decisions that are best at the moment, without worrying about the consequences of those decisions in the future.

Key Characteristics of Greedy Algorithms:

1. Local Optimization: In every step, the algorithm picks the option that seems to be the best based on the current situation. It chooses the best possible solution for that step without worrying about the impact on future steps.
2. No Backtracking: Once a decision is made, the algorithm doesn’t revisit it, unlike dynamic programming or backtracking algorithms.
3. Feasibility Check: Greedy algorithms usually require that each local decision be feasible and not violate any constraints of the problem.
4. Optimal Substructure: Greedy algorithms are applicable to problems that exhibit optimal substructure, meaning that an optimal solution to the entire problem can be constructed from optimal solutions to its subproblems.

However, greedy algorithms do not always guarantee an optimal solution for every problem. They are guaranteed to work for some problems, but for others, they may only produce an approximate or suboptimal solution.

Steps to Design a Greedy Algorithm:

1. Greedy Choice Property: Ensure that a locally optimal choice leads to a globally optimal solution. This means that you can build up an optimal solution by making a series of locally optimal choices.
2. Feasibility Check: Ensure that the solution remains feasible after each choice. The choices must not violate the constraints of the problem.
3. Irrevocability: Once a choice is made, it cannot be undone. This is why backtracking or revisiting earlier decisions is not part of greedy algorithms.
4. Optimal Substructure: Ensure that the problem can be solved by combining solutions to smaller subproblems, and each of those smaller subproblems can be solved using a greedy approach.

Examples of Greedy Algorithms:

1. Activity Selection Problem

Given a set of activities with their start and end times, you need to select the maximum number of non-overlapping activities. The greedy approach is to always select the activity that finishes first (i.e., the activity with the earliest finishing time), as this leaves the most room for subsequent activities.

Steps:

• Sort the activities by their finish time.
• Select the activity that finishes first.
• For each subsequent activity, select the first one that starts after the last selected activity ends.

Time Complexity:

• Sorting the activities takes O(n log n) time.
• The greedy choice process takes O(n) time.

C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Activity {
    int start;
    int finish;
};

bool compare(Activity a, Activity b) {
    return a.finish < b.finish; // Sort by finish time
}

void activitySelection(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare);
    int n = activities.size();
    
    // Select the first activity
    cout << "Selected activities: \n";
    cout << "Activity 1: Start = " << activities[0].start << ", Finish = " << activities[0].finish << endl;

    // The last selected activity's finish time
    int lastFinish = activities[0].finish;

    for (int i = 1; i < n; i++) {
        if (activities[i].start >= lastFinish) { // Activity can be selected
            cout << "Activity " << i + 1 << ": Start = " << activities[i].start << ", Finish = " << activities[i].finish << endl;
            lastFinish = activities[i].finish;
        }
    }
}

int main() {
    vector<Activity> activities = {{1, 3}, {2, 5}, {4, 7}, {6, 9}, {5, 8}, {8, 9}};
    activitySelection(activities);
    return 0;
}

2. Fractional Knapsack Problem

In the fractional knapsack problem, you are given a set of items, each with a weight and a value, and a knapsack with a fixed capacity. The goal is to maximize the total value of the items in the knapsack, but unlike the 0/1 knapsack problem, you are allowed to take fractional parts of items.

The greedy approach here is to select items based on their value per unit weight. The idea is to first pick the item with the highest value-to-weight ratio until the knapsack is full or all items have been considered.

Steps:

• Calculate the value-to-weight ratio for each item.
• Sort the items by this ratio in decreasing order.
• Take the item with the highest ratio and fill the knapsack until it reaches capacity. If there is remaining space, take a fraction of the next item.

Time Complexity:

• Sorting the items takes O(n log n) time.
• The greedy choice process takes O(n) time.

C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    int weight;
    int value;
    double valuePerWeight; // value per unit weight
};

// Function to compare two items based on value per unit weight
bool compare(Item a, Item b) {
    return a.valuePerWeight > b.valuePerWeight;
}

double fractionalKnapsack(int W, vector<Item>& items) {
    // Calculate value per weight for each item
    for (auto& item : items) {
        item.valuePerWeight = (double)item.value / item.weight;
    }

    // Sort items by value per weight in descending order
    sort(items.begin(), items.end(), compare);

    double totalValue = 0.0;
    for (auto& item : items) {
        if (W == 0) break;

        // Take as much of the item as possible
        if (item.weight <= W) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.valuePerWeight * W;
            W = 0;
        }
    }

    return totalValue;
}

int main() {
    int W = 50; // Knapsack capacity
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};

    cout << "Maximum value in Knapsack = " << fractionalKnapsack(W, items) << endl;

    return 0;
}

3. Huffman Coding (Data Compression)

Huffman coding is a greedy algorithm used for data compression. It assigns variable-length codes to input characters based on their frequencies. Characters that occur more frequently are assigned shorter codes, while characters with lower frequencies are assigned longer codes.

Steps:

1. Create a priority queue (min-heap) where each node represents a character and its frequency.
2. Combine the two nodes with the smallest frequencies into a new node.
3. Insert the new node back into the priority queue.
4. Repeat the process until only one node is left, which represents the optimal encoding tree.

Time Complexity:

• Building the min-heap takes O(n log n) time.
• Constructing the Huffman tree takes O(n) time.

C++ Code:

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

// A structure to represent a Huffman tree node
struct Node {
    char data;
    int freq;
    Node* left;
    Node* right;

    Node(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};

// Comparator function to compare two nodes (for min-heap)
struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

// Function to print the Huffman codes using the tree
void printHuffmanCodes(Node* root, string str) {
    if (!root) return;
    if (!root->left && !root->right) {
        cout << root->data << ": " << str << endl;
    }
    printHuffmanCodes(root->left, str + "0");
    printHuffmanCodes(root->right, str + "1");
}

// Main function to implement Huffman Coding
void huffmanCoding(string text) {
    // Calculate frequency of each character in the string
    unordered_map<char, int> freq;
    for (char c : text) {
        freq[c]++;
    }

    // Create a priority queue (min-heap) for Huffman tree
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // Create leaf nodes for each character and insert them into the priority queue
    for (auto& pair : freq) {
        pq.push(new Node(pair.first, pair.second));
    }

    // Build the Huffman tree
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();

        Node* newNode = new Node('$', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;
        pq.push(newNode);
    }

    // Print the Huffman codes for each character
    printHuffmanCodes(pq.top(), "");
}

int main() {
    string text = "this is an example for huffman encoding";
    huffmanCoding(text);
    return