Greedy Choice, Huffman Coding & Interval Scheduling
“Optimal substructure vs greedy-choice property, activity selection, and Huffman prefix codes.”
1.The Greedy Framework & Exchange Arguments
§ 3.1.A problem exhibits Greedy-Choice Property if a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
The Exchange Argument Proof Technique:
1. Let G be the greedy solution, and let O be an arbitrary optimal solution.
2. If G = O, greedy is optimal.
3. If G != O, consider the first point where G and O differ.
4. Show that modifying O by exchanging its choice with the greedy choice produces another valid solution O' whose objective value is at least as good as O (text{value}(O') >= text{value}(O)).
5. By induction, O can be transformed into G without reducing value. Hence G is optimal.
2.Huffman Coding: Prefix Codes & Tree Properties
§ 3.2.A prefix-free code is a code in which no codeword is a prefix of any other codeword. Prefix codes are uniquely decodable without delimiters.
Huffman's algorithm constructs an optimal prefix code using a min-priority queue:
1. Initialize n single-node trees, each labeled with symbol frequency f_i.
2. Extract the two minimum frequency trees T_1 and T_2.
3. Merge them into a parent node with frequency f_1 + f_2.
4. Repeat until a single tree remains.
Running time: O(n log n) with binary min-heap.
Properties of Huffman Trees:
- Every internal node has exactly 2 children (strictly full binary tree).
- The two least frequent characters are siblings at the maximum depth of the tree.
3. Worked Problem: Huffman Tree Construction & Compression Ratio
Remember that the two lowest frequencies MUST be merged first. When merging two subtrees, their combined weight must be re-inserted into the candidate set.
Problem: A file contains 5 characters with frequencies: A (0.40), B (0.25), C (0.15), D (0.10), E (0.10). Construct the optimal Huffman code and find the expected code length.
Step 1: Priority Queue iterations:
Initial: {D: 0.10, E: 0.10, C: 0.15, B: 0.25, A: 0.40}
Iteration 1: Merge D(0.10) and E(0.10) => DE(0.20). Set: {C: 0.15, DE: 0.20, B: 0.25, A: 0.40}
Iteration 2: Merge C(0.15) and DE(0.20) => CDE(0.35). Set: {B: 0.25, CDE: 0.35, A: 0.40}
Iteration 3: Merge B(0.25) and CDE(0.35) => BCDE(0.60). Set: {A: 0.40, BCDE: 0.60}
Iteration 4: Merge A(0.40) and BCDE(0.60) => Root(1.00).
Step 2: Assign bit lengths from tree depth:
A: depth 1 => length = 1 bit (code '0')
B: depth 2 => length = 2 bits (code '10')
C: depth 3 => length = 3 bits (code '110')
D: depth 4 => length = 4 bits (code '1110')
E: depth 4 => length = 4 bits (code '1111')
Step 3: Compute expected bits per symbol L:
L = (0.40 1) + (0.25 2) + (0.15 3) + (0.10 4) + (0.10 * 4)
L = 0.40 + 0.50 + 0.45 + 0.40 + 0.40 = 2.15 bits/symbol.
Step 4: Compare with fixed-length encoding:
5 symbols require ceil(log_2 5) = 3 bits/symbol.
Compression savings = (3 - 2.15) / 3 = 0.85 / 3 = 28.33%.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Best visual explanations of algorithm design and complexity analysis.
Exam-focused with GATE PYQ numericals on every major algorithm.