Unit - 3

TITLE

Greedy Algorithms

1. Introduction

1.1 Overview

• A greedy algorithm always makes the choice that seems to be the best at that moment.
• It never reconsiders this decision once it has been made.
• Example: Getting the best possible dress from a shop for yourself.

2. Characteristics of Greedy Algorithms

2.1 Key Features

1. The greedy approach forms a set or list of candidates $C$.
2. Once a candidate is selected in the solution, it is there forever. Once a candidate is excluded from the solution, it is never reconsidered.
3. To construct the solution in an optimal way, the Greedy Algorithm maintains two sets:
   • One set contains candidates that have already been considered and chosen.
   • The other set contains candidates that have been considered but rejected.

3. Elements of Greedy Strategy

3.1 Four Functions

1. Solution Function: Checks whether a chosen set of items provides a solution.
2. Feasible Function: Checks the feasibility of a set.
3. Selection Function: Tells which of the candidates is the most promising.
4. Objective Function: Gives the value of a solution (doesn't always appear explicitly).

4. Minimum Spanning Tree (MST)

4.1 Concept

• Let $G = \langle N, A \rangle$ be a connected, undirected graph where:
  • $N$ is the set of nodes.
  • $A$ is the set of edges.
• Each edge has a given positive length or weight.
• A spanning tree of a graph $G$ is a sub-graph which is a tree and contains all the vertices of $G$ but does not contain cycles.
• A minimum spanning tree (MST) of a weighted connected graph $G$ is a spanning tree with the minimum or smallest weight of edges.

4.2 Algorithms for MST

1. Kruskal’s Algorithm
2. Prim’s Algorithm

5. Kruskal’s Algorithm

5.1 Concept

• A greedy algorithm that finds an MST for a connected weighted graph by adding increasing cost edges at each step.

5.2 Step-by-Step Explanation

1. Sort: Sort all edges of the graph in increasing order of their weight.
2. Initialize: Create a disjoint set for each vertex to keep track of connected components. Create an empty set T for the MST.
3. Iterate: Loop through the sorted edges. For each edge $(u, v)$:
   • Check if $u$ and $v$ belong to different connected components using find(u) and find(v).
   • If they do, adding this edge won't form a cycle. Add it to T and merge(u, v) the two components.
   • If they belong to the same component, discard the edge (as it would form a cycle).
4. Terminate: Stop when T contains $V - 1$ edges (where $V$ is the number of vertices).

5.3 Algorithm Complexity

• Time Complexity: $\Theta(E \log V)$ or $\Theta(E \log E)$ where $E$ is the number of edges and $V$ is the number of vertices (due to sorting edges).
• Space Complexity: $O(V)$ for the disjoint set data structure.

5.4 Algorithm

Simple (Easy to Remember)

💡 The Big Idea in Plain English

Imagine connecting cities with roads at the lowest possible cost: You list every possible road sorted from cheapest to most expensive. You start building from the cheapest road. If a road would create a redundant loop (cycle) between cities that can already reach each other, you simply skip it! Once every city is connected without any loops, you're done!

👣 3 Easy Steps to Remember

1. Sort All Edges: List all edges in ascending order of their weights (cheapest first).
2. Pick the Cheapest Edge:
   • Check if the two endpoints $u$ and $v$ are already in the same connected group (FindSet(u) == FindSet(v)).
   • If different groups (No Cycle): Include this edge in the MST and merge their groups (Union(u, v)).
   • If same group (Forms a Cycle): Discard the edge!
3. Finish: Stop when you have collected exactly $V - 1$ edges (connecting all $V$ vertices).

🧠 Memory Trick: Sort edges $\to$ Pick cheapest $\to$ Skip cycles (Union-Find). Edge-focused approach with $O(E \log E)$ time complexity.

Formal Algorithm (Code)

Algorithm Kruskal(G, w)
// Finds Minimum Spanning Tree (MST) using greedy approach
// Input: Connected, undirected weighted graph G = (V, E) with weight function w
// Output: Set of edges A forming the MST
{
    A <- empty set;

    for each vertex v in V do
        MakeSet(v);

    // Sort edges into non-decreasing order by weight w
    sort the edges of E in non-decreasing order of weight w;

    for each edge (u, v) in E (taken in sorted order) do
    {
        if (FindSet(u) != FindSet(v)) then
        {
            A <- A union {(u, v)};
            Union(u, v);
        }
    }
    return A;
}

6. Prim’s Algorithm

6.1 Concept

• In Prim's algorithm, the minimum spanning tree grows in a natural way, starting from an arbitrary root.
• At each stage, a new branch is added to the tree already constructed; the algorithm stops when all nodes have been reached.

6.2 Step-by-Step Explanation

1. Initialize: Create a set $B$ to keep track of vertices included in the MST.
2. Start: Pick an arbitrary vertex and add it to $B$.
3. Iterate: While $B$ does not contain all vertices:
   • Find the edge $e = \{u, v\}$ with the minimum weight such that $u \in B$ and $v \notin B$.
   • Add $v$ to $B$ and include $e$ in the MST.
4. Terminate: Return the MST when all vertices are in $B$.

6.3 Algorithm Complexity

• Time Complexity: $\Theta(V^2)$ with an adjacency matrix, or $\Theta(E \log V)$ using a Min-Heap.
• Space Complexity: $O(V + E)$ or $O(V^2)$ depending on graph representation.

6.4 Algorithm

Simple (Easy to Remember)

💡 The Big Idea in Plain English

Think of laying electrical cables outwards from your house: You start at any single house (the root). You look at all the neighboring houses directly reachable from your current wired network and ask: "Which neighbor is the cheapest to connect?" You lay cable to that cheapest neighbor. Now your wired network has two houses. Repeat: always pick the cheapest edge connecting an already-wired house to an un-wired house. The tree grows steadily outward like a creeping vine until all houses are powered!

👣 3 Easy Steps to Remember

1. Plant the Seed: Pick any start node $r$. Set its cost to $0$ (key[r] = 0) and all other nodes to $\infty$. Put all nodes in a priority queue.
2. Pick the Cheapest Unreached Node:
   • Pull the node $u$ with the lowest cost out of the queue (ExtractMin). It is now locked into the MST!
3. Update Its Neighbors:
   • Look at all neighbors $v$ of $u$ that are still waiting in the queue.
   • If the road from $u$ to $v$ is cheaper than $v$'s current best known connection, update $v$'s cost and remember that $v$ connects through $u$ (parent[v] = u).
   • Repeat until the queue is empty!

🧠 Memory Trick: Start with 1 node $\to$ Always grow outward along the cheapest attached branch $\to$ All nodes covered! Vertex-focused approach with $O(E \log V)$ time using a Min-Heap.

Formal Algorithm (Code)

Algorithm Prim(G, w, r)
// Finds Minimum Spanning Tree (MST) starting from root vertex r
// Input: Connected, undirected weighted graph G = (V, E) with weight function w, root r
// Output: MST represented by parent pointers parent[u]
{
    for each u in V do
    {
        key[u] <- infinity;
        parent[u] <- NIL;
    }
    key[r] <- 0;
    Q <- V; // Build min-priority queue of all vertices keyed by key[u]

    while not EMPTY(Q) do
    {
        u <- ExtractMin(Q);
        for each vertex v in Adj[u] do
        {
            if (v in Q and w(u, v) < key[v]) then
            {
                parent[v] <- u;
                key[v] <- w(u, v);
                DecreaseKey(Q, v, key[v]);
            }
        }
    }
}

7. Dijkstra’s Algorithm

7.1 Concept

• Used to find the Single Source Shortest Path in a directed (or undirected) graph with positive edge weights.

7.2 Step-by-Step Explanation

1. Initialize: Create a distance array $D$ initialized to infinity ($\infty$) for all vertices except the source vertex, which is set to $0$.
2. Set up: Maintain a set of unvisited vertices $C$.
3. Iterate:
   • Extract the vertex $u$ from $C$ that has the minimum distance value $D[u]$.
   • For every adjacent vertex $v$ of $u$:
     • If $D[v] > D[u] + \text{weight}(u, v)$, update $D[v] = D[u] + \text{weight}(u, v)$.
4. Terminate: The algorithm finishes when all vertices are evaluated. The array $D$ will hold the shortest distances from the source to all other vertices.

7.3 Algorithm Complexity

• Time Complexity: $O(V^2)$ with basic arrays, or $O((V+E) \log V)$ using a Min-Priority Queue.
• Space Complexity: $O(V)$ for the distance array and priority queue.

7.4 Algorithm

Simple (Easy to Remember)

💡 The Big Idea in Plain English

Think of GPS navigation calculating the quickest route from your home to everywhere else: You start at home with distance $0$, while the distance to every other location is set to $\infty$ (unexplored). At each step, you pick the unvisited location currently closest to home. From there, you check each road to its neighbors and ask: "Can I get to neighbor $v$ faster by driving through here?" If the shortcut is better, you update $v$'s shortest distance (this is called edge relaxation!). Repeat until every location has been visited.

👣 3 Easy Steps to Remember

1. Initialize Distances:
   • Distance to source $s$ is $0$ (dist[s] = 0).
   • Distance to all other nodes is $\infty$ (dist[v] = infinity).
   • Add all vertices into a Min-Priority Queue.
2. Pick the Closest Node:
   • Extract the node $u$ with the minimum dist[u]. Its shortest path from source is now finalized!
3. Relax Neighbors:
   • For every neighbor $v$ of $u$:
   • If taking the road through $u$ is shorter: dist[u] + weight(u, v) < dist[v]
   • Update: dist[v] = dist[u] + weight(u, v) and set parent[v] = u.
   • Repeat until the queue is empty!

🧠 Memory Trick: Start at 0, others $\infty$ $\to$ Pick smallest $\to$ Relax neighbors: if dist[u] + cost < dist[v], take the shortcut! Works only for non-negative edge weights. Runs in $O((V+E) \log V)$ with a Min-Heap.

Formal Algorithm (Code)

Algorithm Dijkstra(G, w, s)
// Single-Source Shortest Paths algorithm on weighted graph with non-negative weights
// Input: Graph G = (V, E), non-negative weight function w, source vertex s
// Output: Array dist[v] containing shortest path distance from s to each vertex v in V
{
    for each vertex v in V do
    {
        dist[v] <- infinity;
        parent[v] <- NIL;
    }
    dist[s] <- 0;
    S <- empty set;
    Q <- V; // Priority queue of all vertices keyed by dist[v]

    while not EMPTY(Q) do
    {
        u <- ExtractMin(Q);
        S <- S union {u};

        for each vertex v in Adj[u] do
        {
            // Edge relaxation step
            if (dist[u] + w(u, v) < dist[v]) then
            {
                dist[v] <- dist[u] + w(u, v);
                parent[v] <- u;
                DecreaseKey(Q, v, dist[v]);
            }
        }
    }
}

8. Fractional Knapsack Problem

8.1 Concept

• Given $n$ objects and a knapsack capacity $W$.
• Object $i$ has a positive weight $w_i$ and a positive value $v_i$.
• Goal: Fill the knapsack to maximize the value, breaking objects into fractions $x_i$ if necessary ($0 \le x_i \le 1$).

8.2 Step-by-Step Explanation

1. Calculate Ratio: Compute the value-to-weight ratio $v_i / w_i$ for each item.
2. Sort: Sort all items in descending order based on their $v_i / w_i$ ratio.
3. Select: Iterate through the sorted items:
   • If the item can completely fit in the remaining knapsack capacity, add it fully.
   • If the item cannot fully fit, add the fraction of the item that exactly fills the remaining capacity, then stop.
4. Return: The total accumulated value.

8.3 Algorithm Complexity

• Time Complexity: $O(n \log n)$ due to sorting.
• Space Complexity: $O(1)$ if sorted in place, otherwise $O(n)$.

8.4 Algorithm

Simple (Easy to Remember)

💡 The Big Idea in Plain English

Imagine filling a backpack with spices or gold dust that can be divided into any amount: You want the maximum possible total value, but your bag can only carry $W$ kilograms. The smartest greedy strategy is simple: calculate the price per kilogram for each item! Always take the item with the highest price per kg first. When your bag is almost full and the next item is too heavy to fit completely, chop it and take just the fraction that fills the remaining space!

👣 3 Easy Steps to Remember

1. Calculate Value-per-Weight: For each item $i$, compute its ratio: $\text{ratio}_i = \text{profit}[i] / \text{weight}[i]$.
2. Sort Items: Arrange all items in descending order of ratio (best value per kg at the top).
3. Fill the Knapsack:
   • For each item, if its entire weight fits into the remaining capacity: take all of it ($x[i] = 1.0$) and reduce remaining capacity.
   • If it cannot fit completely: take the exact fraction that tops off the bag ($x[i] = \text{remainingCapacity} / \text{weight}[i]$) and stop!

🧠 Memory Trick: Calculate Profit/Weight $\to$ Sort highest first $\to$ Take whole items $\to$ Slice the last item to fill the gap! Runs in $O(n \log n)$ time due to sorting.

Formal Algorithm (Code)

Algorithm FractionalKnapsack(W, n, p, w)
// Solves the Fractional Knapsack problem using a greedy approach
// Input: Knapsack capacity W, number of items n, profits p[1..n], weights w[1..n]
// Output: Array x[1..n] where x[i] is the fraction of item i included (0 <= x[i] <= 1)
{
    // Sort items in non-increasing order of value-to-weight ratio p[i]/w[i]
    sort items such that p[1]/w[1] >= p[2]/w[2] >= ... >= p[n]/w[n];

    for i <- 1 to n do
        x[i] <- 0.0;

    remainingCapacity <- W;

    for i <- 1 to n do
    {
        if (w[i] <= remainingCapacity) then
        {
            x[i] <- 1.0;
            remainingCapacity <- remainingCapacity - w[i];
        }
        else
        {
            // Take fractional share of item i
            x[i] <- remainingCapacity / w[i];
            remainingCapacity <- 0;
            break;
        }
    }
    return x;
}

9. Activity Selection Problem

9.1 Concept

• Given a set of $n$ activities with a start time $s_i$ and finish time $f_i$.
• Find the maximum size set of mutually compatible activities (activities that do not overlap).

9.2 Step-by-Step Explanation

1. Sort: Sort all input activities in increasing order of their finish times ($f_i$).
2. Select First: Always select the first activity from the sorted array, as it finishes earliest and leaves maximum time for subsequent activities.
3. Iterate: For each remaining activity:
   • If its start time $s_i$ is greater than or equal to the finish time of the previously selected activity, add it to the selected set.
4. Return: The set of selected activities.

9.3 Algorithm Complexity

• Time Complexity: $O(n \log n)$ due to sorting. If already sorted, it takes $O(n)$.
• Space Complexity: $O(1)$ or $O(n)$ depending on storage for results.

9.4 Algorithm

Simple (Easy to Remember)

💡 The Big Idea in Plain English

Imagine you have one single conference hall and 10 speakers wanting to use it today: Each speaker gives you their start time and end time. You want to host the maximum number of talks without any overlaps. What is the golden rule? Always pick the talk that finishes earliest! Why? Because finishing early leaves the most free time remaining for future speakers throughout the rest of the day!

👣 3 Easy Steps to Remember

1. Sort by Finish Time: Arrange all activities in order of when they finish ($f_1 \le f_2 \le \dots \le f_n$).
2. Pick the Earliest Finisher: Always schedule the very first activity ($A = \{1\}$). Set your clock pointer $k = 1$.
3. Filter Compatible Talks:
   • Walk through the remaining activities one by one ($m = 2 \dots n$).
   • If activity $m$ starts after or when activity $k$ finishes ($s[m] \ge f[k]$):
     • Book it! Add $m$ to your schedule ($A = A \cup \{m\}$).
     • Update your clock: $k = m$.
   • Otherwise, skip it because it clashes!

🧠 Memory Trick: Sort by finish time $\to$ Take the first $\to$ Take next whenever start >= last_finish! Greedy choice: whoever ends earliest wins! Runs in $O(n \log n)$ time.

Formal Algorithm (Code)

Algorithm ActivitySelection(s, f, n)
// Selects a maximum-size set of mutually compatible activities
// Input: Start times s[1..n] and finish times f[1..n] sorted such that f[1] <= f[2] <= ... <= f[n]
// Output: Set A of selected mutually compatible activities
{
    A <- {1};  // Select the first activity
    k <- 1;    // Index of the last activity selected

    for m <- 2 to n do
    {
        // If start time of activity m is >= finish time of last selected activity
        if (s[m] >= f[k]) then
        {
            A <- A union {m};
            k <- m;
        }
    }
    return A;
}

10. Huffman Codes

10.1 Concept

• A greedy algorithm that constructs an optimal prefix code for lossless data compression.
• It assigns variable-length codes to input characters based on their frequencies.
• The most frequent character gets the smallest code, while the least frequent character gets the largest code.
• Prefix codes ensure that no code is a prefix of another code, preventing decoding ambiguity.

10.2 Step-by-Step Explanation

1. Count Frequencies: Calculate the frequency of each character in the input data.
2. Initialize Min-Heap: Create a leaf node for each character and insert them into a priority queue (min-heap) based on frequency.
3. Build Tree: While the heap contains more than one node:
   • Extract the two nodes with the minimum frequencies.
   • Create a new internal node with a frequency equal to the sum of the two nodes.
   • Attach the two nodes as left and right children.
   • Insert the new node back into the min-heap.
4. Assign Codes: Traverse the tree from the root. Assign 0 to the left branch and 1 to the right branch. The path from the root to a leaf node provides the Huffman code for that character.

10.3 Algorithm Complexity

• Time Complexity: $O(n \log n)$ to build the heap and tree.
• Space Complexity: $O(n)$ for storing the tree and codes.

10.4 Algorithm

Simple (Easy to Remember)

💡 The Big Idea in Plain English

Think of Morse code or ZIP file compression: In any English book, the letter 'E' appears thousands of times, while 'Z' is very rare. If we assign 'E' a super short code (like 0) and 'Z' a longer code (like 11101), the entire book becomes much smaller! Huffman coding creates the perfect variable-length code: It repeatedly merges the two rarest characters together, building a binary tree from the ground up until every character has a code!

👣 3 Easy Steps to Remember

1. Count & Put into Min-Heap: Count how often each character appears, and place all characters into a Min-Priority Queue.
2. Merge the Two Smallest Nodes:
   • While the queue has more than 1 node:
   • Pop the two nodes with the smallest frequencies ($x$ and $y$).
   • Create a parent node $z$ whose frequency is their sum ($x.\text{freq} + y.\text{freq}$).
   • Set $x$ as the left child and $y$ as the right child.
   • Put $z$ back into the queue!
3. Assign Binary Bits:
   • The final remaining node is the root of the tree.
   • Trace from the root to every leaf: label left branches with 0 and right branches with 1.
   • The sequence of bits leading to each character is its compressed prefix code!

🧠 Memory Trick: Take 2 lowest frequencies $\to$ Merge into parent $\to$ Push back into Min-Heap $\to$ Repeat until 1 tree $\to$ Left=0, Right=1. Frequent letters get short codes! Runs in $O(n \log n)$ time.

Formal Algorithm (Code)

Algorithm Huffman(C)
// Generates optimal prefix codes (Huffman tree) for characters in set C
// Input: Set C of characters, where each c in C has frequency c.freq
// Output: Root node of the optimal prefix tree
{
    n <- |C|;
    Q <- C; // Initialize min-priority queue with all characters keyed by frequency

    for i <- 1 to n - 1 do
    {
        allocate new internal node z;
        z.left <- x <- ExtractMin(Q);
        z.right <- y <- ExtractMin(Q);
        z.freq <- x.freq + y.freq;
        Insert(Q, z);
    }
    return ExtractMin(Q); // Returns root of Huffman tree
}