Greedy methods and minimum spanning trees notes — Unit 3

The Greedy method is used to solve Optimization Problems—problems where you are trying to find the absolute maximum profit or the absolute minimum cost among a massive set of possible solutions.

⇒1.1 The Core Philosophy

A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.

It makes a locally optimal choice at each stage, blindly hoping that these local optima will eventually add up to the global optimum solution.

The Rule: Once a greedy algorithm makes a choice, it NEVER reconsiders it. It never looks back, and it never looks far ahead into the future to calculate consequences.

The critical engineering question is: Does taking the best immediate option actually lead to the best overall outcome?

⇒2.1 The Coin Change Example

Problem: Make $36$ cents using the absolute fewest number of coins. Available coins: `[25, 10, 5, 1]`.

Greedy Strategy: Always pick the largest coin that fits.

• Pick 25. Remaining: 11.
• Pick 10. Remaining: 1.
• Pick 1. Remaining: 0.

Result: 3 coins. This is the mathematically optimal global solution. Greedy works perfectly for standard US/Indian currency systems.

⇒2.2 When it Fails

Change the available coins to a weird system: `[20, 15, 1]`. Goal: Make 30 cents.

Greedy Strategy: Pick 20. Remaining: 10. You are forced to pick ten 1-cent coins. Result: 11 coins.

Optimal Solution: Ignore the 20, pick two 15-cent coins. Result: 2 coins.

Conclusion: Greedy algorithms are incredibly fast and easy to write, but they do NOT work for all optimization problems. You must mathematically prove that the problem exhibits the Greedy-Choice Property.

A classic optimization problem. You are a thief in a store. You have a knapsack that can hold a maximum weight $W$. The store has $n$ items. Each item $i$ has a weight $w_i$ and a total value $v_i$.

Crucially, in the Fractional version, you are allowed to cut items into smaller pieces (like stealing half a bag of gold dust).

Goal: Maximize the total value in your knapsack without exceeding weight $W$.

⇒3.1 The Greedy Strategy

How do you decide what to steal first? The heaviest item? The most valuable item?

The mathematically optimal greedy choice is to calculate the Value-to-Weight Ratio ($v_i / w_i$) for every item. This represents the profit per kilogram.

1. Sort all items in descending order of their $v_i / w_i$ ratio.
2. Iterate through the sorted list. If the entire item fits in the remaining capacity, take it entirely.
3. If it doesn't fit completely, take the exact fraction that fills the remaining capacity.
4. Stop. The knapsack is full.

Time Complexity: The sorting step dictates the time: $O(n \log n)$.

You have a single CPU (or worker) and a list of $n$ jobs to execute. Each job takes exactly 1 unit of time to complete. Each job has a Deadline $d_i$ and a Profit $p_i$. You only earn the profit if the job is completed before or on its deadline.

Goal: Find a sequence of jobs that maximizes total profit.

⇒4.1 The Greedy Strategy

Greedy logic: We must prioritize the jobs that pay the most money.

1. Sort all jobs in descending order of Profit.
2. Find the maximum deadline across all jobs (say, $D$). Create an array of empty time slots from 1 to $D$.
3. Iterate through the sorted high-profit jobs.
4. The Greedy Choice: For the current job, try to schedule it in the latest possible empty time slot before its deadline. (e.g., If deadline is 4, check slot 4. If full, check 3, then 2, then 1).
5. If all slots before the deadline are full, reject the job.

Time Complexity: Sorting takes $O(n \log n)$. Scanning empty slots takes $O(n^2)$ in the worst case. Total time is $O(n^2)$.

Computers store characters using fixed-length codes (e.g., ASCII uses 8 bits per character). The word "MISSISSIPPI" (11 chars) takes $11 \times 8 = 88$ bits.

David Huffman invented a greedy algorithm to compress data using Variable-Length Codes. The concept: Give short binary codes to letters that appear frequently (like 'I' and 'S'), and long codes to rare letters (like 'M' and 'P').

⇒5.1 The Prefix Rule

If codes are variable length, how does the computer know where one letter ends and the next begins?
Huffman guarantees the Prefix Rule: No code can be a prefix of another code. If 'S' is `10`, then no other letter's code can start with `10`.

The algorithm uses a Min-Priority Queue (usually a Min-Heap) to construct a binary tree from the bottom up.

• 1. Count the frequency of each unique character in the file.
• 2. Create a leaf node for each character. Insert all nodes into a Min-Heap based on their frequency.
• 3. Greedy Choice: Extract the two nodes with the absolute lowest frequencies from the heap. (These will get the longest codes).
• 4. Create a new internal parent node. Its frequency is the sum of the two children's frequencies. Attach the two extracted nodes as its left and right children.
• 5. Insert this new parent node back into the Min-Heap.
• 6. Repeat steps 3-5 until exactly one node remains in the heap. This is the Root of the Huffman Tree.

⇒6.1 Generating the Codes

Traverse from the root to each leaf. Assign a `0` every time you branch left, and a `1` every time you branch right. The path to the leaf is the optimal prefix code for that character.

Consider a connected, undirected graph where vertices are cities, edges are roads, and edge weights represent the cost to pave that road.

⇒7.1 Spanning Tree

A Spanning Tree is a subgraph that includes ALL the vertices of the original graph, but is connected by exactly $V-1$ edges (meaning it contains absolutely no cycles/loops).

⇒7.2 Minimum Spanning Tree (MST)

A graph can have hundreds of different valid spanning trees. The Minimum Spanning Tree is the specific tree whose total sum of edge weights is the absolute minimum.

Real-world application: What is the cheapest way to lay down fiber optic cables to connect all buildings on a campus without creating redundant loops?

Prim's is a greedy algorithm to find the MST. It builds the tree by growing a single, connected component from a starting node.

⇒8.1 The Strategy

• 1. Initialize a set `MST` to keep track of vertices already included in the tree. (Initially empty).
• 2. Pick any arbitrary vertex to start. Add it to `MST`.
• 3. Look at all edges that connect a vertex inside the `MST` set to a vertex outside the set.
• 4. Greedy Choice: Among all those crossing edges, pick the edge with the absolute minimum weight.
• 5. Add the newly connected vertex to the `MST` set.
• 6. Repeat until all vertices are in the `MST` set.

Time Complexity: If implemented efficiently using an Adjacency List and a Min-Priority Queue (Fibonacci Heap), the time is $O(E + V \log V)$, making it extremely fast for dense graphs with many edges.

Kruskal's is another greedy algorithm for finding the MST. Unlike Prim's which grows a single tree, Kruskal's builds a "forest" of multiple trees and gradually merges them together.

⇒9.1 The Strategy

• 1. Sort ALL edges in the entire graph in ascending order of their weight.
• 2. Initialize a forest where each vertex is its own separate tree.
• 3. Iterate through the sorted edges, starting from the lightest.
• 4. Greedy Choice: For the current edge, check if adding it to the MST would create a cycle (a closed loop).
• 5. If it does NOT create a cycle, add it to the MST.
• 6. If it creates a cycle, throw it away and move to the next edge.
• 7. Stop when exactly $V-1$ edges have been added.

To quickly check for cycles, Kruskal's algorithm uses a sophisticated Data Structure called Disjoint-Set (Union-Find).

Time Complexity: Dominated by the initial sorting of edges: $O(E \log E)$. It is typically preferred for sparse graphs.

Given a weighted, directed graph representing cities and toll roads, what is the absolute cheapest path from a specific Source city to every other city in the network? This is the Single-Source Shortest Path problem.

⇒10.1 The Flaw in Edge Weights

In the real world, costs are positive (time, distance, money). However, in abstract mathematical graphs, an edge weight can theoretically be negative.

If a graph contains a cycle where the sum of the edge weights is negative (a Negative Weight Cycle), the shortest path problem becomes mathematically unsolvable. You could theoretically loop around that cycle infinitely to achieve a path cost of negative infinity.

Invented by Edsger W. Dijkstra, this is the most famous greedy algorithm in computer science. It solves the Single-Source Shortest Path problem. It is the foundation of network routing protocols (OSPF) and GPS navigation.

⇒11.1 The Strict Limitation

Dijkstra's Algorithm STRICTLY REQUIRES that all edge weights in the graph must be non-negative. If a single negative edge exists, the greedy logic breaks down entirely, and the algorithm may output the wrong answer.

The algorithm maintains an array `dist[]` that holds the current shortest known distance from the Source to every other vertex. Initially, `dist[Source] = 0` and all others are Infinity.

⇒12.1 The Process

• 1. Maintain a set of vertices whose final, absolute shortest path has already been permanently calculated (the "Processed" set).
• 2. Greedy Choice: From the un-processed vertices, pick the vertex $u$ with the absolute minimum `dist[u]` value.
• 3. Mark $u$ as Processed. (Once marked, its shortest path is mathematically guaranteed and will never change).
• 4. Edge Relaxation: Look at all adjacent neighbors $v$ of the newly processed vertex $u$. Calculate: `NewDistance = dist[u] + weight(u to v)`.
  If `NewDistance` is strictly less than the current `dist[v]`, update `dist[v] = NewDistance`.
• 5. Repeat until all vertices are Processed.

Time Complexity: Identical to Prim's Algorithm. Using a Min-Priority Queue, it takes $O(E + V \log V)$.

Unit 3 shifts from recurrence relations to graph theory and optimization algorithms.

⇒13.1 University Exam Checklist

• Explain the core philosophy of the Greedy Paradigm. What makes it different from Dynamic Programming?
• Solve a numerical problem for the Fractional Knapsack. Explain why the 0/1 Knapsack (where items cannot be broken) cannot be solved with a greedy approach.
• Solve a numerical problem for Job Sequencing with Deadlines, showing the scheduling array step-by-step.
• Construct a Huffman Tree for a given set of character frequencies and determine the prefix code for each character. Explain the Prefix Rule.
• Define a Minimum Spanning Tree.
• Execute Prim's Algorithm on a given weighted graph to find the MST.
• Execute Kruskal's Algorithm on a given weighted graph. Explain how cycle detection works (Union-Find).
• Trace Dijkstra's Algorithm on a directed graph to find the shortest path from a source. Show the distance array and relaxation steps at each iteration.
• Explain why Dijkstra's algorithm fundamentally fails if the graph contains negative weight edges.